Re: Using the DHT to find download sources

--- In [email protected], Michael Rogers <m.rogers@...> wrote:
>
> On Jul 23 2008, pwang708 wrote:
> >For example, say the published DHT value includes the full file name,
> >then you search the DHT with key=sha1(debian), when you find the
> >replica roots, send a findValue including the list of keywords, in
> >this case "debian", "lenny", and "iso". The replica roots search their
> >database and find the DHT value with filename="debian lenny iso"
> >matching all the keywords, then return the value. Kad does something
> >similar. Arne posted a link which explains a lot about Kad. 
> 
> That works if I search for "debian" first, but what happens if I
search for 
> "iso" first? The values will be spread across a large number of
nodes to 
> avoid hotspots - contacting all of them will be expensive.
> 
> Perhaps we could pause after retrieving the first few results,
calculate 
> the distance between the ideal location and the location where we
found the 
> results, and use that to estimate the popularity of the keyword (these 
> estimates can be cached). Do the same for each keyword in the query
(this 
> can be done in parallel). Then send the full query to the nodes listed 
> under the least popular keyword.
> 

So we come back to the question of how to figure out keywords'
popularity. If we don't find a good solution, we will have a big hot
spot problem. Or we publish to non-full nodes closest to the target
key. Then we may run into the case Michael just described and searches
become less efficient. :-( 


> By the way, the Kad paper is great! Sometimes I think I should give up 
> computer science and devote my life to producing a race of
super-geeks by 
> crossbreeding Daniel Stutzbach and Dan Kaminsky. :)
> 

:-)

> >Not really a important operation, since DHT values expire. But it
> >could be useful if we put a quota on each client. I think I should
> >have used the word "modify" :-) E.g., only I can modify my push proxy
> >information published in DHT...  
> 
> Hmm, perhaps we could use the hash of a public key as the node's
long-term 
> identity. The push proxy addresses (or any other data the node wants to 
> publish) would be signed (and dated, to prevent replays) with the 
> corresponding private key, and DHT nodes would verify the signature
before 
> storing it. But public key crypto is expensive - this might expose DHT 
> nodes to a CPU DoS attack.
> 

We can use signatures. Please take a look at Sean Rhea's openDHT paper
(OpenDHT: a public DHT service and its uses). Excellent paper. I like
 its put/get interface. It also has a good "STORAGE ALLOCATION"
scheme. I listed "a richer API" as one of DHT requirements. That is
inspired by this paper.  

While, public key crypto is expensive, but not that expensive. We can
also try to find a signature scheme which has small verification time,
since DHT nodes (replica roots) only verify signatures. Or we can use
things like crypto puzzles and replica roots can change the complexity
based on their load... We will need to discuss about an attack model
soon.  

Best,
Peng