From asg46  Wed Feb  8 20:17:58 2006
Return-Path: <asg46>
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 k191Hwt08132
	for <egs+summary>; Wed, 8 Feb 2006 20:17:58 -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 k191Hv1b006616
	for <egs+summary>; Wed, 8 Feb 2006 20:17:57 -0500 (EST)
Received: from 128.84.98.90
        by webmail.cornell.edu with HTTP;
        Wed, 8 Feb 2006 20:17:57 -0500 (EST)
Message-ID: <1716.128.84.98.90.1139447877.squirrel@webmail.cornell.edu>
Date: Wed, 8 Feb 2006 20:17:57 -0500 (EST)
Subject: paper 6 - O(1)
From: "Abhishek Santosh Gupta" <asg46>
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 LOOKUPS



BASIC STRUCTURE:

every node randomly chooses a 128-bit node identifier resulting in the
formation of a ring.
the ring is divided into k contiguous intervals called slices. each slice
has a slice leader which is dynamically chosen as the successor of the
mid-point of the slice identifier space.

each slice is subdivided into u equal units. Each unit has a unit leader
which is dynamically chosen as the successor of the mid-point of the slice
identifier space.


NODE STATE : each node stores O(n) state. using odinary pinging mechansims
"keep alive" messages would  consume considerable bandwidth- however the
above structure helps to reduce this b/w consumption.

this results in O(1) lookup for most queries ( f is defined fraction). A
query fails in its first attempt only if the notification due to
membership change does not reach the querying node before the
query.



INFORMATION FLOW:
1) whenever a node detects a change in membership(due to failed successor
or new node) it sends a message to its slice leader
2) the slice leader collects all such messages aggregates them for tbig
before sending to other slice leaders
(note that communication between different slice leaders is not synchronized)
3) each slice leader aggreates the messages that it recieves for twait and
then dispatches the aggregate message to
unit leaders.
4) information now flows within each unit such that if flows always away
from the unit leader to the end of the unit.

CHOOSING VALUES:
the authors represent all variables in the form of 2 independent variables
k and u and optimise the amount of b/w required for this entire
information flow process stated above.


leaders require more bandwidth than an odinary node. the authors suggest
that some nodes could be classified as "super nodes" provided they satisfy
required bandwidth criteria which seems pretty reasonable.

POTENTIAL FLAWS:

The authors mention that when a slice or unit leader fails, its successor
detects this failure and becomes the new leader. It will also communicate
with remaining nodes for missed events.
However, the authors do not discuss as to what protocol should be carried
out if a slice leader fails just before twait i.e. it has aggregated a set
of messages (to which it has also sent ack) - these messages would be lost
unless the sending node buffers the message even after receiving the
acknowledgement.

a similar situation also arises if a slice leader fails before tbig.
in both cases, buffering should be sufficient, however increasing the
lookup time for a certain set of queries.
note that the interval at which the buffer can be reused is at the max
total information flow cycle time (ttot)



From kash@cs.cornell.edu  Mon Feb 13 17:04:38 2006
Return-Path: <kash@cs.cornell.edu>
X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on 
	sundial.cs.cornell.edu
X-Spam-Status: No, score=-1.0 required=5.0 tests=ALL_TRUSTED,AWL,HTML_10_20,
	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 k1DM4ct26399
	for <egs@unix.cucs>; Mon, 13 Feb 2006 17:04:38 -0500 (EST)
Received: from EXCHVS1.cs.cornell.edu ([128.84.97.23]) by exchfe1.cs.cornell.edu with Microsoft SMTPSVC(6.0.3790.1830);
	 Mon, 13 Feb 2006 17:04:38 -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_01C630E9.7B4FCF27"
X-MimeOLE: Produced By Microsoft Exchange V6.5
Subject: PAPER 6
Date: Mon, 13 Feb 2006 17:04:38 -0500
Message-ID: <2EE48095D8C21643B0B70EC95F9BFBAF0EE63A@EXCHVS1.cs.cornell.edu>
X-MS-Has-Attach: 
X-MS-TNEF-Correlator: 
Thread-Topic: PAPER 6
thread-index: AcYw6XtGRuovWLXOQs2tl2FyzaAbzg==
From: "Ian Kash" <kash@cs.cornell.edu>
To: <egs+summary@cs.cornell.edu>
X-OriginalArrivalTime: 13 Feb 2006 22:04:38.0072 (UTC) FILETIME=[7B4BDB80:01C630E9]

This is a multi-part message in MIME format.

------_=_NextPart_001_01C630E9.7B4FCF27
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable

Lv et. al. examine a pair of search methods that are superior to =
flooding in
unstructured P2P networks.  The first is expanding ring, which is =
essentially
flooding with an iteratively deepening TTL (which fixes the problem of
finding the right TTL).  The second is a number of random walks on the =
graph,
which gives two orders of magnitude improvement in search costs for =
realistic
graph models.  This has the nice side effect of supporting partial =
searches
because the walkers "call home" to see if they should continue so the =
user
can decide when the partial search has produced sufficient results.  =
They
then examine the effects of replication in their models.  Their results =
show
that uniform replication and replication proportional to the query =
frequency
give the same weighted average performance.  However, replicating
proportional to the square root of the query frequency gives optimal
performance.  The downside is that this proportion is difficult to =
implement.

The claims about the implementation square root replication are =
theoretically
shaky (though their results show that it is an improvement in practice). =
 In
particular, they say that it their path replication system is described =
by a
differential equation that has a fixed point corresponding to the sqrt =
n.
This immediately raises several issues.  Is this the only fixed point?  =
If
not, why should the system converge to it rather than some other?  Is it =
even
stable (i.e will the system converge to it from nearby or do you tend to
drift farther away once you get a little distance away)?  If the system =
does
converge to this fixed point, how long will it take?  In their =
evaluation,
they seemingly arbitrarily wait 5000s in Figure 7, but it is unclear how =
this
extends beyond the specific settings of their simulation.  This =
convergence
rate is of practical importance, because the rate will effect the =
ability of
the system to handle sudden changes in request frequency.

Beehive is a replication system built on top of a structured DHT that
provides O(1) lookups by exploiting the search patterns of the DHT.  =
Since
there is a deterministic set of possible paths to an object, Beehive can
shorten every path by one hop by replicating the object at every node =
one hop
back along one of these paths.  Using a closed-form optimal solution to =
a
system of equations, Beehive can provide average lookup of c hops for =
any
constant c while still having the worst case O(log n) hops provided by
Pastry.  Experimental results show significant performance improvements =
over
Pastry with passive caching of objects at every node along a query path
(PC-Pastry).  Once concern is that Figure 6 shows that after a large =
change
in object popularity, Beehive's latency rises to that of PC-Pastry and =
takes
longer to return to its basely.  If the popularity of objects is =
constantly
changing, this may lead to no improvement in latency over Pastry =
(although it
will still have significantly fewer object transfers).

------_=_NextPart_001_01C630E9.7B4FCF27
Content-Type: text/html; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<DEFANGED_META HTTP-EQUIV=3D"Content-Type" CONTENT=3D"text/html; =
charset=3Diso-8859-1">
<DEFANGED_META NAME=3D"Generator" CONTENT=3D"MS Exchange Server version =
6.5.7638.1">
<TITLE>PAPER 6</TITLE>
</HEAD>
<BODY>
<!-- Converted from text/plain format -->

