On space-stretch trade-offs: lower bounds

ABSTRACT

One of the fundamental trade-offs in compact routing schemes is between the space used to store the routing table on each node and the stretch factor of the routing scheme -- the ratio between the cost of the route induced by the scheme and the cost of a minimum cost path between the same pair. Using a distributed Kolmogorov Complexity argument, we give a lower bound for the name-independent model that applies even to single-source schemes and does not require a girth conjecture. For any integer k ≥ 1 we prove that any routing scheme for networks with arbitrary weights and arbitrary node names (even a single-source routing scheme) with maximum stretch strictly less than 2k + 1 requires Ω((n log n)^1/k)-bit routing tables. We extend our results to lower bound the average-stretch, showing that for any integer k ≥ 1 any name-independent routing scheme with (n/(9k))^1/k-bit routing tables has average-stretch of at least k/4 + 7/8. This result is in sharp contrast to recent results on the average-stretch of labeled routing schemes.

REFERENCES

• 1: Ittai Abraham , Yair Bartal , Ofer Neimany, Advances in metric embedding theory, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132557]
• 2: Noga Alon, Shlomo Hoory, and Nathan Linial. The Moore bound for irregular graphs. Graph and Combinatorics, 18(1):53--57, 2002.
• 3: Harry Buhrman , Jaap-Henk Hoepman , Paul Vitányi, Space-efficient Routing Tables for Almost All Networks and the Incompressibility Method, SIAM Journal on Computing, v.28 n.4, p.1414-1432, Aug. 1999 [doi>10.1137/S0097539796308485]
• 4: Paul Erdös. Extremal problems in graph theory. In Publ. House Cszechoslovak Acad. Sci., Prague, pages 29--36, 1964.
• 5: Pierre Fraigniaud , Cyril Gavoille, Routing in Trees, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.757-772, July 08-12, 2001
• 6: Pierre Fraigniaud , Cyril Gavoille, A Space Lower Bound for Routing in Trees, Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, p.65-75, March 14-16, 2002
• 7: Cyril Gavoille , Stéphane Pérennès, Memory requirement for routing in distributed networks, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.125-133, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248075]
• 8: Evangelos Kranakis , Danny Krizanc, Lower Bounds for Compact Routing (Extended Abstract), Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science, p.529-540, February 22-24, 1996
• 9: Kofi A. Laing, Brief announcement: name-independent compact routing in trees, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011841]
• 10: Kofi A. Laing , Rajmohan Rajaraman, A space lower bound for name-independent compact routing in trees, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1074005]
• 11: Felix Lazebnik, Vasiliy A. Ustimenko, and Andrew J. Woldar. A new series of dense graphs of high girth. Bulletin of the American Mathematical Society (New Series), 32(1):73--79, January 1995.
• 12: Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications (2nd ed.), Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 13: David Peleg , Eli Upfal, A trade-off between space and efficiency for routing tables, Journal of the ACM (JACM), v.36 n.3, p.510-530, July 1989 [doi>10.1145/65950.65953]
• 14: Mikkel Thorup , Uri Zwick, Compact routing schemes, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.1-10, July 2001, Crete Island, Greece [doi>10.1145/378580.378581]

INDEX TERMS

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

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

General Terms:
Algorithms, Theory

Keywords:
compact routing