douwei3172
2018-07-03 13:13
浏览 172
已采纳

Kadmelia K-Bucket算法中的路由表,而无需遍历节点ID中的每个位

Context

I'm trying to implement Kadmelia's K-Bucket algorithm to keep track of closer nodes. I understand in theory how the algorithm works

  1. When a new node is added
  2. If the bucket size hasn't exceeded k (bucket size) we add it to the current bucket
  3. else we split the bucket and divide the contacts in the parent bucket by looping over each bit and split them into two buckets.
  4. This also implies that for a given node there would be k * 8 buckets (or lists)

Question

The question is in reference to the approach adopted in this example http://blog.notdot.net/2009/11/Implementing-a-DHT-in-Go-part-1

Given that we have defined a Node as a byte array of length 20



const IdLength = 20
type NodeID [IdLength]byte

I'm trying to understand what the PrefixLen function does to actually compute the prefix and populate the routing table. I understand what each component of the method does. By that I mean, I understand what the bit shift operators do and AND with 1 to check if the bit is set.

What I fail to understand is the return values and why they're set in that way.



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;
}

How is the return value suitable to be used as an index for the routing table?


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

How is this approach identical to looping over each bit? How does the author achieve the same result using the PrefixLen method.

Could you help me understand this with examples. Thanks in advance.

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • dqqpf32897 2018-07-03 18:34
    已采纳

    How is this approach identical to looping over each bit?

    The loop simply iterates over bytes and then for each byte over the bits doing shifts and masks. So in effect it does iterate over all bits, the bits just happen to be packed into bytes since the smallest addressable unit of memory generally is one byte.

    What I fail to understand is the return values and why they're set in that way.

    It simply calculates the bit position in terms of i complete bytes and j bits in the last partial byte.

    Context

    The context is actually misguided here since you're trying to explain the splittable routing table design while looking at a code sample with a fixed array layout. That is a common source of confusion.

    已采纳该答案
    打赏 评论

相关推荐 更多相似问题