Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems (Antony Rowstron and Peter Druschel)PastryOutlineGuaranteesPastry Node State (1)Routing TableRouting MessagesRouting Performance: IntuitionThe Pastry APISelf-organization: Node ArrivalState InitializationSelf-organization: Node FailureLocalityHandling Malicious NodesRouting PerformanceMessaging DistanceQuality of Routing TablesTake-awayDiscussionPastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems(Antony Rowstron and Peter Druschel)Shariq RizviFirst Year Graduate StudentCS Division, UC [email protected] 8, 2003 CS 294-4: Peer-to-Peer Systems2PastryAn overlay network that provides a self-organizing routing and location service (like Chord)Seeks to minimize the distance (scalar proximity metric like routing hops) messages travel Expected number of routing steps is O(log N); N=No. of Pastry nodes in the networkSep 8, 2003 CS 294-4: Peer-to-Peer Systems3OutlineGuaranteesDesign of pastryNode stateRouting algorithmSelf-organizationAddressing localityExperimental ResultsDiscussionSep 8, 2003 CS 294-4: Peer-to-Peer Systems4GuaranteesNodeId randomly assigned from {0, .., 2128-1}b, |L| are configuration parametersUnder normal conditions:1. A pastry node can route to the numerically closest node to a given key in less than log2b N steps2. Despite concurrent node failures, delivery is guaranteed unless more than |L|/2 nodes with adjacent NodeIds fail simultaneously3. Each node join triggers O(log2b N) messagesSep 8, 2003 CS 294-4: Peer-to-Peer Systems5Pastry Node State (1)Set of nodes with |L|/2 smaller and |L|/2 larger numerically closest NodeIds|M| “physically” closest nodes Prefix-based routing entriesSep 8, 2003 CS 294-4: Peer-to-Peer Systems6Routing TableNodeIds are in base 2bSeveral rows – one for each prefix of local NodeId (Log2b N populated on average)2b – 1 columns – one for each possible digit in the NodeId representationb defines the tradeoff:(Log2b N) x (2b – 1) entries Vs. Log2b N routing hopsSep 8, 2003 CS 294-4: Peer-to-Peer Systems7Routing MessagesD: Message KeyLi: ith closest NodeId in leaf setshl(A, B): Length of prefix shared by nodes A and BRij: (j, i)th entry of routing table(1) Single hop(2) Towards better prefix-match(3) Towards numerically closer NodeIdSep 8, 2003 CS 294-4: Peer-to-Peer Systems8Routing Performance: Intuition(1) – Single hop, termination(2) – No. of nodes which prefix-match the key upto current length reduces by 2b(3) – Low probability, adds one hopSep 8, 2003 CS 294-4: Peer-to-Peer Systems9The Pastry APIOperations exported by PastrynodeId = pastryInit(Credentials,Application)route(msg,key)Operations exported by the application working above Pastrydeliver(msg,key)forward(msg,key,nextId)newLeafs(leafSet)Sep 8, 2003 CS 294-4: Peer-to-Peer Systems10Self-organization: Node ArrivalArriving Node X knows “nearby” node AX asks A to route a “join” message with key = NodeId(X)Message targets Z, whose NodeId is numerically closest to NodeId(X)All nodes along the path A, B, …, Z send state tables to XX initializes its state using this informationX sends its state to “concerned” nodesSep 8, 2003 CS 294-4: Peer-to-Peer Systems11State InitializationX borrows A’s Neighborhood SetX’s leaf set derived from Z’s leaf setX0 set to A0X1 set to B1, X2 set to C2, …XABCZSep 8, 2003 CS 294-4: Peer-to-Peer Systems12Self-organization: Node FailureDetected when a live node tries to contact a failed nodeUpdating Leaf set – get leaf set from L-|L|/2 or L|L|/2Updating routing table - To repair Rdl , ask Ril for its RdlUpdating neighborhood set – Ask alive set-members for their neighbors|L|/2 bound on failed nodesSep 8, 2003 CS 294-4: Peer-to-Peer Systems13LocalityApplication provides the “distance” functionInvariant: “All routing table entries refer to a node that is near the present node, according to the proximity metric, among all live nodes with an appropriate prefix” Invariant maintained on self-organizationSep 8, 2003 CS 294-4: Peer-to-Peer Systems14Handling Malicious NodesRouting is deterministicRandomize choice between multiple suitable candidates – with a bias towards the best oneSep 8, 2003 CS 294-4: Peer-to-Peer Systems15Routing Performanceb=4; |L|=16; |M|=32; 200,000 lookups; Random end pointsSep 8, 2003 CS 294-4: Peer-to-Peer Systems16Messaging Distance b=4; |L|=16; |M|=32; 200,000 lookups; Random end pointsSep 8, 2003 CS 294-4: Peer-to-Peer Systems17Quality of Routing Tablesb=4; |L|=16; |M|=32; 5000 New NodesSep 8, 2003 CS 294-4: Peer-to-Peer Systems18Take-away “Locality concerns added to O(log N) routing and self-organization”Sep 8, 2003 CS 294-4: Peer-to-Peer Systems19DiscussionWhen is the neighborhood set used?No equivalent of Chord’s key migration when new nodes join – will non-replicating file-sharing applications suffer? role of newLeafs(leafSet)
View Full Document
Unlocking...