Очень несбалансированный Kademlia таблица маршрутизации

Question

В статье Kademlia, последний абзац раздела 2.4 гласит, что для того, чтобы правильно обрабатывать сильно несимметричные дерева ...

Kademlia узлов держать все действительные контакты в поддереве размера в наименее k узлов, даже если для этого требуются разделяющие ведра, в которых собственный идентификатор узла узла не находится.

Однако в предыдущем разделе статьи, кажется, утверждать, что если к-ведро уже имеет к элементам, что любые дальнейшие дополнения в к этим к-ведрам требуют удаление stalest узла (Pinging это первый, чтобы увидеть, если его живым) или иным образом кэшировать добавление до тех пор, пока слот не станет доступен в этом k-ведре.

Эта статья, кажется, противоречит этим двум точкам.

В каких условиях необходимо разделить k-ведро и почему? Кажется нецелесообразным сохранять «все действительные контакты» в таблице маршрутизации, так как таблица маршрутизации будет очень быстро работать очень быстро. В этом примере речь идет о дереве с множеством узлов, начиная с 001 и с одним узлом, начинающимся с 000. Узел, начинающийся с 000, должен будет непрерывно разбить свой k-bucket на 001 для хранения каждого допустимого узла, начинающегося с 001? В 160-битовом адресном пространстве не будет ли это потенциально хранить 2^157 узлов в таблице маршрутизации 000?

Формулировка в процитированном блоке тоже очень запутанная ...

«в поддереве» - в каком поддереве таблицы маршрутизации?

«размер atleast k nodes» - какую метрику мы используем для определения размера поддерева? В этом случае узлы ссылаются на узлы kademlia или k-buckets или что-то еще?

Answer 1

Однако в предыдущем разделе статьи, кажется, утверждать, что если к-ведро уже имеет к элементов, что любые дальнейшие дополнения в к этому к-ведра требуют удаления stalest узла (Pinging его первым, чтобы увидеть, если его живым) или иным образом кэшировать добавление до тех пор, пока слот не станет доступен в этом k-ведре.

Это то, как ведро поддерживается всякий раз, когда есть контакт с узлом для вставки, но ковш не подходит для разделения.

В каких условиях необходимо разделить k-ведро и почему?

В первом приближении: Разделить ведро каждый раз, когда новый узел не может быть вставлен и ID-пространство ведра покрывает свой идентификатор узла.

Это необходимо для обеспечения полной осведомленности о вашем районе, имея лишь смутное осознание удаленных участков ключа. То есть для местности.

Чтобы покрыть корпус несбалансированного дерева - это может произойти, если идентификаторы узлов не являются (псевдо) случайными или, по крайней мере, в листовых ведрах, из-за статистических ударов, когда они назначаются наугад - подход должен быть смягчены следующим образом:

Когда

• пытается вставить новый контакт C в таблице маршрутизации
• ведро, в котором C принадлежит полный
• С находится ближе к идентификатору узла, чем К^й -closest узла в вашей таблице маршрутизации, где К является размером ведра

затем разделить ведро.

На практике это должно быть изменено немного дальше, так что расслабляющее расщепление используется для ответов, в то время как незапрашиваемые запросы должны использовать только строгое разделение, в противном случае вы могли бы получить какую-то странно искаженную таблицу маршрутизации, когда расслабленное расщепление происходит во время запуска, когда таблица еще не заполнена.