More Web Proxy on the site http://driver.im/

Article

On space-stretch trade-offs: upper bounds

Authors:

Cyril Gavoille,

Dahlia MalkhiAuthors Info & Claims

SPAA '06: Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures

Pages 217 - 224

https://doi.org/10.1145/1148109.1148144

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 maximum ratio over all pairs between the cost of the route induced by the scheme and the cost of a minimum cost path between the same pair. All previous routing schemes required storage that is dependent on the diameter of the network. We present a new scale-free routing scheme, whose storage and header sizes are independent of the aspect ratio of the network. Our scheme is based on a decomposition into sparse and dense neighborhoods. Given an undirected network with arbitrary weights and n arbitrary node names, for any integer k ≥ 1 we present the first scale-free routing scheme with asymptotically optimal space-stretch tradeoff that does not require edge weights to be polynomially bounded. The scheme uses Õ(n^1/k) space routing table at each node, and routes along paths of asymptotically optimal linear stretch O(k).

References

[1]

Ittai Abraham and Cyril Gavoille. Object location using path separators. In 25rd Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM Press, July 2006.]]

Digital Library

[2]

Ittai Abraham, Cyril Gavoille, A.V. Goldberg, and Dahlia Malkhi. Routing in networks with low doubling dimension. Technical Report MSR-TR-2005-175, Miscrosoft Research, December 2005. To appear in The 26th International Conference on Distributed Computing Systems (ICDCS 06).]]

[3]

Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. Routing with improved communication-space trade-off. In 18th International Symposium on Distributed Computing (DISC), volume 3274 of Lecture Notes in Computer Science, pages 305--319. Springer, October 2004.]]

[4]

Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. Compact routing for graphs excluding a fixed minor. In 19th International Symposium on Distributed Computing (DISC), volume 3724 of Lecture Notes in Computer Science, pages 442--456. Springer, September 2005.]]

Digital Library

[5]

Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, Noam Nisan, and Mikkel Thorup. Compact name-independent routing with minimum stretch. In 16th Annual ACM Symposium on Parallel Algorithms and Architecture (SPAA), pages 20--24. ACM Press, July 2004.]]

Digital Library

[6]

Marta Arias, Lenore J. Cowen, Kofi Ambrose Laing, Rajmohan Rajaraman, and Orjeta Taka. Compact routing with name independence. In 15th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 184--192. ACM Press, June 2003.]]

Digital Library

[7]

Baruch Awerbuch, Amotz Bar-Noy, Nathan Linial, and David Peleg. Compact distributed data structures for adaptive routing. In 21st Annual ACM Symposium on Theory of Computing (STOC), pages 479--489. ACM Press, May 1989.]]

Digital Library

[8]

Baruch Awerbuch, Amotz Bar-Noy, Nathan Linial, and David Peleg. Improved routing strategies with succinct tables. Journal of Algorithms, 11(3):307--341, 1990.]]

Digital Library

[9]

Baruch Awerbuch and David Peleg. Sparse partitions. In 31th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 503--513. IEEE Computer Society Press, October 1990.]]

Digital Library

[10]

Baruch Awerbuch and David Peleg. Routing with polynomial communication-space trade-off. SIAM Journal on Discrete Mathematics, 5(2):151--162, May 1992.]]

Digital Library

[11]

J. Lawrence Carter and Mark N. Wegman. Universal hash functions. Journal of Computer and System Sciences, 18(2):143--154, 1979.]]

[12]

T. H. Hubert Chan, Anupam Gupta, Bruce M. Maggs, and Shuheng Zhou. On hierarchical routing in doubling metrics. In 16th Symposium on Discrete Algorithms (SODA), pages 762--771. ACM-SIAM, January 2005.]]

Digital Library

[13]

Lenore J. Cowen. Compact routing with minimum stretch. Journal of Algorithms, 38:170--183, 2001.]]

Digital Library

[14]

Tamar Eilam, Cyril Gavoille, and David Peleg. Compact routing schemes with low stretch factor. Journal of Algorithms, 46:97--114, 2003.]]

Digital Library

[15]

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.]]

Digital Library

[16]

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.]]

Digital Library

[17]

Cyril Gavoille. Routing in distributed networks: Overview and open problems. ACM SIGACT News - Distributed Computing Column, 32(1):36--52, March 2001.]]

Digital Library

[18]

Cyril Gavoille and David Peleg. Compact and localized distributed data structures. Journal of Distributed Computing, 16:111--120, May 2003. PODC 20-Year Special Issue.]]

Digital Library

[19]

Goran Konjevod, Andréa Werneck Richa, and Donglin Xia. On optimal stretch name-independent compact routing in doubling metrics. In 25rd Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM Press, July 2006.]]

Digital Library

