New version page

UT CS 395T - Pastry - Scalable, decentralized object location and routing

Documents in this Course
TERRA

TERRA

23 pages

OpenCL

OpenCL

15 pages

Byzantine

Byzantine

32 pages

Load more
Upgrade to remove ads

This preview shows page 1-2-21-22 out of 22 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

Pastry: Scalable, decentralized object location androuting for large-scale peer-to-peer systems?Antony Rowstron1and Peter Druschel2??1Microsoft Research Ltd, St. George House,1 Guildhall Street, Cambridge, CB2 3NH, [email protected] University MS-132, 6100 Main Street,Houston, TX 77005-1892, [email protected] This paper presents the design and evaluation of Pastry, a scalable,distributed object location and routing substrate for wide-area peer-to-peer ap-plications. Pastry performs application-level routing and object location in a po-tentially very large overlay network of nodes connected via the Internet. It canbe used to support a variety of peer-to-peer applications, including global datastorage, data sharing, group communication and naming.Each node in the Pastry network has a unique identifier (nodeId). When presentedwith a message and a key, a Pastry node efficiently routes the message to thenode with a nodeId that is numerically closest to the key, among all currentlylive Pastry nodes. Each Pastry node keeps track of its immediate neighbors inthe nodeId space, and notifies applications of new node arrivals, node failuresand recoveries. Pastry takes into account network locality; it seeks to minimizethe distance messages travel, according to a to scalar proximity metric like thenumber of IP routing hops.Pastry is completely decentralized, scalable, and self-organizing; it automaticallyadapts to the arrival, departure and failure of nodes. Experimental results obtainedwith a prototype implementation on an emulated network of up to 100,000 nodesconfirm Pastry’s scalability and efficiency, its ability to self-organize and adapt tonode failures, and its good network locality properties.1 IntroductionPeer-to-peer Internet applications have recently been popularized through file sharingapplications like Napster, Gnutella and FreeNet [1,2,8]. While much of the attentionhas been focused on the copyright issues raised by these particular applications, peer-to-peer systems have many interesting technical aspects like decentralized control, self-organization, adaptation and scalability. Peer-to-peer systems can be characterized asdistributed systems in which all nodes have identical capabilities and responsibilitiesand all communication is symmetric.?Appears in Proc. of the 18th IFIP/ACM International Conference on Distributed Systems Plat-forms (Middleware 2001). Heidelberg, Germany, November 2001.??Work done in part while visiting Microsoft Research, Cambridge, UK.There are currently many projects aimed at constructing peer-to-peer applicationsand understanding more of the issues and requirements of such applications and sys-tems [1, 2,5,8,10,15]. One of the key problems in large-scale peer-to-peer applicationsis to provide efficient algorithms for object location and routing within the network.This paper presents Pastry, a generic peer-to-peer object location and routing scheme,based on a self-organizing overlay network of nodes connected to the Internet. Pastryis completely decentralized, fault-resilient, scalable, and reliable. Moreover, Pastry hasgood route locality properties.Pastry is intended as general substrate for the construction of a variety of peer-to-peer Internet applications like global file sharing, file storage, groupcommunication andnaming systems. Several application have been built on top of Pastry to date, includinga global, persistent storage utility called PAST [11,21] and a scalable publish/subscribesystem called SCRIBE [22]. Other applications are under development.Pastry provides the following capability. Each node in the Pastry network has aunique numeric identifier (nodeId). When presented with a message and a numeric key,a Pastry node efficiently routes the message to the node with a nodeId that is numeri-cally closest to the key, among all currently live Pastry nodes. The expected number ofrouting steps is O(log N), where N is the number of Pastry nodes in the network. Ateach Pastry node along the route that a message takes, the application is notified andmay perform application-specific computations related to the message.Pastry takes into account network locality; it seeks to minimize the distance mes-sages travel, according to a scalar proximity metric like the number of IP routing hops.Each Pastry node keeps track of its immediate neighbors in the nodeId space, and no-tifies applications of new node arrivals, node failures and recoveries. Because nodeIdsare randomly assigned, with high probability, the set of nodes with adjacent nodeId isdiverse in geography, ownership, jurisdiction, etc. Applications can leverage this, asPastry can route to one ofknodes that are numerically closest to the key. A heuristicensures that among a set of nodes with thekclosest nodeIds to the key, the message islikely to first reach a node “near” the node from which the message originates, in termsof the proximity metric.Applications use these capabilities in different ways. PAST, for instance, uses afileId, computed as the hash of the file’s name and owner, as a Pastry key for a file.Replicas of the file are stored on thekPastry nodes with nodeIds numerically closest tothe fileId. A file can be looked up by sending a message via Pastry, using the fileId as thekey. By definition, the lookup is guaranteed to reach a node that stores the file as longas one of theknodes is live. Moreover, it follows that the message is likely to first reacha node near the client, among theknodes; that node delivers the file and consumes themessage. Pastry’s notification mechanisms allow PAST to maintain replicas of a fileon theknodes closest to the key, despite node failure and node arrivals, and using onlylocal coordination among nodes with adjacent nodeIds. Details on PAST’s use of Pastrycan be found in [11,21].As another sample application, in the SCRIBE publish/subscribe System, a list ofsubscribers is stored on the node with nodeId numerically closest to the topicId of atopic, where the topicId is a hash of the topic name. That node forms a rendez-vouspoint for publishers and subscribers. Subscribers send a message via Pastry using thetopicId as the key; the registration is recorded at each node along the path. A publishersends data to the rendez-vous point via Pastry, again using the topicId as the key. Therendez-vouspoint forwards the data along the multicast tree formed by the reverse pathsfrom the rendez-vous point to all subscribers. Full


View Full Document
Download Pastry - Scalable, decentralized object location and routing
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Pastry - Scalable, decentralized object location and routing and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Pastry - Scalable, decentralized object location and routing 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?