Re: Using the DHT to find download sources

--- In [email protected], Arne Babenhauserheide <arne_bab@...>
wrote:
>
> 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. 
> 

What I meant was the anti-spam system may not stop spams on rare files. 

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

This thesis is very helpful for understanding the Kad network which I
think is the most active kademlia based DHT network. 

Daniel Stutzbach and Reza Rejaie
(http://www.cs.uoregon.edu/~reza/PUB/infocom06-kad.pdf) estimated KAD
had about 1 million "DHT" nodes and the number of hops was 2.7. (Some
other papers reported more nodes...) And there are several million
firewalled users using the DHT service provided by the 1 million DHT
nodes.  

Mojito DHT implemented by Limewire has several hundred thousand "DHT"
nodes. A client joins Mojito if it satisfies several requirements,
e.g. not firewalled (of course), needs to be online for at lease one
hour after it started. This is based on the observation that a node
stays online for long time will stay online longer, with high
probability. For example, node A has been online for one hour, node B
has been online for 5 minutes. Most likely node B dies first. Because
these requirements, Mojito DHT network size is smaller, but the
network is healthier, e.g., less number of dead contacts in nodes'
routing table. 

Because mojito's size is smaller than Kad, and both are based on
Kademlia, so I expect the hops should be smaller, when they use the
same parameters. 


I agree with "how do you find out before searching that your search
will be a rare one?". This is a problem we need to solve. :)

I am not sure I understand this part: "the kademlia is far more
efficient in hash searching than Gnutella can be, but for keyword
based searches I do doubt it." If a hash is popular or close to you in
Gnutella, then searching it in Gnutella should be fast, right? On the
other hand, if a keyword is not popular or far away from you, then
searching it in Gnutella should be slow. To me, the choice between DHT
and Gnutella is more about data popularity. Am I missing something here? 


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

A certain amount for the same keywords. 

Best,
Peng

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