Как понять протокол Kademlia (KAD)

Question

Недавно я прочитал документ протокола Kademlia, я попытался понять протокол, но у меня все еще есть вопрос: Почему узел должен найти другой узел, когда он знает его ID, но ip или порт? Почему у него есть идентификатор, когда он не знает ip или порт, где он получил идентификатор? Я думаю, что «расстояние» между двумя разными узлами не является расстоянием маршрутизации или реальным расстоянием, это только виртуальное расстояние, которое может использовать алгоритм для быстрого поиска узла, это так?

Возможно, мой английский не очень ясен, потому что английский не мой родной язык, но я постараюсь выразить свое ясность, если вам нужно. Большое спасибо!

Answer 1

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

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

Использование побитового XOR в качестве меры условного расстояния между идентификаторами имеет то преимущество, что для данного идентификатора цели никакие два идентификатора не могут иметь одинаковое расстояние до цели.

Представьте себе простой пример, когда идентификаторы находятся в диапазоне от 00 до 63. Если Kademlia используется, например, чистое математическое различие как мера расстояния 15 и 35 будет равным расстоянию до 25 - оба будут иметь расстояние 10. Используя XOR, расстояние между 15 и 25 составляет 22, а между 25 и 35 - 58.

Таким образом, группа k ближайших идентификаторов к идентификатору цели может быть рассчитана однозначно.

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

Процесс поиска предназначен для возврата либо группы из k узлов (перед сохранением данных на каждом из них), либо возврата одного фрагмента данных (от первого узла, удерживающего его во время итераций поиска).

Из-за этого чистая Kademlia не подходит для поиска только одного узла, поэтому я не уверен, что часть вашего вопроса слишком актуальна. Если вы хотите использовать Kademlia для поиска единственного узла, вероятно, стоит изменить процесс поиска, чтобы закончить раньше, как только любой узел вернет контактные данные целевого узла (точно так же, как поиск заканчивается раньше, если целевое значение во время процесса).

Answer 2

Поскольку сеть распределена, по определению нет одной главной таблицы сопоставлений ID-> адресов. Узлы не должны (и обычно не знают) обо всех других узлах. Процесс «нахождения» узла в основном заключается в том, чтобы спросить известные узлы «ближе» к цели не столько о целевом узле напрямую, сколько о , какие узлы ближе к цели. Результат этого запроса дает вам следующую группу узлов для запроса, и процесс повторяется - и поскольку узел будет возвращать результаты, которые ближе, чем есть, каждая итерация стремится находить узлы ближе и ближе к цели, пока вы, наконец, достигните узла, который может сказать «О, узел Х? Он прямо там».

По крайней мере, это то, что я понимаю.