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

From: buford at research.panasonic.com ([email-masked])
Date: Sun Nov 13 18:05:06 2005

Hi Adam,
Thanks for the pointers for correct documentation on Gnutella,
I'll take a look at them when I get back.

Some other reasons why Chord is talked about
(and I am not advocating Chord for P2P-SIP) are that
its protocol is public and there is some published
work that shows guaranteed query response for
high levels of churn of peers.  

Deterministic behavior seems important for P2P SIP.

Best,
John

Content-Type: multipart/alternative; 
	boundary="----=_Part_1514_10942674.1131753625665"

------=_Part_1514_10942674.1131753625665
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

 Hi John-

The wiki is wrong, unfortunately. The relevant documents on search are the
Gnutella search RFCs I authored at the following (you may need an account
for these to work):

http://tinyurl.com/d6mr5
http://tinyurl.com/cuzuf

I'm not sure who wrote the wiki entry, but it should be corrected. All of
the major Gnutella clients implement some version of the above, including
LimeWire, BearShare, and Morpheus, and you'll see all of these headers in
almost all Gnutella connections.

Regarding Kazaa, I think the key phrase in that study is: "it may flood the
query over the overlay network to **one or more** of the SNs to which it is
connected." The "one or more" should be very similar to the way Gnutella
does it, aka "random walk" or "dynamic querying" or whatever you want to
call it. This is where the real action takes place -- the hops beyond that
first one to the SN -- because that's where the vast majority of the search
traffic is. Again, I don't know for sure, but the response patterns of Kaza=
a
nodes so closely resembles those from the protocols we implemented on
Gnutella that it's hard to imagine they're doing something that different.

Now, granted, Gnutella and Kazaa are incorrectly published all over the
place as "flooding" architectures, and that's very true of their initial
implementations. Both are rapidly evolving networks, though, and long ago
moved beyond these roots. Just holding the p2p SIP group to a higher
standard!

On the Chord/CAN/other DHTs issue, it's just that I don't think there's any
reason you'd ever seriously consider Chord or CAN as realistic options over
others out there, so it seems silly to mention them. As far as I know, ther=
e
are other DHTs that simply do everything better, so it's not a matter of
weighing the advantages and disadvantages of Chord/CAN versus the advantage=
s
and disadvantages of another algorithm.

I guess I can see Chord having more existing open source implementations an=
d
possibly being easier to implement than some others, but that's about it.
Would you agree with that statement, Bryan? Thanks for your participation.

All the Best,

-Adam

John Buford wrote:

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] <[email-masked]>]O=
n
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-

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:

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=
<http://www.cs.uml.edu/%7Ebuford/irtf-p2prg/p2psip/JBuford-IETF-P2PSIP-Over=
lay>

-Systems-v3.pdf

John

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

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

------=_Part_1514_10942674.1131753625665
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

<div class=3D"moz-text-flowed" style=3D"font-family: -moz-fixed; font-size:=
 13px;" lang=3D"x-western">Hi John-
<br>
<br>The wiki is wrong, unfortunately. The relevant documents on search are
the Gnutella search RFCs I authored at the following (you may=20
need an account for these to work):
<br>
<br><a class=3D"moz-txt-link-freetext" href=3D"http://tinyurl.com/d6mr5">ht=
tp://tinyurl.com/d6mr5</a>
<br><a class=3D"moz-txt-link-freetext" href=3D"http://tinyurl.com/cuzuf">ht=
tp://tinyurl.com/cuzuf</a>
<br>
<br>I'm not sure who wrote the wiki entry, but it should be corrected. All
of the major Gnutella clients implement some version of the above,
including LimeWire, BearShare, and Morpheus, and you'll see all of these he=
aders in almost all Gnutella connections. <br>
<br>
Regarding Kazaa, I think
the key phrase in that study is: &quot;it may flood the query over the
overlay network to **one or more** of the SNs to which it is
connected.&quot;&nbsp; The &quot;one or more&quot; should be very similar t=
o the way
Gnutella does it,
aka &quot;random walk&quot; or &quot;dynamic querying&quot; or whatever you=
 want to call
it. This is where the
real action takes place -- the hops beyond that first one to the SN --
because that's where the vast majority of the search traffic is. Again,
I don't know for sure, but the response patterns of Kazaa nodes so
closely resembles those from the protocols we implemented on Gnutella
that it's hard to imagine they're doing something that different.
<br>
<br>
Now, granted, Gnutella and Kazaa are incorrectly published all over the
place as &quot;flooding&quot; architectures, and that's very true of their
initial implementations.&nbsp; Both are rapidly evolving networks,
though, and long ago moved beyond these roots.&nbsp; Just holding the
p2p SIP group to a higher standard!<br>
<br>On the Chord/CAN/other DHTs issue, it's just that I don't think there's
any reason you'd ever seriously consider Chord or CAN as realistic
options over others out there, so it seems silly to mention them. As far
as I know, there are other DHTs that simply do everything better, so
it's not a matter of weighing the advantages and disadvantages of Chord/CAN=
 versus the
