9

在 Kademlia 论文中，第 2.4 节的最后一段指出，为了正确处理高度不平衡的树......

Kademlia 节点将所有有效联系人保存在大小至少为 k 个节点的子树中，即使这需要拆分不包含节点自己 ID 的桶。

然而，论文的前一部分似乎指出，如果一个 k-bucket 已经有 k 个元素，那么对该 k-bucket 的任何进一步添加都需要删除最旧的节点（首先对其进行 ping 操作以查看其是否存在）或以其他方式缓存添加直到该 k-bucket 中的插槽可用。

这篇论文似乎与这两点自相矛盾。

在什么条件下应该拆分 k-bucket，为什么？在路由表中保留“所有有效联系人”似乎不切实际，因为路由表会很快变得非常大。该示例讨论了一棵树，它有许多以 001 开头的节点和一个以 000 开头的节点。以 000 开头的节点必须不断地将其 k-bucket 拆分为 001 以保存以 001 开头的每个有效节点？在一个 160 位的地址空间中，最终不会在 000 的路由表中存储 2^157 个节点吗？

引用块中的措辞也很混乱......

“在子树中”——在路由表的哪个子树中？

“大小至少为 k 个节点”——我们使用什么指标来确定子树的大小？在这种情况下，节点是指 kademlia 节点或 k-buckets 或其他东西？

4

1 回答 1

7

但是，论文的前一部分似乎指出，如果 k-bucket 已经有 k 个元素，则对该 k-bucket 的任何进一步添加都需要删除最旧的节点（首先对其进行 ping 操作以查看其是否存在）或以其他方式缓存添加直到该 k-bucket 中的插槽可用。

这就是每当有要插入的节点联系人但存储桶不符合拆分条件时维护存储桶的方式。

在什么条件下应该拆分 k-bucket，为什么？

作为第一个近似值：每当无法插入新节点并且存储桶的 ID 空间覆盖您的节点 ID 时，拆分存储桶。

这对于保持对您的邻居的全面了解是必要的，同时对远程键空间部分只有模糊的了解。即地方性。

为了涵盖不平衡树的情况——如果节点 ID 不是（伪）随机的，或者至少在叶桶中，由于随机分配时的统计侥幸，这种情况可能会发生——方法必须放宽如下：

什么时候

  • 试图在路由表中插入一个新的联系人C
  • C所属的桶已满
  • C比路由表中第K个最近的节点更接近您的节点 ID ，其中K是存储桶大小

然后拆分桶。

在实践中，这必须进一步修改，以便对响应使​​用宽松拆分，而未经请求的请求应该只使用严格拆分，否则当表不在启动期间的早期发生宽松拆分时，您可能会得到一些奇怪扭曲的路由表人口稠密。

于 2015-08-24T16:42:39.170 回答