高度不平衡的Kademlia路由表 [英] Highly unbalanced Kademlia routing table
问题描述
在Kademlia论文中，第2.4节的最后一段指出，为了正确处理高度不平衡的树木...
In the Kademlia paper, the last paragraph of section 2.4 states that in order to properly handle highly unbalanced trees...
Kademlia节点将所有有效联系人保留在大小至少为k的子树中 节点，即使这需要拆分节点自己的存储桶 ID不存在.
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中的某个插槽可用为止.
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.
本文似乎与这两点矛盾.
The paper seems to be contradicting itself with these two points.
在什么条件下应该分解一个k桶，为什么?将所有有效联系人"保留在路由表中似乎不切实际，因为路由表很快就会变得非常大.该示例讨论一棵树，该树有许多以001开头的节点和一个以000开头的节点.以000开头的节点将不得不连续拆分其k-bucket以容纳001，以容纳每个以001开头的有效节点?在160位地址空间中，最终不会在000的路由表中潜在地存储2 ^ 157个节点吗?
Under what conditions should a k-bucket be split and why? It seems not practical to keep "all valid contacts" in the routing table, as the routing table would then get very large very quickly. The example talks about a tree that has many nodes starting with 001 and one node starting with 000. The node starting with 000 would have to continually split its k-bucket for 001 to hold every valid node starting with 001? In a 160-bit address space, wouldn't that end up potentially storing 2^157 nodes in 000's routing table??
引号中的措词也很混乱...
The wording in the quoted block is also very confusing...
在子树中"-路由表的哪个子树中?
"in a subtree" -- in which subtree of the routing table?
大小至少为k个节点" –我们使用什么度量来确定子树的大小?在这种情况下，节点是指kademlia节点还是k-buckets或其他对象?
"of size atleast k nodes" -- what metric are we using to determine size of the subtree? nodes in this case refers to kademlia nodes or k-buckets or something else?
推荐答案
但是，本文的前一部分似乎指出，如果一个k-bucket已经具有k个元素，则对该k-bucket的任何进一步添加都需要删除最旧的节点(首先对其进行ping操作以查看其是否还存在)或以其他方式将添加内容缓存到该k-bucket中的某个插槽可用为止.
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.
每当有节点要插入但该存储桶不符合拆分条件时，这就是维护存储桶的方式.
That is how a bucket is maintained whenever there is a node contact to insert but the bucket is not eligible for splitting.
在什么条件下应该分解一个k-bucket，为什么?
Under what conditions should a k-bucket be split and why?
作为第一个近似值:每当无法插入新节点时都会拆分存储桶，并且存储桶的ID空间会覆盖您的节点ID.
As a first approximation: Split a bucket whenever a new node cannot be inserted and the bucket's ID-space covers your node ID.
这对于保持对邻域的完全了解，而对远程键空间部分只有模糊的认识是必要的. IE.本地化.
This is necessary to maintain full awareness of your neighborhood while having only vague awareness of remote keyspace portions. I.e. for locality.
要覆盖不平衡树的情况-如果节点ID不是(伪)随机，或者至少在叶子存储桶中，由于随机分配时的统计波动，可能会发生这种情况-该方法必须是放松如下:
To cover the unbalanced-tree case - which may happen either if node IDs aren't (pseudo-)random or, at least in leaf buckets, due to statistical flukes when they are assigning at random - the approach has to be relaxed as follows:
何时
- 试图在路由表中插入新的联系人 C
- C 所属的存储桶已满
- C 比您的路由表中的 K th -最靠近节点，其中 K 是存储桶大小
- attempting to insert a new contact C in the routing table
- the bucket into which C belongs is full
- C is closer to your node ID than the Kth-closest node in your routing table, where K is the bucket size
然后将水桶劈开.
在实践中，必须对它进行一些修改，以便将放松拆分用于响应，而未经请求的请求应仅使用严格拆分，否则当放松拆分在启动期间的早期发生时，您可能会得到一些奇怪的路由表.尚未填充.
In practice this has to be modified a little further so that relaxed splitting is used for responses while unsolicited requests should only use strict splitting, otherwise you could get some strangely distorted routing table when the relaxed splitting happens early during startup when the table isn't populated yet.
这篇关于高度不平衡的Kademlia路由表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
