Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks

ABSTRACT

Several peer-to-peer networks are based upon randomized graph topologies that permit efficient greedy routing, e. g., randomized hypercubes, randomized Chord, skip-graphs and constructions based upon small-world percolation networks. In each of these networks, a node has out-degree Θ(log n), where n denotes the total number of nodes, and greedy routing is known to take O(log n) hops on average. We establish lower-bounds for greedy routing for these networks, and analyze Neighbor-of-Neighbor (NoN)-greedy routing. The idea behind NoN, as the name suggests, is to take a neighbor's neighbors into account for making better routing decisions.The following picture emerges: Deterministic routing networks like hypercubes and Chord have diameter Θ(log n) and greedy routing is optimal. Randomized routing networks like randomized hypercubes, randomized Chord, and constructions based on small-world percolation networks, have diameter Θ(log n / log log n) with high probability. The expected diameter of Skip graphs is also Θ(log n / log log n). In all of these networks, greedy routing fails to find short routes, requiring Ω(log n) hops with high probability. Surprisingly, the NoN-greedy routing algorithm is able to diminish route-lengths to Θ(log n / log log n) hops, which is asymptotically optimal.

REFERENCES

• 1: Ittai Abraham , Baruch Awerbuch , Yossi Azar , Yair Bartal , Dahlia Malkhi , Elan Pavlov, A Generic Scheme for Building Overlay Networks in Adversarial Scenarios, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.40.2, April 22-26, 2003
• 2: M. Aizenman and C. M. Newman. Discontinuity of the percolation density in one dimensional 1/|x-y|2 percolation models. Communications in Mathematical Physics, 107:611--647, 1986.
• 3: James Aspnes , Zoë Diamadi , Gauri Shah, Fault-tolerant routing in peer-to-peer systems, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571862]
• 4: James Aspnes , Gauri Shah, Skip graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 5: Albert-Laszlo Barabasi, Linked, Perseus Publishing, 2002
• 6: Lali Barrière , Pierre Fraigniaud , Evangelos Kranakis , Danny Krizanc, Efficient Routing in Networks with Long Range Contacts, Proceedings of the 15th International Conference on Distributed Computing, p.270-284, October 03-05, 2001
• 7: Itai Benjamini , Noam Berger, The diameter of long-range percolation clusters on finite cycles, Random Structures & Algorithms, v.19 n.2, p.102-111, September 2001 [doi>10.1002/rsa.1022]
• 8: M. Castro, P. Druschel, Y. C. Hu, and A. I. T. Rowstron. Topology-aware routing in structured peer-to-peer overlay networks. In Proc. Intl. Workshop on Future Directions in Distrib. Computing (FuDiCo 2003), pages 103--107, 2003.
• 9: H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Mathmematical Statistics, 23:493--509, 1952.
• 10: Don Coppersmith , David Gamarnik , Maxim Sviridenko, The diameter of a long-range percolation graph, Random Structures & Algorithms, v.21 n.1, p.1-13, August 2002 [doi>10.1002/rsa.10042]
• 11: P. S. Dodds, M. Roby, and D. J. Watts. An experimental study of search in global social networks. Science, 301:827--829, 2003.
• 12: Pierre Fraigniaud , Philippe Gauron, Brief announcement: an overview of the content-addressable network D2B, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.151-151, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872056]
• 13: P. Fraigniaud, C. Gavoille, and C. Paul. Eclecticism shrinks the world. Technical Report LRI-1376, University Paris-Sud, November 2003.
• 14: Prasanna Ganesan , Gurmeet Singh Manku, Optimal routing in Chord, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 15: K. Gummadi , R. Gummadi , S. Gribble , S. Ratnasamy , S. Shenker , I. Stoica, The impact of DHT routing geometry on resilience and proximity, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863998]
• 16: Nicholas J. A. Harvey , J. Ian Munro, Brief announcement: deterministic skipnet, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.152-152, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872057]
• 17: N. J. A. Harvey, M. Jones, S. Saroiu, M. Theimer, and A. Wolman. Skipnet: A scalable overlay network with practical locality properties. In Proc. 4th USENIX Symposium on Internet Technologies and Systems (USITS 2003), 2003.
• 18: M. F. Kaashoek and D. R. Karger. Koorde: A simple degree-optimal hash table. In Proc. 2nd Intl. Workshop on Peer-to-Peer Systems (IPTPS 2003), pages 98--107, 2003.
• 19: Jon Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.163-170, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335325]
• 20: Dmitri Loguinov , Anuj Kumar , Vivek Rai , Sai Ganesh, Graph-theoretic analysis of structured peer-to-peer systems: routing distances and fault resilience, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863999]
• 21: Dahlia Malkhi , Moni Naor , David Ratajczak, Viceroy: a scalable and dynamic emulation of the butterfly, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571857]
• 22: Gurmeet Singh Manku, Routing networks for distributed hash tables, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.133-142, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872054]
• 23: G. S. Manku, M. Bawa, and P. Raghavan. Symphony: Distributed hashing in a small world. In Proc. 4th USENIX Symposium on Internet Technologies and Systems (USITS 2003), pages 127--140, 2003.
• 24: S. Milgram. The small world problem. Psychology Today, 67(1):60--67, May 1967.
• 25: Moni Naor , Udi Wieder, Novel architectures for P2P applications: the continuous-discrete approach, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777421]
• 26: M. Naor and U. Wieder. Know thy neighbor's neighbor: Better routing for skip-graphs and small worlds. In The Third International Workshop on Peer-to-Peer Systems (IPTPS), 2004.
• 27: C. M. Newman and L. S. Schulman. One dimensional 1/|j-i|s percolation models: The existence of a transition for $sleq 2$. Communications in Mathematical Physics, 180:483--504, 1986.
• 28: M. E. J. Newman, D. J. Watts, and S. H. Strogatz. Random graph models of social networks. Proc. National Academy of Science, USA, 99 (suppl 1):2566--2572, 2002.
• 29: I. Pool and M. Kochen. Contacts and influence. Social Networks, 1:1--48, 1978.
• 30: William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990 [doi>10.1145/78973.78977]
• 31: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 32: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 33: L. S. Schulman. Long range percolation in one dimension. Journal of Physics A, 16(17):L639--L641, 1983.
• 34: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 35: D. Watts and S. Strogatz. Collective dynamics of small-world networks. Nature, pages 440--442, 1998.
• 36: Hui Zhang , Ashish Goel , Ramesh Govindan, Incrementally improving lookup latency in distributed hash table systems, ACM SIGMETRICS Performance Evaluation Review, v.31 n.1, June 2003
• 37: B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, and J. D. Kubiatowicz. Tapestry: A resilient global-scale overlay for service deployment. IEEE Journal on Selected Areas in Communications, 22(1), Jan. 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

General Terms:
Algorithms

Keywords:
greedy routing, peer to peer networks, random structures