skip to main content
10.1145/1148109.1148143acmconferencesArticle/Chapter ViewAbstractPublication PagesspaaConference Proceedingsconference-collections
Article

On space-stretch trade-offs: lower bounds

Published: 30 July 2006 Publication History

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, and Ofer Neiman. Advances in metric embedding theory. In 38th Annual ACM Symposium on Theory of Computing (STOC), pages 271--286. ACM Press, May 2006.]]
[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, and Paul Vitányi. Space-efficient routing tables for almost all networks and the incompressibility method. SIAM Journal on Computing, 28(4):1414--1432, 1999.]]
[4]
Paul Erdös. Extremal problems in graph theory. In Publ. House Cszechoslovak Acad. Sci., Prague, pages 29--36, 1964.]]
[5]
Pierre Fraigniaud and Cyril Gavoille. Routing in trees. In 28th International Colloquium on Automata, Languages and Programming (ICALP), volume 2076 of Lecture Notes in Computer Science, pages 757--772. Springer, July 2001.]]
[6]
Pierre Fraigniaud and Cyril Gavoille. A space lower bound for routing in trees. In 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 2285 of Lecture Notes in Computer Science, pages 65--75. Springer, March 2002.]]
[7]
Cyril Gavoille and Stéphane Pérennès. Memory requirement for routing in distributed networks. In 15th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 125--133. ACM Press, May 1996.]]
[8]
Evangelos Kranakis and Danny Krizanc. Lower bounds for compact routing. In 13th Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 1046 of Lecture Notes in Computer Science, pages 529--540. Springer-Verlag, February 1996.]]
[9]
Kofi Ambrose Laing. Brief announcement: name-independent compact routing in trees. In 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 382--382. ACM Press, July 2004.]]
[10]
Kofi Ambrose Laing and Rajmohan Rajaraman. Brief announcement: A space lower bound for name-independent compact routing in trees. In 17th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), page 216. ACM Press, July 2005.]]
[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 and Paul M. B. Vitányi. An Introduction to Kolmogorov Complexity and its Applications (second edition). Springer-Verlag, 1997.]]
[13]
David Peleg and Eli Upfal. A trade-off between space and efficiency for routing tables. Journal of the ACM, 36(3):510--530, July 1989.]]
[14]
Mikkel Thorup and Uri Zwick. Compact routing schemes. In 13th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 1--10. ACM Press, July 2001.]]

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SPAA '06: Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures
July 2006
344 pages
ISBN:1595934529
DOI:10.1145/1148109
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 July 2006

Permissions

Request permissions for this article.

Check for updates

Author Tag

  1. compact routing

Qualifiers

  • Article

Conference

SPAA06
SPAA06: 18th ACM Symposium on Parallelism in Algorithms and Architectures 2006
July 30 - August 2, 2006
Massachusetts, Cambridge, USA

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)0
Reflects downloads up to 18 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2016)A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General GraphsACM Transactions on Algorithms10.1145/288839712:4(1-31)Online publication date: 3-Aug-2016
  • (2016)Scale-Free Compact Routing Schemes in Networks of Low Doubling DimensionACM Transactions on Algorithms10.1145/287605512:3(1-29)Online publication date: 15-Jun-2016
  • (2015)k-Chordal GraphsAlgorithmica10.1007/s00453-014-9871-y72:3(758-777)Online publication date: 1-Jul-2015
  • (2013)Fast routing table construction using small messagesProceedings of the forty-fifth annual ACM symposium on Theory of Computing10.1145/2488608.2488656(381-390)Online publication date: 1-Jun-2013
  • (2013)On the Communication Complexity of Distributed Name-Independent Routing SchemesDistributed Computing10.1007/978-3-642-41527-2_29(418-432)Online publication date: 2013
  • (2013)Social Structure DetectionHandbook of Combinatorial Optimization10.1007/978-1-4419-7997-1_74(3089-3132)Online publication date: 26-Jul-2013
  • (2012)A compact routing scheme and approximate distance oracle for power-law graphsACM Transactions on Algorithms10.1145/2390176.23901809:1(1-26)Online publication date: 26-Dec-2012
  • (2012)k-chordal graphsProceedings of the 39th international colloquium conference on Automata, Languages, and Programming - Volume Part II10.1007/978-3-642-31585-5_54(610-622)Online publication date: 9-Jul-2012
  • (2011)Electric routing and concurrent flow cuttingTheoretical Computer Science10.1016/j.tcs.2010.06.013412:32(4123-4135)Online publication date: 1-Jul-2011
  • (2010)Adaptive Decentralized Routing in Small-World Networks2010 INFOCOM IEEE Conference on Computer Communications Workshops10.1109/INFCOMW.2010.5466704(1-6)Online publication date: Mar-2010
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media