A trade-off between space and efficiency for routing tables

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A trade-off between space and efficiency for routing tables

Full text

Pdf (1.68 MB)

Source

Journal of the ACM (JACM) archive
Volume 36 , Issue 3 (July 1989) table of contents

Pages: 510 - 530

Year of Publication: 1989

ISSN:0004-5411

Authors

David Peleg	Weizmann Institute, Rehovot, Israel
Eli Upfal	Weizmann Institute, Rehovot, Israel

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 68, 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/65950.65953 What is a DOI?

ABSTRACT

Two conflicting goals play a crucial role in the design of routing schemes for communication networks. A routing scheme should use paths that are as short as possible for routing messages in the network, while keeping the routing information stored in the processors' local memory as succinct as possible. The efficiency of a routing scheme is measured in terms of its stretch factor-the maximum ratio between the length of a route computed by the scheme and that of a shortest path connecting the same pair of vertices. Most previous work has concentrated on finding good routing schemes (with a small fixed stretch factor) for special classes of network topologies. In this paper the problem for general networks is studied, and the entire range of possible stretch factors is examined. The results exhibit a trade-off between the efficiency of a routing scheme and its space requirements. Almost tight upper and lower bounds for this trade-off are presented. Specifically, it is proved that any routing scheme for general n-vertex networks that achieves a stretch factor k ≥ 1 must use a total of &OHgr;(n1+1/(2k+4)) bits of routing information in the networks. This lower bound is complemented by a family K(k) of hierarchical routing schemes (for every k ≥ l) for unit-cost general networks, which guarantee a stretch factor of O(k), require storing a total of O(k3n1+(1/h)logn)- bits of routing information in the network, name the vertices with O(log2n)-bit names and use O(logn)-bit headers.

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	Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985 [doi>10.1145/4221.4227]
	2	AWERBUCH, B., BAR-NOV, A., LINIAL, N., AND PELEG, D. Improved routing strategies with succinct tables. Tech. Rep. MIT/LCS/TM-354. MIT, Cambridge, Mass., Apr. 1988.
	3	AWERBUCH, B., BAR-NOV, A., LINIAL, N., AND PELEG, D. Memory-balanced routing strategies. Tech. Rep. MIT/LCS/TM-369. MIT, Cambridge, Mass., Aug. I988.
	4	B. Awerbuch , A. Bar-Noy , N. Linial , D. Peleg, Compact distributed data structures for adaptive routing, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.479-489, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73053]
	5	A E Baratz , J M Jaffe, Establishing virtual circuits in large computer networks, Computer Networks and ISDN Systems, v.12 n.1, p.27-34, August 1986 [doi>10.1016/0169-7552(86)90081-4]
	6	BOLLOBAS., B.Random Graphs. Acadmic Press, London, 1985.
	7	CHANG, G. J., AND NEMHAUSER, G.L. The k-domination and k-stability problems on sun-free chordal graphs. SlAM J. Algor. Discrete Meth. 5 (1984), 332-345.
	8	CHERNOFF, H. A measure of asymptotic efficiency for tests of hypothesis based on the sum of observations. Ann. Math. Stat. 23 (1952), 493-507.
	9	E J Cockayne , B Gamble , B Shepherd, An upper bound for the k-domination number of a graph, Journal of Graph Theory, v.9 n.4, p.533-534, Dec. 1985 [doi>10.1002/jgt.3190090414]
	10	FREDERICKSON, G. N., AND JANARDAN, R. Separator-based strategies for efficient message routing. In Proceedings of the 27th Symposium on Foundations of Computer Science. IEEE, New York, I986, pp. 428-437.
	11	FREDERICKSON, O. N., AND J ANARDAN, R. Designing networks with compact routing tables. Algorithmica 3 (1988), 171-190.
	12	KLEINROCK, L., AND KAMOUN, F. Hierarchical routing for large networks; Performance evaluation and optimization. Comput. Netw. I (1977), 155-174.
	13	KLEINROCK, L., AND KAMOUN, F. Optimal clustering structures for hierarchical topological design of large computer networks. Networks 10 (1980), 221-248.
	14	PELEG, D., AND SCHAFFER, A.A. Graph spanners. J. Graph Theory 13 (1989), 99-116.
	15	David Peleg , Jeffrey D. Ullman, An optimal synchronizer for the hypercube, SIAM Journal on Computing, v.18 n.4, p.740-747, Aug. 1989 [doi>10.1137/0218050]
	16	PELEG, D., AND UPFAL, E. Efficient message passing using succinct routing tables. Res. Rep. RJ 5768. IBM, Almaden, Aug. 1987.
	17	PERLMAN, R. Hierarchical networks and the subnetwork partition problem. In Proceedings of the 5th Conference on System Sciences, 1982.
	18	SANTORO, N., AND KHATIB, R. Labelling and implicit routing in networks. The Comput. J. 28 (1985), 5-8.
	19	SUNSHINE, C. A. Addressing problems in multi-network systems. In Proceedings of the IEEE Infocom 82 (Las Vegas, Nev.). IEEE, New York, 1982.
	20	VAN LEEUWEN, J., AND TAN, R. B. Routing with compact routing tables. In The Book of L, G. Rozenberg and A. Salomaa, eds. Springer-Verlag, New York, 1986, pp. 259-273.
	21	J. Van Leeuwen , R. B. Tan, Interval routing, The Computer Journal, v.30 n.4, p.298-307, Aug. 1987 [doi>10.1093/comjnl/30.4.298]