advantages and disadvantages of another algorithm. <br>
<br>
I guess I can see Chord having more=20
existing open source implementations and possibly being easier to=20
implement than some others, but that's about it. Would you agree with=20
that statement, Bryan?
Thanks for your participation.<br>
<br>All the Best,<br>
<br>-Adam
<br>
<br>
<br>
<br>John Buford wrote:
<br>
<br><blockquote type=3D"cite">Hi Adam,
<br>Thanks for the comments.
<br>
<br>Looking at the wiki for the Gnutella Developers Forum in the
<br>section &quot;Querying the Network&quot;
<br>
<br>&quot;A servent SHOULD forward incoming Query messages to all of its di=
rectly
<br>connected servents, except the one that delivered the incoming Query.
<br>Servents using Flow control or Ultrapeers (sections 3.1 and 3.2) will n=
ot
<br>always forward every Query over every connection. &quot;&nbsp; There is=
 also a TTL on
<br>the packet which is decremented.
<br>
<br>This sounds like flooding not random walk.
<br>
<br>According to the GDF wiki, during bootstrapping, if a node can't
<br>connect using entries in the host cache,
<br>it can randomly select a GWebCache to populate its host cache.
<br>
<br>Regarding Kazaa, the protocol is proprietary.&nbsp; One research group =
analyzed
<br>pollution in Kazaa (Ross et al. &quot;Pollution in P2P File Sharing Sys=
tems&quot;)
<br>and built a crawler to crawl the Kazaa network.
<br><blockquote type=3D"cite">From their paper:
<br></blockquote>&quot;When a user wants to find files, the user's ON sends
<br>a query with keywords over the TCP connection to its
<br>SN. For each match in its local index, the SN returns the
<br>metadata and IP addresses corresponding to the match.
<br>When a SN receives a query, it may flood the query
<br>over the overlay network to one or more of the SNs<br>to which it is co=
nnected. A given query will in general
<br>visit a small subset of the SNs, and hence will obtain
<br>the metadata information of a small subset of all the ONs.&quot;
<br>
<br>More recently this same research group has reported on a detailed
<br>analysis of the Kazaa overlay in the paper
<br>J. Liang, R. Kumar, and K.W. Ross, The Kazaa Overlay: A Measurement Stu=
dy,
<br>Computer Networks (Special Issue on Overlays), to appear.
<br>
<br>In this paper they describe, among other things, &quot;connection shuff=
ling&quot;
<br>which both SNs and ONs use.&nbsp; It appears that this connection shuff=
ling
<br>allows peers to reach other parts of the overlay over time, and may be
<br>related to work load re-distribution.
<br>
<br>So it appears that within a given set of SN-SN and SN-ON connections
<br>Kazaa uses flooding, but these connections change over time.
<br>
<br>Yes, CAN and Chord are not &quot;state of the art&quot; depending on wh=
at you
<br>are looking for in an overlay.
<br>
<br>Again, thanks for the comments.
<br>
<br>John
<br>
<br>-----Original Message-----
<br>From: <a class=3D"moz-txt-link-abbreviated" href=3D"mailto:p2p-sip-boun=
[email-masked]">[email-masked]</a>
<br>[<a class=3D"moz-txt-link-freetext" href=3D"mailto:[email-masked]=
olumbia.edu">mailto:[email-masked]</a>]On Behalf Of Adam F=
isk
<br>Sent: Thursday, November 10, 2005 2:14 PM
<br>To: <a class=3D"moz-txt-link-abbreviated" href=3D"mailto:[email-masked]=
umbia.edu">[email-masked]</a>; <a class=3D"moz-txt-link-abbreviate=
d" href=3D"mailto:[email-masked]">[email-masked]</a>
<br>Subject: Re: [p2p-sip] slides for P2P-SIP Ad Hoc<br>
<br>
<br>Hi John-
<br>
<br>The slides look great.&nbsp; I just wanted to point out that both Gnute=
lla<br>and Kazaa's search algorithms are more accurately described as rando=
m
<br>walks than as flooding.&nbsp; Kazaa has used a massive indexing and ran=
dom
<br>walk approach for many years, and Gnutella clients have used a similar
<br>approach for at about the last 3 years.&nbsp;&nbsp; Gnutella basically =
uses bloom
<br>filters to index all data within 2 hops, and then dynamically queries
<br>supernodes depending on how many results are coming back over time.&nbs=
p; In
<br>many cases this leads to queries not going beyond the nearest
<br>supernode.&nbsp; Kazaa uses something similar, although no one outside =
of
<br>their organization knows the details.
<br>
<br>&quot;Random walk&quot; does not quite capture it either, but it's clos=
er than
<br>&quot;flooding&quot;.&nbsp; Thes algorithms are actually <b class=3D"mo=
z-txt-star"><span class=3D"moz-txt-tag">*</span>very<span class=3D"moz-txt-=
tag">*</span></b> efficient, producing
<br>light load and broad network reach, although they cannot scale as well
<br>as DHTs, clearly.
<br>
<br>That's not particularly relevant to the purposes of this group, but mor=
e
<br>for the sake of everyone's general knowledge.
<br>
<br>On the DHT side, it may be worth talking to Bryan Turner from the p2p
<br>hackers group, as he's by far the most knowledgeable person on the
<br>various DHT implementations I've come across.&nbsp; Are you on this lis=
t,
<br>Bryan?&nbsp; He's implemented many of them, and he's a strong advocate =
of
<br>&quot;The Continuous Discrete Approach&quot;.&nbsp; The DHT world evolv=
es very quickly,
<br>and things like Chord and CAN are certainly not the state of the art.
<br>
<br>I'm ccing Bryan on this.&nbsp; I don't know you, Bryan, but your posts =
on p2p
<br>hackers make your depth of knowledge in this area clear.
<br>
<br>-Adam
<br>
<br>
<br><a class=3D"moz-txt-link-abbreviated" href=3D"mailto:[email-masked]=
nasonic.com">[email-masked]</a> wrote:
<br>
<br>&nbsp;
<br>
<br><blockquote type=3D"cite">Here are the slides on P2P overlays for the a=
d hoc session on Friday
<br>
<br><a class=3D"moz-txt-link-freetext" href=3D"http://www.cs.uml.edu/%7Ebuf=
ord/irtf-p2prg/p2psip/JBuford-IETF-P2PSIP-Overlay">http://www.cs.uml.edu/~b=
uford/irtf-p2prg/p2psip/JBuford-IETF-P2PSIP-Overlay</a>
<br>&nbsp;&nbsp;=20

<br></blockquote>-Systems-v3.pdf<br>&nbsp;
<br>
<br><blockquote type=3D"cite">John
<br>
<br>
<br>_______________________________________________
<br>p2p-sip mailing list
<br><a class=3D"moz-txt-link-abbreviated" href=3D"mailto:[email-masked]=
a.edu">[email-masked]</a>
<br><a class=3D"moz-txt-link-freetext" href=3D"http://lists.cs.columbia.edu=
/mailman/listinfo/p2p-sip">http://lists.cs.columbia.edu/mailman/listinfo/p2=
p-sip</a>
<br>
<br>
<br>
<br>&nbsp;&nbsp;=20

<br></blockquote>_______________________________________________
<br>p2p-sip mailing list
<br><a class=3D"moz-txt-link-abbreviated" href=3D"mailto:[email-masked]=
a.edu">[email-masked]</a>
<br><a class=3D"moz-txt-link-freetext" href=3D"http://lists.cs.columbia.edu=
/mailman/listinfo/p2p-sip">http://lists.cs.columbia.edu/mailman/listinfo/p2=
p-sip</a>
<br>
<br>
<br>&nbsp;
<br>
<br></blockquote>
<br>
<br></div>

------=_Part_1514_10942674.1131753625665--
-------------- next part --------------
_______________________________________________
p2p-sip mailing list
[email-masked]
http://lists.cs.columbia.edu/mailman/listinfo/p2p-sip

---

From: adamfisk at gmail.com (Adam Fisk)
Date: Sun Nov 13 22:02:55 2005

Hi John-

I think my previous links do require registration. I found a link to it on
the Wiki, though, at:

http://www.the-gdf.org/wiki/index.php?title=Dynamic_Query_Protocol

The "Ultrapeer Query Routing" spec doesn't appear to be in the Wiki yet. If
you're a member of the GDF, though, you can navigate to it at:

http://groups.yahoo.com/group/the_gdf/files/Proposals/Working%20Proposals/search/

Note that I'm using the term "RFC" very loosely here.

-Adam

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.cs.columbia.edu/pipermail/p2p-sip/attachments/20051113/0b8afb9f/attachment.html