Tight lower bounds for greedy routing in uniform small world rings

ABSTRACT

We consider augmented ring-based networks with vertices 0,...,n-1, where each vertex is connected to its left and right neighbor and possibly to some further vertices (called long range contacts). The outgoing edges of a vertex v are obtained by choosing a subset D of {1,2,...n-1}, with 1, n-1 in D, at random according to a probability distribution mu on all such D and then for each i in D connecting v to (v+i) mod n by a unidirectional link. The choices for different v are done independently and uniformly in the sense that the same distribution mu is used for all v. The expected number of long range contacts is l=E(|D|)-2. Motivated by Kleinberg's (2000) Small World Graph model and packet routing strategies for peer-to-peer networks, the greedy routing algorithm on augmented rings, where a packet sitting in a node v is routed to the neighbor of v closest to the destination of the package, has been investigated thoroughly, both for the "one-sided case", where packets can travel only in one direction, and the "two-sided case", where there is no such restriction. In this paper, for both the one-sided and the two-sided case and for an arbitrary distribution mu, we prove a lower bound of Omega((log n)²/l) on the expected number of hops that are needed by the greedy strategy to route a package between two randomly chosen vertices on the ring. This bound is tight for Omega(1)<=l=O(log n).

REFERENCES

• 1: 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]
• 2: 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
• 3: M. Dietzfelbinger, J. E. Rowe, I. Wegener, and P. Woelfel. Tight bounds for blind search on the integers. In Proc. 25th Annual. Symp. on Theoretical Aspects of Computer Science (STACS), pp. 241--252,2008.
• 4: M. Flammini, L. Moscardelli, A. Navarra, and S. Perennes. Asymptotically optimal solutions for small world graphs. In Proc. 19th Int. Symp. on Distributed Computing (DISC), pp. 414--428, 2005.
• 5: P. Fraigniaud. Small worlds as navigable augmented networks: Model, analysis, and validation. In Proc. 15th European Symp. on Algorithms (ESA), pp. 2--11,2007.
• 6: Pierre Fraigniaud , Cyril Gavoille , Adrian Kosowski , Emmanuelle Lebhar , Zvi Lotker, Universal augmentation schemes for network navigability: overcoming the √n-barrier, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248379]
• 7: 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
• 8: George Giakkoupis , Vassos Hadzilacos, On the complexity of greedy routing in ring-based peer-to-peer networks, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281117]
• 9: 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]
• 10: Jens Jägersküpper, Algorithmic analysis of a basic evolutionary algorithm for continuous optimization, Theoretical Computer Science, v.379 n.3, p.329-347, July 2007 [doi>10.1016/j.tcs.2007.02.042]
• 11: J. M. Kleinberg. Navigation in a small world. Nature, p. 845, 2000.
• 12: 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]
• 13: J. M. Kleinberg. Complex networks and decentralized search algorithms. In Proc. International Congress of Mathematicians, Vol. III, pp. 1019--1044, 2006.
• 14: Gurmeet Singh Manku , Mayank Bawa , Prabhakar Raghavan, Symphony: distributed hashing in a small world, Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems, p.10-10, March 26-28, 2003, Seattle, WA
• 15: S. Milgram. The small-world problem. Psychology Today, 67(1):60--67, 1967.
• 16: Ion Stoica , Robert Morris , David Liben-Nowell , David R. Karger , M. Frans Kaashoek , Frank Dabek , Hari Balakrishnan, Chord: a scalable peer-to-peer lookup protocol for internet applications, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.17-32, February 2003 [doi>10.1109/TNET.2002.808407]
• 17: D. Watts and S. Strogatz. Collective dynamics of small-world networks. Nature, 393:440--442, 1998.
• 18: J. Xu. On the fundamental tradeoffs between routing table size and network diameter in peer-to-peer networks. In Proc. 22nd Ann. Joint Conf. of the IEEE Computer and Communications Societies (INFOCOM), 2003

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

General Terms:
Algorithms, Performance, Theory

Keywords:
greedy routing, lower bound, peer-to-peer, random graphs, small world graphs, small worlds