Re: Re: Using the DHT to find download sources

[email protected] wrote:
> 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.

I really like this proposal, it's a lot more elegant than mine. Just a
couple of minor points to add below.

> 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.

The probability of an SHA1 collision is negligible, so I don't think we
need to take any special measures to avoid it.

Metadata can be supported without changing the protocol by incorporating
the metadata into the key. For example, to store a push proxy address,
prepend "PUSH:" to your GUID and hash the result to get the DHT key. To
store a file address, prepend "SHA1:" to the file's SHA1 and hash the
result to get the DHT 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).

Nice - we could even use the distance between the key and the KUID of
the node where we stored the data as a popularity metric.

> 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).

It might be worth returning a security token even if the lookup is for a
GET, because the node performing the lookup can cache the token and use
it in future PUTs. (Incidentally, did we resolve the question of how
long security tokens should be valid?)

> 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".

Can I suggest a slight modification? Instead of trying to work out
whether the ideal location is full, the node should just return a flag
indicating whether the node itself full. If so, the requester should
store the item at the previous node visited. If not, continue the
lookup. This saves DHT nodes from having to monitor each other's fullness.

If you agree with the suggestions above about metadata and security
tokens then I believe the "full" flag in FIND_NODE_RESPONSE is the only
change we need to make to the protocol.

Cheers,
Michael