1

Closest question to this I think.

One obvious method of structuring a routing table is to simply maintain a literal table. Map(XOR,Node)

Kademlia discusses the use of 'Buckets' which are organised by the most significant bit of the XOR. What is the actual purpose of 'buckets'? Why mess around with 'longest prefix' when we can simply hold the 'actual' XOR as a key in a map?

Obviously the map could potentially be 2^160 large, but we could use some heuristics to limit the size of the map, rather than implementing some arbitrary bucket concept? In any case (buckets or not) when searching for a nodeId close to the one we've been asked to find, we still have to iterate through all nodes in the table and do an XOR on each?

What am I missing?

Richard
  • 1,070
  • 9
  • 22
  • Possible duplicate of [Why does Kademlia structure its routing table how it does?](https://stackoverflow.com/questions/11273007/why-does-kademlia-structure-its-routing-table-how-it-does) – the8472 Oct 12 '18 at 18:35

1 Answers1

0

One obvious method of structuring a routing table is to simply maintain a literal table. Map(XOR,Node)

I read the key is xor but the xor of what? xor takes two argument:

distance = xor(hash, peerid)

What is the actual purpose of 'buckets'?

k-bukcets allow to speed the following python code:

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

That is find the closest peers to a given hash.

Why mess around with 'longest prefix' when we can simply hold the 'actual' XOR as a key in a map?

Like I said, above you can not store the xor value of every possible hash.

when searching for a nodeId close to the one we've been asked to find, we still have to iterate through all nodes in the table and do an XOR on each?

That the thing with k-buckets you don't need to iterate over the whole map to find the closest peers, because peers hash aka. peerid are organized by prefix and you know that the nearest peers share the same prefix as the given hash.

Why use Buckets and not a map?

You can use a map instead of k-bucket.

amirouche
  • 7,682
  • 6
  • 40
  • 94
  • Hello! Do you have any pseudocode, sequence diagrams, or clear description of how we populate the routing table. So something like : bootstrap finds a single active node XOR that with our peer id and place in correct bucket. Query that node for our own peerid, for each peer returned, xor and place in buckets.... Etc. But for a tree based system, and not flat buckets? – Richard May 30 '19 at 14:51
  • Hello Richard, I do not understand how the k-bucket data structure works. The best option you have, I think, is to look at the implementation of existing dht project like libdht used in transmission. Otherwise I have dht implementation but it doesn't rely on k-buckets https://github.com/amirouche/qadom – amirouche May 30 '19 at 14:53
  • If you're not using KBuckets how are you doing it? – Richard May 30 '19 at 14:58
  • I use that very line : `nsmallest(k, peers, key=functools.partial(operator.xor, hash))`. That is a sort every peers using xor metric against the requested hash and pick `k` peers that have the smallest distance. Don't forget to upvote / mark as correct my answer if it is answering the question. Thanks! – amirouche May 30 '19 at 15:00
  • The code for the DHT table I use is in [`peer.py`](https://github.com/amirouche/qadom/blob/master/qadom/peer.py) – amirouche May 30 '19 at 15:01