Official eMule-Board: Highly Unbalanced Kademlia Routing Table - Official eMule-Board

Jump to content


Page 1 of 1

Highly Unbalanced Kademlia Routing Table

#1 User is offline   offbynull 

  • Newbie
  • Pip
  • Group: Members
  • Posts: 2
  • Joined: 20-August 15

Posted 21 August 2015 - 12:00 AM

Hi, I've asked this question on another forum already but I feel like it's better to ask here since eMule has one of the most successful Kademlia implementations in use.

My question has to do with section 2.4 of the original Kademlia paper. The last paragraph states that in order to properly handle highly unbalanced trees...

Quote

Kademlia nodes keep all valid contacts in a subtree of size at least k nodes, even if this requires splitting buckets in which the node's own ID does not reside.


However, the previous section of the paper seems to state that if a k-bucket already has k elements, that any further additions in to that k-bucket require removing the stalest node (pinging it first to see if its alive) or otherwise caching the addition until a slot becomes available in that k-bucket.

The paper seems to be contradicting itself with these two points.

Under what conditions should a k-bucket be split and why? It seems not practical to keep "all valid contacts" in the routing table, as the routing table would then get very large very quickly. The example talks about a tree that has many nodes starting with 001 and one node starting with 000. The node starting with 000 would have to continually split its k-bucket for 001 to hold every valid node starting with 001? In a 160-bit address space, wouldn't that end up potentially storing 2^157 nodes in 000's routing table??

The wording in the quoted block is also very confusing...

"in a subtree" -- in which subtree of the routing table?

"of size atleast k nodes" -- what metric are we using to determine size of the subtree? nodes in this case refers to kademlia nodes or k-buckets or something else?


I understand almost all of the paper, but this portion of section 2.4 has me extremely confused. I don't understand under what conditions a k-bucket should be further split. I've tried doing many google searches but I wasn't able to find anything on this topic.
0

#2 User is offline   fox88 

  • Golden eMule
  • PipPipPipPipPipPipPip
  • Group: Members
  • Posts: 4616
  • Joined: 13-May 07

Posted 27 August 2015 - 07:47 AM

I briefly looked at the paper; and perhaps the answers should be already there.

View Postoffbynull, on 21 August 2015 - 03:00 AM, said:

However, the previous section of the paper seems to state that if a k-bucket already has k elements

The number k is a constant for bucket capacity - that is, maximum. Not the actual number of nodes at any given time.

There is also fixed limit of total number of nodes stored locally; therefore unlimited growth is impossible.
New node can replace one of already stored, bucket could be splitted, or new node might be ignored.

The metric used is XOR; and node ID unambiguously defines it's position in a tree.

This post has been edited by fox88: 27 August 2015 - 07:47 AM

0

#3 User is offline   offbynull 

  • Newbie
  • Pip
  • Group: Members
  • Posts: 2
  • Joined: 20-August 15

Posted 27 August 2015 - 06:45 PM

The "answer" in the paper is a non-answer. For anyone interested, I got a pretty good answer to this question on SO: http://stackoverflow...-routing-table.

Not sure if eMule's Kademlia implementation handles this. The issue is that you need to maintain links to the the k closest node IDs to your own in the network. Otherwise, you run the risk of not being able to find the closest node to some ID.
1

  • Member Options

Page 1 of 1

1 User(s) are reading this topic
0 members, 1 guests, 0 anonymous users