在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或其他？
然而,本文的前一部分似乎表明,如果一个k-bucket已经有k个元素,那么对该k-bucket的任何进一步添加都需要删除最旧的节点(首先ping它以查看它是否存活)或以其他方式缓存添加直到该k-bucket中的插槽可用.
这就是每当有要插入的节点联系人但没有资格进行拆分时,如何维护存储桶.
在什么条件下应该拆分k-bucket以及为什么？
作为第一个近似值:每当无法插入新节点并且存储桶的ID空间覆盖您的节点ID 时拆分存储桶.
这对于保持对邻居的完全意识是必要的,同时只能模糊地了解远程键空间部分.即地方性.
为了覆盖不平衡树的情况 - 如果节点ID不是(伪)随机的,或者至少在叶子桶中,当它们随机分配时由于统计吸收而可能发生 - 该方法必须放宽如下:
什么时候
然后分开桶.
在实践中,这需要进一步修改,以便放松拆分用于响应,而未经请求的请求应该只使用严格的拆分,否则当启动期间放松拆分时,你可能得到一些奇怪的扭曲路由表人口稠密.