Как понять протокол Кадемлии (Кад)

Question

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

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

Answer 1

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

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

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

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

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

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

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

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

Answer 2

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

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