Что именно K-Bucket означает в Kademlia DHT?

Question

Я хочу подтвердить свое понимание ведер в Kademlia DHT.Kademlia имеет m k-сегментов , где m - размер сети в битах, а k - количество ключ-значение пар.хранится в ведре.например, скажем m=4, тогда мы можем иметь 2^4 узлов, а именно от 0 до 15.

+========+
| NodeId |
+========+
|   0000 |
+--------+
|   0001 |
+--------+
|   0010 |
+--------+
|   0011 |
+--------+
|   0100 |
+--------+
|   0101 |
+--------+
|   0110 |
+--------+
|   0111 |
+--------+
|   1000 |
+--------+
|   1001 |
+--------+
|   1010 |
+--------+
|   1011 |
+--------+
|   1100 |
+--------+
|   1101 |
+--------+
|   1110 |
+--------+
|   1111 |
+--------+

Каждый узел имеет таблицу маршрутизации с 0-битным соответствием, 1-битным соответствием и2-битное совпадение и так далее, это m сегментов.Кроме того, для каждого сегмента он будет хранить k представителей вместо одного NodeId.Итак, если мы скажем k = 2, таблица маршрутизации для узла 0101 будет выглядеть примерно так:

┌──────────────────────┐
│         0101         │
├──────────────────────┤
|                      |
| +==================+ |
| |       xxxx       | |
| +==================+ |
| |   1001, <value>  | |
| +------------------+ |
| |   1010, <value>  | |
| +------------------+ |
|                      |
| +==================+ |
| |       0xxx       | |
| +==================+ |
| |   0000, <value>  | |
| +------------------+ |
| |   0111, <value>  | |
| +------------------+ |
|                      |
| +==================+ |
| |       01xx       | |
| +==================+ |
| |   0110, <value>  | |
| +------------------+ |
| |   0111, <value>  | |
| +------------------+ |
|          .           |
|          .           |
|          .           |
└──────────────────────┘

Верно ли мое предположение?

Answer 1

Каждый узел в Kademlia хранит список других узлов.Этот список основан на битовых различиях и слабо обозначается как сегменты.Теперь 'k' - это параметр репликации всей системы.Это означает, что для каждого списка есть k записей внутри этого «сегмента».Это моё понимание. Это ссылка на статью.Надеюсь, это поможет ..:)

Answer 2

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

Реализация полного алгоритма kademlia требует динамической компоновки таблицы маршрутизации .Поэтому m не является фиксированным.Компоновка с фиксированным размером использовалась только в упрощенной пре-печатной версии статьи как часть теоретического доказательства.