Compact routing schemes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Compact routing schemes

Full text

Pdf (328 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures table of contents

Crete Island, Greece

Pages: 1 - 10

Year of Publication: 2001

ISBN:1-58113-409-6

Authors

Mikkel Thorup	AT&T Labs - Research, 180 Park Avenue, Florham Park, NJ
Uri Zwick	School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 26, Downloads (12 Months): 168, Citation Count: 61

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/378580.378581 What is a DOI?

ABSTRACT

We describe several compact routing schemes for general weighted undirected networks. Our schemes are simple and easy to implement. The routing tables stored at the nodes of the network are all very small. The headers attached to the routed messages, including the name of the destination, are extremely short. The routing decision at each node takes constant time. Yet, the stretch of these routing schemes, i.e., the worst ratio between the cost of the path on which a packet is routed and the cost of the cheapest path from source to destination, is a small constant. Our schemes achieve a near-optimal tradeoff between the size of the routing tables used and the resulting stretch. More specifically, we obtain:

A routing scheme that uses only O (n ^1/2) bits of memory at each node of an n-node network that has stretch 3. The space is optimal, up to logarithmic factors, in the sense that every routing scheme with stretch < 3 must use, on some networks, routing tables of total size &OHgr;(n²), and every routing scheme with stretch < 5 must use, on some networks, routing tables of total size &OHgr;(n^3/2). The headers used are only (1 + &Ogr;(1)) log²> n-bits long and each routing decision takes constant time. A variant of this scheme with [log2 n] -bit headers makes routing decisions in &Ogr;(log log n) time.
Also, for every integer k > 2, a general handshaking based routing scheme that uses O (n^1/k) bits of memory at each node that has stretch 2k - 1. A conjecture of Erdös from 1963, settled for k = 3, 5, implies that the routing tables are of near-optimal size relative to the stretch. The handshaking is similar in spirit to a DNS lookup in TCP/IP. Headers are &Ogr;(log² n) bits long and each routing decision takes constant time. Without handshaking, the stretch of the scheme increases to 4k — 5. One ingredient used to obtain the routing schemes mentioned above, may be of independent practical and theoretical interest:
A shortest path routing scheme for trees of arbitrary degree and diameter that assigns each vertex of an n-node tree a (1 + &Ogr;(1)) log² n-bit label. Given the label of a source node and the label of a destination it is possible to compute, in constant time, the port number of the edge from the source that heads in the direction of the destination.

The general scheme for k > 2 also uses a clustering technique introduced recently by the authors. The clusters obtained using this technique induce a sparse and low stretch tree cover of the network. This essentially reduces routing in general networks into routing problems in trees that could be solved using the above technique.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Serge Abiteboul , Haim Kaplan , Tova Milo, Compact labeling schemes for ancestor queries, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.547-556, January 07-09, 2001, Washington, D.C., United States
	2	N. Alon and M. Naor. Derandomization, witnesses for boolean matrix multiplication, and construction of perfect hash functions. Algorithmica, 16:434-449, 1996.
	3	S. Alstrup. Personal communication, SODA 2001.
	4	Baruch Awerbuch , Amotz Bar Noy , Nathan Linial , David Peleg, Improved routing strategies with succinct tables, Journal of Algorithms, v.11 n.3, p.307-341, Sep. 1990 [doi>10.1016/0196-6774(90)90017-9]
	5	Baruch Awerbuch , David Peleg, Routing with polynomial communication-space trade-off, SIAM Journal on Discrete Mathematics, v.5 n.2, p.151-162, May 1992 [doi>10.1137/0405013]
	6	Paul Beame , Faith E. Fich, Optimal bounds for the predecessor problem, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.295-304, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301323]
	7	Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
	8	Lenore J. Cowen, Compact routing with minimum stretch, Journal of Algorithms, v.38 n.1, p.170-183, Jan. 2001 [doi>10.1006/jagm.2000.1134]
	9	S. Deering and R. Hinden. Internet protocol, version 6 (IPv6), specification. Network Working Group, Request for Comments: 2460, ftp://ftp.ipv6.org/pub/rfc/rfc2460.txt, December 1998.
	10	Dorit Dor , Shay Halperin , Uri Zwick, All-Pairs Almost Shortest Paths, SIAM Journal on Computing, v.29 n.5, p.1740-1759, March 2000 [doi>10.1137/S0097539797327908]
	11	Tamar Eilam , Cyril Gavoille , David Peleg, Compact routing schemes with low stretch factor (extended abstract), Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.11-20, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277702]
	12	P. Erdos. Extremal problems in graph theory. In Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), pages 29-36. Publ. House Czechoslovak Acad. Sci., Prague, 1964.
	13	Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
	14	Pierre Fraigniaud , Cyril Gavoille, Memory requirement for universal routing schemes, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.223-230, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224989]
	15	P. Fraigniaud and C. Gavoille. Interval routing schemes. Algorithmica, 21(2):155-182, 1998.
	16	Michael L. Fredman , János Komlós , Endre Szemerédi, Storing a Sparse Table with 0(1) Worst Case Access Time, Journal of the ACM (JACM), v.31 n.3, p.538-544, July 1984 [doi>10.1145/828.1884]
	17	Cyril Gavoille, A survey on interval routing, Theoretical Computer Science, v.245 n.2, p.217-253, Aug. 28, 2000 [doi>10.1016/S0304-3975(99)00283-2]
	18	C. Gavoille. Personal communication at SODA, 2001.
	19	Cyril Gavoille , Marc Gengler, Space-efficiency for routing schemes of stretch factor three, Journal of Parallel and Distributed Computing, v.61 n.5, p.679-687, May 2001 [doi>10.1006/jpdc.2000.1705]
	20	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]
	21	Brian W. Kernighan , Dennis M. Ritchie, The C programming language, Prentice Hall Press, Upper Saddle River, NJ, 1989
	22	David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
	23	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]
	24	N. Santoro and R. Khatib. Labelling and implicit routing in networks. The Computer Journal, 28(1):5-8, 1985.
	25	Mikkel Thorup , Uri Zwick, Approximate distance oracles, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.183-192, July 2001, Hersonissos, Greece [doi>10.1145/380752.380798]
	26	P. van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters, 6(3):80-82, 1977.
	27	P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Math. Syst. Theory, 10:99-127, 1977.
	28	J. van Leeuwen and R. Tan. Computer networks with compact routing tables. In G. Rozemberg and A. Salomaa, editors, The book of L, pages 259-273. Springer-Verlag, 1986.

