IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 22, NO. 1, JANUARY 2004 41Tapestry: A Resilient Global-Scale Overlay forService DeploymentBen Y. Zhao, Ling Huang, Jeremy Stribling, Sean C. Rhea, Anthony D. Joseph, Member, IEEE, andJohn D. Kubiatowicz, Member, IEEEAbstract—We present Tapestry, a peer-to-peer overlay routinginfrastructure offering efficient, scalable, location-independentrouting of messages directly to nearby copies of an object orservice using only localized resources. Tapestry supports a genericdecentralized object location and routing applications program-ming interface using a self-repairing, soft-state-based routinglayer. This paper presents the Tapestry architecture, algorithms,and implementation. It explores the behavior of a Tapestrydeployment on PlanetLab, a global testbed of approximately 100machines. Experimental results show that Tapestry exhibits stablebehavior and performance as an overlay, despite the instabilityof the underlying network layers. Several widely distributedapplications have been implemented on Tapestry, illustrating itsutility as a deployment infrastructure.Index Terms—Overlay networks, peer-to-peer (P2P), service de-ployment, Tapestry.I. INTRODUCTIONINTERNET developers are constantly proposing new andvisionary distributed applications. These new applicationshave a variety of requirements for availability, durability, andperformance. One technique for achieving these properties isto adapt to failures or changes in load through migration andreplication of data and services. Unfortunately, the ability toplace replicas or the frequency with which they may be movedis limited by underlying infrastructure. The traditional way todeploy new applications is to adapt them somehow to existinginfrastructures (often an imperfect match) or to standardize newInternet protocols (encountering significant intertia to deploy-ment). A flexible but standardized substrate on which to developnew applications is needed.In this paper, we present Tapestry [1], [2], an extensibleinfrastructure that provides decentralized object location androuting (DOLR) [3]. The DOLR interface focuses onroutingof messages to endpoints such as nodes or object replicas.DOLR virtualizes resources, since endpoints are named byopaque identifiers encoding nothing about physical location.Properly implemented, this virtualization enables messageManuscript received November 15, 2002; revised May 1, 2003. This paperwas supported in part by the National Science Foundation (NSF) under CareerAward ANI-9985129 and Career Award ANI-9985250, in part by the NSF In-formation Technology Research (ITR) under Award 5710001344, in part by theCalifornia Micro Fund under Award 02-032 and Award 02-035, and in part byGrants from IBM and Sprint.B. Y. Zhao, L. Huang, S. C. Rhea, A. D. Joseph, and J. D. Kubiatowicz arewith the University of California, Berkeley, CA 94720 USA (e-mail: [email protected]; [email protected]; [email protected]; [email protected]; [email protected]).J. Stribling is with Massachusetts Institute of Technology, Cambridge, MA02139 USA (e-mail: [email protected]).Digital Object Identifier 10.1109/JSAC.2003.818784delivery to mobile or replicated endpoints in the presence ofinstability in the underlying infrastructure. As a result, a DOLRnetwork provides a simple platform on which to implementdistributed applications—developers can ignore the dynamicsof the network except as an optimization. Already, Tapestry hasenabled the deployment of global-scale storage applicationssuch as OceanStore [4] and multicast distribution systems suchas Bayeux [5]; we return to this in Section VI.Tapestry is a peer-to-peer (P2P) overlay network that pro-vides high-performance, scalable, and location-independentrouting of messages to close-by endpoints, using only localizedresources. The focus on routing brings with it a desire for effi-ciency: minimizing message latency and maximizing messagethroughput. Thus, for instance, Tapestry exploits locality inrouting messages to mobile endpoints such as object replicas;this behavior is in contrast to other structured P2P overlaynetworks [6]–[11].Tapestry uses adaptive algorithms with soft state to maintainfault tolerance in the face of changing node membership andnetwork faults. Its architecture is modular, consisting of an ex-tensible upcall facility wrapped around a simple, high-perfor-mance router. This applications programming interface (API)enables developers to develop and extend overlay functionalitywhen the basic DOLR functionality is insufficient.In the following pages, we describe a Java-based implemen-tation of Tapestry, and present both microbenchmarks and mac-robenchmarks from an actual, deployed system. During normaloperation, the relative delay penalty (RDP)1to locate mobileendpoints is two or less in the wide area. Simulations show thatTapestry operations succeed nearly 100% of the time under bothconstant network changes and massive failures or joins, withsmall periods of degraded performance during self-repair. Theseresults demonstrate Tapestry’s feasibility as a long running ser-vice on dynamic, failure-prone networks such as the wide-areaInternet.The following section discusses related work. Then,Tapestry’s core algorithms appear in Section III, with details ofthe architecture and implementation in Section IV. Section Vevaluates Tapestry’s performance. We then discuss the use ofTapestry as an application infrastructure in Section VI andconclude with Section VII.II. RELATED WORKThe first generation of peer-to-peer systems includedfile-sharing and storage applications: Napster, Gnutella,1RDP, or stretch, is the ratio between the distance traveled by a message to anendpoint and the minimal distance from the source to that endpoint.0733-8716/04$20.00 © 2004 IEEE42 IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 22, NO. 1, JANUARY 2004MojoNation, and Freenet. Napster uses central directoryservers to locate files. Gnutella provides a similar, but dis-tributed service using scoped broadcast queries, limitingscalability. MojoNation [12] uses an online economic model toencourage sharing of resources. Freenet [13] is a file-sharingnetwork designed to resist censorship. Neither Gnutella norFreenet guarantee that files can be located—even in a func-tioning network.The second generation of P2P systems are structured P2Poverlay networks, including Tapestry [1], [2], Chord [8], Pastry[7], and CAN
View Full Document
Unlocking...