[p2p-hackers] kademlia bucket spliting

[Gary Jefferson]

I'm having a hard time following one detail in the Kademlia paper (long version, http://citeseer.ist.psu.edu/sex02sex.html) and was hoping someone could clarify.  From section 2.4, we know that when a bucket gets full and a new node can be added to it, we only split the bucket if it contains our own node ID.  Otherwise, we either discard the new node's contact info or replace an old entry with it, depending on whether the LRU entry is still alive or not.  But then we read:
  
  "One complication arises in highly unbalanced trees. Suppose node u joins the system and is the only node whose ID begins 000. Suppose further that the system already has more than k nodes with prefix 001. Every node with prefix 001 would have an empty k-bucket into which u should be inserted, yet u's bucket refresh would only notify k of the nodes. To avoid this problem, 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. Figure 5 illustrates these additional splits. When u refreshes the split buckets, all nodes with prefix 001 will learn about it."
  
  So when do we split a bucket?  From the above, it sounds as if we always split buckets when they get full and new nodes can be added, regardless of whether the bucket contains our own node ID.  But doesn't this mean we have an essentially limitless number of nodes that we can add to our buckets (and a corresponding memory issue as the network gets large)?
  
  I'm sure I'm missing something here, but I just can't make it out.  I'm running into some pathological cases where I can't converge to the correct node unless I do split every bucket...
  
  Thanks,
  Gary 
 

			
---------------------------------
Yahoo! Shopping
 Find Great Deals on Holiday Gifts at Yahoo! Shopping 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://zgp.org/pipermail/p2p-hackers/attachments/20051215/f34f2f1e/attachment.html