Know thy Neighbor’s Neighbor: the Power of Lookahead inRandomized P2P Networks∗Gurmeet Singh MankuStanford UniversityCalifornia [email protected] Naor†Weizmann Institute of ScienceRehovot [email protected] WiederWeizmann Institute of ScienceRehovot [email protected] peer-to-peer networks are based upon randomized graphtopologies that permit efficient greedy routing, e.g., random-ized hypercubes, randomized Chord, skip-graphs and construc-tions based upon small-world percolation networks. In each ofthese networks, a node has out-degree Θ(log n), where n denotesthe total number of nodes, and greedy routing is known to takeO(log n) hops on average. We establish lower-bounds for greedyrouting for these networks, and analyze Neighbor-of-Neighbor(NoN)-greedy routing. The idea behind NoN, as the name sug-gests, is to take a neighbor’s neighbors into account for makingbetter routing decisions.The following picture emerges: Deterministic routing networkslike hypercubes and Chord have diameter Θ(log n)andgreedyrouting is optimal. Randomized routing networks like random-ized hypercubes, randomized Chord, and constructions based onsmall-world percolation networks, have diameter Θ(log n/ log log n)with high probability. The expected diameter of Skip graphs isalso Θ(log n/ log log n). In all of these networks, greedy rout-ing fails to find short routes, requiring Ω(log n) hops with highprobability. Surprisingly, the NoN-greedy routing algorithm isable to diminish route-lengths to Θ(log n/ log log n)hops,whichis asymptotically optimal.Categories and Subject DescriptorsC.2.1 [Computer Systems]: computer-communication networks;General TermsAlgorithmsKeywordsGreedy Routing, Peer to Peer Networks, Random Structures∗Research supported in part by the RAND/APX grantfrom the EU Program IST, NSF Grants IIS-0118173, EIA-0137761, and an SNRC grant.†Incumbent of the Judith Kleeman Professorial Chair.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.STOC’04, June 13–15, 2004, Chicago, Illinois, USA.Copyright 2004 ACM 1-58113-852-0/04/0006 ...$5.00.1. INTRODUCTIONRandomized network constructions that model the Small-World Phenomenon have recently received considerable at-tention. A widely-held belief pertaining to social networks isthat any two people in the world are connected via a chain ofsix acquaintances (six-degrees of separation)1.Thequanti-tative study of the phenomenon started with Milgram’s [24]experiments in 1960’s, asking people to send letters to un-familiar targets only through acquaintances. Milgram’s ex-periments, and a work by Pool and Kochen [29] confirmedthat random pairs of individuals are indeed connected byshort chains. As was noticed by Kleinberg [19], Milgram’sexperiments also demonstrated that individuals are able toroute messages to unknown targets..To model the routing aspects of the Small-World Phe-nomenon, Kleinberg constructed a family of random graphs.The graphs not only have small diameter (to model the“six degrees of separation”) but also allow short routes tobe discovered on the basis of local information alone (tomodel Milgram’s observation that messages can be “routedto unknown individuals efficiently”). In particular, Klein-berg considered a 2D n ×n grid with n2nodes. Each nodeis equipped with a small set of “local” contacts and one“long-range” contact drawn from a harmonic distribution.With greedy routing, the path-length between any pair ofnodes is O(log2n) hops, w.h.p. Local knowledge available toanodesufficesforgreedy routing – a message is forwardedalong that out-going link which takes it closest to the des-tination. Barri`ere et al [6] showed that greedy routingrequires Ω(log2n) hops for Kleinberg’s construction.Randomized Peer-to-Peer NetworksSymphony [23] is a successful adaptation of Kleinberg’s con-struction [19] to arrive at a randomized P2P routing net-work. The idea is to place nodes in a ring (instead ofa 2D grid) and to equip each node with multiple “long-distance” links (instead of one). The average length ofgreedy routes has been shown to be O(log2nk)bothbyManku et al [23] and by Aspnes et al [3]. Recently, threemore randomized P2P networks have been devised, all ofwhich use greedy routing: randomized-hypercube [15, 8],randomized-Chord [15, 36], and skip-graphs [4] (also knownas SkipNet [17]). Randomized-Chord is a variation on adeterministic P2P routing network called Chord [34, 14].1AccordingtoBarab´asi [5] this idea may have its origins in ashort story “Chains” by the Hungarian writer Frigyes Karinthyfrom 1929; this idea has been retold and recast many times sincethen, in the literature, popular press as well as scientific studies.54Skip-graphs build upon the intuition inherent in the skip-lists data structure [30]. All of these networks have Θ(log n)out-going links per node. greedy routing is known to takeO(log n) hops on average.Among the various P2P routing networks, skip-graphs areunique in that node identifiers (or “keys” associated withnodes) can be drawn from an arbitrary ordered domain,e.g., the set of character strings. This property makes skip-graphs the only P2P routing network that naturally sup-ports prefix-search. Other P2P routing networks assumethat nodes are assigned identifiers that are drawn uniformlyfrom the unit interval [0, 1).Many P2P networks share structural similarities with anetwork in which nodes are associated with a d−dimensionaltorus, and an edge (i, j) is established with probability1||i−j||d.We call this network a small-world percolation network.Thesmall-world percolation network has its antecedents in clas-sical “long range percolation” models. We outline a briefhistory at the beginning of Section 2.Our work addresses two questions: (a) Is greedy routingoptimal? (b) What is the role of look-ahead upon greedyrouting? The idea underlying “look-ahead” is to allow anode to gain knowledge of its neighbor’s neighbors for as-sistance in making better routing decisions. In a networkwith k out-going links per node, the average
View Full Document
Unlocking...