[20]

Robert Krauthgamer, James R. Lee, Manor Mendel, and Assaf Naor. Measured descent: A new embedding method for finite metrics. In 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 434--443. IEEE Computer Society Press, October 2004.]]

Digital Library

[21]

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.]]

Digital Library

[22]

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.]]

Digital Library

[23]

Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995.]]

Digital Library

[24]

David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications, 2000.]]

Digital Library

[25]

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.]]

Digital Library

[26]

Aleksandrs Slivkins. Distance estimation and object location via rings of neighbors. In 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 41--50. ACM Press, July 2005.]]

Digital Library

[27]

Kunal Talwar. Bypassing the embedding: Algorithms for low dimensional metrics. In 36th Annual ACM Symposium on Theory of Computing (STOC), pages 281--290. ACM Press, June 2004.]]

Digital Library

[28]

Mikkel Thorup. Compact oracles for reachability and approximate distances in planar digraphs. Journal of the ACM, 51(6):993--1024, November 2004.]]

Digital Library

[29]

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.]]

Digital Library

[30]

Mikkel Thorup and Uri Zwick. Approximate distance oracles. Journal of the ACM, 52(1):1--24, January 2005.]]

Digital Library

Cited By

Konjevod GRicha AXia D(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
https://dl.acm.org/doi/10.1145/2876055
Gavoille CGlacet CHanusse NIlcinkas D(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
https://doi.org/10.1007/978-3-642-41527-2_29
Chen WSommer CTeng SWang Y(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
https://dl.acm.org/doi/10.1145/2390176.2390180
Show More Cited By

Index Terms

On space-stretch trade-offs: upper bounds

Recommendations

Compact name-independent routing with minimum stretch

Given a weighted undirected network with arbitrary node names, we present a compact routing scheme, using aÕ(√n,) space routing table at each node, and routing along paths of stretch 3, that is, at most thrice as long as the minimum cost paths. This is ...
On space-stretch trade-offs: lower bounds
SPAA '06: Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures

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 ...
Compact name-independent routing with minimum stretch
SPAA '04: Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures

Given a weighted undirected network with arbitrary node names, we present a compact routing scheme, using a Õ(√n) space routing table at each node, and routing along paths of stretch 3, that is, at most thrice as long as the shortest paths. This is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

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

General Chair:
Phillip B. Gibbons
Intel Research, USA
,
Program Chair:
Uzi Vishkin
UMIACS, University of Maryland, USA

Copyright © 2006 ACM.

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.

Request Permissions

Check for updates

Author Tag

compact routing

Qualifiers

Article

Conference

SPAA06

Sponsor:

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

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
199
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Konjevod GRicha AXia D(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
https://dl.acm.org/doi/10.1145/2876055
Gavoille CGlacet CHanusse NIlcinkas D(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
https://doi.org/10.1007/978-3-642-41527-2_29
Chen WSommer CTeng SWang Y(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
https://dl.acm.org/doi/10.1145/2390176.2390180
Kosowski ALi BNisse NSuchan K(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
https://dl.acm.org/doi/10.1007/978-3-642-31585-5_54
Woodruff D(2010)Additive spanners in nearly quadratic timeProceedings of the 37th international colloquium conference on Automata, languages and programming10.5555/1880918.1880970(463-474)Online publication date: 6-Jul-2010
https://dl.acm.org/doi/10.5555/1880918.1880970
Baswana SKavitha TMehlhorn KPettie S(2010)Additive spanners and (α, β)-spannersACM Transactions on Algorithms10.1145/1868237.18682427:1(1-26)Online publication date: 8-Dec-2010
https://dl.acm.org/doi/10.1145/1868237.1868242
Pettie S(2010)Distributed algorithms for ultrasparse spanners and linear size skeletonsDistributed Computing10.1007/s00446-009-0091-722:3(147-166)Online publication date: 1-Mar-2010
https://dl.acm.org/doi/10.1007/s00446-009-0091-7
Woodruff D(2010)Additive Spanners in Nearly Quadratic TimeAutomata, Languages and Programming10.1007/978-3-642-14165-2_40(463-474)Online publication date: 2010
https://doi.org/10.1007/978-3-642-14165-2_40
Malkhi DSen STalwar KWerneck RWieder U(2009)Virtual Ring Routing TrendsDistributed Computing10.1007/978-3-642-04355-0_42(392-406)Online publication date: 2009
https://doi.org/10.1007/978-3-642-04355-0_42
Chen WSommer CTeng SWang Y(2009)Compact Routing in Power-Law GraphsDistributed Computing10.1007/978-3-642-04355-0_41(379-391)Online publication date: 2009
https://doi.org/10.1007/978-3-642-04355-0_41
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents