Memory requirement for routing in distributed networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Memory requirement for routing in distributed networks

Full text

Pdf (1.02 MB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing table of contents

Philadelphia, Pennsylvania, United States

Pages: 125 - 133

Year of Publication: 1996

ISBN:0-89791-800-2

Authors

Cyril Gavoille	LIP, École Normale Supérieure de Lyon
Stéphane Pérennès	I3S, Université de Nice-Sophia Antipolis

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 13, Citation Count: 14

Additional Information:

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/248052.248075 What is a DOI?

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 , 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]
	2	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]
	3	E. M. BAKKER, J. VAN LEEUWEN, AND R. B. TAN, Linear interval routing, Algorithms Review, 2 (1991), pp. 45-61.
	4	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 [doi>10.1145/248052.248076]
	5	F. DESPREZ, E. FLEURY, AND M. LOI, T9000 et C104: La nouvelle generation de transputers, Research Report 93-01, LIP, Ecole Normale Superieure de Lyon, 69364 Lyon Cedex 07, France, Feb. 1993.
	6	P. FRAIGNIAUD AND C. GAVOILLE, Interval routing schemes, Research Report 94-04, LIP, Ecole Normale Superieure de Lyon, 69364 Lyon Cedex 07, France, Jan. 1994.
	7	Pierre Fraigniaud , Cyril Gavoille, Optimal Interval Routing, Proceedings of the Third Joint International Conference on Vector and Parallel Processing: Parallel Processing, p.785-796, September 06-08, 1994
	8	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]
	9	---, Universal routing schemes. Manuscript submitted to JDC, June 1995.
	10	G. N. FREDERICKSON AND R. JANARDAN, Designing networks with compact routing tables, Algorithmica. 3 (1988), pp. 171-190.
	11	Greg N. Frederickson , Ravi Janardan, Efficient message routing in planar networks, SIAM Journal on Computing, v.18 n.4, p.843-857, Aug. 1989 [doi>10.1137/0218058]
	12	Greg N. Frederickson , Ravi Janardan, Space-efficient message routing in c-decomposable networks, SIAM Journal on Computing, v.19 n.1, p.164-181, Feb. 1990 [doi>10.1137/0219011]
	13	C. GAVOILLE, Complexite memoire du routage dans les reseaux distribues, PhD thesis, Ecole Normale Superieure de Lyon, 46, allee d'Italie, Jan. 1996.
	14	C. GAVOILLE AND E. GUEVREMONT, Worst case bounds for shortest path interval routing, Research Report 95-02, LIP, Ecole Normale Superieure de Lyon. 69364 Lyon Cedex 07, France. Jan. 1995.
	15	A. N. KOLMOGOROV, Three approaches to the quantitative definition of information, Problems Inform. Transmission, 1 (1965), pp. 1-7.
	16	E. KRANAKIS AND D. KRIZANC, Lower bounds for compact routing, Tech. Rep. TR-95-18, Carleton University. July 1995. To appear in STACS '96.
	17	Evangelos Kranakis , Danny Krizanc , S. S. Ravi, On Multi-Label Linear Interval Routing Schemes (Extended Abstract), Proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science, p.338-349, June 16-18, 1993
	18	David Peleg , Eli Upfal, A tradeoff between space and efficiency for routing tables, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.43-52, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62217]
	19	N. SANTORO AND R. KHATIB, Labelling and implicit routing in networks, The Computer Journal, 28 (1985). pp. 5-8.
	20	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 14

	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
	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
	Pierre Fraigniaud , Cyril Gavoille, Local memory requirement of universal routing schemes, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.183-188, June 24-26, 1996, Padua, Italy
	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
	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
	Cyril Gavoille , David Peleg, Compact and localized distributed data structures, Distributed Computing, v.16 n.2-3, p.111-120, September 2003
	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
	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
	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
	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
	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