Re: Re: Using the DHT to find download sources

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. 

Here's a code example (Python). 

########## CODE EXAMPLE  (skip if you want to) ########## 

------ Keywords for a Bloodspell dedicated share ------
from os import listdir

# First get the list of files
files = listdir(".") #: The list of files

#: A list of keywords. 
keywords = files

# Now split each file into keywords. 
#: Characters by which the filenames get splitt - short version for bloodspell
split_chars = ["_", "."]
#: A helper list for splitting keywords
tmp_keywords = []

for i in split_chars: 
   # Create the a list of keyword lists. 
   tmp_keywords = [word.split(i) for word in keywords]
   # Empty the keywords
   keywords = []
   # And fill them with the new smaller keywords. 
   for wordlist in tmp_keywords: 
       keywords += wordlist

# We only want to see one instance of each keyword, 
# So we just turn the keyword list into a set. 
keywords = set(keywords)
------ /Keywords for a Bloodspell dedicated share ------

output: 
>>> print keywords: 
set(['en', 'avi', 'BS', '3', '1', 'Teaser', '2', '5', '4', '7', '6', '9', '8', 'Episode', 'de', 'Large', 'MakingOf', 'Trailer', '11', '10', '13', '12', '14', 'BloodSpell', 'srt', 'Makingof'])
>>> len(keywords)
26

That's 26 from millions of possible keywords and from 31 files. 

But more importantly: The keywords excepting the numbers are what users search 
for, and there are only 12 of them. 

Now the same for the first letters of sha1 hashes: 
------ Cathegorize a Bloodspell dedicated share by parts of sha1 hashes ------
from os import listdir

# First get the base32 sha1 for Python from the magma module
# -> http://pypi.python.org/pypi/magma/
from sha1_gnutella import sha1_gnutella

files = listdir(".")
hashes = [sha1_gnutella(file) for file in files]

hash_parts = [hash[0:2] for hash in hashes]

# Weed out multiple entries. 
hash_parts = set(hash_parts)
------ /Cathegorize a Bloodspell dedicated share by parts of hashes ------

>>> len(set(hashparts))
29 

for 31 files 
>>> len(files)
31

from max 1024 seperate entries. 

########## / CODE EXAMPLE ########## 

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? 

> We don't want the DHT to handle popular keywords, right? Even for rare
> keywords, we are still debating. :-)

:) 

A question is still unanswered: How can you avoid sending out DHT queries for 
popular queries? 

Ideas: 
 * Check the accumulated QRT of your UP (it needs to pass that on, then). If 
it contains (all) your keywords, they are too common for your search. Danger: 
This includes keywords for your own files. 

* Don't send DHT keyword queries at all, or only after a Gnutella query didn't 
bring sufficient results. 

Best wishes, 
Arne

PS: It's great to discuss network structure and implementation in here, again! 

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