Re: Using the DHT to find download sources

[Warning: long message ahead]

Quoting Michael Rogers <[email protected]> from ml.gnutella.dev-forum:
: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.
:
:Any thoughts?

I'm not sure we have to introduce these new non-standard calls in
Kademlia.

My preference goes strongly for a sloppy DHT model, and it is very easy
to turn Kademlia into a sloppy model that I believe is suitable for what
we are trying to achieve.

The original Kademlia specs are aimed at providing a true Distributed Hash
Table (DHT) layer. Like a hash table (HT), the DHT will offer PUT(key, value)
and GET(key) features.  But the Kademlia DHT, just like the HT, does not
make provision for multiple values under the same key.  That is, PUT will
override the value already stored under the key.

A natural usage of a DHT in Gnutella would be to have keys be the SHA1
of files (or the SHA1 of your binary GUID to store push-proxies) and the
value you put is simply your IP:port.  By issuing PUT(key, IP:port),
you tell the DHT that you supply "key" at IP:port.  If key is a SHA1,
it means you offer the file, if key is the SHA1 of your GUID, it means
the IP:port is the address of your push-proxy.

Therefore the Gnutella DHT is not meant to store a single value at a key
but an array of IP:port instead.

Note that there is always the remote possibility of a collision, whereby
the SHA1 of your GUID would match the SHA1 of a file, and therefore
push-proxy locations and IP:port of hosts offering the SHA1 would mix.
One way to overcome this is to attach a small set of meta-data to the value.
For instance, to publish yourself as the location of a file, you would
issue PUT(key, 'H', IP:port) to signal the value is a host and therefore
the key the SHA1 of a file, whereas to publish a push-proxy you would say
PUT(key, 'P', IP:port) to signal the value is actually that of a push-proxy.

Then naturally, the retrieval would have to specify what you really want:
a GET(key, 'H') would return ONLY a vector of IP:port that were stored via
a PUT(key, 'H') and not those stored under the same key but which were the
result of a PUT(key, 'P').

How do we then add sloppyness to this model to make a Distributed Sloppy
Hash Table (DSHT)? Well, we have to consider that it does not really matter
to have more than a reasonable amount of IP:port stored at a given key for
a given node.  Let's say each node can store at most 5 IP:port for a given
key and a given "type", 'H' or 'P'.  What it will do is that the next time
a PUT(key, 'H', IP:port) comes and it already has 5 IP:port stored, it will
reject the PUT with error code "Full".

[The maximum amount of IP:port entries we can allow to store under a key can
of course be debated.  The proposed 5 here could be too small.]

The publisher will then attempt to repeat the same operation on the node
that was just before in the lookup path (likely to always be the same for
every lookup in the Kademlia space since the XOR metric is unidirectional,
that is there is only a single point "p" in the space that matches d(target,
p) = v, for every v).  If the other host, which will apply the same logic,
also returns "Full" then you start to get an indication that maybe this
key is "popular".  You can attempt to publish the value in the host that
precedes this second one in the lookup path and stop if it also returns
"Full".

So the "sloppyness" is just there to indicate that the DSHT will not
attempt to remember every value for a key, but will only accept to store
some resonable amount.  The "sloppyness" also provides a natural cache
for popular keys, since the getters will converge to the target node in
the same lookup path and therefore will hit the early "spill-over" nodes
before they hit the ideal target, thereby offloading the ideal target
from some load.  And the getter will in turn store the value to the first
node in its lookup path that did not return the value, according to the
original Kademlia specs, which in turns spills the value to an earlier
circle of nodes in front of the ideal target, shielding it further from
some lookup traffic for other GET(key...).

Now back to your original problem: how do we determine that a key is
popular to avoid publishing it too often? When you attempt to store your
value with PUT(key, 'H', IP:port) and get a "Full" indication, you do know
that there is a small amount of popularity.  When you attempt to store on
the next-best closer node (the one before the ideal target in the lookup
path) and you get "Full" again, that suspected popularity starts to become
even more likely.  When the third node also returns "Full", you know and
can stop publishing that key for some time (more than 24 hours, naturally).

One possible shortcoming in this scheme is that we will always attempt to
issue the first PUT(key, 'H', IP:port) to the ideal target we could find,
because nodes that want to PUT issue FIND_NODE RPCs, and it is not possible
to know whether these FIND_NODE calls are for bucket refreshes or for locating
a node for the purpose of issuing a PUT.

We could therefore slightly modify the FIND_NODE calls to add an argument
to the mandatory KUID: a flag indicating whether we're locating for PUT
purposes or not, and which type of data we're looking at ('H' or 'P' for
instance).  Only when locating for PUT purposes would the FIND_NODE
return a meaningful Security Token in the reply (by specifying the length
of the token to be 0, we can avoid sending anything back in the current
LimeWire published message architecture).

What does this buy us? It gives a node the opportunity to filter-out the
ideal target for a PUT if it is itself storing data for that key and it is
also "Full" already.  It knows that the ideal target is also "Full" because
it gets periodic republishing from the ideal target and it can see how many
items that node holds, and therefore can tell whether it is also "Full".

[It is necessary to include the 'H' or 'P' indication in our modified
FIND_NODE call because it is possible a host be "Full" for 'H' values
but has nothing for 'P' values, under the same key]

If the ideal target is not returned during FIND_NODE calls meant to identify
the ideal target, chances are the node attempting the put will not find it
out (provided he is not in the closest sub-tree of the ideal target) and
therefore we can avoid some extra load being directed to the ideal target
for that key.

By making Kademlis a DSHT instead of a DHT, I think we can achieve the
important goals: identify that a key is popular and avoid extra publishing
traffic, and ensure that the ideal target for a popular key will not get
overloaded with PUT and GET requests for that key.  Making it a DSHT is a
simple matter of slightly adjusting the FIND_NODE RPC by adding an extra
parameter and creating the logic necessary to identify the "Full" condition
of neighbours for a key of a given type.  Finally, we also need to slightly
adapt the logic of the PUT to handle the "Full" condition error properly.

I view these as really minor adjustements that do not shake the fundamentals
of the Kademlia design, whilst providing a good level of load balancing
and auto-limitating of the amount of values that can get published under
a given key, which in turn limits the overall traffic.

Raphael