Re: Using the DHT to find download sources

--- In [email protected], Arne Babenhauserheide <arne_bab@...>
wrote:
>
> Am Donnerstag 24 Juli 2008 20:40:49 schrieb pwang708:
> > In Query Routing Protocol nodes push their keyword list one or two
> > hops away from themselves, so that "a query reaches only hosts which
> > might have results for it". Theoretically, nodes can also push their
> > hash lists out like they push out their keyword lists. So I guess by
> > "breaks" you meant a incrementally deployment problem. Or
something else?
> 
> I mean that the way how Query routing tables are constructed works
very well 
> with keywords, which are duplicated in many messages and tend to
cluster on 
> similar files = for a user, but doesn't work very well on sha1
hashes, which 
> are random by design. 
> 
> A user will have a relatively low number of keywords (if he shares
mostly a 
> certain type of files, for example all bloodspell movies), but he
will have 
> all kinds of hashes, so keywords cluster on users, but hashes are just 
> randomly created. 
> If you take the above example, you could easily compile a list of
keywords. 
> 
> And the Query routing table uses as principle that people only get
messages 
> which might score a hit. 
> 
...
> 
> And for keyword searches, you can now check the queries keywords
against all 
> keywords of all files of the user. 
> If all Keywords of the Query are somewhere in the share of the user,
his 
> ultrapeer sends him the query. 
> 
> For sha1 searches, you'd have to increase the size of the Query routing 
> tables, since they aren't clustered as strongly as keywords (almost
every 
> file would have its own sha1_part entry). 
> 
> Putting them into Query routing tables would still work, but less
efficiently 
> than keywords. 
> 
> LimeWire decided not to put sha1 hashes (or parts of them) into the
query 
> routing tables, so routing by sha1 hash doesn't work in Gnutella. 
> 
> -> Does a client put sha1 hashes into QRTs, and how well does it work? 
> 

So the query routing table protocol will be inefficient because we
cannot cluster hashes, i.e., pushing hashes out for two hops is
expensive. To make things clear, I did some calculation. If we apply
query routing table protocol to hashes, then an UP needs to spend in
the order of 1~10 KB per second. (A hash is 20 bytes long. Assuming
every client shares 1000 files, a leaf connect to 5 UPs, each UP has
30 leaves, 0.5M UPs in the network, and 20M session are launched per
day.) We can do some optimization and bring the cost down below 1 KB
per second, or even less. Now the question is "does it worth it?" 

I was also told that hash search is "exact file match". So the chance
of a hit is lower than keyword search. Hence searches need to travel
much more hops. Note that the hops are broadcast hops, as a result the
cost grow exponentially. Hence hash searches are expensive. Query
routing table protocol reduces the number of hops by 2. But hash
searches may still be expensive and Query routing table protocol has a
non-trivial cost itself. 

In summary, hash searches in Gnutella is most likely expensive unless
we can make hits happen within couple of hops. This "unless..." part
is an interesting topic to think about. :-) Peer group may help...