[p2p-hackers] DHTs in highly-transient networks

[Bryan Turner]

	The DHTs that I've studied behave well in high-churn environments.
The problem is network migration events; large swings of population in a
short time.  Chord is the worst for this, as its rigid structure quickly
buckles when you lose a large chunk of the network.  Kademlia survives
pretty well; maintaining connections with long-lived nodes is a definite
win, as is maintaining connectivity to hubs/supernodes.

	All of them get screwed when large populations join.  The network
turns to chaos for a while until things settle down.  Kademlia is better off
(lookups continue to work).  The largest problem is the sudden lack of
bandwidth due to all the key-transfers between the nodes.

	In my implementations I had to add a 'slop' factor that was larger
than my largest expected node-join event.  During a lookup, if the
'ultimate' node didn't have the data, he passed the request through the
oldest couple of nodes in the slop region.  This allowed one last chance to
find the right owner.  It worked well in practice, but I still believe
there's a better way.

--Bryan
bryan.turner at pobox.com

-----Original Message-----
From: p2p-hackers-bounces at zgp.org [mailto:p2p-hackers-bounces at zgp.org] On
Behalf Of Sean Rhea
Sent: Thursday, December 01, 2005 6:02 PM
To: Peer-to-peer development.
Subject: Re: [p2p-hackers] DHTs in highly-transient networks

On Dec 1, 2005, at 5:53 PM, Michael Rogers wrote:
> To what extent does this depend on the distribution of session times 
> as well as the mean? Kademlia assumes that old nodes will outlive new 
> nodes, and Daniel's paper shows that Gnutella contains an emergent 
> core of long-lived nodes - how well do Bamboo and Chord survive under 
> non-uniform churn?

We used exponentially-distributed node lifetimes, so old nodes do not
generally outlive new ones.  However, I _think_ that choice only makes the
problem harder, though.  In particular, I would suspect that Bamboo/Chord
would do just as well if old nodes lived longer than new ones, and possibly
better.  They won't take advantage of it like Kademlia does, but it
shouldn't hurt them either.  (At least that's my guess; I don't have data to
prove it.)

Sean
-- 
           When I see the price that you pay / I don't wanna grow up
                                  -- Tom Waits