<P><FONT SIZE=3D2>Lv et. al. examine a pair of search methods that are =
superior to flooding in unstructured P2P networks.&nbsp; The first is =
expanding ring, which is essentially flooding with an iteratively =
deepening TTL (which fixes the problem of finding the right TTL).&nbsp; =
The second is a number of random walks on the graph, which gives two =
orders of magnitude improvement in search costs for realistic graph =
models.&nbsp; This has the nice side effect of supporting partial =
searches because the walkers &quot;call home&quot; to see if they should =
continue so the user can decide when the partial search has produced =
sufficient results.&nbsp; They then examine the effects of replication =
in their models.&nbsp; Their results show that uniform replication and =
replication proportional to the query frequency give the same weighted =
average performance.&nbsp; However, replicating proportional to the =
square root of the query frequency gives optimal performance.&nbsp; The =
downside is that this proportion is difficult to implement.<BR>
<BR>
The claims about the implementation square root replication are =
theoretically shaky (though their results show that it is an improvement =
in practice).&nbsp; In particular, they say that it their path =
replication system is described by a differential equation that has a =
fixed point corresponding to the sqrt n.&nbsp; This immediately raises =
several issues.&nbsp; Is this the only fixed point?&nbsp; If not, why =
should the system converge to it rather than some other?&nbsp; Is it =
even stable (i.e will the system converge to it from nearby or do you =
tend to drift farther away once you get a little distance away)?&nbsp; =
If the system does converge to this fixed point, how long will it =
take?&nbsp; In their evaluation, they seemingly arbitrarily wait 5000s =
in Figure 7, but it is unclear how this extends beyond the specific =
settings of their simulation.&nbsp; This convergence rate is of =
practical importance, because the rate will effect the ability of the =
system to handle sudden changes in request frequency.<BR>
<BR>
Beehive is a replication system built on top of a structured DHT that =
provides O(1) lookups by exploiting the search patterns of the =
DHT.&nbsp; Since there is a deterministic set of possible paths to an =
object, Beehive can shorten every path by one hop by replicating the =
object at every node one hop back along one of these paths.&nbsp; Using =
a closed-form optimal solution to a system of equations, Beehive can =
provide average lookup of c hops for any constant c while still having =
the worst case O(log n) hops provided by Pastry.&nbsp; Experimental =
results show significant performance improvements over Pastry with =
passive caching of objects at every node along a query path =
(PC-Pastry).&nbsp; Once concern is that Figure 6 shows that after a =
large change in object popularity, Beehive's latency rises to that of =
PC-Pastry and takes longer to return to its basely.&nbsp; If the =
popularity of objects is constantly changing, this may lead to no =
improvement in latency over Pastry (although it will still have =
significantly fewer object transfers).</FONT></P>

</BODY>
</HTML>
------_=_NextPart_001_01C630E9.7B4FCF27--

From asr32@cornell.edu  Mon Feb 13 20:12:16 2006
Return-Path: <asr32@cornell.edu>
X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on 
	sundial.cs.cornell.edu
X-Spam-Status: No, score=0.5 required=5.0 tests=AWL,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 k1E1CGt15922
	for <egs+summary@cs.cornell.edu>; Mon, 13 Feb 2006 20:12:16 -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 k1E1CF3h006670
	(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT)
	for <egs+summary@cs.cornell.edu>; Mon, 13 Feb 2006 20:12:16 -0500 (EST)
Message-Id: <6.2.1.2.2.20060212161233.034e6fb8@postoffice8.mail.cornell.edu>
X-Mailer: QUALCOMM Windows Eudora Version 6.2.1.2
Date: Mon, 13 Feb 2006 20:14:23 -0500
To: egs+summary@cs.cornell.edu
From: Ari Rabkin <asr32@cornell.edu>
Subject: PAPER 6
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"; format=flowed


"Search and Replication in Unstructured P2P networks"

         Whereas most DHT papers leave replication to the application 
layer, this paper discusses the proper number and placement of replicas in 
unstructured networks, and also the best way to do queries across these 
networks.  The authors show that flood searches, and expanding ring, are 
both very network-intensive, and that controlled random walk is much more 
frugal with bandwidth for equivalent search quality.  The authors also 
propose a new replication scheme, with the number of replicas of an object 
proportional to the square root of the query frequency.  They show that 
this scheme is optimal in terms of search size (and thus total network 
load).  They also show that path replication can achieve this replication, 
and greatly improve performance.
         Square-root replication is only valid insofar as the assumptions 
are valid.  Gnutella is substantially a file-sharing system, and users do 
not delete files randomly.  Controlled Random-walk, while a good idea, is 
probably not practical for gnutella since the installed systems do not 
support it.  If we're going to be altering the existing gnutella installed 
base, why not go to a structured system in the first place?

Beehive:
         Beehive is in many ways the counterpart for structured P2P 
systems.  It offers a mathematical analysis, and an optimal replication 
scheme under certain assumptions: In particular, the authors assume that 
object replication has a fixed cost.  The Beehive authors show that the 
optimum replication degree can be computed analytically given the item 
frequency and the zipf-law parameter; they show that these can be measured 
efficiently at runtime by aggregating statistics, and then doing linear 
regression.  Beehive then pushes the updated objects out along the routing 
trees in the logical way; the authors show that this can easily be tweaked 
to allow mutable objects.
         The beehive scheme in only optimal if object replication has a 
fixed cost.  This is not true in all applications.  The authors suggest 
replicating only pointers, but this is not always suitable: replication may 
be employed either to speed queries or to improve reliability, and 
replicating only pointers does not improve reliability.  Moreover, Beehive 
is actually quite slow to adapt to changes in frequency, taking many hours 
to adapt to sudden changes in object usage.  Also, Beehive is geared to 
users who know how many hops they would like searches to take in the 
average case; in practice, the users are more likely to specify total 
resources to be used, and the challenge is to tune the system to use them 
optimally.


Ari Rabkin  asr32@cornell.edu      Risley Hall 454   3-2842

The resources of civilization are not yet exhausted.
         --William Gladstone  

From okennedy@cs.cornell.edu  Mon Feb 13 22:03:11 2006
Return-Path: <okennedy@cs.cornell.edu>
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 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 k1E33At15357
	for <egs@unix.cucs>; Mon, 13 Feb 2006 22:03:10 -0500 (EST)
Received: from exchfe2.cs.cornell.edu ([128.84.97.34]) by exchfe1.cs.cornell.edu with Microsoft SMTPSVC(6.0.3790.1830);
	 Mon, 13 Feb 2006 22:03:10 -0500
Received: from [192.168.2.3] ([128.253.212.193]) by exchfe2.cs.cornell.edu over TLS secured channel with Microsoft SMTPSVC(6.0.3790.1830);
	 Mon, 13 Feb 2006 22:03:10 -0500
Mime-Version: 1.0 (Apple Message framework v746.2)
Content-Transfer-Encoding: 7bit
Message-Id: <9FA5D92B-4932-4332-855A-DA9265E6B899@cs.cornell.edu>
Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed
To: egs+summary@cs.cornell.edu
From: Oliver Kennedy <okennedy@cs.cornell.edu>
Subject: PAPER 6
Date: Mon, 13 Feb 2006 22:03:07 -0500
X-Mailer: Apple Mail (2.746.2)
X-OriginalArrivalTime: 14 Feb 2006 03:03:10.0550 (UTC) FILETIME=[2FF71760:01C63113]

