Subject: [p2p-sip] slides for P2P-SIP Ad Hoc

From: buford at research.panasonic.com ([email-masked])
Date: Wed Nov 9 19:42:38 2005

Here are the slides on P2P overlays for the ad hoc session on Friday

http://www.cs.uml.edu/~buford/irtf-p2prg/p2psip/JBuford-IETF-P2PSIP-Overlay-Systems-v3.pdf

John

---

From: afisk at speedymail.org (Adam Fisk)
Date: Thu Nov 10 14:15:22 2005

Hi John-

The slides look great.  I just wanted to point out that both Gnutella 
and Kazaa's search algorithms are more accurately described as random 
walks than as flooding.  Kazaa has used a massive indexing and random 
walk approach for many years, and Gnutella clients have used a similar 
approach for at about the last 3 years.   Gnutella basically uses bloom 
filters to index all data within 2 hops, and then dynamically queries 
supernodes depending on how many results are coming back over time.  In 
many cases this leads to queries not going beyond the nearest 
supernode.  Kazaa uses something similar, although no one outside of 
their organization knows the details. 

"Random walk" does not quite capture it either, but it's closer than 
"flooding".  Thes algorithms are actually *very* efficient, producing 
light load and broad network reach, although they cannot scale as well 
as DHTs, clearly.

That's not particularly relevant to the purposes of this group, but more 
for the sake of everyone's general knowledge.

On the DHT side, it may be worth talking to Bryan Turner from the p2p 
hackers group, as he's by far the most knowledgeable person on the 
various DHT implementations I've come across.  Are you on this list, 
Bryan?  He's implemented many of them, and he's a strong advocate of 
"The Continuous Discrete Approach".  The DHT world evolves very quickly, 
and things like Chord and CAN are certainly not the state of the art.

I'm ccing Bryan on this.  I don't know you, Bryan, but your posts on p2p 
hackers make your depth of knowledge in this area clear.

-Adam

[email-masked] wrote:

>_______________________________________________
>p2p-sip mailing list
>[email-masked]
>http://lists.cs.columbia.edu/mailman/listinfo/p2p-sip
>
>  
>

---

From: buford at research.panasonic.com (John Buford)
Date: Thu Nov 10 15:50:56 2005

Hi Adam,
Thanks for the comments.

Looking at the wiki for the Gnutella Developers Forum in the
section "Querying the Network"

"A servent SHOULD forward incoming Query messages to all of its directly
connected servents, except the one that delivered the incoming Query.
Servents using Flow control or Ultrapeers (sections 3.1 and 3.2) will not
always forward every Query over every connection. "  There is also a TTL on
the packet which is decremented.

This sounds like flooding not random walk.

According to the GDF wiki, during bootstrapping, if a node can't
connect using entries in the host cache,
it can randomly select a GWebCache to populate its host cache.

Regarding Kazaa, the protocol is proprietary.  One research group analyzed
pollution in Kazaa (Ross et al. "Pollution in P2P File Sharing Systems")
and built a crawler to crawl the Kazaa network.
>From their paper:
"When a user wants to find files, the user?s ON sends
a query with keywords over the TCP connection to its
SN. For each match in its local index, the SN returns the
metadata and IP addresses corresponding to the match.
When a SN receives a query, it may flood the query
over the overlay network to one or more of the SNs
to which it is connected. A given query will in general
visit a small subset of the SNs, and hence will obtain
the metadata information of a small subset of all the ONs."

More recently this same research group has reported on a detailed
analysis of the Kazaa overlay in the paper
J. Liang, R. Kumar, and K.W. Ross, The Kazaa Overlay: A Measurement Study,
Computer Networks (Special Issue on Overlays), to appear.

In this paper they describe, among other things, "connection shuffling"
which both SNs and ONs use.  It appears that this connection shuffling
allows peers to reach other parts of the overlay over time, and may be
related to work load re-distribution.

So it appears that within a given set of SN-SN and SN-ON connections
Kazaa uses flooding, but these connections change over time.

Yes, CAN and Chord are not "state of the art" depending on what you
are looking for in an overlay.

Again, thanks for the comments.

John

-----Original Message-----
From: [email-masked]
[mailto:[email-masked]]On Behalf Of Adam Fisk
Sent: Thursday, November 10, 2005 2:14 PM
To: [email-masked]; [email-masked]
Subject: Re: [p2p-sip] slides for P2P-SIP Ad Hoc

Hi John-

-Adam

---

From: brturn at cisco.com (Bryan Turner (brturn))
Date: Sat Nov 12 01:51:17 2005

Hello,

	Thanks for inviting me to the discussion, although I'm a bit lost on
the context (not a member of the p2p-sip list).

	As Adam has mentioned I've implemented several of the major DHTs
(Chord, Kademlia, Continuous-Discrete) and researched the rest (Pastry, CAN,
etc).  I'm happy to transmit my experiences on this topic.

	I am not up to speed on the unstructured filesharing systems
(Gnutella, Kazaa, etc).  So Adam's input on that topic is new to me. :)

Let me know if I can help,
--Bryan
[email-masked]

-----Original Message-----
From: Adam Fisk [mailto:[email-masked]] 
Sent: Thursday, November 10, 2005 2:14 PM
To: [email-masked]; [email-masked]
Subject: Re: [p2p-sip] slides for P2P-SIP Ad Hoc

Hi John-

The slides look great.  I just wanted to point out that both Gnutella and
Kazaa's search algorithms are more accurately described as random walks than
as flooding.  Kazaa has used a massive indexing and random walk approach for
many years, and Gnutella clients have used a similar 
approach for at about the last 3 years.   Gnutella basically uses bloom 
filters to index all data within 2 hops, and then dynamically queries
supernodes depending on how many results are coming back over time.  In many
cases this leads to queries not going beyond the nearest supernode.  Kazaa
uses something similar, although no one outside of their organization knows
the details. 

"Random walk" does not quite capture it either, but it's closer than
"flooding".  Thes algorithms are actually *very* efficient, producing light
load and broad network reach, although they cannot scale as well as DHTs,
clearly.

That's not particularly relevant to the purposes of this group, but more for
the sake of everyone's general knowledge.

On the DHT side, it may be worth talking to Bryan Turner from the p2p
hackers group, as he's by far the most knowledgeable person on the various
DHT implementations I've come across.  Are you on this list, Bryan?  He's
implemented many of them, and he's a strong advocate of "The Continuous
Discrete Approach".  The DHT world evolves very quickly, and things like
Chord and CAN are certainly not the state of the art.

-Adam