Сколько k-сегментов может хранить узел в своей таблице маршрутизации в Kademlia DHT?

Question

Из Википедии
Kademlia routing tables consist of a list for each bit of the node ID. If a node ID consists of 128 bits, a node will keep 128 such lists.

Учитывая, что пространство ключей от 0-2^160 это означает, что максимальное количество узлов может присутствовать в этом пространстве ключей 2^160 и каждый идентификатор узла 160-битный. Если k=20, то максимальное количество записей, которое может хранить узел в своей таблице маршрутизации, равно 160x20, Как узел может отслеживать такое огромное количество узлов в своей таблице маршрутизации. Не должен ли узел хранить записи только тех 20 узлов, которые присутствуют в его собственном k-сегменте с размером блока k=20? Как он может хранить 160 таких списков, даже если сам этот узел отсутствует в этих списках, за исключением того, что он присутствует в одном списке с 20 узлами?

Я использую списки и ведро взаимозаменяемо, они оба одинаковы.

Answer 1

Размер таблицы маршрутизации асимптотически ограничен O(log₂(n/k)) где n фактическое количество узлов в сети, а не теоретический предел 2^160 а также k это размер сегмента, поэтому более крупные сегменты немного уменьшают количество сегментов в таблице маршрутизации.

На практике для bittorrent ipv4 dht с k=8 и ~7M достижимыми узлами вы получаете глубину таблицы маршрутизации около 19-22 сегментов.

И хотя теоретически, 160*20 не будет таким плохим, как вы думаете. Это всего лишь 3200 IP-адресов + небольшое связанное состояние для хранения в памяти и отправки пакетов время от времени. Снижение числа пингов до одной в секунду означает, что вы все равно можете обновить всю таблицу маршрутизации менее чем за час.