Optimizing Routing in Structured Peer-to-Peer Overlay NetworksUsing Routing Table RedundancyRongmei Zhang and Y. Charlie HuSchool of Electrical and Computer EngineeringPurdue UniversityWest Lafayette, IN 47907Peter DruschelDepartment of Computer ScienceRice UniversityHouston, TX 770051 IntroductionStructured peer-to-peer (p2p) overlay networks likeCAN, Chord, Pastry and Tapestry [3, 6, 5, 9] provide aself-organizing substrate for large-scale peer-to-peer ap-plications. These systems provide efficient, fault-tolerantrouting, object locatio n and load balancing within a self-organization overlay network.In this paper, we show how redundant information that iscollected as part of the normal overlay maintenance proto-col can be exploited to improve the performance of routing,in terms of both the number of routing hops and routing de-lay penalty. We use Pastry as a concrete example to describethe set of optimizations and to evaluate their improvementin routing performance via a large scale simulation usinga realistic network topology model. We then discuss howthese optimizations can be applied to other structured p2poverlays.2 Background on PastryIn th is section, we give a brief description o f Pastry.Pastry is a scalable, fault-tolerant, peer-to-peer substrate.Each Pastry node has a unique, uniform randomly assignednodeId in a circular 128-bit identifier space. Given a 128-bit key, Pastry routes the associated message towards thelive node whose nodeId is numerically closest to the key.For the purpose of routing, nodeIds and keys are thoughtof as a sequence of digits in base(is a configurationparameter with typical value 4). A node’s routing tableis organized intorows andcolumns. Theen-tries in rowof the routing table contain the IP addressesof nodes whose nodeIds share the firstdigits with thepresent node’s nodeId; the th nodeId digit of the nodein column of rowequals . A routing table entry isleft empty if no node with the appropriate nodeId prefix isknown. The uniform random distribution of nodeIds en-sures an even population of the nodeId space; thus, on aver-age onlylevels are populated in the routing table.Each node also maintains a leaf set. The leaf set is theset ofnodes with nodeIds that are numerically closest tothe present node’s nodeId, withlarger andsmallernodeIds than the current node’s id. A typical value forisapproximately. The leaf set ensures reliablemessage delivery and is used to store replicas of app licationobjects.At each routing step, a node seeks to forward the mes-sage to a node whose nodeId shares with the key a prefixthat is at least one digit (orbits) longer than the currentnode’s shared prefix. If no such node can be found in therouting table, the message is forwarded to a node whosenodeId shares a prefix with the key as long as the currentnode, but is numerically closer to the key than the presentnode’s id. Several such nodes can normally be found in therouting table; moreover, such a node is guaranteed to ex-ist in the leaf set unless the message has already arrived atthe node with numerically closest nodeId or its immediateneighbor. And, unless allnodes in one half of the leafset have failed simultaneously, at least one of those nodesmust be live.Experiments and analysis [5, 2] show that the expectednumber of forwarding hops is slightly below,with a d istribution that is tight around the mean.Node joining An arriving node with new nodeIdjoinsthe network by asking an existing, nearby Pastry nodeto route a special message usingas the key. (The IPaddress of an existing Pastry node must be learnt throughsome out-of-band mechanism). The message is routed tothe existing nodewith nodeId numerically closest to.then obtains the leaf set fromand appropriate rout-ing table entries from nodes encountered along path fromto. Using this information,can correctly initialize itsstate and notify other nodes that need to know of its arrival,thereby updating their node states.Proceedings of the The Ninth IEEE Workshop on Future Trends of Distributed Computing Systems (FTDCS’03) 0-7695-1910-5/03 $17.00 © 2003 IEEELocality-aware routing Pastry maintains a proximity-aware overlay by minimizing the distance, according to aproximity metric like network delay, to each of the nodesthat appear in a node’s routing table. Each entry refers toone of the nearest nodes with the required prefix match.Since the expected number of nodes with a given nodeIdprefix decreases exponentially with the length of the prefixmatch, the expected distance to an entry in a node’s rout-ing table increases exponentially with the length of the pre-fix match. As a result, in routing a random message, theexpected distance traveled in each successive routing stepincreases exponentially, and the distance of the last stepdominates. Because of this property of prefix routing, Pas-try routing exhibits two locality properties: (1) Low delaystretch: Analysis and simulations in [2] using realistic net-work topologies shows that the total delay experienced byPastry routing relative to the delay between the source anddestination via the underlying IP routing is usually belowtwo; (2) Local route convergence: Analysis and simula-tions also show that the routes of messages sent from nearbynodes to the same destination tend to converge at a nodenear the sending nodes.2.1 Redundancy in routing tablesDepending on how Pastry is implemented, each routingtable entry can hold more than one nodes. In [2], routing ta-ble maintenance was proposed to prevent the deteriorationof routing quality when the proximity metric may changedynamically. For each row in the routing table, the main-tenance procedure periodically requests the correspondingrow from a randomly chosen entry in that row. Each entry inthe obtained row is compared with the current entry and theclosest node is installed in the routing table. When a node isreplaced during the routing table maintenance or as a resultof an update caused by the arrival of a new node, it is keptin a list of alternative nodes instead of being removed fromthe routing table. The nodes in the list are selected basedon proximity if there are more candidates than the size ofthe entry. In [2], up to 10 nodes are saved in each entryof the routing table. Effectively, the
View Full Document
Unlocking...