时间戳

首页 > 解决方案 > Kadmelia K-Bucket 算法中的路由表，无需遍历节点 ID 中的每一位

go - Kadmelia K-Bucket 算法中的路由表，无需遍历节点 ID 中的每一位

问题描述

语境

我正在尝试实现 Kadmelia 的 K-Bucket 算法来跟踪更近的节点。我从理论上理解算法是如何工作的

  1. 当一个新节点added
  2. 如果桶大小没有超过 k（桶大小），我们将它添加到当前桶中
  3. 否则，我们拆分桶并通过循环每个位来划分父桶中的联系人并将它们分成两个桶。
  4. 这也意味着对于给定的节点，会有k * 8桶（或列表）

问题

问题是指本示例中采用的方法http://blog.notdot.net/2009/11/Implementing-a-DHT-in-Go-part-1

假设我们已将 Node 定义为长度为 20 的字节数组



const IdLength = 20
type NodeID [IdLength]byte

我试图了解该PrefixLen函数实际计算前缀和填充路由表的作用。我了解该方法的每个组件的作用。我的意思是，我了解位移运算符的作用，并AND用 1 检查该位是否已设置。

我不明白的是返回值以及为什么以这种方式设置它们。 



func (node NodeID) PrefixLen() (ret int) {
  for i := 0; i < IdLength; i++ {
    for j := 0; j < 8; j++ {
      if (node[i] >> uint8(7 - j)) & 0x1 != 0 {
        return i * 8 + j;
      }
    }
  }
  return IdLength * 8 - 1;
}

返回值如何适合用作路由表的索引？


  ...
  prefix_length := contact.id.Xor(table.node.id).PrefixLen();
  bucket := table.buckets[prefix_length];
  ...

这种方法与循环遍历每一位有何相同之处？作者如何使用 PrefixLen 方法达到相同的结果。

您能否通过示例帮助我理解这一点。提前致谢。

标签： gobit-manipulationdhtkademlia

解决方案

这种方法与循环遍历每一位有何相同之处？

循环简单地迭代字节，然后对每个字节进行移位和掩码。所以实际上它确实迭代了所有位，这些位恰好被打包成字节，因为最小的可寻址内存单元通常是一个字节。

我不明白的是返回值以及为什么以这种方式设置它们。

i它只是根据完整字节和j最后部分字节中的位来计算位位置。

语境

这里的上下文实际上是被误导的，因为您在查看具有固定阵列布局的代码示例时试图解释可拆分路由表设计。这是一个常见的混淆来源。

推荐阅读