4

我现在通过阅读经典论文Kademlia: A Peer-to-peer Information System Based on the XOR Metric 来学习 Kademlia 网络。我想了解其操作的复杂性，但仍然无法弄清楚。

在3 Sketch of proof部分，论文给出了两个定义：

  1. 节点深度（h）：160 - i，其中 i 是非空桶的最小索引
  2. 节点 y 在节点 x 中的桶高度：x 将插入 y 的桶的索引减去 x 的最低有效空桶的索引。

以及三个结论：

  1. 对于具有 n 个节点的系统，任何给定节点的高度以压倒性的概率将在log n的常数内。
  2. 与第 k 个最近节点中的 ID 最近的节点的桶高度可能在log k的常数内。
  3. 如果这个节点的 h个最重要的 k-buckets中没有一个是空的，则查找过程将在每一步中找到一个接近一半的节点（或者更确切地说，它的距离短一点），从而在h - log k步中找到该节点.

所以我的问题是：

  1. 什么是“最不重要的空桶”和“最重要的 k 桶”？
  2. 如何直观地解释深度和铲斗高度？
  3. 如何理解第二个和第三个结论，比如说，为什么log k和h-log k？
4

1 回答 1

4

自从我真正阅读这篇论文已经有一段时间了，所以我主要是根据我的实施经验将这些拼凑起来，而不是试图将我脑海中的概念与论文中的正式定义相匹配，所以采取加一点盐

什么是“最不重要的空桶”和“最重要的 k 桶”？

这基本上是指按相对于节点自身 ID 的异或距离排序的桶

如何直观地解释深度和铲斗高度？

每个桶覆盖一个键空间区域。例如，从 0x0000简化为 2 字节到 0x0FFF 用于 1/16 的键空间。这可以用类似 CIDR 的掩码 0x0/4（4 个前缀位）来表示。这或多或少是一个桶的深度。

有几种方法可以组织路由表。“正确”的方法是将其表示为基于存储桶表示的最低 ID 的树或排序列表。这种方法允许任意存储桶拆分操作，因为某些路由表优化要求并且还可以用于实现节点多宿主。

一个简化的实现可以改为使用一个固定长度的数组，并将每个桶放在相对于节点自己的 ID 的共享前缀位的位置。即数组中的位置 0 将有 0 个共享前缀位，它是最远的存储桶，该存储桶覆盖 50% 的键空间，最高有效位是节点自身 ID 的倒置 MSB 的存储桶。

在这种情况下，深度只是阵列位置。

如何理解第二个和第三个结论，比如说，为什么 log k 和 h - log k？

假设您正在寻找离您自己节点的 ID 最远的 ID。那么你将只有一个桶覆盖键空间的那一部分，即它将覆盖一半的键空间，最高有效位与你的不同。因此，您从该存储桶中询问一个（或多个）节点。由于它们的 ID 位与您的查找目标具有相同的第一位，因此它们或多或少地保证将其拆分为两个或多个，即目标空间的键空间覆盖率至少是两倍。所以他们可以提供至少 1 位更好的信息。

当您查询离目标更近的节点时，它们也会在目标区域附近有更好的键空间覆盖，因为这也更接近它们自己的节点 ID。

冲洗，重复直到找不到更近的节点。

由于每个跃点一次至少减少 1 位距离，因此您基本上需要 O(log(n)) 跃点计数，其中 n 是网络大小。由于网络大小基本上决定了节点之间的平均距离，因此决定了您的主存储桶所需的存储桶深度。

如果目标键更接近您自己的 ID，您将需要更少的步骤，因为您将更好地覆盖键空间的该区域。

由于k是一个常数（每个桶的节点数），所以log k也是。将桶中的节点数量加倍，它将具有给定键空间区域的两倍的分辨率，因此（概率上）会产生一个比 k/2 大小的桶更接近目标的节点。即，对于您希望保存的每个跃点，您必须将每个桶的条目数加倍。

编辑：这是一个实际的单宿主 bittorrent DHT 路由表的可视化，按前缀排序，即与本地节点 ID 无关：

Node ID: 2A631C8E 7655EF7B C6E99D8A 3BF810E2 1428BFD4
buckets: 23 / entries: 173
000...   entries:8 replacements:8
00100...   entries:8 replacements:0
0010100...   entries:8 replacements:2
0010101000...   entries:8 replacements:4
00101010010...   entries:8 replacements:7
001010100110000...   entries:8 replacements:3
0010101001100010...   entries:8 replacements:3
00101010011000110000...   entries:8 replacements:1
001010100110001100010...   entries:3 replacements:0
0010101001100011000110...   entries:6 replacements:0
0010101001100011000111...   entries:6 replacements:0
0010101001100011001...   entries:8 replacements:2
001010100110001101...   entries:8 replacements:1
00101010011000111...   entries:8 replacements:2
00101010011001...   entries:7 replacements:0
0010101001101...   entries:8 replacements:0
001010100111...   entries:8 replacements:0
001010101...   entries:8 replacements:1
00101011...   entries:7 replacements:0
001011...   entries:8 replacements:0
0011...   entries:8 replacements:8
01...   entries:8 replacements:8
1...   entries:8 replacements:8
于 2015-03-13T21:19:50.397 回答