CITED BY 61

	Mikkel Thorup , Uri Zwick, Approximate distance oracles, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.183-192, July 2001, Hersonissos, Greece
	Stephen Alstrup , Theis Rauhe, Improved labeling scheme for ancestor queries, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.947-953, January 06-08, 2002, San Francisco, California
	Liam Roditty , Mikkel Thorup , Uri Zwick, Roundtrip spanners and roundtrip routing in directed graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.844-851, January 06-08, 2002, San Francisco, California
	Stephen Alstrup , Cyril Gavoille , Haim Kaplan , Theis Rauhe, Nearest common ancestors: a survey and a new distributed algorithm, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	Stephen Alstrup , Philip Bille , Theis Rauhe, Labeling schemes for small distances in trees, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Haim Kaplan , Tova Milo , Ronen Shabo, A comparison of labeling schemes for ancestor queries, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.954-963, January 06-08, 2002, San Francisco, California
	Marta Arias , Lenore J. Cowen , Kofi A. Laing , Rajmohan Rajaraman , Orjeta Taka, Compact routing with name independence, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Tamar Eilam , Cyril Gavoille , David Peleg, Compact routing schemes with low stretch factor, Journal of Algorithms, v.46 n.2, p.97-114, February 2003
	Kirsten Hildrum , John D. Kubiatowicz , Satish Rao , Ben Y. Zhao, Distributed object location in a dynamic network, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	Marta Arias , Lenore J. Cowen , Kofi A. Laing, Compact roundtrip routing with topology-independent node names, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.43-52, July 13-16, 2003, Boston, Massachusetts
	James Newsome , Dawn Song, GEM: graph eMbedding for routing and data-centric storage in sensor networks without geographic information, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA
	Cyril Gavoille , David Peleg, Compact and localized distributed data structures, Distributed Computing, v.16 n.2-3, p.111-120, September 2003
	Ittai Abraham , Dahlia Malkhi , Oren Dobzinski, LAND: stretch (1 + ε) locality-aware networks for DHTs, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Ittai Abraham , Cyril Gavoille , Dahlia Malkhi , Noam Nisan , Mikkel Thorup, Compact name-independent routing with minimum stretch, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Kunal Talwar, Bypassing the embedding: algorithms for low dimensional metrics, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Ittai Abraham , Dahlia Malkhi, Compact routing on euclidian metrics, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Mikkel Thorup , Uri Zwick, Approximate distance oracles, Journal of the ACM (JACM), v.52 n.1, p.1-24, January 2005
	Philip Klein, Preprocessing an undirected planar network to enable fast approximate distance queries, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.820-827, January 06-08, 2002, San Francisco, California
	Edith Cohen , Haim Kaplan , Tova Milo, Labeling dynamic XML trees, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
	Michal Katz , Nir A. Katz , David Peleg, Distance labeling schemes for well-separated graph classes, Discrete Applied Mathematics, v.145 n.3, p.384-402, 30 January 2005
	Michael A. Bender , Jeremy T. Fineman , Seth Gilbert , Charles E. Leiserson, On-the-fly maintenance of series-parallel relationships in fork-join multithreaded programs, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Aleksandrs Slivkins, Distance estimation and object location via rings of neighbors, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Surender Baswana , Telikepalli Kavitha , Kurt Mehlhorn , Seth Pettie, New constructions of (α, β)-spanners and purely additive spanners, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Ittai Abraham , Dahlia Malkhi, Name independent routing for growth bounded networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Michael Elkin, Computing almost shortest paths, ACM Transactions on Algorithms (TALG), v.1 n.2, p.283-323, October 2005
	Mikkel Thorup, Compact oracles for reachability and approximate distances in planar digraphs, Journal of the ACM (JACM), v.51 n.6, p.993-1024, November 2004
	Mikkel Thorup , Uri Zwick, Spanners and emulators with sublinear distance errors, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.802-809, January 22-26, 2006, Miami, Florida
	Ittai Abraham , Cyril Gavoille , Dahlia Malkhi, On space-stretch trade-offs: lower bounds, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Michael Dinitz, Compact routing with slack, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Cyril Gavoille , Martin Nehéz, Interval routing in reliability networks, Theoretical Computer Science, v.333 n.3, p.415-432, 3 March 2005
	Ittai Abraham , Cyril Gavoille , Dahlia Malkhi, On space-stretch trade-offs: upper bounds, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Arthur Brady , Lenore Cowen, Compact routing with additive stretch using distance labelings, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Victor Chepoi , Feodor F. Dragan , Yann Vaxès, Distance and routing labeling schemes for non-positively curved plane graphs, Journal of Algorithms, v.61 n.2, p.60-88, November, 2006
	Dmitri Krioukov , kc claffy , Marina Fomenkov , Fan Chung , Alessandro Vespignani , Walter Willinger, The workshop on internet topology (wit) report, ACM SIGCOMM Computer Communication Review, v.37 n.1, January 2007
	Feodor F. Dragan , Irina Lomonosov, On compact and efficient routing in certain graph classes, Discrete Applied Mathematics, v.155 n.11, p.1458-1470, June, 2007
	Victor Chepoi , Feodor F. Dragan , Yann Vaxès, Addressing, distances and routing in triangular systems with applications in cellular networks, Wireless Networks, v.12 n.6, p.671-679, November 2006
	S. Chechik , M. Langberg , David Peleg , L. Roditty, Fault-tolerant spanners for general graphs, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Goran Konjevod , Andrea Werneck Richa , Donglin Xia , Hai Yu, Compact routing with slack in low doubling dimension, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Goran Konjevod , Andréa W. Richa , Donglin Xia, Optimal scale-free compact routing schemes in networks of low doubling dimension, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.939-948, January 07-09, 2007, New Orleans, Louisiana
	Ittai Abraham , Cyril Gavoille , Dahlia Malkhi , Noam Nisan , Mikkel Thorup, Compact name-independent routing with minimum stretch, ACM Transactions on Algorithms (TALG), v.4 n.3, p.1-12, June 2008
	Dmitri Krioukov , k c claffy , Kevin Fall , Arthur Brady, On compact routing for the internet, ACM SIGCOMM Computer Communication Review, v.37 n.3, July 2007
	Kofi A. Laing, Name-independent compact routing in trees, Information Processing Letters, v.103 n.2, p.57-60, July, 2007
	Amos Korman , Shay Kutten, Controller and estimator for dynamic networks, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Michael Elkin, A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Byung-Gon Chun , Sylvia Ratnasamy , Eddie Kohler, NetComplex: a complexity metric for networked system designs, Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation, p.393-406, April 16-18, 2008, San Francisco, California
	Iam Roditty , Mikkel Thorup , Uri Zwick, Roundtrip spanners and roundtrip routing in directed graphs, ACM Transactions on Algorithms (TALG), v.4 n.3, p.1-17, June 2008
	Costas Busch , Ryan LaFortune , Srikanta Tirthapura, Improved sparse covers for graphs excluding a fixed minor, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Bilel Derbel , Cyril Gavoille, Fast deterministic distributed algorithms for sparse spanners, Theoretical Computer Science, v.399 n.1-2, p.83-100, June, 2008
	Amos Korman , David Peleg, Labeling schemes for weighted dynamic trees, Information and Computation, v.205 n.12, p.1721-1740, December, 2007
	Marta Arias , Lenore J. Cowen , Kofi A. Laing, Compact roundtrip routing with topology-independent node names, Journal of Computer and System Sciences, v.74 n.5, p.775-795, August, 2008
	Bilel Derbel , Cyril Gavoille , David Peleg , Laurent Viennot, On the locality of distributed sparse spanner construction, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Amos Korman, Improved compact routing schemes for dynamic trees, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Cedric Westphal , James Kempf, A compact routing architecture for mobility, Proceedings of the 3rd international workshop on Mobility in the evolving internet architecture, August 22-22, 2008, Seattle, WA, USA
	Seth Pettie, Distributed algorithms for ultrasparse spanners and linear size skeletons, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Amos Korman , David Peleg, Dynamic routing schemes for graphs with low local density, ACM Transactions on Algorithms (TALG), v.4 n.4, p.1-18, August 2008
	Surender Baswana , Vishrut Goyal , Sandeep Sen, All-pairs nearly 2-approximate shortest paths in O(n2polylogn) time, Theoretical Computer Science, v.410 n.1, p.84-93, January, 2009
	Arnab Bhattacharyya , Elena Grigorescu , Kyomin Jung , Sofya Raskhodnikova , David P. Woodruff, Transitive-closure spanners, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.932-941, January 04-06, 2009, New York, New York
	Amos Korman , Shay Kutten, Note: A note on models for graph representations, Theoretical Computer Science, v.410 n.14, p.1401-1412, March, 2009
	Pierre Fraigniaud , Amos Korman, On randomized representations of graphs using short labels, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, August 11-13, 2009, Calgary, AB, Canada
	Branislav Kusy , HyungJune Lee , Martin Wicke , Nikola Milosavljevic , Leonidas Guibas, Predictive QoS routing to mobile sinks in wireless sensor networks, Proceedings of the 2009 International Conference on Information Processing in Sensor Networks, p.109-120, April 13-16, 2009
	Erol Gelenbe, Steps toward self-aware networks, Communications of the ACM, v.52 n.7, July 2009