[p2p-hackers] Paradigma Question: DHT's or Small World?

[Serguei Osokine]

On Thursday, February 03, 2005 Rita H. Wouhaybi wrote:
> Note that super-peers in Kazaa and Gnutella do actually help
> the network become more like a small-world.

	Not necessarily. Or at least, to a much smaller extent than
the intuitive thinking would suggest. Superpeers do make the network
smaller in terms of the node numbers, but at the same time they 
increase the traffic on the intra-ultrapeer links in exactly the
same proportion, making it more difficult to route anything to the
remote nodes. So the actual query reach improvement (the degree of
'small-worldness', so to speak) is improved only due to the better
than average super-peer bandwidth:

http://www.grouter.net/gnutella/search.htm#PlainSuperpeerNetwork
http://www.grouter.net/gnutella/search.htm#Eq25

	Basically, if you cannot reach all hosts in a 'flat' network 
(without super-peers), chances are pretty high that the introduction
of super-peers won't change this situation unless the original flat
network was already pretty close to being a 'small world' (fully
reachable) one. 

	The search reach in the super-peered nets like Kazaa really 
is better, but it comes from first, higher than average superpeer 
bandwidth, and second, from the proactive index replication that
naturally happens when a leaf connects to several superpeers at
once (three or so in Kazaa case, I believe). This one tends to be 
viewed as just something done to improve a connection reliability
through redundancy, whereas in fact it also improves the query reach 
in direct proportion to the number of redundant links:

http://www.grouter.net/gnutella/search.htm#RedundantSuperpeerClusters

	I think this effect was first noted by the Stanford P2P 
research group, which named it 'k-redundancy':
 
http://www-db.stanford.edu/~byang/pubs/superpeer.pdf

	Best wishes -
	S.Osokine.
	3 Feb 2005.


-----Original Message-----
From: p2p-hackers-bounces at zgp.org [mailto:p2p-hackers-bounces at zgp.org]On
Behalf Of Rita H. Wouhaybi
Sent: Thursday, February 03, 2005 11:00 AM
To: p2p-hackers at zgp.org; aloeser at cs.tu-berlin.de
Subject: Re:[p2p-hackers] Paradigma Question: DHT's or Small World? 


Alexander Löser wrote:
> Hey all,
> structured overlay networks  based on DHT's, such as Pastry and  Chord
> among others, have been investigated in the past to construct scalable
> and performance orientated peer-to-peer networks.  However, unstructured
> networks, such as Gnutella or Kazaa,  are still widely used among the
> file sharing community. Recently researchers proposed extensions to
> unstructured networks  networks based on the small world idea: peers
> dynamically create shortcuts to other peers based on their interests.
> Over a while peers with the same interests became direct neighbors
> through its shortcuts and build interest based clusters.   Hence peers
> no longer flood messages but partly route it's queries via a interested
> based/semantic  overlay.  Examples are described in [1] [2] among
> others.
> 
> Comparing small world and DHT  approaches is a difficult task, since
> simulations usually differ in scenarios, data sets or simulation
> methodology.    I'm interested in scenarios and arguments PRO small
> world overlays for unstructured networks. Does anybody now actual
> theoretic or practical work that compares both approaches in different
> scenarios (high churn, no super peers, key word based search, meta data
> based search)?  Which scenarios or arguments support small world
> approaches for unstructured networks?
> 
> Alex
> 
> 
> 
> 
> [1] Gia - Making Gnutella like P2P Systems Scalable
> http://berkeley.intel-research.net/sylvia/1103-chawathe.pdf
>
http://seattle.intel-research.net/people/yatin/publications/talks/sigcomm2003
-gia.ppt
> 
> [2]  Efficient Content Location Using Interest Based Locality in
> Peer-to-Peer Systems
> http://www.ieee-infocom.org/2003/papers/53_01.PDF
> --
> ___________________________________________________________
> 
>   Alexander Löser
>   Technische Universitaet Berlin
>   hp: http://cis.cs.tu-berlin.de/~aloeser/
>   office: +49- 30-314-25551
>   fax   : +49- 30-314-21601
> ___________________________________________________________
> 
> 
> _______________________________________________
> p2p-hackers mailing list
> p2p-hackers at zgp.org
> http://zgp.org/mailman/listinfo/p2p-hackers

Interesting discussion Alex.

>From the practical and system challenges that faced researchers working on
DHTs (long time for the network to become stable, updates and maintenance for
nodes join and leave, high cost of messaging when adding an object to the
network, ..), it has become the norm to think about the application when
trying to decide to use structured (DHTs) or unstructured (gnutella-like) p2p
topologies. That is probably one of the reasons why people did not compare
both structures in an analysis similar to what you are asking for. Thus,
small world and power-law have emerged to bridge the gap between a total
random network and a "rigid" DHT. Note that super-peers in Kazaa and Gnutella
do actually help the network become more like a small-world. We also have
worked in this area and created a power-law distribution P2P network that
might interest you: 
- Rita H. Wouhaybi, and Andrew T. Campbell, "Phenix: Supporting Resilient
Low-Diameter Peer-to-Peer Topologies", IEEE INFOCOM'2004, Hong Kong, China,
March 7-11, 2004. 


Rita H. Wouhaybi
rita at comet.columbia.edu
http://comet.columbia.edu/~rita/