From eyh5@ee.cornell.edu Mon Dec 3 13:31:15 2001 Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.81.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fB3IVET18281 for ; Mon, 3 Dec 2001 13:31:14 -0500 (EST) Received: from photon.ece.cornell.edu (photon.ece.cornell.edu [128.84.81.138]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id fB3IRvM21001 for ; Mon, 3 Dec 2001 13:27:57 -0500 Date: Mon, 3 Dec 2001 13:27:59 -0500 (EST) From: Edward Hua X-X-Sender: To: Subject: 615 Paper # 68 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Tapestry: An Infrastructure for Fault tolerant Wide-area Location and Routing Ben Y. Zhao, John Kubiatowicz, and Anthony D. Joseph This paper proposes Tapestry, a wide-area network infrastructure that is capable of routing requests to service objects efficiently in the presence of heavy load and network/node faults. Inspired by the Plaxton scheme, Tapestry is self-organizing, easily scalable, fault-tolerant, uses multiple root nodes to point to an object, and uses explicit locality knowledge to route service requests. Tapestry achieves overall network performance through the accumulation of statistics, and its routing is done independent of the physical location of the server. The routing in Tapestry is done using the neighbor maps. The neighbor maps contain entries whose neighbor node IDs are computed using a hashing function such as SHA-1. The destination nodes in the neighbor map can be resolved digit when a service request traverses through the network. The location scheme in Tapestry is done by having multiple root nodes serving an object. Each root node contains pointer pointing to the actual location of the object. And each intermediate hop from the root node to the object location node contains a tuple assist a client quickly locating the needed object. The use of multiple root nodes solves the problem of single point of failure, as is present in the Plaxton algorithm. Tapestry allows soft-state, graceful fault recovery. It requires the publisher of the object to periodically update and/or maintain the object in the server, and will delete the object if a long period of inaction is observed. This scheme has the advantage of treating faults as part of Tapestry's normal operations, and thus no dedicated mechanism is required to address the fault-tolerance issue. In Tapestry, load balancing may be achieved using two algorithms implemented in Tapestry nodes. The first is a refresher thread that runs in the background to update the network latency from the node to each of its neighbors. If the latency exceeds some predefined threshold, a secondary neighbor node (each Tapestry neighbor map entry keeps one primary and two secondary neighbors) will be used to route the message. The second algorithm enables the node to keep track of sources of heavy query load, or hotspots, and offer suggestions on locations where additional copies of the service object may improve query response time. The simulation results presented in this paper largely confirm the objectives the researchers set out to accomplish. Specifically, the results show that the use of location pointers in Tapestry nodes allows the relative delay penalty to be kept fairly constant, irrespective of the number of hops a message traverses; the replicas of object in several locations help bring down the latency; multiple root nodes also have the same positive impact; and Tapestry performs better when under high load stress. However, there are some trade-offs to be made aware of. First is the bandwidth. Tapestry requires an ample supply of bandwidth to carry out its operations. Secondly, especially when multiple replicas of object and multiple root nodes are deployed, there is a stringent requirement on the disk space the replica servers and root nodes need to possess. Tapestry seems to act under the assumption that the nodes will have enough disk space to support object replicas and to serve as root nodes. This may not be true in the real world. A result will be a replica of the object can not find a suitable node to be housed. From wbell@CS.Cornell.EDU Mon Dec 3 14:04:07 2001 Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fB3J46T24430 for ; Mon, 3 Dec 2001 14:04:06 -0500 (EST) Received: from dhcp-190.rover.cornell.edu (dhcp-190.rover.cornell.edu [128.84.24.190]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id OAA23588 for ; Mon, 3 Dec 2001 14:04:05 -0500 (EST) Subject: 615 PAPER #68 From: Walter Bell To: egs@CS.Cornell.EDU Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: Evolution/0.99.1+cvs.2001.11.07.16.47 (Preview Release) Date: 03 Dec 2001 14:03:44 -0500 Message-Id: <1007406247.913.33.camel@brute> Mime-Version: 1.0 68) Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing Tapestry is an application level infrastructure for fault tolerance with respect to routing and location. The main idea is that given Moore's law, we can afford to utilize more and more bits and cycles to promote redundancy and therefore better scalability rather than the current house of cards which is the Internet. I think this philosophy is incredibly flawed-- the only reason why the Internet has scaled as it has is because of Moore's law technology growth while the use of that technology hasn't substantially changed. This has allowed the Internet to scale in the number of hosts, as the cycles needed to support a single host has remained relatively constant. What they propose would dramatically increase the relative amount of resources needed to support a host, which would lead to a quadratic scaling of the need for resources on the Internet, which even Moore's law growth cannot support. With that said, they hope to promote a Pastry-like location and routing service based on the Plaxton mesh topology construction, where routing happens on an overlay network and is done via prefixes of the node identifier. Nodes expose objects to root nodes via identifiers which propagate with home information throughout the system. They replicate root nodes in order to provide better accessibility as well as redundency in object directories. State maintenance is done via soft state with incredibly large timeouts (on the order of days) which makes me question the scalability of this system. Their protocols for adding and removing nodes are very complex and expensive which would seem to be a large impairment to not only scalability but ability to deploy such a system on the Internet. I was not convinced of the stability of such a scheme as they assume that nodes have frequently out of date or wrong information, but yet set timeouts to be very high (such as waiting for days to remove a dead host.) I hate to be too skeptical, but they had too many places where they asked me to believe that certain properties held. I felt that the initial idea of stability through statistics (not only catchy, but a useful way to view the problem) was a good one, but that they promoted a view of routing that was somewhat ill-conceived-- routing is something that people do in order to get what they really want done, and hence it should not require large resources, which is exactly the opposite of their focus, where routing was a very expensive and primary activity. From c.tavoularis@utoronto.ca Mon Dec 3 20:22:12 2001 Received: from bureau6.utcc.utoronto.ca (bureau6.utcc.utoronto.ca [128.100.132.16]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fB41MBT27730 for ; Mon, 3 Dec 2001 20:22:11 -0500 (EST) Received: from webmail4.ns.utoronto.ca ([128.100.132.34] EHLO webmail4.ns.utoronto.ca ident: IDENT-NOT-QUERIED [port 63535]) by bureau6.utcc.utoronto.ca with ESMTP id <238904-17211>; Mon, 3 Dec 2001 20:22:06 -0500 Received: by webmail4.ns.utoronto.ca id <164259-211>; Mon, 3 Dec 2001 20:21:48 -0500 To: COM S 615 Subject: 615 PAPER 68 Message-ID: <1007428903.3c0c252730de0@webmail.utoronto.ca> Date: Mon, 03 Dec 2001 20:21:43 -0500 (EST) From: c.tavoularis@utoronto.ca MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit User-Agent: IMP/PHP IMAP webmail program 2.2.3 This article presents Tapestry, an overlay routing infrastructure that provides location independent routing to the closest copy of an object or service. Tapestry is decentralized such that nodes maintain a fair amount of soft state routing information in a simple, scalable and fault tolerant manner. Tapestry is based on Moore’s law to achieve stability through statistics by creating redundant copies of objects. Tapestry employs a variation of Plaxton mechanisms for locating and routing named objects. Object and node names, independent of location, are random numbers of fixed length, and exist in the same uniform namespace (created using hash functions). Routing is accomplished digit by digit. Plaxton meshes are data structures at each node that contain a routing map. Routing maps are organized in levels according to matching suffix of a specific length. The message is forwarded to the node at the next level with an entry matching the next digit in the destination Id. This algorithm guarantees a number of hops to the destination of order logarithm of the total number of nodes. The maps to objects resemble an embedded set of trees, one rooted at every node. Each object has a set of nodes to serve as its roots. Plaxton only uses one root node per object, which sets the stage for single points of failure. Tapestry also uses surrogate-routing, instead of global information, to select root nodes. This method is dynamic for changing environments, and deterministic so that any Id will be mapped to an existing node. A node must publish objects it hosts to the root node of the object by forwarding a message to it. Pointers along the path from host node to root node are maintained. A new node can join by bootstrapping to a gateway node in the network, and trying to route to itself while gathering copies of neighbor maps along the way. It then must notify other nodes to include it in their routing tables. Location-independent names of objects make it easy for applications to request services, and at the closest possible location with high probability. Replicated objects must maintain some consistency, although strict consistency is not essential since re-requests can be implemented. Using a soft-state approach, periodic update messages are sent to nearby nodes, such that caches expire if updates are not being received over some time. This allows old information to disappear gracefully. Location mappings are also soft-state and servers must republish the existence of their objects. Immediate neighbors send each other hearbeat messages so that node failures can be detected promptly. Some explicit updating is used to reduce some of the bandwidth overhead caused by soft state maintenance. Tapestry showed good performance characteristics including reasonable latency, graceful degradation in the event of failures and small overhead. The infrastructure adopted here proves that object and routing information replication in large networks provide durability and performance enhancement, while adding minimal overhead to deal with consistency. Tapestry upgrades Plaxton mechanisms to provide adaptability and further fault tolerance. From ramasv@CS.Cornell.EDU Tue Dec 4 11:24:39 2001 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fB4GOd629827 for ; Tue, 4 Dec 2001 11:24:39 -0500 (EST) Subject: cs615 PAPER 68 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Date: Tue, 4 Dec 2001 11:24:38 -0500 content-class: urn:content-classes:message X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 Message-ID: <706871B20764CD449DB0E8E3D81C4D4301E7F29D@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: cs615 PAPER 68 Thread-Index: AcF84Cub4aeA/TBXTOCUDee6VxOwXA== From: "Venu Ramasubramanian" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id fB4GOd629827 Tapestry: An Infrastructure for Fault tolerant Wide-area Location and Routing. This paper presents tapestry, yet another object location (i.e., routing) scheme designed for large scale peer-peer networks. The tapestry routing algorithm closely resembles pastry, both being based on a radix sort like approach of plaxton et al. Tapestry like pastry provides log(n) bound on the number of hops and also have similar optimizations to route to closest server in the actual internet topology based on a suitable metric such as latency. Tapestry also shares other design goals such as decentralization, scalability and fault tolerance with pastry, chord and others. In tapestry, the objects are not distributed throughout the network. The objects are assumed to be in persistent storage of a set of servers responsible for the objects. Only pointers to the location of the obejct (server id) is distributed in the network. This makes the size of contents distributed in the network small and equal. Therefore no special load balancing techniques are required and repeated copying of the contents does not consume excessive bandwidth. Tapestry also differs from pastry in the way replicas of the contents (object, server mappings) are distributed. Instead of choosing topologically adjacent nodes, it relicates the contents on root serrvers uniformly distributed in the topology. The object id is rehashed after adding a salt (to represent replica number) in order to locate the root server. This facilitates parallel routing queries lowering the retrieval latency by a little. The contents distributed in the network are considered as soft state, to be deleted unless refreshed by periodic refresh messages. Thus the server responsible for an object is expected to periodically route refresh messages in order to preserve the (object, server) mapping in the tapestry nodes. Thus log(n) messages are periodically generated for each object in the network. Further each tapestry node is also expected to send periodic heart beat messages to all the neighbors, i.e., other nodes with this node in their routing tables. This generates b*log(n) (size of routing table) at every node during a period. These periodic mesages consume a fair bit of available bandwidth and would pose great restrictions to scalability of this algorithm with number of objects and with number of faults. From mh97@cornell.edu Tue Dec 4 11:51:41 2001 Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fB4Gpf604326 for ; Tue, 4 Dec 2001 11:51:41 -0500 (EST) Received: from mars (syr-66-24-28-66.twcny.rr.com [66.24.28.66]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA19848 for ; Tue, 4 Dec 2001 11:51:37 -0500 (EST) From: "hao ming" To: "'Emin Gun Sirer'" Subject: 615 PAPER 68 Date: Tue, 4 Dec 2001 11:51:07 -0500 Message-ID: <000001c17ce3$dfba8d50$6801a8c0@mars> MIME-Version: 1.0 X-Security: MIME headers sanitized on sundial.cs.cornell.edu See http://www.impsec.org/email-tools/procmail-security.html for details. $Revision: 1.131 $Date: 2001-11-23 19:59:32-08 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="----=_NextPart_000_0001_01C17CB9.F6E48550" X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook, Build 10.0.2627 Importance: Normal X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 This is a multi-part message in MIME format. ------=_NextPart_000_0001_01C17CB9.F6E48550 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Tapestry: An Infrastructure for Fault tolerant Wide-area Location and Routing Ben Y. Zhao, John Kubiatowicz, and Anthony D. Joseph the paper comes from the same point as the last 4 papers: how to distribute and retrieve the information world-widely. the development of Internet makes this possible. And some systems has been set up like Past, Freenet. this paper outlines 5 basic requirements needed by this kind of system. 1. load balance 2. scalability 3. self-organization 4. fault-torlerance 5. decentralized the routing method is similar to that of Pastry. first, a SHA-1 hash is used to evenly distribute the information among the name space. Then a Plaxton routing routing method is used which guarantee the LogN routing step. the main new features Tapetry can be seen from its difference from Plaxton from which Tapestry inherits many things. 1. more flexible mechanism to select the replica. 2. using backup neighbors and hello message to detect and bypassing fault nodes. a second chance is given to the fault neighbors to reduce reinsertion overhead. 3. multiple root for object to avoid single point failure 4. refreshing of pointers along the route to the root. 5. nodes can join and depart dynamically. new nodes get their neighbor maps by routing to its own ID from a known gateway and retrieve the neighbor map one level from each node along the route. further optimization is carried out. comments: in comparison with Pastry, we can find some drawback of Tapestry. Pastry cleverly use prefix insdead of suffix in order to taking Distance into account. though Pastry also retrieve the routing info from nodes along the route, it has much less overhead because it already takes locality into account and make distance optimization not unnecessary. -ming ------=_NextPart_000_0001_01C17CB9.F6E48550 Content-Type: text/html; charset="us-ascii" Content-Transfer-Encoding: quoted-printable -->

 

Tapestry: An Infrastructure for Fault =
tolerant Wide-area 
Location =
and Routing
Ben Y. =
Zhao, John Kubiatowicz, and Anthony D. =
Joseph

 

the paper comes from the = same point as the last 4 papers:

how to distribute and = retrieve the information world-widely.

the development of = Internet makes this possible. And some

systems has been set up = like Past, Freenet.

 

this paper outlines 5 = basic requirements needed by this kind

of  system.=

 

1. load = balance

2. scalability

3. self-organization

4. fault-torlerance

5. decentralized =

 

 

the routing method is = similar to that of Pastry. first, a SHA-1 =

hash is used to evenly = distribute the information among the

name space. Then a Plaxton routing routing method is used which

guarantee the LogN routing step.

 

the main new features = Tapetry can be seen from its difference =

from Plaxton from which Tapestry inherits many things.

 

1. more flexible mechanism to select = the replica.

2. using backup neighbors and hello = message to detect and

   bypassing fault nodes. a second chance is given to the = fault

   neighbors to reduce reinsertion overhead.

 

3. multiple root for object to avoid = single point failure

4. refreshing of pointers along the = route to the root.

5. nodes can join and depart = dynamically. new nodes get their

   neighbor maps  by routing to its own = ID from a known gateway

   and retrieve the neighbor map one level from each node along =

   the route. further optimization  is carried = out.

 

comments:

 in comparison with Pastry, we can find some drawback of Tapestry. =

Pastry cleverly use prefix insdead = of suffix in order to taking

Distance into account. though Pastry = also retrieve the routing info

from nodes along the = route, it has much less overhead because it

already takes locality = into account and make distance optimization

not = unnecessary.

 

 

-ming

 

------=_NextPart_000_0001_01C17CB9.F6E48550-- From samar@ece.cornell.edu Tue Dec 4 12:12:21 2001 Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.81.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fB4HCL608110 for ; Tue, 4 Dec 2001 12:12:21 -0500 (EST) Received: from aquinas.ee.cornell.edu (aquinas.ee.cornell.edu [128.84.236.57]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id fB4H8xM16447 for ; Tue, 4 Dec 2001 12:08:59 -0500 Date: Tue, 4 Dec 2001 12:10:43 -0500 (EST) From: Prince Samar X-Sender: samar@aquinas.ee.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 68 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing Tapestry is an object location and routing scheme for large, fault-tolerant peer-to-peer networks. It is quite similar to Pastry and the scheme proposed by Plaxton et al. Messages locate objects and are routed across the network, while using a routing map with size logarithmic to the network namespace at each hop. The main goals of Tapestry are adaptivity, self-management and fault-resilience in the presence of failures. Neighbor maps are used at each node to incrementally route overlay messages to the destination ID digit by digit. Neighbor maps are organized into routing levels and each level contains entries that point to a set of nodes closest in network distance that matches the suffix for that level. Tapestry does not replicate and cache the objects at numerous locations in the network. Instead, pointers to the location of the object are distributed in the network. This reduces the need for external load balancing techniques, though it also reduces the redundancy and thus fault-tolerance in the network. Tapestry addresses fault-tolerance by using soft-state to maintain cached content, rather than provide reliable guarantees for hard state. Caches are updated by periodic update messages or are expired if none is received. These periodic messages have the potential of consuming a considerable fraction of the bandwidth, affecting the scalability of the scheme. To circumvent the presence of faults in the network, TCP timeouts are used and two backup neighbors in addition to the primary neighbor in the neighbor map are maintained. Tapestry adds "salt" values to maintain multiple roots to each object. Surrogate routing is used to incrementally and deterministically compute a unique root node. tapestry uses some algorithms to support dynamic operations in the network in a distributed way. From teifel@csl.cornell.edu Tue Dec 4 13:08:47 2001 Received: from disney.csl.cornell.edu (disney.csl.cornell.edu [132.236.71.87]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fB4I8l617606 for ; Tue, 4 Dec 2001 13:08:47 -0500 (EST) Received: from localhost (teifel@localhost) by disney.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id fB4I8f323381 for ; Tue, 4 Dec 2001 13:08:41 -0500 (EST) (envelope-from teifel@disney.csl.cornell.edu) X-Authentication-Warning: disney.csl.cornell.edu: teifel owned process doing -bs Date: Tue, 4 Dec 2001 13:08:41 -0500 (EST) From: "John R. Teifel" To: Subject: 615 PAPER 68 Message-ID: <20011204115907.C17542-100000@disney.csl.cornell.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Tapestry: Tapestry is an overlay location and routing infrastructure that provides location-independent routing of messages directly to the closest copy of an object or service using only point-to-point links and without centralized resources. Routing and directory information is maintained in a soft state and is easily repairable. This infrastructure is self-administering, fault-tolerant, and resilient under load. Tapestry builds on much of the ideas from Plaxton, et al. including simple fault handling, scalability, locality exploitation, and proportional route distance. Tapestry then attempts to solve the problems associated with Plaxton, naming global knowledge, root node vulnerability, and lack of ability to adapt. One of Tapestry's main contribution is dynamic algorithms that support dynamic operations in a decentralized manner. The simulations used to evaluate Tapestry were quite extensive, utilizing both artificial and real network data. They showed that the Tapestry system, with its soft state information, can provide self-administration, robustness, scalability, dynamic adapation, and graceful degration in the presence of failures and high load, all while avoiding the problems of the Plaxton system. What is left out of this paper is how Tapestry compares to Pastry, Chord, CAN, etc. This makes this paper somewhat difficult to evaluate in terms of raw performance and overhead, but I think it provides enough motivating ideas on these types of distriubted systems to make it valuable literature. From daehyun@csl.cornell.edu Tue Dec 4 13:44:55 2001 Received: from wilkes.csl.cornell.edu (wilkes.csl.cornell.edu [132.236.71.69]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fB4Iis623936 for ; Tue, 4 Dec 2001 13:44:54 -0500 (EST) Received: (from daehyun@localhost) by wilkes.csl.cornell.edu (8.9.3/8.9.2) id NAA76344 for egs@cs.cornell.edu; Tue, 4 Dec 2001 13:44:49 -0500 (EST) (envelope-from daehyun) From: Daehyun Kim Message-Id: <200112041844.NAA76344@wilkes.csl.cornell.edu> Subject: 615 PAPER 68 To: egs@CS.Cornell.EDU Date: Tue, 4 Dec 2001 13:44:49 -0500 (EST) X-Mailer: ELM [version 2.4ME+ PL54 (25)] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit This paper presents Tapestry which is an overlay location and routing infrastructure that provides location-independent routing of messages using only point-to-point links and without centralized resources. Tapestry is a self-organizing, scalable, robust wide-area infrastructure that efficiently routes requests to contents. It is based on the Plaxton distributed search technique, augmented with additional mechanisms to provide availability, scalability and adaptation in the presence of failure and attacks. It offers system-wide stability through statistics. Faulty components are masked, failed routes are bypassed, nodes under attack are removed from the service and communication topologies are rapidly adapted to circumstances. Tapestry overcome the limitation of Plaxton - the static nature of the algorithm. It focuses on supporting dynamic operations in a decentralized manner. It has additional mechanisms that leverage soft state information and eliminate the need for global information, root node vulnerabilities and a lack of adaptability, which provide good features mentioned above. The simulation results also show that they have achieved these design goals. From gupta@CS.Cornell.EDU Tue Dec 4 14:40:43 2001 Received: from zinger.cs.cornell.edu (zinger.cs.cornell.edu [128.84.96.55]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fB4Jeg603780 for ; Tue, 4 Dec 2001 14:40:42 -0500 (EST) From: Indranil Gupta Received: (from gupta@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id fB4JegO17932 for egs@cs.cornell.edu; Tue, 4 Dec 2001 14:40:42 -0500 (EST) Message-Id: <200112041940.fB4JegO17932@zinger.cs.cornell.edu> Subject: 615 PAPER 68 To: egs@CS.Cornell.EDU Date: Tue, 4 Dec 2001 14:40:42 -0500 (EST) X-Mailer: ELM [version 2.5 PL3] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Tapestry: an infrastructure for fault-tolerant wide-area location and routing, Zhao, Kubiaowitz, Joseph. Reviewer: Indranil Gupta This paper describes Tapestry, a large-scale routing infrastructure. Tapestry's underlying infrastructure is very similar to Pastry, with nodes choosing random id's based on a hash with SHA-1. The routing infrastructure relies on the neighbor table, which is the same as in Pastry. The only major differences with Pastry are 1) object replication is not done across neighbors in the namespace, but by using salts to hash the object id, and 2) that objects are not cached at intermediate nodes (between requesting node and root) in Tapestry - only pointers to the root are. Comments: - Tapestry is subject to a lot of the same criticisms as Pastry and Chord. Several researchers have raised the issue of whether such systems might actually be inherently unscalable due to several reasons, such as excessive copying due to pathological node failures. - Heartbeating across sets of nodes holding the same replicated object can impose a large load on the network (each node has to heartbeat to a subgroup of nodes for each object replica it holds), leading to either a compromise of the object availability properties, or a high load on core routers. From papadp@ece.cornell.edu Tue Dec 4 14:45:25 2001 Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.81.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fB4JjO604666 for ; Tue, 4 Dec 2001 14:45:24 -0500 (EST) Received: from kiki.ece.cornell.edu (kiki.ece.cornell.edu [128.84.83.13]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id fB4Jg1M20822; Tue, 4 Dec 2001 14:42:01 -0500 Date: Tue, 4 Dec 2001 14:48:42 -0500 (EST) From: "Panagiotis (Panos) Papadimitratos" To: Emin Gun Sirer cc: papadp@ece.cornell.edu Subject: 615 PAPER 68 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Review of:"Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing," by B. Y. Zhao et al. Panagiotis Papadimitratos papadp@ece.cornell.edu Tapestry is an application-level routing protocol that addresses the issue of locating data objects, which in principle are replicated through out the network. The addressing scheme draws from the classless inter-domain routing architecture, in the sense that it also aims at reducing dramatically the size of the routing tables (of course, no question it would be exhausting its name space :) The data are replicated and reside to a relatively limited set of servers, while meta-data, i.e., their advertisements are stored throughout the network, as servers publish the file ID's and they propagate. The server IDs are generated in a pseudo-random manner and are location-independent, and each published advertisement comprises the server Id -object Id pair. Routing is perfromed to the nearest 'neighbor' according to the name suffix, which guarantees log_b(N) hops per message. The suffix-based organization of names allows the neighbor table sizes to also be logarithmically bounded, due to the route aggregation in single route entries. The size is increased by the back-up links that are maintained in order to deal with 'route' failures. Algorithms for dynamic insertion and removal of nodes, node state handling and additional optimizations are also provided.