Using the DHT to find download sources

Hi all,

I have a suggestion for using the DHT to find download sources. Since it
works differently to a standard Kademlia lookup I thought I'd ask for
comments here first, and if it sounds like a good idea maybe we could
incorporate it into a future version of the Gnutella/Kademlia specs.

The obvious approach would be to store your address in the DHT under the
hash of every file you're sharing, and when you want to download a file,
get the list of addresses stored under its hash. But there are a couple
of problems with that. First, some files are vastly more popular than
others, so the DHT nodes responsible for those keys will be overloaded.
Second, it's a waste of bandwidth to use the DHT for popular files
because we can easily find sources with a short-range Gnutella search.
So we'd like to store only the rare files in the DHT. The problem is,
how do we tell which files are rare?

My suggestion is to use the DHT lookup process to estimate popularity.
This requires two new messages, PUT_ADDRESS and GET_ADDRESS. Both are
similar to FIND_NODE: they return a list of DHT nodes close to the
specified key. But in addition they return a list of nodes (not
necessarily DHT nodes) that have recently sent PUT_ADDRESS for the
specified key. The addresses of nodes that send GET_ADDRESS are not
stored or returned - that's the only difference between PUT_ADDRESS and
GET_ADDRESS.

A node performing a PUT_ADDRESS or GET_ADDRESS lookup can estimate the
popularity of the key from the number of addresses returned; if a
certain number of addresses are found before the lookup reaches the
root, the lookup is terminated. This prevents the roots of popular keys
from being overloaded.

Note that there's no attempt to ensure that the node performing the
lookup gets all the addresses associated with the key, or that two
lookups return the same set of addresses. Quite the opposite. For an
unpopular key, the lookup might go all the way to the root and find all
the addresses, but for a popular key that's exactly what we want to avoid.

How long should DHT nodes cache the addresses of PUT_ADDRESS senders? We
could use a short timeout (say fifteen minutes), with sources
republishing their addresses periodically if they're still alive. But
that would use a lot of bandwidth. If we assume that node lifetime
follows a power law distribution [1,2] then a node's lifetime so far is
likely to be proportional to its total lifetime. So perhaps the timeout
should be based on the sender's lifetime so far. This translates to an
exponentially increasing timeout: 15 minutes the first time the address
is published, then 30, then 60, etc.

Any thoughts?

Cheers,
Michael

[1] http://2003.iwcw.org/papers/bustamante.pdf
[2] http://saikat.guha.cc/pub/iptps06-skype.pdf