CITED BY 61

	Cyril Gavoille , David Peleg , Stéphane Pérennes , Ran Raz, Distance labeling in graphs, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.210-219, January 07-09, 2001, Washington, D.C., United States
	Baruch Awerbuch , David Peleg, Concurrent online tracking of mobile users, ACM SIGCOMM Computer Communication Review, v.21 n.4, p.221-233, Sept. 1991
	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
	Lenore J. Cowen , Christopher G. Wagner, Compact roundtrip routing for digraphs, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.885-886, January 17-19, 1999, Baltimore, Maryland, United States
	Shlomi Dolev , Evangelos Kranakis , Danny Krizanc , David Peleg, Bubbles: adaptive routing scheme for high-speed dynamic networks, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.528-537, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Mahmoud Al-Omari , Mohammed Mahafzah, Fault-tolerant routing in hypercubes using masked interval routing scheme, Proceedings of the 1999 ACM symposium on Applied computing, p.481-485, February 28-March 02, 1999, San Antonio, Texas, United States
	Victor Chepoi , Alexis Rollin, Interval routing in some planar networks, Theoretical Computer Science, v.290 n.3, p.1503-1540, 3 January 2003
	Philip Klein , Serge A. Plotkin , Satish Rao, Excluded minors, network decomposition, and multicommodity flow, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.682-690, May 16-18, 1993, San Diego, California, United States
	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
	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
	Baruch Awerbuch , David Peleg, Online tracking of mobile users, Journal of the ACM (JACM), v.42 n.5, p.1021-1058, Sept. 1995
	Shay Kutten , David Peleg, Fast distributed construction of k-dominating sets and applications, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.238-251, August 20-23, 1995, Ottowa, Ontario, Canada
	Baruch Awerbuch , Boaz Patt-Shamir , David Peleg , Michael Saks, Adapting to asynchronous dynamic networks (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.557-570, May 04-06, 1992, Victoria, British Columbia, Canada
	Cyril Gavoille, Routing in distributed networks: overview and open problems, ACM SIGACT News, v.32 n.1, March 2001
	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
	Pierre Fraigniaud , Cyril Gavoille , Bernard Mans, Interval routing schemes allow broadcasting with linear message-complexity (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.11-20, July 16-19, 2000, Portland, Oregon, United States
	Lenore J. Cowen , Christopher G. Wagner, Compact roundtrip routing in directed networks (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.51-59, July 16-19, 2000, Portland, Oregon, United States
	Cyril Gavoille , David Peleg , Stéphane Pérennes , Ran Raz, Distance labeling in graphs, Journal of Algorithms, v.53 n.1, p.85-112, October 2004
	Lucia Draque Penso , Valmir C. Barbosa, A distributed algorithm to find k-dominating sets, Discrete Applied Mathematics, v.141 n.1-3, p.243-253, 30 May 2004
	Harry Buhrman , Jaap-Henk Hoepman , Paul Vitányi, Optimal routing tables, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.134-142, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Serafino Cicerone , Gabriele Di Stefano , Michele Flammini, Static and dynamic low-congested interval routing schemes, Theoretical Computer Science, v.276 n.1-2, p.315-354, April 6, 2002
	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
	Cyril Gavoille , Akka Zemmari, The compactness of adaptive routing tables, Journal of Discrete Algorithms, v.1 n.2, p.237-254, April 2003
	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
	Lenore J. Cowen , Christopher G. Wagner, Compact roundtrip routing in directed networks, Journal of Algorithms, v.50 n.1, p.79-95, January 2004
	Friedhelm Meyer auf der Heide , Christian Scheideler, Space-efficient routing in vertex-symmetric networks (extended abstract), Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.137-146, June 24-26, 1995, Santa Barbara, California, United States
	Lenore J. Cowen, Compact routing with minimum stretch, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.255-260, January 17-19, 1999, Baltimore, Maryland, United States
	M. B. Hadim , I. Sakho, The Multi-Level Communication: Efficient Routing for Interconnection Networks, The Journal of Supercomputing, v.18 n.2, p.153-177, Feb. 1, 2001
	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
	Michael Elkin , Jian Zhang, Efficient algorithms for constructing (1+,ε, β)-spanners in the distributed and streaming models, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Eric Fleury , Pierre Fraigniaud, A General Theory for Deadlock Avoidance in Wormhole-Routed Networks, IEEE Transactions on Parallel and Distributed Systems, v.9 n.7, p.626-638, July 1998
	T. Eilam , S. Moran , S. Zaks, The complexity of the characterization of networks supporting shortest-path interval routing, Theoretical Computer Science, v.289 n.1, p.85-104, 23 October 2002
	Don Coppersmith , Michael Elkin, Sparse source-wise and pair-wise distance preservers, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Hubert T-H. Chan , Anupam Gupta , Bruce M. Maggs , Shuheng Zhou, On hierarchical routing in doubling metrics, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Anupam Gupta , Amit Kumar , Mikkel Thorup, Tree based MPLS routing, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	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
	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
	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
	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
	Tamar Eilam , Cyril Gavoille , David Peleg, Average stretch analysis of compact routing schemes, Discrete Applied Mathematics, v.155 n.5, p.598-610, March, 2007
	Antonio Carzaniga , Cyrus P. Hall, Content-based communication: a research agenda, Proceedings of the 6th international workshop on Software engineering and middleware, November 10-10, 2006, Portland, Oregon
	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
	Surender Baswana , Sandeep Sen, A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs, Random Structures & Algorithms, v.30 n.4, p.532-563, July 2007
	Yon Dourisboure , Feodor F. Dragan , Cyril Gavoille , Chenyu Yan, Spanners for bounded tree-length graphs, Theoretical Computer Science, v.383 n.1, p.34-44, September, 2007
	Lionel Sacks , Ognjen Prnjat , Ioannis Liabotis , Temitope Olukemi , Adrian Ching , Mike Fisher , Paul Mckee , Nektarios Georgalas , Hideki Yoshii, Active Robust Resource Management in Cluster Computing Using Policies, Journal of Network and Systems Management, v.11 n.3, p.329-350, September 2003
	Eyal Felstaine , Reuven Cohen , Ofer Hadar, Crankback Prediction in Hierarchical ATM Networks, Journal of Network and Systems Management, v.10 n.3, p.327-355, September 2002
	Whay C. Lee, Topology aggregation for hierarchical routing in ATM networks, ACM SIGCOMM Computer Communication Review, v.25 n.2, p.82-92, April 1995
	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
	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
	Surender Baswana , Soumojit Sarkar, Fully dynamic algorithm for graph spanners with poly-logarithmic update time, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1125-1134, January 20-22, 2008, San Francisco, California
	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
	Michael Q. Rieck , Subhankar Dhar, Hierarchical routing in ad hoc networks using k-dominating sets, ACM SIGMOBILE Mobile Computing and Communications Review, v.12 n.3, July 2008
	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
	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
	Silvio Lattanzi , D. Sivakumar, Affiliation networks, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA