Re: Re: Using the DHT to find download sources

Am Dienstag 22 Juli 2008 21:22:01 schrieb pwang708:
> Good point! But I am not really sure if reputation based anti spam
> systems work well for rare files. Any ideas or links?

I don't think it's about detecting rare files via the system. It is about 
detecting the extremely well spread spam files. 

The rare files are the rest which doesn't get detected as spam. 

> A DHT can find rare files efficiently. A DHT search takes several
> hops, say 3 or 4. Then in Gnutella, unless a copy of the file are
> within less number of hops from your machine, you will need more time
> to find it. In addition, if a rare file exists, then a DHT is able to
> find it. With Gnutella, it is expensive to provide such guarantee.
> Note that we are only talking about rare files. Gnutella is very good
> at finding popular files.

What is the load for those 3 or 4 steps? 

Gnutella doesn't try to give the guarantee that it will find every file. But a 
bit of scaling up will make the search mostly global again (most rare files 
are there about two or three times, so missing one doesn't hurt - missing 
most due to spam stopping the search does hurt, though). 

And Gnutella creates extremly low overhead and copes perfectly with the 
average uptime of only 2h. 

For rare files I wonder, though: How does the DHT manage to find them within 3 
or 4 hops? 

From what I understand, a kademlia search jumps from node to node, always 
choosing the one which is closest to the destination (the sha1 of the request 
or similar). 

With 5 million simultaneous users, that kind of "doing the search myself" 
doesn't look faster than the massive (but cheap) parallelism Gnutella offers. 

And even though there's a shortcut mechanism, I remember (hopefully correctly) 
that this will only work for files which are often searched for. 

That means, Kademlia will have to go many hops before it finds a target (about 
O(log(N)) hops, if I remember correctly). 

log(5 mio) is still about 15 (if all reported nodes are still online), while 
Gnutella starts many parallel searches which go only 4 hops. 

Using UDP should speed it up a bit, though. 

I wouldn't doubt, that kademlia is far more efficient in hash searching than 
Gnutella can be, but for keyword based searches I do doubt it (and how do you 
find out before searching that your search will be a rare one?). 

I'm reading a paper on Kademlia right now to find out more: 
- http://www.eurecom.fr/~btroup/BThesis/MasterThesisBrunner.pdf

> > 5) Searching for specific users (which could be used in decentral
> > contact-list functions, for example instant messaging).
>
> Good idea!

A very old one, it just never got implemented, because Gnutella couldn't do 
hash-searches very well :) 

> > Or rather something like avoiding overloading clients?
>
> Write quota. A user can only publish a certain number of data items,
> to each DHT node. Yes, avoiding overloading clients...

That means, the network lets me publish only a certain amount of files? 
Or only a certain amount of files for the same keywords? 

Arne

-- Weblog: http://blog.draketo.de
-- Infinite Hands: http://infinite-hands.draketo.de - singing a part of the 
history of free software. 
-- Ein Würfel System: http://1w6.org - einfach saubere (Rollenspiel-) Regeln

-- PGP/GnuPG: http://draketo.de/inhalt/ich/pubkey.txt


[Non-text portions of this message have been removed]