From kash Wed Feb 8 16:08:21 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-1.4 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE autolearn=ham version=3.1.0 X-Spam-Level: Received: from exchfe2.cs.cornell.edu (exchfenlb-2.cs.cornell.edu [128.84.97.34]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k18L8Kt26645 for ; Wed, 8 Feb 2006 16:08:20 -0500 (EST) Received: from EXCHVS2.cs.cornell.edu ([128.84.97.24]) by exchfe2.cs.cornell.edu with Microsoft SMTPSVC(6.0.3790.1830); Wed, 8 Feb 2006 16:08:20 -0500 X-MimeOLE: Produced By Microsoft Exchange V6.5 Content-class: urn:content-classes:message MIME-Version: 1.0 X-Security: message sanitized on sundial.cs.cornell.edu See http://www.impsec.org/email-tools/sanitizer-intro.html for details. $Revision: 1.148 $Date: 2004-12-19 11:59:17-08 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="----_=_NextPart_001_01C62CF3.C99C006E" Subject: PAPER 5 Date: Wed, 8 Feb 2006 16:08:18 -0500 Message-ID: <2EE48095D8C21643B0B70EC95F9BFBAF011008BF@EXCHVS1.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: PAPER 5 Thread-Index: AcYs88jQIOtJX2aOSKuv2ZaFSmOKog== From: "Ian Kash" To: X-OriginalArrivalTime: 08 Feb 2006 21:08:20.0264 (UTC) FILETIME=[C9E68280:01C62CF3] This is a multi-part message in MIME format. ------_=_NextPart_001_01C62CF3.C99C006E Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable One Hop Lookups proposes that that it is practical for each node to know the identity of every other so that most lookups can be completed in a single hop (the small number that cannot are due to information not having yet been propagated). Nodes are still arranged in a ring structure so that neighbors can determine who is alive. To limit bandwidth usage, nodes are grouped into slices and information about liveness is exchanged between slices only by slice leaders. To cut down on the bandwidth slice leaders use sending this information on to their slices each slice is divided into a few units each with a unit leader who passes these messages from the slice leader to each member of the slice. =20 Liveness is only checked by neighbors, so if three nodes in a row along the righ fail, there may be a problem with getting the status of the one in the middle straightened out. If nodes elsewhere are allowed to report deadness in this case, there may be significant confusion when network partitions occur. Another problem is the load on slice leaders. In a network of 10^6 nodes, they claim the load on a slice leader is 350 kbps. They not that this requires a serious connection such as an institutional one. At 350 kbps, that is 3.6 GB of bandwidth used per day. It seems unreasonable to expect any institution or individual to donate that much bandwidth, so this system has significant incentive problems. Even in a small system of 10^5 nodes, 360 MB per day is a significant overhead for the home user with a cable modem they claim is suitable for a slice leader. =20 Kelips proposes a similar concept, bust instead of requiring 1 hop they relax this to O(1) hops. Along with accepting longer time for infomation to propagate, this allows them to eliminate the excessive requirements on the slice leaders that the one hop paper had. Eacn node knows only its local affinity group of size sqrt(n) in its entirety and knows a few members of each other group. Rather than having leaders to maintain this information, it is maintained by gossip. While this does eliminate the heavy bandwidth consumption by = the leaders, the tradeoff is that, as the one hop paper points out, it can take an hour in large systems for everyone to know about a particular join or leave. How much of a problem this presents in practice is = unclear. ------_=_NextPart_001_01C62CF3.C99C006E Content-Type: text/html; charset="us-ascii" Content-Transfer-Encoding: quoted-printable -->

One Hop Lookups proposes that that it is practical = for each node to

know the identity of every other so that most lookups = can be completed

in a single hop (the small number that cannot are due = to information

not having yet been propagated).  Nodes are = still arranged in a ring

structure so that neighbors can determine who is = alive.  To limit

bandwidth usage, nodes are grouped into slices and information about

liveness is exchanged between slices only by slice = leaders.  To cut

down on the bandwidth slice leaders use sending this information on to

their slices each slice is divided into a few units = each with a unit

leader who passes these messages from the slice = leader to each member

of the slice.

 

Liveness is only checked by neighbors, so if three = nodes in a row

along the righ fail, there may be a problem with = getting the status of

the one in the middle straightened out.  If = nodes elsewhere are

allowed to report deadness in this case, there may be significant

confusion when network partitions occur.  = Another problem is the load

on slice leaders.  In a network of 10^6 nodes, = they claim the load on

a slice leader is 350 kbps.  They not that this = requires a serious

connection such as an institutional one.  At 350 = kbps, that is 3.6 GB

of bandwidth used per day.  It seems = unreasonable to expect any

institution or individual to donate that much = bandwidth, so this

system has significant incentive problems.  Even = in a small system of

10^5 nodes, 360 MB per day is a significant overhead = for the home user

with a cable modem they claim is suitable for a slice leader.

 

Kelips proposes a similar concept, bust instead of = requiring 1 hop

they relax this to O(1) hops.  Along with = accepting longer time for

infomation to propagate, this allows them to = eliminate the excessive

requirements on the slice leaders that the one hop = paper had.  Eacn

node knows only its local affinity group of size = sqrt(n) in its

entirety and knows a few members of each other = group.  Rather than

having leaders to maintain this information, it is maintained by

gossip.  While this does eliminate the heavy = bandwidth consumption by the

leaders, the tradeoff is that, as the one hop paper = points out, it can

take an hour in large systems for everyone to know = about a particular

join or leave.  How much of a problem this = presents in practice is unclear.

------_=_NextPart_001_01C62CF3.C99C006E-- From okennedy Wed Feb 8 19:43:28 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=ham version=3.1.0 X-Spam-Level: Received: from exchfe2.cs.cornell.edu (exchfenlb-2.cs.cornell.edu [128.84.97.34]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k190hSt29410 for ; Wed, 8 Feb 2006 19:43:28 -0500 (EST) Received: from exchfe1.cs.cornell.edu ([128.84.97.33]) by exchfe2.cs.cornell.edu with Microsoft SMTPSVC(6.0.3790.1830); Wed, 8 Feb 2006 19:43:28 -0500 Received: from [128.84.98.36] ([128.84.98.36]) by exchfe1.cs.cornell.edu over TLS secured channel with Microsoft SMTPSVC(6.0.3790.1830); Wed, 8 Feb 2006 19:43:27 -0500 Mime-Version: 1.0 (Apple Message framework v746.2) Content-Transfer-Encoding: 7bit Message-Id: Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: egs+summary From: Oliver Kennedy Subject: PAPER 5 Date: Wed, 8 Feb 2006 19:44:02 -0500 X-Mailer: Apple Mail (2.746.2) X-OriginalArrivalTime: 09 Feb 2006 00:43:27.0627 (UTC) FILETIME=[D749CDB0:01C62D11] One hop lookups takes Chord and redesigns it with the thought that memory space is less valuable than lookup time. In particular, if we're efficient about the amount of information we're storing for each host (say keep each entry to under 20 bytes; enough to store an IP address and a 128 bit identifier), we can hold the entire lookup table in a small (in the above example: 20 MB) portion of memory. OHL notes that traditional ring networks are more concerned about reducing state to reduce the bandwidth consumed by keepalive messages than they are about memory usage. To that end, their system uses a three level tree structure to disseminate updates to the lookup table. By intelligently buffering updates, overall bandwidth is minimized. Since update periods are constant, OHL is able to set a concrete cap on the amount of time that a node's failure will remain unknown to another node. Also, since the entire system state is known to all nodes (within a reasonable period of time) recovery is OHL is a good idea in theory, though its scalability is limited in some respects. A constant three tier update distribution tree may be suitable for the range of nodes in the system that they describe, but as the number of nodes increases, stress on the slice leaders will increase and they become a single (though rapidly replaceable) point of fracture. Moreover, the update delay experienced by nodes at the edges of a unit will increase considerably as well (Though this might be alleviated by having the unit size step dynamically as the network changes size; something which will increase stress on the slice leaders). Memory usage is also not as minor a feature as they claim. OHL is unsuitable for use on any sort of mobile device such as a PDA or Cellphone where memory is at a premium. Even on a desktop, 20 MB is a significant hit for what most would not consider a performance critical application. Kelips makes a similar observation, but notes that with a constant (2) number of hops, a significant reduction in state may be obtained. Kelips breaks up the identifier space into a set of affinity groups. A node deterministically joins a specific affinity group based on its identifier. Data is owned collectively by the entire affinity group. One host in the affinity group is chosen at random to host each object. Each node in the affinity group is required to keep track of all of the objects owned by that affinity group. Because of this, lookups can be performed by simply contacting any member of the affinity group, and a node is only required to store state about the other members of the affinity group (O(sqrt(n)) assuming sqrt(n) affinity groups) and a constant amount of information about each other affinity group. The fact that an object is owned by the entire group helps to reduce load on some level (though hot objects still pose a problem). A heavily loaded node might redistribute a subset of its objects to other nodes in its group. It also makes reassigning file ownership in the case of a failure easier. Two problems make themselves apparent. Firstly, the fact that each node in a group is supposed to store a reference to all objects held by that group partially defeats the purpose of a DHT. With a high object/node ratio this becomes particularly inefficient. Of more concern is the fact that the O(1) lookup guarantee assumes an up-to- date file list. Depending on the network's churn rate, propagating an accurate file list through gossip may not be feasible. The most discomforting aspect of Kelips is that unlike several of the other DHTs we've studied, it makes no guarantee that a valid query will ever succeed (only that it will succeed with high probability). While this is still a better guarantee than that offered by grid networks such as Gnutella, it seems a little strange. - Oliver Kennedy They laughed at Einstein. They laughed at the Wright Brothers. But they also laughed at Bozo the Clown. -- Carl Sagan From asr32 Wed Feb 8 23:47:19 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.6 required=5.0 tests=AWL,DATE_IN_PAST_06_12, MAILTO_TO_SPAM_ADDR autolearn=no version=3.1.0 X-Spam-Level: Received: from authusersmtp.mail.cornell.edu (granite1.mail.cornell.edu [128.253.83.141]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k194lJt01088 for ; Wed, 8 Feb 2006 23:47:19 -0500 (EST) Received: from dreadnought.cornell.edu (r253240123.resnet.cornell.edu [128.253.240.123]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k194lI7Z005596 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for ; Wed, 8 Feb 2006 23:47:19 -0500 (EST) Message-Id: <6.2.1.2.2.20060208102046.032741a0@postoffice8.mail.cornell.edu> X-Mailer: QUALCOMM Windows Eudora Version 6.2.1.2 Date: Wed, 08 Feb 2006 17:27:02 -0500 To: egs+summary From: Ari Rabkin Subject: PAPER 5 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed One-hop routing: Most peer-to-peer systems are careful only to store some sublinear quantity of information about other nodes in the system; most ring based system keep O(log N) state, Kelips keeps O(sqrt(N)), and Viceroy keeps O(1). In contrast, Gupta et al propose that every node keep a full list of nodes in the system, which will allow one-hop routing. This approach is probably feasible for networks with fewer than 10^5 nodes, although the slice leader nodes will need substantial bandwidth. The authors show that their scheme actually is close to the theoretically optimum bandwidth consumption It is unclear how to make the system work without enough supernodes. As might be expected from a system with O(N) state required, the one-hop proposal does not scale. The authors admit that for large networks, a two-layer scheme might be applicable; this proposed scheme is very reminiscent of Kelips, with nodes divided into sqrt(N) groups, and nodes knowing all the nodes in their group, and a few nodes in each other group. There are other important weaknesses in this scheme. Particularly under churn, and especially in the presence of an attacker, there may not always be consensus about which nodes are slice and unit leaders. The system will perform poorly if either slice or unit leaders have poor connections, or drop packets. Kelips: Kelips makes quite different design choices, and has quite different performance characteristics, from ring-based DHT systems. Instead of a ring, Kelips groups nodes into sqrt(n) replication groups. Each node has fairly complete state for its group, and knows how to find nodes in each other group. Instead of a rigid topology to specify where data will be and which nodes can route to where, Kelips uses a fairly loose structure, coupled with gossip. The authors of Kelips claim O(1) insertion, but do not mention that there will be a lag between the insertion time, and when all members of the affinity group are aware of the insertion. This lag is longer than O(1); it grows as O( sqrt(N) log^3 (N)). This can be many minutes for large systems (Gupta et al claim that it is over an hour for systems approaching a million nodes). This also means that if a node does an insert, followed immediately by a lookup, the lookup will fail. No specific numbers are given for bandwidth cost, as a function of stabilization time, nor for query accuracy. Ari Rabkin asr32 Risley Hall 454 3-2842 The resources of civilization are not yet exhausted. --William Gladstone From ymir.vigfusson Wed Feb 8 23:51:11 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=ham version=3.1.0 X-Spam-Level: Received: from uproxy.gmail.com (uproxy.gmail.com [66.249.92.194] (may be forged)) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k194pAt02106 for ; Wed, 8 Feb 2006 23:51:10 -0500 (EST) Received: by uproxy.gmail.com with SMTP id u2so51733uge for ; Wed, 08 Feb 2006 20:51:09 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:mime-version:content-type:content-transfer-encoding:content-disposition; b=FgxpJVKSTwit5HXEi6QuFmoB2QgMhqwZV3LLnOrG1afJFI4n8+T3B4DJ/iRmTPJZVDgf30se36UczJsFXM/W64zBENJfLiwaH3Ff1Wbku1BjCQt742eVkmIcUxlKXnM7Ck7dX3R0vZ5SP/B2Ftoza2KGYcVIcD7vOuW+XxVhz3U= Received: by 10.48.157.2 with SMTP id f2mr2213373nfe; Wed, 08 Feb 2006 20:51:09 -0800 (PST) Received: by 10.49.43.1 with HTTP; Wed, 8 Feb 2006 20:51:09 -0800 (PST) Message-ID: <9302f1e20602082051o5515bdf8t61e8da90897d2c0f@mail.gmail.com> Date: Wed, 8 Feb 2006 23:51:09 -0500 From: Ymir Vigfusson To: egs+summary Subject: PAPER 5 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id k194pAt02106 Kelips is a system designed to reduce file lookup times to O(1) time by maintaining a list of O(sqrt(n)) nodes in memory (soft-state) and increasing background traffic. The motivation is to explore alternative tradeoffs to the O(lg n) nodes/hops for state/lookup established by the ring-based protocols (Chord, Pastry, etc.) The authors argue that high latency/low bandwidth nodes are common and will likely slow down lookups. Kelips improves on this by providing O(1) lookup costs. This is implemented by creating k virtual affinity groups of nodes (in the paper, k = sqrt(n)) where each node maintains a list of pointer to the nodes that handle files that fall in the hash range for the affinity group. This way, to look up a file, we calculate the hash, find our "contact" in the affinity group that handles this hash value and ask that node to provide us with a pointer to the homenode of that file. This takes clearly O(1) hops (if everything is okay). However, as the paper by Gupta et al. points out, for constant cost of lookups to be possible, the routing tables need to be accurate, yet the expected convergence time for membership changes in Kelips is O(sqrt(n) * log^3(n)) which is impractical for very large n. The second paper boldly proposes a network with one hop lookups by maintaining all routing information, in other words the network is a complete graph. The authors argue that attempting to keep routing information small, as is done in the networks we have discussed, (usually O(lg n)) serves a limited practical purpose because disk space and memory is cheap, but bandwidth/latency is not. The paper shows how this can be implemented robustly so that traffic overhead is small. The design is as follows: Imagine a ring like Chord with 2^128 identifiers representing the identifier space where nodes keep track of successors and predecessors. We now cut the ring into equally sized pieces called slices and assign the middle node of every slice to be a slice so called slice leader. The interval is then in turn cut into more pieces called units, and the middle node from each unit is a unit leader. This three level hierarchy is shown to lead to reasonable bandwidth consumption. The idea is to make the leaders aggregate information about membership changes and propagate to their "underlings". If any of these leader nodes fail, their successor will take their place. The lost information will be recovered by communicating with the slice leader in the case of unit leader failure, and collectively by the unit leaders and other slice leaders in the case of a slice leader failure. The paper then talks about scalability, and determines the optimal packet delays for the aggregate information. It turns out that with 10^5 nodes a slice leader needs 35kbps upstream bandwidth, and 350kbps if there are 10^6 nodes, assuming rather realistic packet sizes. Of course, the major weakness here is the uneven load on the leader nodes. The paper states that such nodes should be well-provisioned, preferably cable modems or having even more bandwidth. Also, neither paper addresses any privacy or security issues. - Ymir From niranjan.sivakumar Thu Feb 9 00:10:37 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=ham version=3.1.0 X-Spam-Level: Received: from xproxy.gmail.com (xproxy.gmail.com [66.249.82.206] (may be forged)) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k195Abt06772 for ; Thu, 9 Feb 2006 00:10:37 -0500 (EST) Received: by xproxy.gmail.com with SMTP id h26so46522wxd for ; Wed, 08 Feb 2006 21:10:36 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:reply-to:to:subject:date:user-agent:organization:mime-version:content-type:content-transfer-encoding:content-disposition:message-id:from; b=SZrO2raqfrhiJZVkTJd3fZJzR03t6d+4S/pmlEynXLnmR2MyvRT8sz7unRAqJtg6UbL5EsDqiqX+EjT8q8Jxpnl+xUnSrrWKonN+G+KqCNeOdKbi8dWLz2DhZlI34TZpNri/al7btU/UVLX/9f8/7DUsU/C0+8PVhoPmn9dhmH8= Received: by 10.70.82.12 with SMTP id f12mr5662371wxb; Wed, 08 Feb 2006 21:10:36 -0800 (PST) Received: from ?192.168.0.101? ( [69.207.63.116]) by mx.gmail.com with ESMTP id h7sm1971622wxd.2006.02.08.21.10.36; Wed, 08 Feb 2006 21:10:36 -0800 (PST) Reply-To: ns253 To: egs+summary Subject: PAPER 5 Date: Thu, 9 Feb 2006 00:10:32 -0500 User-Agent: KMail/1.9 Organization: Cornell University MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200602090010.33467.ns253> From: Niranjan Sivakumar One Hop Lookups for Peer-to-Peer Overlays Kelips: Building Efficient and Stable P2P DHT Through Increased Memory and Background Overhead Both Kelips and the One Hop Lookup papers focus on increasing memory usage to improve lookup performance. Kelips is designed around a system of "affinity groups." These groups maintain a partial index (that all members of the group are responsible for) by gossipping with each other. Nodes also need to maintain some fixed contact information about other affinity groups (any node in the affinity group can be contacted, as each member has all the information about its group.) A number of issues with Kelips are pointed out in the One Hop Lookups paper. Among these are the inability of Kelips to scale to large systems. Also, there can be very long delays in propagation of events through the system. This can result in stale routing tables and many queries that fail on the first attempt. One Hop Lookups takes the concept one step further than Kelips and insists on having every node essentially have an index of the whole system to allow for direct connections to the target nodes. The basic structure is a ring based DHT, similar to Chord. The system is broken down into three tiers. Slices are the first tier and slice leaders are selected to gather information and pass it on to other slice leaders at fixed intervals (but not synchronized). The second tier are units with a unit leader in charge. Unit boundaries are used to keep redundant information from being passed around. Finally, the third tier are nodes. With the three tier system and periodic updates, although there will be instances where queries fail on the first attempt, updates should be received within some threshold time. One of the flaws seen in the One Hop Lookup system seems to be the amount of bandwidth that is required by the leader nodes. As noted in the paper, this can be reasonably high when the system scales to a size of 10^6. This seems to unfairly put the bandwidth burden on some "supernodes." This could be particularly problematic if the economic model of charging for bandwidth shifts to one where payment is related to the amount of bandwidth used. Also, in the case of having "supernodes" these nodes may be targets of attack or institutions such as Universities may be able to look for traffic patterns and block nodes from joining. From lackhand Thu Feb 9 00:56:11 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.6 required=5.0 tests=HTML_00_10,HTML_MESSAGE autolearn=no version=3.1.0 X-Spam-Level: Received: from zproxy.gmail.com (zproxy.gmail.com [64.233.162.201]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k195uBt16588 for ; Thu, 9 Feb 2006 00:56:11 -0500 (EST) Received: by zproxy.gmail.com with SMTP id s18so89503nze for ; Wed, 08 Feb 2006 21:56:10 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:mime-version:content-type; b=byo9GLbO9v07YUZRdySJPBzWb3QDvrtXKmG03G6AIcZWZIAoycUCCCwOkyFlZFVLqET3f9mQw9dFjAg2YyIUu0R2OeANanwnHSMqq3lRV894Rvi0YAFMiNak2l40+v6Al5RCnnTMguHIoTEWzBha1Q79RphAKAo+QXOv8SqKg6o= Received: by 10.36.22.16 with SMTP id 16mr1634753nzv; Wed, 08 Feb 2006 21:56:10 -0800 (PST) Received: by 10.36.148.4 with HTTP; Wed, 8 Feb 2006 21:56:10 -0800 (PST) Message-ID: <9aa7a97d0602082156r7c359becx98e7ecd1b30a88f9@mail.gmail.com> Date: Thu, 9 Feb 2006 00:56:10 -0500 From: Andrew Cunningham To: egs+summary Subject: PAPER 5 MIME-Version: 1.0 X-Security: message sanitized on sundial.cs.cornell.edu See http://www.impsec.org/email-tools/sanitizer-intro.html for details. $Revision: 1.148 $Date: 2004-12-19 11:59:17-08 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="----=_Part_11413_19060006.1139464570284" ------=_Part_11413_19060006.1139464570284 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Andrew Cunningham arc39 _One_Hop_Lookups_for_Peer-to-Peer_Overlays_ Anjali Gupta, Barbara Liskov, Rodrigo Rodrigues In many ways, the central conceit of this paper is as obvious as it is frightening: each node maintains routing information about each other node in the system. This O(n) state leads to O(1) routing, which means that it performs much better than the systems we've studied so far, in terms of performance speed, but suffers in terms of theoretical state; it also requires O(n) operations on a join leave, but they use a clever subsystem t= o reduce this. The paper maintains that performance statistics for current systems that fill the same need indicate that certain assumptions about the actual values of n may be made, and that this system performs well given those numbers; it becomes unreasonable for only values of n many orders of magnitude greater (by which time what is reasonable may have changed definition). The interesting-to-analyze portion of this paper is its join and remove operations, since its search is simply direct, or if this fails (which it will, with some analyzed probability), some other operations that are worst-case-but-unlikely, and any search that requires these is considered 'failed'. The method of choosing update-tree leaders is very clever, though the scheme relies on a k being well known, which would seem to indicate it being pre-chosen, which means that, while each leader maintaining O(N) stat= e is the essence of this algorithm, it can't be dynamically tuned, which mean= s that if the address space does become unbalanced (which is unlikely) it is difficult to fix. It is not precisely certain whether the tree structure of dissemination is fixed, in which case in the general case either O(N) state is maintained with O(1) hops to distribute, or O(LogN) state is maintained with O(LogN) hops; it seems to indicate a three level O(1) hop implementation; this is part of the spirit of the paper, and so I cannot fault it; the O(1) dissementation is impressive. They make a curious statement: since there are relatively fewer unit an= d section leaders, their failure does not have to be corrected -- "pursued" -= - as vigorously. This is a curious statement; the logic is that since there are fewer of them, they fail with lesser probability. This is true, and the algorithm for replacing them is easy enough to implement, but the comment catches me by surprise, as all update events rely on their presence and functioning correctly, neither of which is guaranteed by less aggressive updates. If they meant that the failure and replacement operation is easy, then this is more obvious, as the replacement operation is rather clever. This is clearly one of the more robust networks that we've studied, but it pays in overhead; the conceit is that by the statistics, this is unimportant. A question is whether this is 'infinitely extensible'; to take a tangential note to the paper, many of the algorithms we've studied thus far -- especially Viceroy -- could serve as self-assembling motes with extraordinarily limited resources. This definitely relies on modern computing power, and thus is more suited to what the paper states it is, clearly a tautology. To borrow from the close of this paper and the beginning of the next one, they assume that joins and exits are rare, which is not true for all applications, and that memory is infinite, which is nearly true. _Kelips:_Building_an_Efficient_and_Stable_P2P_DHT_Through_Increased_Memory_= And_Background_Overhead_ Indranil Gupta, Ken Birman, Prakash Linga, Al Demers, Robbert van Renesse Kelips makes a similar guarantee to the (unnamed?) previous system, though also backs it up with statistics taken from gnutella, to establish that O(sqrt(n)) space and O(1) time for lookups are acheivable. In some ways, it establishes this by using the network as a form of storage; more specifically, a high degree of overhead maintains accuracy. The connections themselves are between k affinity groups, segments of the nodeID space; they consist of some subset of the affinity group of a given node and a constant number of contacts in other affinity groups. It uses a gossip-like system of heartbeats to keep information fresh, with goo= d time-performance, though of course this requires overhead proportional to O(sqrt(n)*log^3(n)), which is more than the overhead per node in the previous scheme. Also, the reduced overhead is coped with via indirect lookups; anything in an affinity group is assumed to be able to find the correct resource in O(1) hops, though more than in the fully connected case= , of course. The advantage is that joins and leaves are more quickly coped with, and that this leads to better performance for applications that must deal with churn. In fact, the system performs better in the presence of churn than One Hop Overlays if only because, though there are similar concepts in that bot= h partition the nodeID spaces into specialized compartments, Kelips gives eac= h node less knowledge about the overall system, and thus gossip need not propagate as far for a consistent view of resources. It is slightly more fragile, but given the massive degree of state stored, it's slight fragilit= y is completely secondary to its performance. Also, given that one of the goals is to cope with relatively rapid joins & leaves, the fragility is ver= y quickly self repairing. ------=_Part_11413_19060006.1139464570284 Content-Type: text/html; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Andrew Cunningham
arc39
    _One_Hop_Lookups_for_Peer-to-Peer_Overlays_
    Anjali Gupta, Barbara Liskov, Rodrigo Rodrigues
   
    In many ways, the central conceit of this paper is as obvious as it is frightening: each node maintains routing information about each other node in the system. This O(n) state leads to O(1) routing, which means that it performs much better than the systems we've studied so far, in terms of performance speed, but suffers in terms of theoretical state; it also requires O(n) operations on a join leave, but they use a clever subsystem to reduce this. The paper maintains that performance statistics for current systems that fill the same need indicate that certain assumptions about the actual values of n may be made, and that this system performs well given those numbers; it becomes unreasonable for only values of n many orders of magnitude greater (by which time what is reasonable may have changed definition).
    The interesting-to-analyze portion of this paper is its join and remove operations, since its search is simply direct, or if this fails (which it will, with some analyzed probability), some other operations that are worst-case-but-unlikely, and any search that requires these is considered 'failed'. The method of choosing update-tree leaders is very clever, though the scheme relies on a k being well known, which would seem to indicate it being pre-chosen, which means that, while each leader maintaining O(N) state is the essence of this algorithm, it can't be dynamically tuned, which means that if the address space does become unbalanced (which is unlikely) it is difficult to fix. It is not precisely certain whether the tree structure of dissemination is fixed, in which case in the general case either O(N) state is maintained with O(1) hops to distribute, or O(LogN) state is maintained with O(LogN) hops; it seems to indicate a three level O(1) hop implementation; this is part of the spirit of the paper, and so I cannot fault it; the O(1) dissementation is impressive.
    They make a curious statement: since there are relatively fewer unit and section leaders, their failure does not have to be corrected -- "pursued" -- as vigorously. This is a curious statement; the logic is that since there are fewer of them, they fail with lesser probability. This is true, and the algorithm for replacing them is easy enough to implement, but the comment catches me by surprise, as all update events rely on their presence and functioning correctly, neither of which is guaranteed by less aggressive updates. If they meant that the failure and replacement operation is easy, then this is more obvious, as the replacement operation is rather clever.
    This is clearly one of the more robust networks that we've studied, but it pays in overhead; the conceit is that by the statistics, this is unimportant. A question is whether this is 'infinitely extensible'; to take a tangential note to the paper, many of the algorithms we've studied thus far -- especially Viceroy -- could serve as self-assembling motes with extraordinarily limited resources. This definitely relies on modern computing power, and thus is more suited to what the paper states it is, clearly a tautology. To borrow from the close of this paper and the beginning of the next one, they assume that joins and exits are rare, which is not true for all applications, and that memory is infinite, which is nearly true.
   
    _Kelips:_Building_an_Efficient_and_Stable_P2P_DHT_Throug= h_Increased_Memory_And_Background_Overhead_
    Indranil Gupta, Ken Birman, Prakash Linga, Al Demers, Ro= bbert van Renesse
   
    Kelips makes a similar guarantee to the (unnamed?) previous system, though also backs it up with statistics taken from gnutella, to establish that O(sqrt(n)) space and O(1) time for lookups are acheivable. In some ways, it establishes this by using the network as a form of storage; more specifically, a high degree of overhead maintains accuracy.
    The connections themselves are between k affinity groups, segments of the nodeID space; they consist of some subset of the affinity group of a given node and a constant number of contacts in other affinity groups. It uses a gossip-like system of heartbeats to keep information fresh, with good time-performance, though of course this requires overhead proportional to O(sqrt(n)*log^3(n)), which is more than the overhead per node in the previous scheme. Also, the reduced overhead is coped with via indirect lookups; anything in an affinity group is assumed to be able to find the correct resource in O(1) hops, though more than in the fully connected case, of course. The advantage is that joins and leaves are more quickly coped with, and that this leads to better performance for applications that must deal with churn.
    In fact, the system performs better in the presence of churn than One Hop Overlays if only because, though there are similar concepts in that both partition the nodeID spaces into specialized compartments, Kelips gives each node less knowledge about the overall system, and thus gossip need not propagate as far for a consistent view of resources. It is slightly more fragile, but given the massive degree of state stored, it's slight fragility is completely secondary to its performance. Also, given that one of the goals is to cope with relatively rapid joins & leaves, the fragility is very quickly self repairing.
------=_Part_11413_19060006.1139464570284-- From victoria Thu Feb 9 01:15:02 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=ham version=3.1.0 X-Spam-Level: Received: from turing.cs.hmc.edu (turing.cs.hmc.edu [134.173.42.99]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k196F2t23167 for ; Thu, 9 Feb 2006 01:15:02 -0500 (EST) Received: by turing.cs.hmc.edu (Postfix, from userid 34382) id 97CA653247; Wed, 8 Feb 2006 22:14:56 -0800 (PST) Date: Wed, 8 Feb 2006 22:14:56 -0800 From: Victoria Krafft To: egs+summary Subject: PAPER 5 Message-ID: <20060209061456.GA14005> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.4.2.1i Thursday's papers focus on p2p networks which offer O(1) lookup, in exchange for O(N) data being stored at each node. The first proposal, by Gupta et al., stores complete membership information at each node. They manage this without using too much bandwidth by partitioning the traditional DHT ring into slices, and assigning a "slice leader" to each slice. This slice leader then receives information from the other slices which it distributes to its slice, and packages up the information about changes to its slice, then distributes these changes to the other slices. Slices are further divided into units, with unit leaders. The other system, Kelips, offers O(1) lookup while only storing O(sqrt(N)) data at each node. It does this by splitting the network into some fixed number of affinity groups. Each node is assigned an affinity group, and it has connections to nodes in its affinity group, as well as nodes in each other affinity group. Each node in an affinity group knows about all the files stored in that affinity group, and information about the state of the network is propagated using an epidemic protocol. Unfortunately, both of these schemes have problems. Gupta's scheme stores O(N) data at each node, which can eat up significant amounts of memory, even for a modern machine. It also requires that there be supernodes, and that the owners of those supernodes allow the increased traffic. While this works for some types of p2p networks, not all p2p networks can provide supernodes. Kelips is definitely an interesting idea, with fast lookup without maintaining as large a routing table. However, the epidemic protocol used to distribute information takes a while to distribute information, so the network may provide inconsistent information - nodes A and C can find a file in the network, but node B cannot. In the p2p systems with O(log n) lookup, if node A can find the file, then node B will almost always find it as well. -- Victoria Krafft From tc99 Thu Feb 9 02:20:11 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=ham version=3.1.0 X-Spam-Level: Received: from postoffice10.mail.cornell.edu (postoffice10.mail.cornell.edu [132.236.56.14]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k197KBt11892 for ; Thu, 9 Feb 2006 02:20:11 -0500 (EST) Received: from webmail.cornell.edu (hermes21.mail.cornell.edu [132.236.56.20]) by postoffice10.mail.cornell.edu (8.12.10/8.12.6) with ESMTP id k197KB1b022993 for ; Thu, 9 Feb 2006 02:20:12 -0500 (EST) Received: from 24.59.114.243 by webmail.cornell.edu with HTTP; Thu, 9 Feb 2006 02:20:12 -0500 (EST) Message-ID: <5843.24.59.114.243.1139469612.squirrel@webmail.cornell.edu> Date: Thu, 9 Feb 2006 02:20:12 -0500 (EST) Subject: paper 5 From: "Theodore Ming Shiuan Chao" To: egs User-Agent: SquirrelMail/1.4.5 MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Priority: 3 (Normal) Importance: Normal The main premise of these two papers is to keep a constant lookup time at the expense of a greater than O(log N) update and maintenence cost that is the property of previous ring-based topology network overlays such as Chord and Pastry. The network in the first paper is also a ring-based topology, but it is fully connected instead of just maintaining a few local pointers and/or remote pointers. To reduce the costs of updates, the ring is partitioned into several non-overlapping segments. Each segment has one "slice leader" who handles all intra-segment communication and several "unit leaders" that distribute messages to neighboring nodes in the segment. The rest of the nodes simply propagate messages in one direction until the end of the segment is hit. Kelips, on the other hand, has no set topology at all, and the lookup time, even with no node failures, is _not_ guaranteed to be constant. Every node that joins is placed in one of k bins. They do not explicitly maintain links to every other node, but each node "gossips" with a constant number of nodes in other bins and with certain nodes in its own bin. The "gossip" lets information propagate through the bins (affinity groups), and the information on the nodes in the group and what files they store are cached as the gossip travels through the group. This keeps the background bandwidth usage constant. According to the authors, all nodes will eventually receive the gossip with high probability, so the lookup will take 2 hops with high probability - one hop to the appropriate affinity group, and the one hop within the group to the appropriate node holding the file. These two methods both sacrificed state required and update cost in favor of reduced lookup times. For one-hop, it requires O(N) state while Kelips requires O(sqrt(N)) state. However, the constant factor of one-hop is extremely small because of the ring-based topology (and since hashed IDs can be used to route requests), and I believe that for most realistic values of N, one-hop will take less space than Kelips, which needs to cache more information per node. A problem in one-hop is that it does not consider physical locality at all. Splice leaders are not guaranteed to be close, nor are their unit leaders. Thus, even though the t_small and t_big may be relatively small, it can still take a long time for some nodes to hear of changes in the network because of latency between nodes. From ryanp Thu Feb 9 04:50:10 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=ham version=3.1.0 X-Spam-Level: Received: from exchfe2.cs.cornell.edu (exchfenlb-2.cs.cornell.edu [128.84.97.34]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k199o7t14852 for ; Thu, 9 Feb 2006 04:50:09 -0500 (EST) Received: from exchfe2.cs.cornell.edu ([128.84.97.28]) by exchfe2.cs.cornell.edu with Microsoft SMTPSVC(6.0.3790.1830); Thu, 9 Feb 2006 04:50:07 -0500 Received: from [128.253.211.203] ([128.253.211.203]) by exchfe2.cs.cornell.edu over TLS secured channel with Microsoft SMTPSVC(6.0.3790.1830); Thu, 9 Feb 2006 04:50:06 -0500 Mime-Version: 1.0 (Apple Message framework v746.2) Content-Transfer-Encoding: 7bit Message-Id: <09F59FEE-B5C8-470D-8869-03475AD2F54B> Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: egs+summary From: "Ryan S. Peterson" Subject: PAPER 5 Date: Thu, 9 Feb 2006 04:50:06 -0500 X-Mailer: Apple Mail (2.746.2) X-OriginalArrivalTime: 09 Feb 2006 09:50:06.0982 (UTC) FILETIME=[353A3260:01C62D5E] Gupta #1, et al. introduce a peer-to-peer system that guarantees one- hop lookups with high probability. While lookup time is greatly improved, each node pays a price by maintaining a routing table with information about every other node in the network. In order to guarantee one-hop lookups, it must be the case that every node knows about every other node. However, as the authors point out, full routing tables generally create problems because of the bandwidth required to maintain routing table consistency, not because of the physical sizes of the tables. Even in a large system with hundreds of thousands of nodes, the size of the routing table is manageable. To overcome the bandwidth consistency problems, the authors employ a trick for circulating routing table information much in the same was as most DHT systems perform O(log n) lookups. Thus, the multihop data is the system metadata rather than the lookups as is the case in similar systems. In the authors' theoretical model, the network has a three-tier hierarchy that functions as a three-level tree for propagating routing information. Nodes in a cluster, or slice, communicate with a common leader node, which communicates to leaders of other slices. As long as a change in the network state is guaranteed to be reflected among all the nodes within a certain bounded amount of time dependent on the number of tiers and the number of slices per tier, the authors prove that with bounded high probability (99% in the paper's example), the node contacted for a lookup will know the location of the requested object. The main problem with one hop lookups as presented is that the system is deceptively unscalable. Although the system can theoretically run with 10^5 or 10^6 nodes, a larger or smaller system would be inefficient unless many system-wide parameters were tweaked. Therefore, such a system could not grow from a small number of nodes to larger and larger sizes in an natural, dynamic way. Instead, a network administrator would have to assess the network and the machines involved in the network, decide on the number of tiers and slices, and then start all the nodes in the network. If the network ever grew significantly larger, the constant parameters would have to be readjusted. Another problem is that not all nodes are equal: each slice has a leader that must be more robust and support more traffic than other nodes in the slice. Leader nodes therefore act as critical points of failure. The paper suggests creating supernodes to serve this purpose for each slice, further complicating implementation. Gupta #2, et al., introduce a compromise between one-hop lookups and the O(log n) lookups with O(log n) routing tables as in Chord and Pastry. The system, called Kelips, clusters nodes into groups, called affinity groups, much in the same way one-hop lookups group nodes into slices. Each node then keeps O(n^(1/2)) pointers to other nodes, one in each other affinity group, as well as information about objects in its own affinity group. Thus, when a query comes in, a node can forward it to the correct affinity group in one hop, and that node can return the address of the node with the object, resulting in O(1) lookup time. Overall, the two papers present a common technique for decreasing lookup time without incurring a huge bandwidth cost. In general, the technique is to periodically disseminate routing information throughout the network and save more routing information at each node. Ryan From pjk25 Thu Feb 9 05:04:11 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=ham version=3.1.0 X-Spam-Level: Received: from authusersmtp.mail.cornell.edu (granite1.mail.cornell.edu [128.253.83.141]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k19A4Bt22905 for ; Thu, 9 Feb 2006 05:04:11 -0500 (EST) Received: from [10.0.1.2] (cpe-69-207-41-159.twcny.res.rr.com [69.207.41.159]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k19A4Aew017750 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT) for ; Thu, 9 Feb 2006 05:04:10 -0500 (EST) Mime-Version: 1.0 (Apple Message framework v746.2) To: egs+summary Message-Id: <1607BAAC-47B1-4F82-9703-6F5D5F679084> Content-Type: multipart/signed; micalg=sha1; boundary=Apple-Mail-1-111132357; protocol="application/pkcs7-signature" From: Philip Kuryloski Subject: PAPER 5 Date: Thu, 9 Feb 2006 05:06:45 -0500 X-Mailer: Apple Mail (2.746.2) --Apple-Mail-1-111132357 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=MACINTOSH; delsp=yes; format=flowed One Hop Lookups for Peer-to-Peer Overlays suggests a radical concept: =20= maintaining complete routing tables at each node allowing for one hop =20= routing between nodes. This scheme shares a similarity with Chord in =20= that nodes are consistently hashed to a ring shaped identifier space, =20= and keys within the network are associated with their successor node. Because all nodes maintain a routing table with entries for all other =20= nodes, efficient notification of joins and leaves/failures are =20 critical to avoid generating a tremendous amount of traffic. A three =20= level hierarchy of nodes is employed, with messages flowing down the =20 hierarchy and moving from predecessor to successor at the lowest =20 level. Messages are aggregated at the upper levels, and combined =20 with keep-alive messages at the lower levels. Differing from other DHT schemes, this is not a pure p2p network, as =20 more robust and well connected nodes are selected as members of the =20 upper levels of node hierarchy. If one of these nodes fails, =20 standard procedure is to for that nodes successor to assume that role. The primary limitation of this system is despite the imposed node =20 hierarchy, the amount of bandwidth needed to maintain node routing =20 tables is quite high, nearly 40kbps for a low level node in a million =20= node network. Coordinating nodes require more bandwidth, and =20 therefore cannot be randomly selected from any member in the network. Kelips, like the MIT proposed system, provides O(1) lookup times. =20 The authors of Kelips, however, argue that maintaining complete state =20= information at each node requires excessive memory and bandwidth. =20 Therefore, Kelips steps down from O(n) state per node to O(=C3n). =20 Kelips divides the identifier space into k =3D =C3n segments, called =20 affinity groups, and file/owner, called filetuple, relationships are =20 replicated across all nodes in the affinity group. Nodes also =20 maintain a small number of pointers to nodes in other affinity =20 groups, leading to O(1) lookup time. A gossip style protocol is used =20= for keeping filetuple entries fresh. Latency between nodes is =20 factored into the gossip protocol, with gossip tending towards faster =20= links. Gossip messages are also sent across affinity groups to =20 maintain far reaching links. Kelips trades increased state information at each node for faster =20 lookup times, however it does so with a less complex overlay =20 structure than CAN, Chord, Tapestry, and other O(log(n)) lookup =20 systems. This may be it's chief advantage over such networks, if the =20= underlying network can sustain the increased background traffic =20 associated with these O(1) lookup schemes.= --Apple-Mail-1-111132357 Content-Transfer-Encoding: base64 Content-Type: application/pkcs7-signature; name=smime.p7s Content-Disposition: attachment; filename=smime.p7s MIAGCSqGSIb3DQEHAqCAMIACAQExCzAJBgUrDgMCGgUAMIAGCSqGSIb3DQEHAQAAoIIGFjCCAs8w ggI4oAMCAQICAw+L7TANBgkqhkiG9w0BAQQFADBiMQswCQYDVQQGEwJaQTElMCMGA1UEChMcVGhh d3RlIENvbnN1bHRpbmcgKFB0eSkgTHRkLjEsMCoGA1UEAxMjVGhhd3RlIFBlcnNvbmFsIEZyZWVt YWlsIElzc3VpbmcgQ0EwHhcNMDUwOTI2MTc1NzM0WhcNMDYwOTI2MTc1NzM0WjBDMR8wHQYDVQQD ExZUaGF3dGUgRnJlZW1haWwgTWVtYmVyMSAwHgYJKoZIhvcNAQkBFhFwamsyNUBjb3JuZWxsLmVk dTCCASIwDQYJKoZIhvcNAQEBBQADggEPADCCAQoCggEBALFkgyhHSufUWaYxKh+wvUSDmrM8cViE JjeRS7Ssdd5tf0ckH2iwktNuSkxSsavsmAY+8zahwJjwk/JWTVyOGW/QsjgA5zoTJeAz4ah/QcKZ hou20lN6NvlFZWA43b4/jwtpVVa2RMS1fitkEs7YA9N16akGyXCpJR2i6EVTk7tx8/zf7i7bqg4t tmbJaySQyMQ4QV1O+F00m+zms0WZN5XRDqPwU2/WZfUE5BK/pGLkkFheBGSJJssuOsct8ctup0AI fJLlLZZhBCEdNeM2x9KfQEm+Tk3Ty0zl0pOewe7oW9vgwBJ2LwTVurzQ7qXeq1VhkDmkQJOwjcxM ssGAPXMCAwEAAaMuMCwwHAYDVR0RBBUwE4ERcGprMjVAY29ybmVsbC5lZHUwDAYDVR0TAQH/BAIw ADANBgkqhkiG9w0BAQQFAAOBgQBanW/NR5+pfeGOS7lM21kLObfzzGKtHvTFZ/RS0cSgWSKaCZfx aLLhqC9EFFFxh0b4wn0zCTv4CQWhrpaPZZC7oroP70kqWypQdjFbQ2rlLrVVS8pE4gtjZnRPFMr0 BEH+1K7kWB6kTHvg2eI1EotCI92yARGzlzKrXjPonHppijCCAz8wggKooAMCAQICAQ0wDQYJKoZI hvcNAQEFBQAwgdExCzAJBgNVBAYTAlpBMRUwEwYDVQQIEwxXZXN0ZXJuIENhcGUxEjAQBgNVBAcT CUNhcGUgVG93bjEaMBgGA1UEChMRVGhhd3RlIENvbnN1bHRpbmcxKDAmBgNVBAsTH0NlcnRpZmlj YXRpb24gU2VydmljZXMgRGl2aXNpb24xJDAiBgNVBAMTG1RoYXd0ZSBQZXJzb25hbCBGcmVlbWFp bCBDQTErMCkGCSqGSIb3DQEJARYccGVyc29uYWwtZnJlZW1haWxAdGhhd3RlLmNvbTAeFw0wMzA3 MTcwMDAwMDBaFw0xMzA3MTYyMzU5NTlaMGIxCzAJBgNVBAYTAlpBMSUwIwYDVQQKExxUaGF3dGUg Q29uc3VsdGluZyAoUHR5KSBMdGQuMSwwKgYDVQQDEyNUaGF3dGUgUGVyc29uYWwgRnJlZW1haWwg SXNzdWluZyBDQTCBnzANBgkqhkiG9w0BAQEFAAOBjQAwgYkCgYEAxKY8VXNV+065yplaHmjAdQRw nd/p/6Me7L3N9VvyGna9fww6YfK/Uc4B1OVQCjDXAmNaLIkVcI7dyfArhVqqP3FWy688Cwfn8R+R NiQqE88r1fOCdz0Dviv+uxg+B79AgAJk16emu59l0cUqVIUPSAR/p7bRPGEEQB5kGXJgt/sCAwEA AaOBlDCBkTASBgNVHRMBAf8ECDAGAQH/AgEAMEMGA1UdHwQ8MDowOKA2oDSGMmh0dHA6Ly9jcmwu dGhhd3RlLmNvbS9UaGF3dGVQZXJzb25hbEZyZWVtYWlsQ0EuY3JsMAsGA1UdDwQEAwIBBjApBgNV HREEIjAgpB4wHDEaMBgGA1UEAxMRUHJpdmF0ZUxhYmVsMi0xMzgwDQYJKoZIhvcNAQEFBQADgYEA SIzRUIPqCy7MDaNmrGcPf6+svsIXoUOWlJ1/TCG4+DYfqi2fNi/A9BxQIJNwPP2t4WFiw9k6GX6E sZkbAMUaC4J0niVQlGLH2ydxVyWN3amcOY6MIE9lX5Xa9/eH1sYITq726jTlEBpbNU1341YheILc IRk13iSx0x1G/11fZU8xggLnMIIC4wIBATBpMGIxCzAJBgNVBAYTAlpBMSUwIwYDVQQKExxUaGF3 dGUgQ29uc3VsdGluZyAoUHR5KSBMdGQuMSwwKgYDVQQDEyNUaGF3dGUgUGVyc29uYWwgRnJlZW1h aWwgSXNzdWluZyBDQQIDD4vtMAkGBSsOAwIaBQCgggFTMBgGCSqGSIb3DQEJAzELBgkqhkiG9w0B BwEwHAYJKoZIhvcNAQkFMQ8XDTA2MDIwOTEwMDY0NlowIwYJKoZIhvcNAQkEMRYEFJXG31uq1cuY uuj9Xy2IAaytWxlkMHgGCSsGAQQBgjcQBDFrMGkwYjELMAkGA1UEBhMCWkExJTAjBgNVBAoTHFRo YXd0ZSBDb25zdWx0aW5nIChQdHkpIEx0ZC4xLDAqBgNVBAMTI1RoYXd0ZSBQZXJzb25hbCBGcmVl bWFpbCBJc3N1aW5nIENBAgMPi+0wegYLKoZIhvcNAQkQAgsxa6BpMGIxCzAJBgNVBAYTAlpBMSUw IwYDVQQKExxUaGF3dGUgQ29uc3VsdGluZyAoUHR5KSBMdGQuMSwwKgYDVQQDEyNUaGF3dGUgUGVy c29uYWwgRnJlZW1haWwgSXNzdWluZyBDQQIDD4vtMA0GCSqGSIb3DQEBAQUABIIBAJgtUQ/vMAY7 i1OFaZTEB8XmlC0MmJn0JgFLFMBA8a+9cw9Yje2WVWqR0LSE9gPlUFBA0zijjRfZwwck8MeRTt3I WFfaSOqa/eRIEZXeMIl4Fhc1+A21T64P+5Ha15m524eOqHoW0MA2tKQ1UHWXU1HJPT4HnAhCD1HB iitR1Y6aAZ2nOJsjaHKqornmYOJA27Titj3BKzYvmlhK5uvb+nH342dHZcZt3iga+/pWj4swIULe 5VpIrDT3+g5f8AmqcMJoq19BaMv56T5AG0bHpJGwOstYNx1FgC/7f2bZ6ua0quIjmT3J9ZA8Am/L z+6yR8h+5eOmFw5K1o0IDzNB4OgAAAAAAAA= --Apple-Mail-1-111132357-- From gp72 Thu Feb 9 10:15:29 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=ham version=3.1.0 X-Spam-Level: Received: from postoffice10.mail.cornell.edu (postoffice10.mail.cornell.edu [132.236.56.14]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k19FFSt06259 for ; Thu, 9 Feb 2006 10:15:28 -0500 (EST) Received: from webmail.cornell.edu (hermes21.mail.cornell.edu [132.236.56.20]) by postoffice10.mail.cornell.edu (8.12.10/8.12.6) with ESMTP id k19FFQ86009068 for ; Thu, 9 Feb 2006 10:15:27 -0500 (EST) Received: from 128.253.122.16 by webmail.cornell.edu with HTTP; Thu, 9 Feb 2006 10:15:27 -0500 (EST) Message-ID: <1314.128.253.122.16.1139498127.squirrel@webmail.cornell.edu> In-Reply-To: <103627068.1138897326162.JavaMail.webber@orpheus3.dataserver.cornell.e du> References: <103627068.1138897326162.JavaMail.webber@orpheus3.dataserver.cornell.edu> Date: Thu, 9 Feb 2006 10:15:27 -0500 (EST) Subject: PAPER 5 From: "Gopal Parameswaran" To: egs+summary User-Agent: SquirrelMail/1.4.5 MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Priority: 3 (Normal) Importance: Normal One Hop lookup is a peer to peer algorithm where all lookups are done in one hop by storing all node lookup information at all nodes and where node information is propagated to all the other nodes at regular interval in a compact way to avoid excessive bandwidth usage. This results in a one hop lookup for a destination node and hence the search algorithm is faster since the latency is greatly reduced. For updation of all the nodes with regards to a node joining or leaving the system the ring is broken up into k equal contiguous intervals called slices and each slice is broken up into units. A super node is chosen at each slice called slice leader and similary unit leaders are chosen grouped under slice leaders. A slice leader gets updated at certain specified intervals by the units in it and each unit gets updated at certain intervals by the nodes that are contained in the unit. Thus information regarding changes in the nodes in the slice is propagated to the slices and each slice sends the information out to all the slices at a certain interval and in a compact manner. This helps keep all the nodes routing tables updated with the latest node states at the expense of pressure on the bandwidth. However since the information is send in a compact manner the bandwidth usage is not that high as it appears but as the number of nodes is increased beyond a million nodes it becomes higher. However the system is not really fault tolerant since if a set of local units go down then all nodes associated with the unit leader would be lost since each unit leader only maintains a list of pointers to its child nodes. There would be no way in this system to recover from such failures. This failure would take on a much higher proportion if any of the slice leaders fail. Also an assumption is made that failures at the splice leader and node leader level will not occur frequently which might not be the case unless they are highly reliable nodes and in a real application it would be essential to have a reliable splice leader since if it goes down it would bring down a portion of the network with itself till the particular slice leader is restored back or the alternate splice leader has taken over. Node additions to this network would be simple and when new nodes are added to the system then the node information is passed on via the same layers of slice leader and unit leader to all nodes. To conclude this network while reducing the overheads on an average for searching at the cost of increased overheads to maintain the network is an effective way for one hop routing though its performance at high level of nodes of 10^10 etc would be slow since the effect on bandwidth would be high. Similarly, the pressure of maintaing the networks are on a few nodes which if they go down would bring the network down with them. From km266 Thu Feb 9 10:37:20 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=ham version=3.1.0 X-Spam-Level: Received: from authusersmtp.mail.cornell.edu (granite1.mail.cornell.edu [128.253.83.141]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k19FbKt12134 for ; Thu, 9 Feb 2006 10:37:20 -0500 (EST) Received: from KEVSTOY (cpe-69-207-37-68.twcny.res.rr.com [69.207.37.68]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k19FbI0j006758 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NOT) for ; Thu, 9 Feb 2006 10:37:19 -0500 (EST) Message-ID: <000301c62d8e$c2ab4cd0$4425cf45@KEVSTOY> Reply-To: "Kevin" From: "Kevin" To: Subject: PAPER 5 Date: Thu, 9 Feb 2006 10:37:39 -0500 MIME-Version: 1.0 Content-Type: text/plain; format=flowed; charset="iso-8859-1"; reply-type=original Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2900.2527 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2527 One hop lookups works on the principle that most nodes can store O(n) state without a problem, as long as updates are done without occupying too much bandwidth. If joins/leaves were disseminated through the network as soon as they occurred, this would be unreasonable. To overcome this, Gupta et al propose a tree-like structure buried in a multi-tiered ring. The outermost ring will hold only those machines that are capable, in bandwidth and cpu, of being supernodes. Supernodes, or slice leaders, are the parent of the tree structure. Their main goal is to gather and, with a time delay, update their children nodes called unit leaders and other roots (other slice leaders). These unit leaders then, once again with a time delay, update all the nodes in their unit. The regular units have pointers to their succ and pred and can pass this information down to the next one with their normal keep-alive heartbeat. By breaking the entire population up into slices and those slices into units and by imposing a hierarchy in the system that allows them to not duplicate messages, they are able to do one hop routing while maintaining O(n) state. The paper focuses very heavily on making sure the slice leaders have enough bandwidth and cpu to keep the system going. While 350kpbs (in a 10^6 size system) is not trivial, a well-provisioned corporate or educational institute should have no problem with that bandwidth. Even newer cable modems and in-home fiber systems handle this information without a hiccup. I see the biggest issue at the regular nodes. In a 10^6 size system, regular nodes experience 38.4kbps just to keep the network up. A regular 56k modem would not be able to handle that! Since it is 38.4kpbs up and down (76.8 total), no average user would be able to support this. Even my broadband connection at home with 1mbits/128kpbs usually maxes out at 100kpbs upload and the system takes up over a third of my bandwidth just for updates. Imagine what would happen with a latency spike! Forgetting the security and other concerns, the core of the paper seems flawed, it is completely unpractical. Kelips, like the above paper, also sacrifices state for lookup time. The idea is to partition the entire space into sqrt(n) 'affinity groups,' each containing sqrt(n) nodes. Each affinity group is responsible for a certain subset of data and each node in an affinity group knows all the other nodes and all the data being stored in the group. A node is chosen at random from the group to store the data. A heartbeat and other information are also stored about group members, along with a couple of pointers to randomly selected nodes in each other affinity group. In this way, using consistent hashing, you can route a request to any affinity group in 2 hops: 1 to get to the affinity group with your group-pointer and then 1 more to get to the actual node in the group that stores the information. O(1) routing is achieved using sqrt(n) space. The biggest issue I saw with this paper is the slow dispersal of data. Even the one-hop routing paper noted that Kelips takes nearly an hour to update the routing tables. While this keeps bandwidth usage low, it makes for lots of miss-routed messages when the system is undergoing churn (which a p2p system would be expected to have). The other issue I seem to have with this paper is they never detail how well the system scales past 10,000 nodes. Almost all papers we have read which discuss empirical results use node numbers 10 or 100 times that. Overall, I think the paper is right in saying that more state and fewer hops are better, but I don't think they hit the nail on the head yet. --Kevin From nsg7 Thu Feb 9 10:49:38 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=ham version=3.1.0 X-Spam-Level: Received: from authusersmtp.mail.cornell.edu (granite1.mail.cornell.edu [128.253.83.141]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k19Fnct16472 for ; Thu, 9 Feb 2006 10:49:38 -0500 (EST) Received: from [127.0.0.1] (cpe-24-59-77-191.twcny.res.rr.com [24.59.77.191]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k19Fna0O019077 for ; Thu, 9 Feb 2006 10:49:37 -0500 (EST) Message-ID: <43EB6504.1020609> Date: Thu, 09 Feb 2006 10:51:32 -0500 From: Nick Gerner User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: egs+summary Subject: PAPER 5 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit in "One Hop..." A. Gupta et al. and in "Kelips..." I. Gupta et al. both suggest that one-hop lookups are possible in DHTs by maintaing O(n) connectivity at all nodes in the overlay. "One Hop..." begins by presenting results of a study on some existing P2P networks suggesting that sizes are between 10^5 and 10^6 and that membership changes can occur at a rate of about 19 per second. With these numbers maintaing O(n) connectivity at all nodes is feasible with modern systems (10^6 32-bit IP addresses takes ~3.8 MB of memory). Maintaining this connectivity is the problem which both papers approach (as opposed to how to efficiently route lookups as we've seen in previous papers). In "One Hop..." every node has connectivity with nearly all other nodes. To maintain this connectivity nodes are organized into k two level trees (k slices each of u units). Every node is responsible for sending keep-alive messages with either it's successor (on an identifier ring, also used for consistent hashing as before) or it's predecessor. The choice is made so that information flows from a unit leader (center of the unit division of the identifier ring) outward, without crossing unit boundaries. When a new member enters or a member fails notification of this message is sent directly to the detecting node's slice leader. The slice leader aggregates events occuring within some time division and sends the aggregated information to other slice leaders. Each slice leader then sends its aggregated information to unit leaders which then piggybacks the information on the keepalives flowing out of it toward unit boundaries. The claim is that this eliminates redundant communication. Kelips also maintains nearly full connectivity between all nodes. However, nodes are divided into k affinity groups (continguous groups over the identifier ring). Nodes within an affinity group maintain full connectivity. Kelips choose k=O(sqrt(n)) to analytically optimize performance. Some connections between groups are also maintained in contact groups at each node (chosen to minimize rtt). Queries can thus be routed in 2 hops (one to reach the correct affinity group via a contact and one to reach the correct destination via full connectivity). Connectivity is maintained by using a epidemic-gossip protocol where new events are propegated fully within an affinity group and occasionally across groups via contacts. Gossip bandwidth is arbitrarily fixed at a certain level. Events not gossiped in the allotted bandwidth are preserved for another round of gossiping. Both papers present schemes that potentially provide very low latency lookups. However, this is a tradeoff made with respect to the amount of state that must be stored (reasonable for modern machines) and also the amount of bandwidth spent to maintain that state. "One Hop..." admits that in a 10^6 node network (the size of Napster at the time) requires a slice leader to use 350kbps upstream bandwidth to disseminate events. This is strong motivation for nodes to misbehave. And even if they do obey the protocol (at high personal cost to the node) the problem of churn in system like this is aggrevated since a failed node causes some kind of failure (and maintenace costs) at all other nodes. Kelips limits the bandwidth arbitrarily so one could say that maintenance overhead is capped; however, it's not clear that arbitrarily capping this bandwidth will allow sufficient bandwidth to maintain nearly full connectivity (or O(sqrt(n)) connectivity), especially in the face of churn. From sh366 Thu Feb 9 11:00:55 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=ham version=3.1.0 X-Spam-Level: Received: from postoffice10.mail.cornell.edu (postoffice10.mail.cornell.edu [132.236.56.14]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k19G0st20090 for ; Thu, 9 Feb 2006 11:00:55 -0500 (EST) Received: from orpheus3.dataserver.cornell.edu (orpheus3.dataserver.cornell.edu [128.253.161.167]) by postoffice10.mail.cornell.edu (8.12.10/8.12.6) with ESMTP id k19G0rIf010274 for ; Thu, 9 Feb 2006 11:00:53 -0500 (EST) Message-ID: <329903805.1139500853018.JavaMail.webber@orpheus3.dataserver.cornell.edu> Date: Thu, 9 Feb 2006 11:00:53 -0500 (EST) From: Huang Shiang-Jia To: egs+summary Subject: PAPER 5 Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 X-Mailer: uPortal WEB email client 3.0 Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id k19G0st20090 * One-Hop enables routing lookup queries in one hop by maintaining complete routing tables in each node. It superimposes a hierarchy, by dividing the identifier space to ‘slices’ and ‘units’, to notify every node the events of membership changes. * According to the fraction of failed queries, total number of nodes and the rate of membership changes, One-Hop tunes the time period to deliver notifications, by adjusting the number of slices (k) and units (u), to minimize bandwidth consumption. * One-Hop is attractive in small systems that can’t tolerate the delay of multi-hop routing. * One-Hop imposes a hierarchical structure, which intuitively contradict the principle of peer-to-peer system. * The slice leaders and unit leaders serve as single point of failures. They may be replaced when failed, but once compromised they can disguise the routing information in a region that nodes in the region can't detect. * Kelips uses O(n^(1/2)) space per node, a larger memory usage (than Pastry/Chord/Tapestry), along with constant background communication overheads, to resolve lookups in O(1) time and message complexity in normal cases. * Kelips is loosely-structured; it consists of virtual affinity groups. It differs from Pastry/Chord/Tapestry in that: Multiple nodes in an affinity group, rather than one single node, are responsible for a file/object’s information. Consistency and freshness of information is achieved by the heartbeating mechanism that originates at the responsible nodes and disseminates through an epidemic-style (gossip-style) protocol. * The memory storage, S(k,n), and background overheads don’t scale well to a very large system. From kelvinso Thu Feb 9 11:42:01 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-0.8 required=5.0 tests=ALL_TRUSTED,AWL,HTML_MESSAGE autolearn=ham version=3.1.0 X-Spam-Level: Received: from exchfe1.cs.cornell.edu (exchfenlb-1.cs.cornell.edu [128.84.97.33]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k19Gg1t04124 for ; Thu, 9 Feb 2006 11:42:01 -0500 (EST) Received: from EXCHVS1.cs.cornell.edu ([128.84.97.23]) by exchfe1.cs.cornell.edu with Microsoft SMTPSVC(6.0.3790.1830); Thu, 9 Feb 2006 11:39:51 -0500 Content-class: urn:content-classes:message MIME-Version: 1.0 X-Security: message sanitized on sundial.cs.cornell.edu See http://www.impsec.org/email-tools/sanitizer-intro.html for details. $Revision: 1.148 $Date: 2004-12-19 11:59:17-08 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="----_=_NextPart_001_01C62D97.72850BE7" Subject: Paper 5 X-MimeOLE: Produced By Microsoft Exchange V6.5 Date: Thu, 9 Feb 2006 11:39:50 -0500 Message-ID: <2AA53C9C489B0049B43E56D28088677B40CD01@EXCHVS2.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: Paper 5 thread-index: AcYtYviI/V17V28iQZ2rr1228s72BQ== From: "Kelvin So" To: X-OriginalArrivalTime: 09 Feb 2006 16:39:51.0562 (UTC) FILETIME=[72C766A0:01C62D97] This is a multi-part message in MIME format. ------_=_NextPart_001_01C62D97.72850BE7 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable One Hop has similar ring-like structure as Chord. One Hop maintains a routing table size of all the members to achieve lookup time = of one hop. In order to reduce bandwidth in the keep-alive messages, One = Hop uses a three-tier hierarchical structure to disseminate membership = changes. The circular identification space is divided into slices, and there is a slice leader in each of them. Slices are partitioned into units with = unit leader in the middle of each unit. Slice leader aggregates all the = membership changes and periodically sends to other slice leader. Once the slice = leader receives the membership changes, it forwards the changes to all the unit leaders in the slice. Finally unit leader will propagate the changes to = the successor and predecessor. The paper analyzes the bandwidth cost of the system and reasons the systems can scale more than 10^5 nodes. However, = with the hierarchical structure, the leaders will have a higher load than = other nodes. Also, if the leader is attacked or malicious, a large potion of = the nodes will be affected. Instead of using hierarchical structure to disseminate = membership changes, Kelips uses gossip protocol instead. Kelips divides the identification space into n^(1/2) affinity groups. A node is mapped to = an affinity group, and the node in the affinity group will have knowledge = about the location of files in the group. The membership changes is spread = using two-level gossiping scheme. Kelips average lookup time is also O(1). = However, it takes some times to propagate changes in the affinity group using = gossip protocol, which can lead to result inconsistency.=20 =20 ------_=_NextPart_001_01C62D97.72850BE7 Content-Type: text/html; charset="us-ascii" Content-Transfer-Encoding: quoted-printable -->

           = ; One Hop has similar ring-like structure as Chord. One Hop maintains a = routing table size of all the members to achieve lookup time of one hop. In order to = reduce bandwidth in the keep-alive messages, One Hop uses a three-tier = hierarchical structure to disseminate membership changes. The circular identification = space is divided into slices, and there is a slice leader in each of them. = Slices are partitioned into units with unit leader in the middle of each unit. = Slice leader aggregates all the membership changes and periodically sends to = other slice leader. Once the slice leader receives the membership changes, it forwards the changes to all the unit leaders in the slice. Finally unit = leader will propagate the changes to the successor and predecessor. The paper = analyzes the bandwidth cost of the system and reasons the systems can scale more = than 10^5 nodes. However, with the hierarchical structure, the leaders will = have a higher load than other nodes. Also, if the leader is attacked or = malicious, a large potion of the nodes will be affected.

           = ; Instead of using hierarchical structure to disseminate membership = changes, Kelips uses gossip protocol instead. Kelips divides the identification = space into n^(1/2) affinity groups. A node is mapped to an affinity group, and = the node in the affinity group will have knowledge about the location of = files in the group. The membership changes is spread using two-level gossiping = scheme. Kelips average lookup time is also O(1). However, it takes some times to propagate changes in the affinity group using gossip protocol, which can = lead to result inconsistency.

 

------_=_NextPart_001_01C62D97.72850BE7-- From niranjan.sivakumar@gmail.com Tue Feb 14 01:04:43 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=ham version=3.1.0 X-Spam-Level: Received: from xproxy.gmail.com (xproxy.gmail.com [66.249.82.204] (may be forged)) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k1E64gt04969 for ; Tue, 14 Feb 2006 01:04:42 -0500 (EST) Received: by xproxy.gmail.com with SMTP id h30so781353wxd for ; Mon, 13 Feb 2006 22:04:42 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:reply-to:to:subject:date:user-agent:organization:mime-version:content-type:content-transfer-encoding:content-disposition:message-id:from; b=bOMTjKmm2udCm4Vi00cIFxG7+e4Ul/+vsHIDDJVgTDIcmBiMZWnt9iHVxDgZCZ/O6T8jIiQOiTynK48J+cfSPwFuh/oUxiHsLbGca0DDjaaJffa5T7+F51EVzxv5kuZjWC57K5otOZ+pjSvqZahIJPgZ+vY5ciFilLNwQ+GySHk= Received: by 10.70.103.19 with SMTP id a19mr3500155wxc; Mon, 13 Feb 2006 22:04:42 -0800 (PST) Received: from ?192.168.0.101? ( [69.207.63.116]) by mx.gmail.com with ESMTP id h37sm6365489wxd.2006.02.13.22.04.41; Mon, 13 Feb 2006 22:04:42 -0800 (PST) Reply-To: ns253@cornell.edu To: egs+summary@cs.cornell.edu Subject: PAPER 5 Date: Tue, 14 Feb 2006 01:04:40 -0500 User-Agent: KMail/1.9 Organization: Cornell University MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200602140104.40846.ns253@cornell.edu> From: Niranjan Sivakumar Niranjan Sivakumar Search and Replication in Unstructured Peer-to-Peer Networks Beehive: O(1) Lookup Performance for Power-Law Query Distributions in Peer-to-Peer Overlays The paper regarding search and replication in unstructured p2p networks considers the idea of improving performance in generally unstructured networks such as Gnutella. Through a series of simulations they illustrate the drawbacks of two popular search methods, flooding and expanding ring, and provide some analysis of two variants of a random walk search. The random walk algorithm that would check back to the originating node to terminate generally performed better than the other approaches in their tests. They also considered replication, and considered two somewhat intuitive approaches, uniform and proportional replication, as well as square-root replication. Although they admit that implementing a square-root replication method is not trivial, their tests show that this method may be more "fair" and a better solution than the others. Beehive does not do away with the idea of structured p2p networks, and instead seeks to exploit the underlying mechanism of a ring-based architecture like that of Pastry to implement a relatively simple method of proactive replication that could lead to sub-one hop routing. An analytical solution that is provided in the paper allows for designers to tune the system for some desired level of performance. The system uses prefix-matching and the idea that the number of hops can be reduced by progressively replicating files at nodes that share one less prefix than the current node that is holding the object. However, Beehive does not require a great deal of coordination between nodes when making replication decisions, even as objects fan out. The system also has a mechanism to evaluate the popularity of a node in order to determine what level an object should be replicated out to. One of the drawbacks in the Search and Replication paper seems to be their very premise as to why they are focusing on unstructured networks instead of structured networks. One of their main reasons seems to simply be that few currently available networks are structured. Furthermore, while their theoretical results are interesting, they themselves indicate that it is quite basic and the take away from the paper seems to be generally applicable "good ideas" for selecting or developing search and replication algorithms. They also did not really provide an exhaustive analysis of algorithms, as they just selected a small sample to test. One issue that I noted in the Beehive paper is related to incentives for maintaining cached copies of objects. Although there is an alternate to hold links instead of an object itself, if the goal is to avoid a "slashdot effect" as is stated in the paper, then it seems that maintaining actual copies would be quite important. Since the system seems to be pushing copies on to nodes that may not actually have any relationship with the content, this could create some issues with getting willing participants in such a network.