Brief announcement: tight lower bounds for greedy routing in uniform small world rings

ABSTRACT

Motivated by Kleinberg's Small World Graph model and packet routing strategies in peer-to-peer networks, greedy routing algorithms on augmented networks have been investigated thoroughly. We prove tight lower bounds for one- and two-sided greedy routing on augmented rings.

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: M. Dietzfelbinger, J. E. Rowe, I. Wegener, and P. Woelfel. Tight bounds for blind search on the integers. In Proc. 25th STACS, pp. 241--252, 2008.
• 3: Martin Dietzfelbinger , Philipp Woelfel, Tight lower bounds for greedy routing in uniform small world rings, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA [doi>10.1145/1536414.1536494]
• 4: M. Flammini, L. Moscardelli, A. Navarra, and S. Pérennes. Asymptotically optimal solutions for small world graphs. In Proc. 19th DISC, pp. 414--428, 2005.
• 5: P. Fraigniaud. Small worlds as navigable augmented networks: Model, analysis, and validation. In Proc. 15th ESA, pp. 2--11, 2007.
• 6: 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
• 7: 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]
• 8: 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]
• 9: 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]
• 10: J. M. Kleinberg. Navigation in a small world. Nature, p. 845, 2000.
• 11: 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]
• 12: J. M. Kleinberg. Complex networks and decentralized search algorithms. In Proc. International Congress of Mathematicians, Vol. III, pp. 1019--1044, 2006.
• 13: 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
• 14: S. Milgram. The small-world problem. Psychology Today, 67(1):60--67, 1967.
• 15: 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]
• 16: D. Watts and S. Strogatz. Collective dynamics of small-world networks. Nature, 393:440--442, 1998.
• 17: J. Xu. On the fundamental tradeoffs between routing table size and network diameter in peer-to-peer networks. In Proc. 22nd 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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms; Network problems

General Terms:
Algorithms, Performance, Theory

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