Реализация узла поиска на таблице маршрутизации torrent kademlia

Question

Реализация узла поиска на таблице маршрутизации torrent kademlia

Я уже рассмотрел ряд документов на эту тему, но есть кое-что не совсем понятное. Например, битовый торрент-документ ( http://www.bittorrent.org/beps/bep_0005.html) гласит

Таблица маршрутизации подразделяется на "ведра", каждый из которых покрывает часть пространства. Пустая таблица имеет один сегмент с диапазоном идентификаторов пространства min=0, max=2^160. Когда узел с идентификатором "N" вставляется в таблицу, он помещается в область с min <= N

Это несколько отличается от других документов, касающихся таблицы маршрутизации kademlia, где сегменты расположены в соответствии с битовым префиксом идентификатора узла, но есть еще одна запутанная вещь. Когда мы отвечаем на запрос "найти узел", мы должны найти 8 ближайших узлов к запрошенному с помощью операции XOR. Я видел несколько реализаций, которые просто просматривали каждый элемент таблицы маршрутизации, выполняя операцию XOR, и таким образом находили 8 ближайших элементов. Мне кажется, что процессор слишком тратится.

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

Я запустил простой тест, используя числа от 0 до 99, где я хотел найти 8 ближайших к XOR чисел, и они были в непосредственной близости от искомого числа, но не рядом с ним. Теперь, думая о наших сегментах, я думаю, возможно, что все идентификаторы узлов в сегменте являются ближайшими для незначительного исключения. Так, например, если мы возьмем этот сегмент, возьмем один слева и один справа и ищем идентификаторы ближайших узлов XOR, мы найдем то, что ищем, и нет смысла проходить ВСЕ узлы в маршрутизации. Таблица.

Я прав или я что-то упустил?

6

routing bittorrent dht kademlia

Источник

user1398726 04 июн '15 в 21:22

1 ответ

Решение

Другие вопросы по тегам routing bittorrent dht kademlia

user1362755 04 июн '15 в 22:38 2015-06-04 22:38 · Accepted Answer · 2015-06-04 22:38

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

Спецификация bittorrent описывает реализацию таблицы маршрутизации, которая только приближается к описанной в документе kademlia. Это проще в реализации, но имеет некоторые недостатки.

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

В обоих случаях - полная реализация древовидной таблицы маршрутизации и упрощенный вариант BEP5- каждый сегмент может рассматриваться как имеющий CIDR-подобный префикс (см. Этот ответ SO), состоящий из префиксных битов, которые охватывает сегмент, и бита маски сосчитать.

В варианте BEP5 префикс каждого сегмента просто выводится из индекса массива и собственного идентификатора вашего узла. В древовидной таблице сегменты должны отслеживать свой префикс из-за операций разделения / объединения сегментов.

Используя эти префиксы, вы можете найти корзину, которая закрывает целевой ключ.

Дело в том, что сегменты не должны быть полными, и если вы хотите отправить, скажем, 20 узлов в ответе, одного сегмента будет недостаточно.

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

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

Вот моя реализация для нахождения N ближайших узлов к определенному целевому ключу из древовидной таблицы маршрутизации.

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

Т.е. полное сканирование таблицы просто осуществить.

Предположим, у нас есть таблица маршрутизации со следующими префиксами битов для каждого сегмента. Буквы служат удобными именами).

A 000... 
B 00100... 
C 0010100... 
D 0010101000... 
E 0010101001...
F 001010101... 
G 00101011... 
H 001011... 
I 0011... 
J 01... 
K 1...

Теперь предположим, что мы ищем этот целевой ключ:

T = 0010011010111111001111100101011000001010010100001100100010011100000000100100000111001101100110110110101100010100111010111001101111110101001001001000100000001001

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

Теперь первое посещение довольно очевидно, это B поскольку его префикс охватывает целевой ключ.

поскольку BПрефикс длиной 5 битов, любая запись в этом сегменте будет иметь расстояние XOR до T из 00000???????..., 5 префиксных битов.

B самое близкое ведро к TЭто означает, что не может быть записей таблицы маршрутизации ближе, чем относительное расстояние 00000..., И наоборот, это означает, что минимальное расстояние, на которое любой вход за B может иметь 00001..., Это означает, что следующее ближайшее ведро должно накрыть T xor 00001... -> 00101110101111110[...],

Ведро, которое покрывает это H,

H не соседствует с B

В конечном итоге - при условии, что нам нужно будет посетить 6 ведер - заказ будет выглядеть так:

00100...      -> B
001011...     -> H
001010101...  -> F
0010101000... -> D
0010101001... -> E
00101011...   -> G

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

00000...
000010...
000011000...
0000110010...
0000110011...
00001101...

Итак, алгоритм выглядит следующим образом:

найти начальное ведро, покрывающее целевой ключ
XOR префикс корзины с целевым ключом (конечные биты нулевой маски)
увеличить расстояние на младший бит этого префикса
Увеличенное расстояние по XOR с помощью целевой клавиши
найти следующее ведро, закрывающее ключ XORed
перейти к 2

TL; DR: "просто посмотри одно ведро влево, одно ведро вправо" недостаточно. Правильный алгоритм достаточно сложен, проще реализовать линейное сканирование всей таблицы.