Как работает таблица маршрутизации Population Pastry?

23

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

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

Я прочитал статью, которую опубликовали авторы [1], и добился некоторого прогресса, но я продолжаю зацикливаться на этом конкретном моменте в работе таблицы маршрутизации:

Газета утверждает, что

A узла маршрутизации таблицы, , организована в войти 2 б N строки с 2 б - 1 записей в каждой. 2 б - 1 записи в строке п таблицы маршрутизации каждый относятся к узлу , чье NodeId акций NodeId нынешнего узла в первом п цифры, но чьи п + - - го цифра имеет один из 2 б - 1 возможных значений, кроме п + 1 - го цифра идентификатора нынешнего узла.ржурнал2бN2б-12б-1NN+12б-1N+1

выступает за конкретного приложения, как правило , переменной 4 . Давайте для простоты используем b = 4 . Так что вышеб4бзнак равно4

Таблица маршрутизации A узла, , организована в войти 16 Н строк с 15 записей в каждой. В 15 записей в строке п таблицы маршрутизации каждые относятся к узлу , чье NodeId акций NodeId нынешнего узла в первом п цифры, но чьи п + - - го цифра имеет один из 2 б - 1 возможных значений, кроме п + 1- я цифра в идентификаторе текущего узла.ржурнал16N1515NN+12б-1N+1

Я так много понимаю. Кроме того, - это количество серверов в кластере. Я тоже это понимаю.N

У меня вопрос: если строка, в которую помещается запись, зависит от общей длины ключа, почему на первый взгляд случайное ограничение на число строк? Каждый идентификатор узла имеет 32 цифры, когда (128-битные идентификаторы узла делятся на цифры по b битам). Так что же происходит, когда N становится достаточно высоким, чтобы log 16 N > 32 ? Я понимаю, что для достижения этого сценария потребуется 340 282 366 920 938 463 463 374 607 431 768 211 457 (если моя математика верна), но это выглядит как странное включение, а корреляция никогда не объясняется.бзнак равно4Nжурнал16N>32

Кроме того, что произойдет, если у вас есть небольшое количество серверов? Если у меня меньше 16 серверов, у меня только одна строка в таблице. Кроме того, ни при каких обстоятельствах каждая запись в строке не будет иметь соответствующий сервер. Должны ли записи быть пустыми? Я понимаю, что смогу найти сервер в наборе листов, несмотря ни на что, учитывая, что несколько серверов, но тот же вопрос возникает для второй строки - что, если у меня нет сервера, который имеет идентификатор узла такой, что я могу заполнить каждую возможную перестановку n-й цифры? Наконец, если у меня есть, скажем, четыре сервера, и у меня есть два узла, которые, скажем, делят, скажем, 20 из их 32 цифр, на какую-то случайную случайность ... я должен заполнить 20 строк таблицы для этого узла, даже если это гораздо больше строк, чем я мог бы даже близко к заполнению?

Вот то, что я придумал, пытаясь объяснить это:

  1. Записи должны быть установлены в нулевое значение, если нет узла, который точно соответствует этому префиксу.
  2. Пустые строки должны добавляться до тех пор, пока не будет достаточно строк, соответствующих общей длине nodeIds.
  3. Если и только если нет соответствующей записи для желаемого идентификатора сообщения, воспользуйтесь поиском в таблице маршрутизации для ID узла, общая длина которого больше или равна текущему идентификатору узла, и чья запись математически ближе, чем текущая ID узла по желаемому идентификатору.
  4. Если в # 3 не найдено подходящего узла, предположим, что это пункт назначения, и доставьте сообщение.

Все четыре из этих предположений верны? Где-то еще я должен искать информацию об этом?


  1. Кондитерские изделия: Масштабируемое, децентрализованное расположение и маршрутизация объектов для крупномасштабных одноранговых систем. Автор А. Роудронг и П. Друшел (2001) - скачать здесь
Пэдди
источник
Вы говорите, что у вас было мало программирования. Эта статья на самом деле не имеет отношения к программированию (напрямую), а скорее к кратчайшему пути сети между двумя узлами. Итак, следующий вопрос: какое количество сетевых знаний вы получили? Это все о маршрутизации по сетям.
Я действительно сказал, что считаю, что у меня достаточно опыта программирования. Это опыт информатики, которого мне не хватает. Несмотря на это, я почти не имею опыта работы в сети. Я не уверен, что согласен с вашим утверждением, что это в первую очередь связано с сетью, но я хотел бы услышать ваши мысли.

Ответы:

5

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

Алгоритм маршрутизации Pastry выглядит следующим образом:

AA

U

яUяU

(я+1)Tчася{0,...,2б-1}

A

UAUAUU1U1

U1A

Lог2бб2бб

Практические сценарии обычно не типичны. Могут быть ситуации, когда в сети не так много узлов. Вот почему мы следуем шагу C выше. - Тем не менее, чтобы гарантировать корректность этого алгоритма, необходимо, чтобы каждый узел был подключен к двум ближайшим к нему узлам (с точки зрения идентификаторов). Это сформирует кольцо упорядоченных узлов [например, 1-> 3-> 4-> 9-> 10-> 11-> 1]

AJed
источник
Не совсем то, о чем я спрашивал, но очень хороший обзор алгоритма дает вам голос и приемлемый ответ в любом случае. :)
Пэдди