Search and replication notes that structured distributed networks  
(such as the ring networks we've been discussing) react very poorly  
to the levels of churn seen on the internet.  With few exceptions,  
most deployed distributed networks are unstructured.  The paper also  
notes that while unstructured networks such as gnutella react very  
well to churn, the flooding approach to searches they use is  
incredibly inefficient.  The paper proposes that rather than flooding  
the network with requests and causing an exponential number of  
messages, the originator of the search should let loose a number of  
walkers.  Rather than forwarding a search request to all adjacent  
hosts, a walker is propagated to only one other adjacent host.   
Rather than placing an exponential load on the network for each  
search, the load is constant with each search.  The paper also  
discusses several options for replicating objects for decreased  
search times.  It notes that replicating objects proportional to the  
number of queries received for them provides no benefit.  The  
benefits gained by having the most common queries be short is lost  
due to all the remaining queries becoming longer.  They state that it  
is most efficient to replicate as the square root of the number of  
queries received.  They suggest a means of implementing this without  
knowing the overall number of queries for an object.  After every  
query, the queried object is replicated proportionally to the number  
of hops it took for the walker to reach the object (for example on  
all the nodes in the successful walker's path).  These replicas die  
after a particular time period.  This scheme converges to square root  
replication and distinctly reduces the number of hops required to  
complete a search.

As they note in the paper, random walking provides a reliability  
tradeoff.  The load on the network is dramatically reduced in  
exchange for a slightly increased chance of the search returning a  
false negative.  Searches will also take longer.  The replication  
scheme they propose is used to combat this effect.  However, this  
requires each node to store more data than it would need to store in  
one of the ring network schemes, or even a gnutella scheme.   
Additionally, for networks with high amounts of object churn, the  
traffic associated with keeping replicas up to date would quickly  
outweigh the gains from random walking.

Beehive takes the view that ring networks are viable for real world  
deployment and attempts to improve their performance using  
replication techniques as done by search and replication.  An object  
is replicated on a fraction of the hosts proportional to its  
popularity.  The node in charge of an object collects usage  
information from the object's replicas (if there are any), and  
decides whether or not the object should be replicated (presumably  
replicating only the X most popular objects it hosts with X as a  
tunable parameter).  Being based on Pastry, it uses the standard log 
(N) digit identifiers.  It replicates the object to all the nodes  
which share one less digit in common with the object's identifier  
than it does.  Each of those nodes then decide (using a similar  
metric) whether the object should be further replicated.  If so, each  
node pushes the object to nodes that share one fewer digit in the  
identifier than they do.  Load balancing is done (presumably) by  
having each node only distribute to nodes which share with it one  
more digit than the node shares with the object.

Beehive's replication scheme performs poorly with high object churn.   
Every copy needs to be updated whenever the object is, so frequent  
updates will increase traffic considerably.  The replication scheme  
also seems to increase storage requirements on each node  
proportionally to the log of the number of nodes joining the  
network.  Though this is ultimately limited by the number of possible  
identifiers, Pastry functions best when that limit is set far above  
the number of nodes that might conceivably join the network.   
Furthermore, this system assumes all nodes are trusted, and includes  
no solution to byzantine failures, much like its parent, Pastry.

- Oliver Kennedy

They laughed at Einstein.  They laughed at the Wright Brothers.  But  
they
also laughed at Bozo the Clown.
                 -- Carl Sagan



-Oliver Kennedy

Cogito cogito ergo cogito sum --
"I think that I think, therefore I think that I am."
                 -- Ambrose Bierce, "The Devil's Dictionary"

From sh366@cornell.edu  Tue Feb 14 00:28:16 2006
Return-Path: <sh366@cornell.edu>
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 k1E5SGt25727
	for <egs+summary@cs.cornell.edu>; Tue, 14 Feb 2006 00:28:16 -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 k1E5SFnC002790
	for <egs+summary@cs.cornell.edu>; Tue, 14 Feb 2006 00:28:16 -0500 (EST)
Message-ID: <1474820170.1139894894454.JavaMail.webber@orpheus3.dataserver.cornell.edu>
Date: Tue, 14 Feb 2006 00:28:14 -0500 (EST)
From: Huang Shiang-Jia <sh366@cornell.edu>
To: egs+summary@cs.cornell.edu
Subject: PAPER 6
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 k1E5SGt25727

The two papers to be discussed today present replication (and search) methods to achieve excellent lookup performance in structured and unstructured peer-to-peer systems, respectively.

“Search and Replication in Unstructured Peer-to-peer Networks”
<Paper Summary>
* Compared with structured peer-to-peer systems that are currently only prevalent in the research literature, unstructured peer-to-peer systems such as Napster and Gnutella are actively used on the Internet; they are extremely resilient to transient population of nodes (joining and leaving the system) and capable of handling partial-match queries.
* To solve the problems of scalability and large loads for lookups in unstructured systems, this paper explores, through simulation, alternatives to Gnutella’s search method, data replication strategy and network topology.
* For the search method, it first suggests an expanding-ring approach (gradually increasing the TTL until the object is found) to reduces unnecessary query message traverses in the system. It then proposes a multiple-walker random walk with checking/state-keeping approach (sending k query messages, each takes it’s own route and periodically checks whether to proceed until one finds the object) that further solves the problems of message overhead and duplication in the flooding-based query. Finally, it points out three principles of scalable searches in unstructured systems: adaptive termination, message duplication and granularity of coverage.
* For the replication strategy, it first compares three replication strategies for Geometric and Pareto query distributions and shows that the square-root replication is theoretically optimal among uniform and proportional replications in terms of average search size. It then proposes a random replication approach (extending path replication but having no topological effects in path replication, by randomly replicating the object on p of the nodes along the paths k walkers visited) that performs close to square-root.
* Simulations for the above methods are run in three pairs of combinations of query distribution and replication distribution; performance of the methods is evaluated in probability of successful queries, number of hops in finding an object, average query messages a node has to process, number of nodes each query message traverse through and number of messages the busiest node has to process. It concludes that, in network topology, uniformly random graphs yields the best performance among power-law random graph and Gnutella-style graph (because of their high degree nodes) with flood-style search.

<Limitations>
* It uses only partial criteria in evaluating the search and replication strategies; the performance issues in real peer-to-peer systems are more complicated than those.
* Even though much improved in this paper, the routing latencies of unstructured systems are still much larger than those in structured systems.


<Paper Summary: Beehive>
* Beehive is a proactive replication framework that can provide constant (O(1)) lookup performance for common, power law, query distributions. It operates on top of prefix-routing distributed hash tables and can serve as a substrate for latency-sensitive applications such as DNS.
* Beehive replication mechanism is an extension of the observation that query path can be reduced by one hop if an object is replicated at all nodes preceding the object on the query paths. The replication level, in this paper, is determined according to objects’ popularity and to meet C, the fraction of queries that are satisfied at the source, specified by the user.
* Beehive combines a local measurement, from the analytical model, and limited aggregation to estimate the relative popularities of objects, and it runs a replication protocol to adaptively implement the optimal solution provided by the above two: each node independently decides whether to replicate the object on nodes with one less matching digit than it. Beehive also guarantees the consistency between the object and its replicas by the use of version number.
* Layered on top of Pastry, Beehive is required to replicate objects in the leaf nodes because Pastry maps objects to the numerically closest node in the ID space, in which objects may share no prefixes with the home node.
* The experimental (using DNS as a driving application) results show that Beehive outperforms passive caching in terms of average latency, storage requirement, network load and bandwidth consumption. They also show that Beehive adapts quickly to flash crowds and changes of query distributions.

<Limitation of Beehive>
* Beehive exploits several properties of Pastry, especially the base-b digit identifier structure in its replication protocol. It is therefore infrastructure-dependent and needs to be modified to be applied in other routing protocols.


<Comments>
Beehive presents a proactive replication framework layered on top of structured distributed hash tables for power law query distributions. The other presents a random replication approach that is close to optimal for Geometric distributions and Pareto distributions in unstructured peer-to-peer systems. Are there any proposed replication mechanisms that are independent of routing infrastructures as well as query distributions?

From ids3@cornell.edu  Tue Feb 14 01:50:51 2006
Return-Path: <ids3@cornell.edu>
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 k1E6oot16606
	for <egs+summary@cs.cornell.edu>; Tue, 14 Feb 2006 01:50:51 -0500 (EST)
Received: from [128.253.212.208] (r253212208.resnet.cornell.edu [128.253.212.208])
	(authenticated bits=0)
	by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k1E6opDP021629
	(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT)
	for <egs+summary@cs.cornell.edu>; Tue, 14 Feb 2006 01:50:51 -0500 (EST)
Message-ID: <43F17DD0.4090507@cornell.edu>
Date: Tue, 14 Feb 2006 01:50:56 -0500
From: Ivan Stoyanov <ids3@cornell.edu>
User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716)
X-Accept-Language: en-us, en
MIME-Version: 1.0
To: egs+summary@cs.cornell.edu
Subject: PAPER 6
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

The first paper proposes two optimizations for query and replication in 
unstructured p2p systems. The authors acknowledge the limitations of 
Gnutella-style floodings and evaluate two alternative query  algorithms. 
The first one is "expanding ring", where the originator sends successive 
floods with increasing TTL, waits for the results of the current round 
to come back before issuing the next round of messages. In "multiple 
random walk", the node sends multiple messages to a random subset of its 
neighbors so that each message is in success forwarded to a different 
subset of the neighbor's neighbors. The walk is stoped either with a TTL 
or by having the walker periodically check with the originator whether 
the object has been found.

The authors also prove that square-root replication is optimal and 
provide experiments show that it is achieved by replicating object a 
number of times proportional to the size of the path - for example, like 
in Freenet, simply on all nodes along the path. The most important graph 
in the paper shows that using the optimal technique 80% of the queries 
are successful in two hops, and 98% in 8 hops, which is relatively good 
for unstructured systems.


Beehive is a framework built on top of Pastry, which uses proactive 
replication to achieve average O(1) lookup performance for queries, with 
sub-one best case and O(logN) worst case. It builds on the fact that 
object popularity in a large number of systems follows a power low 
distribution. Therefore, replicating the most popular objects on a large 
number of nodes will tremendously shift the average towords a constant. 
This architecture is particularly designed for latency-sensitive 
applications for which the typical O(logN) DHTs do not work.

An object of popularity i is replicated to the i-th neighborhood of the 
home node (the set of nodes that share common prefix of length i with 
the home node). To find the appropriate level for each object, the 
system provides an analytical model that takes as input the number of 
requests for each object and the desired average lookup time. The number 
of requests for each object is determined by a dedicated monitoring 
protocol. The third piece of the system is the actual replication 
protocol that copies of objects (or pointers to objects) throughout the 
network.

A particularly strong achievement of Beehive is resilience against 
"flash crowds", althogh figure 6 shows that passive caching does 
comparably well.

It seems like proactive replication will only work in power low 
distribution context. Otherwise, the network load will be too high to 
offset the improved performance. It is also not clear how well Beehive 
handles frequent object mutations. Nevertheless, since the system seems 
to be designed particularly as a DNS replacement, these assumptions are 
relatively safe.

The paper does not mention defense against nodes that report erroneous 
access numbers and thus potentially changing the popularity landscape.

From tc99@cornell.edu  Tue Feb 14 02:08:12 2006
Return-Path: <tc99@cornell.edu>
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 k1E78Bt20402
	for <egs@cs.cornell.edu>; Tue, 14 Feb 2006 02:08:12 -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 k1E78729004202
	for <egs@cs.cornell.edu>; Tue, 14 Feb 2006 02:08:08 -0500 (EST)
Received: from 24.59.114.243
        by webmail.cornell.edu with HTTP;
        Tue, 14 Feb 2006 02:08:08 -0500 (EST)
Message-ID: <1786.24.59.114.243.1139900888.squirrel@webmail.cornell.edu>
Date: Tue, 14 Feb 2006 02:08:08 -0500 (EST)
Subject: paper 6
From: "Theodore Ming Shiuan Chao" <tc99@cornell.edu>
To: egs@cs.cornell.edu
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 two papers discussed this week both involve replicating objects at
nodes to  reduce lookup costs. However, the first one is applied on
unstructured graphs a la  Gnutella while Beehive is applied on ring-based
prefix routing schemes such as  Pastry.
The first paper looks at various alternatives to Gnutella's
power-law-distribution  random graph and flooding-based routing. It tests
four graph topology generation  algorithms (Power-law Random Graph,
Gnutella Graph, Random Graph, and 2D Grid) and  expanding-ring TTL
searches and several variations of random-walk (path tracing)  query
routing. Finally, it also considers three approaches to replication:
uniform,  proportional to the Zipf distribution, and square-root of the
Zipf distribution  (both path replication and random replication).
The conclusions reached by the paper were that random walk (with checking)
 performed far better than the flooding based approach because of the
linear rather  than exponential cost increase with increased TTLs. Also,
random graphs performed  better than highly-connected PWLGs since the
lower connectivity actually reduces  messages duplication. The authors
then take the k-random walk query routing and  replicate objects retrieved
by succesful searches on k-nodes, which approximates  the square-root
distribution. The path replication resulted in topologically  dependent
replication, so they used random replication on k nodes among any of the
random walks taken.
Beehive works by replicating entires along prefix-matches in the reverse
path  sequence of prefix-routing in ring-based networks such as Tapestry
and Pastry. Each  replication on a lower level (fewer matching prefixs)
reduces the number of hops to  find the object. In a strict prefix
matching, the object is stored at the highest  level at a node whose ID
matches the object ID the most closely. If Beehive  decides, based on the
aggregation approximation to the Zipf distribution, that an  object should
have additional copies replicated, copies are pushed to nodes that  match
one fewer prefixes (ie. are one hop closer on the routing scheme). An
extension specific to Pastry is that since objects are stored on the
numerically  closest (and not most prefixes matched) and the last hop is
based on the leaf  table, the first replication push is done with the leaf
table and not the  prefix-based routing table.

Beehive does seem to work well for latency-sensitive applications...
however, it  also seems highly dependent on the network being stable with
low churn. Consider  that an analysis phase takes about 8 hours and
adaptation to a flash mob takes 16  hours to reach the target in the worst
case. Aggregation itself takes 48 minutes,  so if there is a high churn
rate, significant amounts of aggregation data could be  lost during that
period and cause an extremely inaccurate estimate of the  popularity of an
object. On the other hand, there is also the question of whether
replication on a high-churn network would make sense in the first place,
since you  would be spending large amounts of resources replicating
objects that have a high  probability of only being available from that
node for a short period of time.

From nsg7@cornell.edu  Tue Feb 14 09:56:16 2006
Return-Path: <nsg7@cornell.edu>
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 k1EEuFt20094
	for <egs+summary@cs.cornell.edu>; Tue, 14 Feb 2006 09:56:15 -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 k1EEuEbF028653
	for <egs+summary@cs.cornell.edu>; Tue, 14 Feb 2006 09:56:14 -0500 (EST)
Received: from 132.236.227.119
        by webmail.cornell.edu with HTTP;
        Tue, 14 Feb 2006 09:56:15 -0500 (EST)
Message-ID: <1682.132.236.227.119.1139928975.squirrel@webmail.cornell.edu>
Date: Tue, 14 Feb 2006 09:56:15 -0500 (EST)
Subject: PAPER 6
From: "Nicholas S Gerner" <nsg7@cornell.edu>
To: egs+summary@cs.cornell.edu
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

"Beehive..." presents a model driven approach (including a detailed
implementation) to replication in a structured peer-to-peer network,
specifically in a DHT.  "Search and Replication..." present analses and
simulation of several search and replication strategies in unstructured
peer-to-peer networks.  Both papers seek to minimize the cost of lookup,
in the case of "Beehive..." to achieve O(1) average lookup performance, in
the case of "Search and Replication..." to avoid the high cost of flooding
in unstructured networks.

"Beehive..." introduces a model of replication which can be optimized
given a tunable average lookup performance parameter.  This model is
implemented in a three phase protocol which naturally integrates with
existing prefix matching DHT work (Pastry is used in this case).  The
model gives the optimal (minimum amount of replication to achieve desired
performance) "replication level" for each object stored in the system. 
These levels indicate how replication should take place and correspond to
the prefix matching in the underlying DHT (so level a level k relication
object is replicated at nodes with prefixes matching k digits. k=logb(n)
means the object is only stored at the home node and k=0 means the object
is stored at all nodes).  The model used by Beehive requires knowledge of
two parameters regarding the distribution of query popularity (assumed to
be a Zipf distribution).  These parameters are estimated in the first
phase "aggregation" where each node aggregates access counts for objects
it stores and forwards these messages on to appropriately selected
neighbors in its routing table.  The "analysis phase" follows where each
node uses popularity estimates and a corresponding estimate for the Zipf
alpha parameter to calculate the appropriate level of replication for each
object it stores.  Finally the "replication phase" distributes (or
removes) objects appropriately so that they have the optimal level of
replication.  "Beehive..." also presents convicing empirical results
indicating that significantly better performance than no replication and
passive replication is achieved and that this performance is achieved in
as little as two analysis intervals (a tunable parameter set at 480minutes
to minimize protocol costs).  Additionally the protocol is shown to be
robust in the face of "flash crowds" (e.g. the slashdot effect),
stabilizing in another two analysis intervals in the worst case (all
popularities are reversed).

"Search and Replication..." presenents simulations and analyses of search
and replication in unstructured networks.  In this setting there is no
prefix matching or efficient underlying DHT style routing.  Specifically
the Guntella approach to routing (flooding) and replication (aggressive,
passive caching) is discussed.  Three replication strategies are examined
with the constraint that the total number of object instances is fixed at
n*rho = R. These strategies are uniform replication (each object has R/m
copies irrespective of popularity), proportional replication (each object
has R*qi copies, where qi is the proportion of queries to object i) and
square root replication (where each object has lambda * sqrt(qi) copies). 
The paper points to another source which shows that square root
replication minimizes search cost given a random walk lookup strategy
(which the paper argues has several nice properties to achieve good lookup
performance and avoids flooding).  The paper goes on to  show (via
simulation) that using a random walk lookup strategy in an unstructured
random network and "path-replication" (the passive-caching scheme used in
Freenet where nodes on the query path replicate the queried object)
achieves results very similar to square-root replication.  Furthermore,
the paper argues (via simulation), "owner replication" (the
passive-caching scheme used in Gnutella) doesn't achieve this distribution
and incurs nearly three times the lookup cost associated with path
replication.

Both papers examine replication as a strategy to minimize lookups, not as
a recovery strategy (although Beehive is likely to replicate all objects
at some low level, therefore at many nodes).  The aggregate storage cost
of replication is not the focus of either paper, although both consider
minimizing it for given lookup performance.  "Beehive..." suggests that
this aspect of replication cost can be addressed by replicating pointers
to the content, rather than the content itself, but this doesn't address
the load incurred by content access (in addition to adding another hop to
the lookup performance parameter).  Alternativly "Beehive..." suggests
that the model could be expanded to include an analysis of cost of
replication or update frequency.  Neither paper includes any such
analysis.

From gp72@cornell.edu  Tue Feb 14 11:02:28 2006
Return-Path: <gp72@cornell.edu>
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 k1EG2Rt13525
	for <egs+summary@cs.cornell.edu>; Tue, 14 Feb 2006 11:02:27 -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 k1EG2Q5Y016878
	for <egs+summary@cs.cornell.edu>; Tue, 14 Feb 2006 11:02:26 -0500 (EST)
Message-ID: <654332395.1139932945940.JavaMail.webber@orpheus3.dataserver.cornell.edu>
Date: Tue, 14 Feb 2006 11:02:26 -0500 (EST)
From: Gopal Parameswaran <gp72@cornell.edu>
To: egs+summary@cs.cornell.edu
Subject: PAPER 6
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Mailer: uPortal WEB email client 3.0

In the paper "Search and replication in Unstructured Peer to Peer Networks" the authors presents
a query algorithm based on multiple random walks that resolve queries almost as quickly as 
Gnutella's flooding method while reducing the network traffic by two orders of magnitude in most cases
for decentralized, unstructured P2P systems. The main issues addressed in this paper are the issues 
of duplicate messages since as the Time To Live (TTL) is increased the number of duplicate 
messages in flooding style messages can be excessive since even though as TTL is increased
 the number of new nodes visited increases the number of visited nodes increases excessively. 
The authors suggest a random graph topology and using a random walk to search through it 
because in a random graph the duplication ratio is same as the fraction of nodes visited so far 
and is small so long as the fraction of nodes visited so far is small. An expanding ring search 
algorithm is suggested where the node starts with a small TTL and if it cannot find the object then the TTL
is increased and the process repeated. A random walk algorithm is used as said earlier.
	Random walk algorithm is good for local search and and might not give desired results for a search 
for an object that is not in close proximity and increasing the number of query messages by a factor of k
only optimises the local search and could take a long time to succeed for distant object nodes.
Also the system discussed does checking with the original requester to check if the node has already been 
traversed and not to send it to nodes that it has traversed. This approach would increase the overhead. 
It seems that the authors have picked up the flooding algorithm which is one of the most inefficient mechanisms
 of doing a search since it is a greedy search algorithm with traversal of duplicate nodes and try to 
present a solution that they claim would improve it. The authors focus on unstructured networks 
claiming that current systems that use Peer to Peer use unstructured system whereas structured 
decentralised systems are in a theoretical stage. However a random walk search is a good algorithm that
 could be applied to structured networks.
	The authors also talk about replications theory and how randomly the searched objects can be replicated
along the path of the search and uses random replication of the object instead of the random replication of the path.

From km266@cornell.edu  Tue Feb 14 11:32:04 2006
Return-Path: <km266@cornell.edu>
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 k1EGW3t24127
	for <egs+summary@cs.cornell.edu>; Tue, 14 Feb 2006 11:32:03 -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 k1EGW3GP024524
	(version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NOT)
	for <egs+summary@cs.cornell.edu>; Tue, 14 Feb 2006 11:32:03 -0500 (EST)
Message-ID: <000301c63184$3ad41720$4425cf45@KEVSTOY>
Reply-To: "Kevin" <yobz@cornell.edu>
From: "Kevin" <km266@cornell.edu>
To: <egs+summary@cs.cornell.edu>
Subject: PAPER 6
Date: Tue, 14 Feb 2006 11:32:21 -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

    The search and replication paper argues that completely unstructured 
peer-to-peer networks have advantages and can be made (order of magnitude) 
more effecient with simple methods.  Structured p2p protocols, the authors 
argue, have problems dealing with massive amount of churn while existing 
unstructured networks have no problems with it.  The problem, however, is 
that a search is usually done by flooding the network with requests which 
exponentially explode.  To alleviate this problem, the authors suggest a 
gossip-like system called random walkers.  In gossip, each node sends the 
message to a random subset of neighbors.  In this system each node forwards 
the message to a random neighbor (preferably one that it has not been 
forwarded to previously) which then passes the message on.  Each message 
still has a TTL, but it is used mainly as a backup if the object being 
searched for does not exist.  This sytem has a two order of magnitude 
improvement over the current flood-based approach.  Another improvement the 
authors argue for is an expanding ring search.  Do a flood search with a TTL 
of 1, then a TTL of 2 and so on until the object is found.  This is 
reminiscent of an iterative-deepening approach commonly used in AI.  The 
idea is that if you send out a message with TTL x then the message you sent 
out with TTL x-1 will be so small in comparison, that you have not used too 
much unnecessary bandwidth by increasing the TTL only 1.  The paper also 
talks about object replication and does a lot of math to determines that 
replicating objects proportional to their popularity is not nearly as 
effecient as replicating them proportional to the square root of their 
popularity.  The object is replicated along the path the message took.  One 
of the nice things about the paper seems to be that a completely random 
network topology does best with the many of the suggested improvements and 
implementing these improvements seem like small changes to an existing 
network.
    The paper flat out says "As a final note about our abstractions and 
metrics, we stress that they omit a lot of issues, including the true 
dynamics of node coming and going in the network, the message delays in the 
network, the actual load on a network node for processing and propagating 
messages, etc."  They assume nothing realistic in their tests, their results 
are not necessarily indicitive of real-world performance.  Furthermore, they 
say that users will be able to tolerate more search time in order to get 
lower load on their system.  As a user of one of these networks, I would 
want to spam out and flood out as many searches as I could possibly fit into 
my pipe if I could get the search back 200ms faster.  I doubt any user would 
sacrifice search time for overall network load, they could care less.  False 
negatives are also a big problem.  A random-walker has a good chance of 
never finding the object it was looking for despite taking a long time to 
look for it.  I think a gossip-style approach might be the best of both 
worlds.  As for the replication, it seems like this would counter a lot of 
the load they tried to take off the system in the first place.  Each node 
would have to store significantly more data than it currently does.

    Beehive is an object replication-centered improvement upon current 
structured p2p systems.  Beehive's authors decided to put it on top of 
Pastry, although any prefix based structured p2p system could be adapted to 
their purposes.  The authors assume a zipf-like distribution of objects 
(which is likely) and use a replication system in order to get expected 
performance of O(1), specifically C, where C is any constant you make it be. 
A small C will have massive (although optimal) object replication while a 
large C will make less replication but more hops.  A C<1 means that with a 
very high probability, you already have the object you are looking for on 
your system.  The beehive scheme works by replicating objects at different 
levels.  An object that is replicated at level 0 is cached in all the nodes 
in the system while an object with level logN is cached only at the home 
node.  By using the underlying network's prefix based routing, the object is 
stored 1 hop closer than the home node.  For example, if an object is placed 
at location 2133, then level 4 replication would mean only the home node has 
it (2133) while level 3 implies that all nodes (213*) have the object. 
Level 2 would mean all the nodes at 21* have the object cached, and so on. 
It is easy to see that the object is stored at exponentially many places as 
its level increases.  The replication level of a particular object is based 
on its popularity, which is measured over the course of a predetermined time 
interval and sent to a node (which is determinstically chosen) in charge of 
its replication level.  Active change notifications are sent out in a 
tree-like manner from the object's home node and in that way avoid 
unnecessary messages.
    The biggest problem I noticed with the paper is that high amount of time 
(measured in hours) that an object takes to get "stable."  In a system with 
a lot of churn, 16 hours is not a reasonable amount of time to have an 
object reach optimal replication.  Furthermore, in a system with a lot of 
nodes and a lot of object, each node will have to store a pretty massive 
amount of data.  The paper suggests using object pointers instead of actual 
object, but this, as the paper points out, adds extra hops.  What it doesn't 
point out is that this is also a single-point of failure.  Furthermore, with 
each node having a pointer to the same home node, that will unbalance the 
network massively as each node sends out an object request to that node. 
Overall, the replication protocol is logical and would work well on DNS and 
other non-file sharing applications.

--Kevin 

From kelvinso@cs.cornell.edu  Tue Feb 14 12:01:23 2006
Return-Path: <kelvinso@cs.cornell.edu>
X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on 
	sundial.cs.cornell.edu
X-Spam-Status: No, score=-0.9 required=5.0 tests=ALL_TRUSTED,AWL 
	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 k1EH1Nt03871
	for <egs@unix.cucs>; Tue, 14 Feb 2006 12:01:23 -0500 (EST)
Received: from EXCHVS1.cs.cornell.edu ([128.84.97.23]) by exchfe2.cs.cornell.edu with Microsoft SMTPSVC(6.0.3790.1830);
	 Tue, 14 Feb 2006 12:01:23 -0500
Content-class: urn:content-classes:message
MIME-Version: 1.0
Content-Type: text/plain;
	charset="us-ascii"
X-MimeOLE: Produced By Microsoft Exchange V6.5
Subject: Paper 6
Date: Tue, 14 Feb 2006 12:01:21 -0500
Message-ID: <2AA53C9C489B0049B43E56D28088677B40D168@EXCHVS2.cs.cornell.edu>
X-MS-Has-Attach: 
X-MS-TNEF-Correlator: 
Thread-Topic: Paper 6
thread-index: AcYxiEf8nitBYb2eQ06y43HtmdGJIg==
From: "Kelvin So" <kelvinso@cs.cornell.edu>
To: <egs+summary@cs.cornell.edu>
X-OriginalArrivalTime: 14 Feb 2006 17:01:23.0078 (UTC) FILETIME=[48A5DA60:01C63188]
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id k1EH1Nt03871

	"Search and Replication in Unstructured Peer-to-Peer Networks"
presents a study on replication and search techniques on decentralized and
unstructured peer-to-peer networks, such as Gnutella. Beehive presents a
replication technique, which achieves O(1) average lookup while using low
storage requirements, bandwidth overhead and network load, using for
structured peer-to-peer network. 
	Lv et. al. looks at different search and replications techniques for
decentralized and unstructured peer-to-peer networks. The paper focuses on
Gnutella-like systems instead of other structured peer-to-peer systems
because it is used by large community of Internet users and it does not have
serious research. Gnutella uses flooding with TTL(Time-To-Live) to propagate
query in the network, but flooding would cause large load on the client.
Therefore, they look at alternative search techniques. The first one they
look at is expanding ring search. It starts using flooding with a TTL = 1,
then it iteratively increases the TTL until it finds the object. The second
approach they look at is random walk. Through the simulations under various
network environments (Random, Power-law Random Graph, Gnutella-like, Grid)
and two different query distributions, they show that both expanding ring
search and random walk reduce network load by a lot when searching an object.
In particular, random walk can reduce two orders of magnitude in network
load. Also, they look at replication techniques, such as uniform replication,
proportional replication and square-root replication. They show that
square-root replication is optimal. Finally, they evaluate owner replication,
path replication and random replication (instead of caching in the path of
the query search, random replication cache in k random location if query
visits k nodes), and show that random replication does better than path
replication. However, in their simulations, they do not show bandwidth
consumption which is used to replicate the objects in high-churn network. The
bandwidth consumption can be high when the network has high degree of churns
because it is wasteful to constantly cache objects on the short-lived node.
	In the second Beehive, Ramasubramanian et. al. show an proactive
replication framework in structured peer-to-peer network, which can achieve
average O(1) lookup latency. Query distributions are commonly Zipf-like. In
Zipf-like distribution, there are a few objects that are very popular while a
lot of nodes with very small demand. The most important idea is to replicate
the objects based on their popularity. If the object is popular, it will be
replicated everywhere in the system. If the object is not popular, it will be
replicated in very few nodes and it will take longer time to route to those
objects. Therefore, it can achieve an average O(1) lookup performance. By
using zipf-like distribution, they analytically derive such optimal number of
replicas needed to achieve O(1) lookup performance. Then, they show how to
implement such a system on top of Pastry. Finally, they present results from
a prototype implementation of peer-to-peer DNS service and show that it can
achieve good performance and can adapt to flash crowds. 
	

From pjk25@cornell.edu  Tue Feb 14 12:13:06 2006
Return-Path: <pjk25@cornell.edu>
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 k1EHD6t07196
	for <egs+summary@cs.cornell.edu>; Tue, 14 Feb 2006 12:13:06 -0500 (EST)
Received: from [192.168.1.102] (host-69-48-92-3.spr.choiceone.net [69.48.92.3])
	(authenticated bits=0)
	by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k1EHD5an003046
	(version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT)
	for <egs+summary@cs.cornell.edu>; Tue, 14 Feb 2006 12:13:06 -0500 (EST)
Mime-Version: 1.0 (Apple Message framework v746.2)
Content-Transfer-Encoding: 7bit
Message-Id: <5D17C0B6-E798-44B4-886D-7BB8AEAC016E@cornell.edu>
Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed
To: egs+summary@cs.cornell.edu
From: Philip Kuryloski <pjk25@cornell.edu>
Subject: PAPER 6
Date: Tue, 14 Feb 2006 12:15:41 -0500
X-Mailer: Apple Mail (2.746.2)

Search and Replication in Unstructured Peer-to-Peer Networks focuses  
primarily in improving search performance in a Gnutella-like  
network.  The authors begin by describing  the inefficiency of the  
flood type search scheme currently employed in Gnutella, where  
searches generate excessive messaging and load in the system.   
Flooding is simulated on several network structures, including a  
regular grid, random graph, power law graph, and a snapshot of the  
Gnutella network, and the authors note that a random graph is the  
optimal "structure" for a flooding based approach as it is the only  
case where the number of new nodes reached at each forward matches  
the number of nodes receiving a duplicate message.

The authors then examine two improved approaches compared to  
flooding, the first they call expanding ring, and the second random  
walks or walkers.  Previously the authors note that it is difficult  
to select a proper TTL for messages when flooding if the network size  
is unknown.  The expanding ring search still floods messages, however  
it begins with a very small TTL and continues to raise it until the  
object is found.  The random walkers search is based on the random  
walk technique, where a message is forwarded randomly to a neighbor  
rather than to all neighbors.  The message is given a TTL, and is  
called a walker.  Random walkers employs the use of several  
concurrent walkers; the authors find that 16-64 walkers gives good  
results.  They later raise the TTL to a very high number, and  
instruct walkers to check in with their originating node every four  
hops to determine if the object has been found.  They also suggest  
keeping a "state" at each node which will allow the walkers to avoid  
returning to nodes they have already traversed, increasing the  
efficiency of the search.

These techniques succeed in greatly reducing the amount of message  
traffic in the network while  retaining comparable lookup times,  
however a limitation of their analysis is that the latency of links  
in the underlying network are completely disregarded.  They also do  
not address issues of network setup to produce a random graph.

The authors also address the issue of replication to reduce search  
times in the network.  They begin by analyzing two schemes, which  
they call uniform and proportional.  Uniform replication replicates  
an even number of copies of objects across all nodes, and  
proportional allocates more objects to nodes which receive more  
requests for that object.  They determine that the average number  
nodes messaged in each scheme is the same, however proportional  
replication achieves better load balancing.  Also, using the  
proportional scheme, more popular objects have a smaller search size,  
and less popular objects have a larger search size.  They introduce  
squareroot replication, where the number of replicas is proportional  
to the square root of the size of the network, and replicas are  
distributed randomly throughout the network.  This scheme produces  
less variance in the search sizes of objects of different popularity  
and also less variance in load.  The authors do not suggest methods  
of implementing the square root replication scheme.

Beehive begins by noting that the O(log N) lookup times associated  
with structured DHTs results in latencies which are too high for  
certain critical applications, such as DNS.  However, the query  
distributions associated with these applications are often known, and  
this structure can be exploited to guide proactive replication and  
yield O(1) lookup times.  In particular, they address a power law  
query distribution that is found in DNS, web-caching, etc.  They  
implement Beehive on top of Pastry, however they note that an prefix  
based DHT could be used as a substrate for Beehive.

For prefix based DHTs, the author's primary insight is that  
replicating an object on all paths leading to a home/owner node for  
an object will reduce the average lookup time for that object by one  
hop.  Beehive adjusts the size of this expanding ring of replicas  
such that the average lookup time across all objects is a constant.   
Based on the Zipf-like, or power law query distribution, the authors  
give closed for solutions to the problem of determining the  
appropriate replication level (size of replication ring) for all  
objects in the network.  The authors note that this model is  
appropriate for objects which do not change frequently, such as dns,  
but may not be appropriate for web objects in general.

In order to use the closed form solutions, the parameter for the Zipf  
distribution must be determined.  The number of requests per object  
is periodically forwarded towards the home node for that object, and  
out from that node, to allow estimation of parameters for objects  
that have been replicated.  In order to achieve replication, nodes  
push replicas to nodes matching one less prefix for the object, who  
may in turn push that object again, depending on it's desired  
replication level.  In order to reduce constant movement of objects  
between replication levels, when a node sorts the objects at that  
level by popularity, it favors the nodes already at that level to  
remain at that level.  Beehive supports mutable objects by  
associating a version number with objects and pushing updates from  
the home node.  Version numbers are also propagated by nodes when  
they push objects to other levels for replication when object  
popularity changes.

Beehive is simulated and compared to Pastry and Pastry with passive  
caching, and provides the best lookup performance of the three,  
averaging less than one hop.  It also maintains low maintenance  
bandwidth.  Beehive also reacts well to sudden changes in object  
popularity.

The primary limitation of Beehive is that it requires queries to  
follow a certain random distribution, which is not the case for all  
classes of objects one may want to store in a P2P network.

From tudorm@cs.cornell.edu  Tue Feb 14 12:47:14 2006
Return-Path: <tudorm@cs.cornell.edu>
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 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 k1EHlDt17144
	for <egs@unix.cucs>; Tue, 14 Feb 2006 12:47:14 -0500 (EST)
Received: from exchfe2.cs.cornell.edu ([128.84.97.34]) by exchfe1.cs.cornell.edu with Microsoft SMTPSVC(6.0.3790.1830);
	 Tue, 14 Feb 2006 12:47:13 -0500
Received: from [128.84.223.148] ([128.84.223.148]) by exchfe2.cs.cornell.edu over TLS secured channel with Microsoft SMTPSVC(6.0.3790.1830);
	 Tue, 14 Feb 2006 12:47:13 -0500
Message-ID: <43F217A0.7040309@cs.cornell.edu>
Date: Tue, 14 Feb 2006 12:47:12 -0500
From: Tudor Marian <tudorm@cs.cornell.edu>
User-Agent: Thunderbird 1.5 (X11/20051201)
MIME-Version: 1.0
To: egs+summary@cs.cornell.edu
Subject: PAPER 6
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-OriginalArrivalTime: 14 Feb 2006 17:47:13.0258 (UTC) FILETIME=[AFE204A0:01C6318E]

Search and Replication in Unstructured P2P Networks - is a detailed 
study of more scalable alternatives to existing unstructured 
decentralized p2p systems with respect to the search and replication 
aspects. The paper compares the impact of various algorithms for several 
network topologies, query distribution and replication. Authors show 
that flooding even with controlled TTL incurs unacceptable overhead, and 
compare it to expanding ring and random walks, concluding that the 
latter coupled with the checking adaptive termination scheme and message 
duplicate suppression works best amongst the methods tried; authors do 
admit that the goal of the paper was not an exhaustive study of all 
search algorithms, nor do they claim that k-random walk is optimal.

It is shown that the search size is minimized for replication 
proportional to the square root of the query relative popularity 
(basically the number of queries issued for objects) and that uniform 
and proportional distributions are significantly suboptimal. The 
square-root replication is approximated by finding the fixed point of a 
differential equation, yet there's no in depth analysis of the viable 
methods for solving it.

The paper notes that the random replication improves upon path 
replication, and it's not clear why this happens, moreover there is no 
explanation for this behavior.


Beehive considers taking the analytical approach to solving the 
replication problem on top of any DHT that has prefix matching routing 
like Pastry. Beehive uses proactive replication to yield constant lookup 
time for power law query distributions. Objects can be replicated at all 
nodes k hops backwards from the home node (of the objects in question), 
thus reducing the lookup latency by k hops. The replication process is 
iterative, starting with the home node and continuing to the nodes with 
ID's that have largest common prefix ids. The decision of which object 
to replicate and at which level is taken by running a distributed 
algorithm and solving a minimization problem that requires continuously 
estimating the popularity of objects and the power law \alpha parameter.

Power law distributions may work well for some particular type of 
queries like DNS, but what about non-Zipf distributions. Most p2p file 
sharing systems have queries that cannot be fitted appropriately by any 
power laws. Also the scheme works for fixed cost replication - while 
this might be true for small DNS entries, it is definitely not for 
regular file content. Moreover the minimization problem is posed in 
terms of reducing storage requirements at the peers, and hence lower 
*not minimize* the communication traffic - arguably, minimizing the 
communication is considerably more important, especially for entries 
that do not have fixed cost of replication.

Paper doesn't mention how computationally expensive is the linear 
regression, also response to flash crowd effect might be acceptable for 
DNS, but it is not clear how the response time is perceived for other 
type of content distribution.


Tudor

From ymir.vigfusson@gmail.com  Tue Feb 14 13:33:24 2006
Return-Path: <ymir.vigfusson@gmail.com>
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 nproxy.gmail.com (nproxy.gmail.com [64.233.182.200] (may be forged))
	by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k1EIXNt03373
	for <egs+summary@cs.cornell.edu>; Tue, 14 Feb 2006 13:33:23 -0500 (EST)
Received: by nproxy.gmail.com with SMTP id o60so477413nfa
        for <egs+summary@cs.cornell.edu>; Tue, 14 Feb 2006 10:33:22 -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=AUkn5pTx6P0qx2IjeV8BeBb3alDqEgNp85gX6QJdOrynmNWPbnZuN8RC5+e80AAkVMzFZ+5K4airN49Kn7HUnAzXnPTgF9x9QeA20IsBWPi011RTDShlPlv1lzmIavbowxhTnVdugc/A7HhbJR0Uo+/ueJ43HNkJ1MBLJ0Blqvc=
Received: by 10.48.49.19 with SMTP id w19mr1395599nfw;
        Tue, 14 Feb 2006 10:33:22 -0800 (PST)
Received: by 10.48.217.10 with HTTP; Tue, 14 Feb 2006 10:33:21 -0800 (PST)
Message-ID: <9302f1e20602141033w64c40558wc6584f407c10bdc8@mail.gmail.com>
Date: Tue, 14 Feb 2006 13:33:21 -0500
From: Ymir Vigfusson <ymir.vigfusson@gmail.com>
To: egs+summary@cs.cornell.edu
Subject: PAPER 6
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 k1EIXNt03373

Beehive is an overlay system on top of a structured DHT peer-to-peer
network such as Pastry. It was motivated by the performance,
scalability and adaptivity requirements of many common demanding
applications such as DNS and web servers. These services have
query distributions that follow a power law distribution.
Since the underlying P2P system is already scalable and adaptive,
what Beehive adds is improved average case lookup performance,
namely O(1). This is accomplished by dynamically maintaining an
estimate of the popularity of the queried data, and proactively
replicating popular data. Beehive maintains a fractional parameter C
that dynamically adjusts to the real-time performance and ensures
that C fraction of the queries are satisfied at the source node
(you know the answer before you ask). If not, you will on average
only ask O(1) nodes, and in the worst case O(log n).
Proactive replication, as opposed to the passive replication where
you e.g. store copies of the result on the paths leading there,
is done by assigning a replication level i to each object, so
objects at level i are replicated on nodes that have at least i
matching prefixes with the object. The extremse are level 0, where
an object is stored on every node, and log_b n where an object
is only stored on its home node. Beehive tries to find the minimal
replication level for each object to keep the average lookup time
down (namely at C). The paper provides the optimization calculations
and gives a closed-form solution minimizing the total number of
replicas for a given object. Furthermore, the solution is optimal
for power query distributions with decay parameter at most 1.
For the adaptation, Beehive aggregates popularity data from a
number of nodes to create an estimate of an object's popularity
by using only a few samples. It turns out for an object replicated
at level i, there are 2(log(n) - i) rounds of aggregation required
to gather the statistics from relevent nodes (sending information
back and forth). It is not crucial that the estimates are completely
accurate.
Beehive can be further optimized by merging the aggregation messages
with the heartbeat messages sent by the underlying P2P network.
Also, fluctuations in the estimates can limited by employing
hysterisis (bias the system towards maintaining already existing
replicas when the popularity different between two objects is small).
Beehive employs versioning on its objects to achieve strong consistency,
i.e. queries to a recently updated object should only return the
modified object. As for joining and parting, there worries are mainly in
the underlying P2P systems. Beehive uses lazy update propagation mechanism
to make sure parting doesn't prevent updates from reaching nodes where
objects are replicated.
As for a major downside, a thorough security evaluation of the protocol
needs to be performed. There are many vulnerable spots, for example
misreporting popularity of an object, or getting it replicated indirectly.

The search paper is a long bloated text of experimental results from
analyzing different kinds of searches in a few graph models. Basically,
the naive TTL flooding in a Gnutella network is shown to be bad (for example
lots of duplicates). Improved methods include expanding ring search, where
you increase your TTL linearly which improves the message overhead
significantly compared to regular flooding. However, message duplication
is still an issue, so the paper proposes doing a random walk using
so-called "checking" where a number of random walkers periodically
check with the original requester before walking to the next (random)
node. The simulations in the paper show that "checking" seems to be the
right approach for terminating search in random walks.
The second part of the paper addresses replication, where uniform or
proportional replication strategies are shown to lose for the optimal
square-root replication in which the allocation of replicas minimize
the average search size.

- Ymir