我现在通过阅读经典论文来学习Kademlia网络我想了解其操作的复杂性,但仍然无法弄清楚。
在证明部分的3个草图中,给出了两个定义:
节点深度(h):160-i,其中i是
非空桶
节点x中节点y的bucket height:x插入y的bucket的索引减去x的最低有效空bucket的索引。
以及三个结论:
对于具有n个节点的系统,任何给定节点的高度都将在logn的常数范围内。
在第k个最近的节点中,最接近id的节点的bucket高度可能在logk的常数内。
如果该节点的h个最重要k-bucket中没有一个是空的,则查找过程将在每个步骤中找到一个接近(或者更确切地说,其距离短一位)一半的节点,从而在h-logk步骤中打开该节点。
所以我的问题是:
什么是“最低有效空桶”和“最高有效k桶”?
如何用视觉的方法来解释深度和桶高?
如何理解第二和第三个结论,比如,为什么log k和h-logk?

最佳答案

我已经有一段时间没有真正读过这篇论文了,所以我主要是从我的实现经验中拼凑出来,而不是试图将我头脑中的概念与论文中的正式定义相匹配,所以请带上一点盐
什么是“最低有效空桶”和“最高有效k桶”?
这基本上是指根据相对于节点自身id的xor距离排序的bucket。
如何用视觉的方法来解释深度和桶高?
每个bucket覆盖一个键空间区域。例如,从0x0000simplified到2 bytes,再到0x0FFF,占键空间的1/16这可以用类似CIDR的掩码0x0/4(4个前缀位)来表示。
差不多是桶的深度。
有几种方法可以组织路由表“正确的”方法是根据bucket表示的最低ID将其表示为树或排序列表。
这种方法允许在某些路由表优化需要时执行任意的bucket拆分操作,也可以用于实现节点多宿主。
一个简化的实现可以使用一个固定长度的数组,将每个bucket放在与节点自身id相关的共享前缀位的位置,即数组中的0位置将有0个共享前缀位,这是最远的bucket,覆盖50%键空间的bucket和最有效位为节点自身ID的反向MSB的bucket。
在这种情况下,深度只是数组的位置。
如何理解第二和第三个结论,比如,为什么log k和h-logk?
假设您正在寻找一个离您自己节点的id最远的id,那么您将只有一个bucket来覆盖该部分键空间,即它将覆盖一半键空间,其中最重要的位与您的不同。
因此,您可以从该bucket中请求一个(或多个)节点。由于它们的ID位具有与查找目标相同的第一个位,因此它们或多或少保证将其分成两个或多个,即至少具有目标空间的两倍键空间覆盖率所以他们至少能提供一点更好的信息。
当您查询离目标更近的节点时,它们在目标区域附近的键空间覆盖率也会更好,因为这也更接近它们自己的节点ID。
冲洗,重复,直到找不到更靠近的节点。
因为每个跳一次至少减少1位距离,所以基本上需要一个o(log(n))跳数,其中n是网络大小。因为网络大小基本上决定了节点之间的平均距离,从而决定了主bucket所需的bucket深度。
如果目标密钥更接近您自己的id,您将需要更少的步骤,因为您将更好地覆盖该键区。
因为k是一个常数(每个bucket的节点数),所以logk也是。bucket中节点数的两倍,它的分辨率是给定键空间区域的两倍,因此(可能)会产生一个比k/2大小的bucket更接近目标的节点也就是说,对于希望保存的每跳每增加一位,必须将每个bucket的条目数增加一倍。
编辑:这是一个实际的单宿主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

09-10 01:18
查看更多