Memory requirement for universal routing schemes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Memory requirement for universal routing schemes

Full text

Pdf (767 KB)

Source

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

Ottowa, Ontario, Canada

Pages: 223 - 230

Year of Publication: 1995

ISBN:0-89791-710-3

Authors

Pierre Fraigniaud	Laboratoire de l'Informatique du Parallélisme, CNRS, École Normale Supérieure de Lyon, 69364 Lyon cedex 07, France
Cyril Gavoille	Laboratoire de l'Informatique du Parallélisme, CNRS, École Normale Supérieure de Lyon, 69364 Lyon cedex 07, France

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/224964.224989 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	E. M. BAKKER, J. VAN LEEUWEN, AND R. B. TAN, L,ncar ~ntcrval routing, Algorithms Review, 2 (1991), pp. 45-61.
	2	W. J. DALLY AND C. L. SEITZ, The torus routing chip, Distributed Computing, I (1986), pp. 187- 196.
	3	W. J. Dally , C. L. Seitz, Deadlock-free message routing in multiprocessor interconnection networks, IEEE Transactions on Computers, v.36 n.5, p.547-553, May 1987 [doi>10.1109/TC.1987.1676939]
	4	F. DESPaEZ, E. FLEURY, AND M. LoI, T9000 et ClO~ ~ La nouvelle g~n4ration de transputers, Tech. Rep. 93-01, LIP-ENS Lyon, LIP, Ecole Normale Sup~rieure de Lyon, 69364 Lyon Cedex 07, France, Feb. 1993.
	5	M. FLAMMINi, J. VAN LEEUWEN, AND A. M. SPAC- CAMELA, Lower bounds on interval routing, Tech. Rep. 69, UniversitS~ di L'Aquila, Dipartemento di matematica Pura ed Applicata, Oct. 1994.
	6	Pierre Fraigniaud , Emmanuel Lazard, Methods and problems of communication in usual networks, Discrete Applied Mathematics, v.53 n.1-3, p.79-133, Sept. 14, 1994
	7	P. FRAIGNIAUD AND C. GAVOILLE, Interval rout- ~ ng schemes, Research Report 94-04, Laboratoire de l'Informatique du Parall~lisme, LIP, t~cole Normale Supdrieure de Lyon, 69364 Lyon Cedex 07, France, Jan. 1994.
	8	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
	9	P. t?RAIGNIAUD, A. LIESTMAN, AND D. SOT- TEAU, Opcr~ problems, Parallel Processing Letters, 3 (1993), pp. 507-524.
	10	G. N. FREDERICKSON AND R. JANARDAN, Designzng networks with compact routing tables, Algorithmica, (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 AND E. GUt~VREMONT, Worst case bounds for 8hottest path interval routin~, Research Report 95-02, Laboratoire de l'Informatique du Paralldisme, LIP, Ecole Normale Sup~rieure de Lyon, 69364 Lyon Cedex 07, France, Jan. 1995.
	14	Michel Gondran , Michel Minoux , Steven Vajda, Graphs and algorithms, John Wiley & Sons, Inc., New York, NY, 1984
	15	M. A. HARmSON, On the number of classes of binary matrices, IEEE Transactions on Computers, C-22 (1973), pp. 1048-1051.
	16	M. C. Heydemann , J.c. Meyer , D. Sotteau, On forwarding indices of networks, Discrete Applied Mathematics, v.23 n.2, p.103-123, May 1989 [doi>10.1016/0166-218X(89)90022-X]
	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	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	19	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]
	20	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]
	21	N. SANTORO AND R. KIIATIB, Labelling and implicit routing in networks, The Computer Journal, 28 (1985), pp. 5-8.
	22	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 10

	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
	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, 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 (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 , David Peleg, Compact and localized distributed data structures, Distributed Computing, v.16 n.2-3, p.111-120, September 2003
	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
	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
	Jie Wu , Zhen Jiang, Extended minimal routing in 2-D meshes with faulty blocks, International Journal of High Performance Computing and Networking, v.1 n.1-3, p.140-152, August 2004