高度不平衡的 Kademlia 路由 table
Highly unbalanced Kademlia routing table
在 Kademlia 论文中，第 2.4 节的最后一段指出，为了正确处理高度不平衡的树...
Kademlia nodes keep all valid contacts in a subtree of size at least k
nodes, even if this requires splitting buckets in which the node's own
ID does not reside.
然而，本文的前一节似乎指出，如果一个 k-bucket 已经有 k 个元素，则对该 k-bucket 的任何进一步添加都需要删除最旧的节点（首先对其进行 ping 以查看它是否活着）或以其他方式缓存添加，直到该 k-bucket 中的插槽可用。
这篇论文似乎与这两点自相矛盾。
k-bucket应该在什么情况下分裂，为什么？将 "all valid contacts" 保留在路由 table 中似乎不切实际，因为路由 table 会很快变得非常大。该示例讨论了一棵树，该树具有许多以 001 开头的节点和一个以 000 开头的节点。以 000 开头的节点必须不断拆分其 k-bucket 以获取 001 以容纳以 001 开头的每个有效节点？在一个 160 位的地址 space 中，最终不会在 000 的路由 table 中存储 2^157 个节点吗？？
引用块中的措辞也很混乱...
"in a subtree" -- 在路由的哪个子树中 table?
"of size atleast k nodes" -- 我们使用什么指标来确定子树的大小？这种情况下的节点指的是 kademlia 节点或 k-buckets 或其他东西？
However, the previous section of the paper seem to state that if a k-bucket already has k elements, that any further additions in to that k-bucket require removing the stalest node (pinging it first to see if its alive) or otherwise caching the addition until a slot becomes available in that k-bucket.
这就是每当有节点联系要插入但桶不符合拆分条件时维护桶的方式。
Under what conditions should a k-bucket be split and why?
作为一阶近似：每当无法插入新节点时拆分桶和桶的ID-space覆盖你的节点 ID。
这是必要的，以保持对您的邻居的充分了解，同时对远程密钥space 部分只有模糊的了解。 IE。对于地区。
为了涵盖不平衡树的情况——如果节点 ID 不是（伪）随机的，或者至少在叶桶中，由于随机分配时的统计侥幸，可能会发生这种情况——该方法具有放宽如下：
什么时候
- 正在尝试在路由 table
中插入新联系人 C
- C所属的桶已满
- C 比 Kth 中最接近的节点更接近您的节点 ID您的路由 table，其中 K 是存储桶大小
然后拆分桶。
在实践中，这必须进一步修改，以便松散拆分用于响应，而未经请求的请求只能使用严格拆分，否则当松散拆分发生时，您可能会得到一些奇怪的扭曲路由 table启动初期 table 尚未填充时。
当然，在合并桶时也需要考虑这一点，这样只要在路由 table.
S/Kademlia paper 中提出的改进之一是使用兄弟列表 insead 来跟踪节点的最近邻居，这可能比非本地拆分更容易实现。
在 Kademlia 论文中，第 2.4 节的最后一段指出，为了正确处理高度不平衡的树...
Kademlia nodes keep all valid contacts in a subtree of size at least k nodes, even if this requires splitting buckets in which the node's own ID does not reside.
然而，本文的前一节似乎指出，如果一个 k-bucket 已经有 k 个元素，则对该 k-bucket 的任何进一步添加都需要删除最旧的节点（首先对其进行 ping 以查看它是否活着）或以其他方式缓存添加，直到该 k-bucket 中的插槽可用。
这篇论文似乎与这两点自相矛盾。
k-bucket应该在什么情况下分裂，为什么？将 "all valid contacts" 保留在路由 table 中似乎不切实际，因为路由 table 会很快变得非常大。该示例讨论了一棵树，该树具有许多以 001 开头的节点和一个以 000 开头的节点。以 000 开头的节点必须不断拆分其 k-bucket 以获取 001 以容纳以 001 开头的每个有效节点？在一个 160 位的地址 space 中，最终不会在 000 的路由 table 中存储 2^157 个节点吗？？
引用块中的措辞也很混乱...
"in a subtree" -- 在路由的哪个子树中 table?
"of size atleast k nodes" -- 我们使用什么指标来确定子树的大小？这种情况下的节点指的是 kademlia 节点或 k-buckets 或其他东西？
However, the previous section of the paper seem to state that if a k-bucket already has k elements, that any further additions in to that k-bucket require removing the stalest node (pinging it first to see if its alive) or otherwise caching the addition until a slot becomes available in that k-bucket.
这就是每当有节点联系要插入但桶不符合拆分条件时维护桶的方式。
Under what conditions should a k-bucket be split and why?
作为一阶近似：每当无法插入新节点时拆分桶和桶的ID-space覆盖你的节点 ID。
这是必要的，以保持对您的邻居的充分了解，同时对远程密钥space 部分只有模糊的了解。 IE。对于地区。
为了涵盖不平衡树的情况——如果节点 ID 不是（伪）随机的，或者至少在叶桶中，由于随机分配时的统计侥幸，可能会发生这种情况——该方法具有放宽如下：
什么时候
- 正在尝试在路由 table 中插入新联系人 C
- C所属的桶已满
- C 比 Kth 中最接近的节点更接近您的节点 ID您的路由 table，其中 K 是存储桶大小
然后拆分桶。
在实践中，这必须进一步修改，以便松散拆分用于响应，而未经请求的请求只能使用严格拆分，否则当松散拆分发生时，您可能会得到一些奇怪的扭曲路由 table启动初期 table 尚未填充时。
当然，在合并桶时也需要考虑这一点，这样只要在路由 table.
S/Kademlia paper 中提出的改进之一是使用兄弟列表 insead 来跟踪节点的最近邻居，这可能比非本地拆分更容易实现。