1

我认为最接近这个问题。

构建路由表的一种明显方法是简单地维护一个文字表。映射(异或,节点)

Kademlia 讨论了由 XOR 的最高有效位组织的“桶”的使用。“桶”的实际目的是什么? 当我们可以简单地将“实际”XOR 作为映射中的键时,为什么还要搞乱“最长前缀”?

显然地图可能有 2^160 大,但我们可以使用一些启发式方法来限制地图的大小,而不是实现一些任意的桶概念?在任何情况下(无论是否存储桶),当搜索一个接近我们被要求找到的 nodeId 时,我们仍然必须遍历表中的所有节点并对每个节点执行 XOR?

我错过了什么?

4

1 回答 1

0

构建路由表的一种明显方法是简单地维护一个文字表。映射(异或,节点)

我读的关键是xor什么xorxor有两个参数:

distance = xor(hash, peerid)

“桶”的实际目的是什么?

k-bukcets 允许加速以下 python 代码:

nsmallest(k, peers, key=functools.partial(operator.xor, hash))

那就是找到与给定哈希最近的对等点。

当我们可以简单地将“实际”XOR 作为映射中的键时,为什么还要搞乱“最长前缀”?

就像我说的,上面你不能存储每个可能散列的异或值。

当搜索一个接近我们被要求找到的 nodeId 时,我们仍然必须遍历表中的所有节点并对每个节点执行 XOR?

使用 k-buckets 的东西你不需要遍历整个地图来找到最近的对等点,因为对等点也可以散列。peerid是按前缀组织的,您知道最近的对等点与给定的哈希共享相同的前缀。

为什么使用 Buckets 而不是 map?

您可以使用地图而不是 k-bucket。

于 2019-05-30T13:24:39.400 回答