1

I redesign our system (P2P application) that was built using "flat model" of k-buckets - each distance has its own k-backet. The distance is length of identifier minus length of shared prefix (XOR). Everything is clear here.

Now we want to use binary tree to hold buckets (as in last Kadelmia docs). The tree approach doesn't deal with distance "directly" when we "look for bucket" to put new contact in. This confuses me, since paper says that k-bucket should be split if new node is closer to local then K-closest node.

My question: how to calculate distance in this case? It cannot be prefix (path) of bucket, since bucket may contain nodes with different prefixes.

What is a convenient way to find K-closest node?

Thanks in advance.

marc_s
  • 732,580
  • 175
  • 1,330
  • 1,459
bw_dev
  • 775
  • 1
  • 7
  • 17

1 Answers1

1

It cannot be prefix (path) of bucket, since bucket may contain nodes with diffrent prefixes.

In the tree layout each bucket does have a prefix, but it is not implicit in its position in the routing table data structure, it must be tracked explicitly during split and merge operations instead, e.g. as base address plus prefix length, similar to CIDR notation.

An empty routing table starts out with a prefix covering the entire keyspace (i.e. 0x00/0), after some splitting one of the buckets might cover the range 0x0CFA0 - 0x0CFBF, which would be be the bucket prefix 0x0CFA/15.

See this answer on another question which contains an example routing table layout

Additionally see this answer for a simple and more advanced bucket splitting algorithm

How to find the matching bucket for a given ID depends on the data structure used. A sorted list will require binary search, a Patricia-Trie with nearest-lookups is another option. Even the brute force approach can be adequate as long as you do not have to handle too many operations per second.

the8472
  • 40,999
  • 5
  • 70
  • 122
  • First of all thanks for links. I use the algorithm described by second link. I use simple binary tree and found out that "found k-th closest" is not so trivial as it was with flat layout. – bw_dev Jul 24 '19 at 15:26
  • You can simply do a linear scan over the routing table and check whether a bucket prefix covers a key. Or use a trie. If you need to find more than bucket for the k-closest set you can use [this algorithm](https://stackoverflow.com/a/30655403/1362755) or just do a greedy accumulation over the whole routing table. It depends on your performance requirements. Real world tables have a few hundred entries at most and need to process a few packets per second, so even suboptimal algorithms are enough in many cases. Edit: Updated my answer – the8472 Jul 24 '19 at 16:17