Очень несбалансированный маршрутный стол Kademlia
В документе Kademlia последний абзац раздела 2.4 гласит, что для правильной работы с сильно несбалансированными деревьями...
Узлы Kademlia сохраняют все действительные контакты в поддереве размером не менее k узлов, даже если для этого требуется разделение сегментов, в которых отсутствует собственный идентификатор узла.
Тем не менее, предыдущий раздел статьи, кажется, утверждает, что если k-сегмент уже имеет k элементов, то любые дополнительные добавления в этот k-сегмент требуют удаления самого устаревшего узла (проверяя его сначала, чтобы увидеть, жив ли он) или кэшируя иным образом добавление, пока слот не станет доступным в этом k-ведре.
Кажется, что статья противоречит этим двум пунктам.
При каких условиях k-ведро должно быть разделено и почему? Кажется нецелесообразным хранить "все действительные контакты" в таблице маршрутизации, поскольку таблица маршрутизации очень быстро станет очень большой. В примере рассказывается о дереве, в котором много узлов, начиная с 001, и одного узла, начинающегося с 000. Узлу, начинающемуся с 000, придется постоянно делить свой k-интервал на 001, чтобы хранить каждый действительный узел, начинающийся с 001? Разве в 160-битном адресном пространстве это не приведет к тому, что в таблице маршрутизации 000 будет храниться 2^157 узлов??
Формулировка в цитируемом блоке тоже очень запутанная...
"в поддереве" - в каком поддереве таблицы маршрутизации?
"размером не менее k узлов" - какую метрику мы используем для определения размера поддерева? узлы в этом случае относится к узлам kademlia или k-ведро или что-то еще?
1 ответ
Тем не менее, предыдущий раздел статьи, кажется, утверждает, что если k-сегмент уже имеет k элементов, то любые дополнительные добавления в этот k-сегмент требуют удаления самого устаревшего узла (проверяя его сначала, чтобы увидеть, жив ли он) или кэшируя иным образом добавление, пока слот не станет доступным в этом k-ведре.
Таким образом, ведро поддерживается, когда есть контакт узла, который нужно вставить, но сегмент не подходит для разбиения.
При каких условиях k-ведро должно быть разделено и почему?
В первом приближении: Разделите корзину, когда новый узел не может быть вставлен, и пространство идентификаторов корзины охватывает идентификатор вашего узла.
Это необходимо для обеспечения полной осведомленности о вашем районе, при этом имея лишь смутную осведомленность об удаленных участках клавиш. Т.е. для местности.
Чтобы охватить случай неуравновешенного дерева - который может происходить либо в том случае, если идентификаторы узлов не являются (псевдо) случайными, либо, по крайней мере, в конечных сегментах, из-за статистических случайностей, когда они назначаются случайным образом, подход должен быть смягчен следующим образом:
когда
- пытается вставить новый контакт C в таблицу маршрутизации
- ведро, в которое входит C, заполнено
- C ближе к вашему идентификатору узла, чем K-й самый близкий узел в вашей таблице маршрутизации, где K - размер сегмента
затем разделить ведро.
На практике это должно быть изменено немного дальше, так что для ответов используется расслабленное расщепление, в то время как незапрашиваемые запросы должны использовать только строгое расщепление, в противном случае вы можете получить странно искаженную таблицу маршрутизации, когда расщепление происходит рано во время запуска, когда таблица не заселены еще.