0

Initially this was a different question. But the questions I ended up answering which gave me a good idea of how everything works were: How are buckets organized?- how does the range system work. How does the xor matrix works for distance? And how is the routing table organized?

orraz1
  • 43
  • 5
  • Did you also read the kademlia paper? – the8472 Jan 12 '23 at 12:45
  • I'll try but I've also heard it's a bit different with mainline dht having more of a dynamic number of k buckets and kademlia having a fixed size – orraz1 Jan 12 '23 at 21:27
  • That's more a matter how it is implemented, not how the general concept works. https://stackoverflow.com/q/51161731/1362755 – the8472 Jan 12 '23 at 22:05
  • So I can implement the bootstrap process however I want to as long as it works? – orraz1 Jan 13 '23 at 09:36
  • 1
    Well, I was responding to your comment about the bucket layout. But yes, the bootstrap process is similar, it has some goals that need to be achieved, the exact details aren't quite as important. Anyway, I mostly suggested to read the kademlia paper so you can refine your question because the BEP leaves out some things that are covered by the paper. – the8472 Jan 13 '23 at 09:39
  • Awesome can you link the official documentation? – orraz1 Jan 13 '23 at 12:26
  • 1
    https://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf – the8472 Jan 13 '23 at 20:03
  • I've read around 70% of it. Wanna make sure I understand. The routing table is composed of a binary trees which breaches are composed of bits representing 1,0. Each brench leads to a bucket of nodes. The range of the bucket I still don't get, tell me if the implementation of range written earlier is possible for the range – orraz1 Jan 15 '23 at 05:43
  • Or perhaps a bucket range will be composed and fit through the binary tree, so every node with 1001 bits at the start for example will be in this bucket range – orraz1 Jan 15 '23 at 05:48
  • You should update your question. – the8472 Jan 15 '23 at 13:10
  • I'll re read the paper and update it – orraz1 Jan 15 '23 at 13:48
  • Going to write an answer tell me if I'm correct – orraz1 Jan 16 '23 at 09:10
  • This should be it, just correct me if I'm wrong, anyways thanks I'll start implementing it in c#, not looking for perfection just a functioning product – orraz1 Jan 16 '23 at 19:35

1 Answers1

0

This is an idea of how I think this works: Routing table is composed of a binary tree composed of 1 and 0. A bucket range is composed of nodes with similar prefix, on a branch number composed of the amount of similar bits on the prefix that are similar. So for example branch 2 composed of 1-0 can have a bucket of (1011,1000,1011) and so on. using your own Id you can xor another nodes Id and the amount of 0's in the prefix will be the branch number and the prefix making the bucket range would be the same as your own node. When needing to insert a new node into a full bucket, if your id fits within the range you'll split the bucket. This way you'll have a routing table composed of nodes similar to you and a bit that don't. Also need to mention the deeper you go on the tree the closer you'll get to your id

the8472
  • 40,999
  • 5
  • 70
  • 122
orraz1
  • 43
  • 5
  • Now your question headline doesn't fit the rest of the question or the answer.... please consider the Q&A format a bit more. This isn't just about answering your questions but also leaving behind information structured in a way that it'll help future readers. – the8472 Jan 17 '23 at 20:13
  • 1
    alright will change first thing in the morning, but is this accurate? Also would the closest node be a range I pick it to be by implementation? – orraz1 Jan 17 '23 at 20:47
  • The routing table is a tree, yes. With buckets covering ranges of the absolute keyspace based on prefix-bitmasks. The XOR distance is not used when putting nodes in the routing table, it's used for lookups. – the8472 Jan 18 '23 at 22:45
  • I thought the routing table is supposed to represent the 160 bit range of your own node. Also removed the new post because I changed this question to the same thing. – orraz1 Jan 19 '23 at 04:12
  • Also If that's the case and I organize my routing table based on my own id theoretically using xor is not an issue correct? – orraz1 Jan 19 '23 at 08:51
  • See the other SO post that I linked in a previous comment, it already covers that. – the8472 Jan 19 '23 at 18:01
  • So what I described is a mixed of flat and binary tree. Can I also implement flat for mainline dht? also for the binary based tree because of how the splitting mechanics work wouldn't most bucket's prefix (that aren't within your range) mostly contain your own with the last being different. – orraz1 Jan 19 '23 at 21:05
  • Seems like a flat routing table isn't wrong just not recommended https://www.bittorrent.org/beps/bep_0045.html – orraz1 Jan 20 '23 at 17:37
  • 1
    I suspect BEP5 was written based on the preprint paper, so the author may not have been aware of the changes of full paper. One of the kademlia authors also recommends studying the approach from the full paper. Yes it "works" well enough that one get some results but I don't know its quality, I haven't seen any comparative study. – the8472 Jan 20 '23 at 21:27
  • Awesome last question and I think I have everything down. In the binary tree based routing table you'll split a bucket that's in your range thus end up with 1 bucket per subtree that's outside your range correct? – orraz1 Jan 20 '23 at 22:35
  • I don't understand that question. This answer contains a visualization of a tree-based routing table: https://stackoverflow.com/a/29042135/1362755. Anyway, I'll stop answering comments now since none of this fits the purpose of the Q&A format. Please make top level questions. – the8472 Jan 21 '23 at 11:23