Таблица маршрутизации в алгоритме Kadmelia Kadmelia без зацикливания каждого бита в ID узла - PullRequest
Новая
       62

Таблица маршрутизации в алгоритме Kadmelia Kadmelia без зацикливания каждого бита в ID узла

0 голосов
/ 03 июля 2018

Context

Я пытаюсь реализовать алгоритм K-Bucket Kadmelia, чтобы отслеживать более близкие узлы. Я теоретически понимаю, как работает алгоритм

  1. Когда новый узел added
  2. Если размер корзины не превысил k (размер корзины), мы добавляем ее в текущую корзину
  3. В противном случае мы разделяем сегмент и делим контакты в родительском сегменте, циклически перебирая каждый бит и разделяя их на два блока.
  4. Это также подразумевает, что для данного узла будет k * 8 сегментов (или списков)

Вопрос

Вопрос относится к подходу, принятому в этом примере http://blog.notdot.net/2009/11/Implementing-a-DHT-in-Go-part-1

Учитывая, что мы определили узел как байтовый массив длиной 20 



const IdLength = 20
type NodeID [IdLength]byte

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

Чего я не понимаю, так это возвращаемых значений и почему они установлены таким образом. 

<code>

func (node NodeID) PrefixLen() (ret int) {
  for i := 0; i < IdLength; i++ {
    for j := 0; j < 8; j++ {
      if (node[i] >> uint8(7 - j)) & 0x1 != 0 {
        return i * 8 + j;
      }
    }
  }
  return IdLength * 8 - 1;
}

Как возвращаемое значение подходит для использования в качестве индекса для таблицы маршрутизации? 

<code>
  ...
  prefix_length := contact.id.Xor(table.node.id).PrefixLen();
  bucket := table.buckets[prefix_length];
  ...

Как этот подход идентичен циклу для каждого бита? Как автор достигает того же результата, используя метод PrefixLen.

Не могли бы вы помочь мне понять это на примерах. Заранее спасибо.

1 Ответ

0 голосов
/ 03 июля 2018

Чем этот подход идентичен циклу для каждого бита?

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

Что я не понимаю, так это возвращаемые значения и почему они установлены таким образом.

Он просто вычисляет позицию бита в терминах i полных байтов и j битов в последнем частичном байте.

Контекст

Здесь контекст на самом деле ошибочен, так как вы пытаетесь объяснить структуру таблицы маршрутизации с разбивкой, рассматривая пример кода с фиксированной компоновкой массива. Это общий источник путаницы .

...