Re: Re: Using the DHT to find download sources

Am Mittwoch 23 Juli 2008 16:48:03 schrieb pwang708:
> What I meant was the anti-spam system may not stop spams on rare files.

From my experience, rare files aren't really being spammed (except with the 
same default spam replies, and those are common, so they'd be recognized). 

Spam, in the way it is used today, is a means to make it harder for people to 
reach some popular files for whoose "protection" the spammers get paid. 

That rare files aren't in our search horizon anymore due to spam is just a 
byproduct. 

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

From what I see, these 2.7 hops don't mean 2.7 requests, but rather a multiple 
of that due to parallel requests (and 2.7 is the theoretical value). 

Without parallelism, their resulst show about 3.2 hops (which is still very 
good). 

That's a mean value, so it would be interesting to have it split by popularity 
of the hash. 


For example searching for "mp3" on Gnutella has about 2 hops and a parallelism 
of 1: The leaf contacts only one of its UPs and the UP just replies with the 
results of its other leaves, and stops after that, since it got a sufficient 
number of results. 

(I just began doubting the efficiency of Gnutella, until I began actually 
calculating the numbers :) ). 

A rare search will have 4 to 5 hops, at the moment (l=leaf, U = UP, x/y = 
amount of nodes contacted via QRP. Should be far smaller than 32 for rare 
searches) 
l - 5* U - 5*32* U - 5*32*32* U - 5*32*32*x* U - 5*32*32*x*y* l

And increasing the outdegree to 128 nodes per UP would remove the necessity to 
store the third step (128^3 = 2097152 - that 5 times for each leaf), so the 
Gnutella design can reach. 

l - 5* U - 5*128*x* U - 5*128*x* U - 5*128*y* l

with x,y something between 1 and 128 (QRTs only travel a few hops and provide 
a keyword structured network). 

Then a rare search (with only few results in the network, so it would reach 
every node which has files which together include all keywords from the 
query) would have about 4 hops. 

And my observations of Phex show that it can take 99 UP-to-UP connections 
without causing much load: 
http://wiki.phex.org/Phex_Performance

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

Maybe it would be possible to always do a Gnutella search first, and if that 
generates less than 300 results, fire up a Kad search afterwards. 

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

Yes: 

Gnutella doesn't do hash based searching at all, because has-based searching 
breaks the Query Routing Protocol, which makes sure that a query reaches only 
hosts which might have results for it. 

I wrote a (nontechnical) description of it a while ago: 

------ Query Routing Tables ------
While with Ultrapeers not everyone needs to participate in sending questions 
to others, and people can specialize in sharing their information instead, 
the Ultrapeers would still send every question to everyone, without ever 
taking into account if that UP even has leaves, who have the files. This 
sounds normal, for how can an Ultrapeer know which files the other Ultrapeers 
have? The answer comes, again, from real life. A normal person knows her 
friends, and knows who of them might know the answer to a specific question, 
and who most surely will not. In Real Life this is mostly done through 
friendly chatting. 

Now, computers normally don't chat idly, so they don't exchange this 
information by the way. Thus the Query Routing Protocol was developed. There 
each Leaf tells its Ultrapeers which files it has, but instead of taking the 
names, which would consume too much space, each word which is part of the 
name of a file is saved as numbers (these are computers after all). You can 
imagine this process like a game of dumping ships (the numbers form the board 
with two coordinates). An Ultrapeer doesn't send all questions to a leaf, but 
only those which it might be able to answer (which hit a ship), and so Leafs 
get far less needless calls. 

When this takes so much pressure off the leaves, why not extend it? Exactly 
that was done. Now all Ultrapeers send their boards to their direct 
neighbors. They send only those searches, which have one more step to go, to 
other Ultrapeers on whose board they score a hit. That means, the last two 
steps of a search will only be taken when there is a chance that they give 
results. You can see quite simply why this heavily reduces the bandwidth 
usage: imagine a tree, a normal tree, not one of those mathematical 
constructs. If you try to count the leaves, you have almost no chance. But if 
you take the leaves away and count only the branches, you have far less work 
to do. If you now take away all those tiny branches, you can really begin to 
count them. QRP doesn't take all leaves and all tiny branches away, but it 
removes those of them who couldn't give you an answer. Since every part 
through which a question has to travel consumes bandwidth, and there are far 
more leaves than branches, taking away, in many cases, many of the last two 
steps (that means many of the leaves and the tiny branches) reduces the 
number of questions the computers have to send on (there are far more leaves, 
than branches). The example doesn't work for all of Gnutella, but here it 
fits nicely. The people of LimeWire talk about 70-80% savings alone through 
this.
------ /Query Routing Tables ------
- source: http://gnufu.net - Gnutella for Users

Which just got me an idea: Would it be possible to create a Kademlia built on 
Query routing tables instead of node hashes? 
Keywords searches would be transformed to QRTs and the metric would be the 
difference between the node QRT and the (node QRT combined with the keyword). 

This could be used to retrieve hosts which could have the file, which would 
then be queried directly. 

One possible problem I spot is that calculating the metric might be too 
expensive. 

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

Ouch. What about people searching for "sex"? 

Who can put the results in there? 

I can already see sex site advertisers fighting for the space there. 

(In Gnutella you just get the results from your nearest neighbors, so by 
grouping with friends you'll mostly get their results)

Best wishes, 
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]