The efficiency of greedy routing in hypercubes and butterflies

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The efficiency of greedy routing in hypercubes and butterflies

Full text

Pdf (1.19 MB)

Source

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

Hilton Head, South Carolina, United States

Pages: 248 - 259

Year of Publication: 1991

ISBN:0-89791-438-4

Authors

George D. Stamoulis	Laboratory for Information and Decisions Systems, Massachusetts Institute of Technology, Cambridge, Mass
John N. Tsitsiklis	Laboratory for Information and Decisions Systems, Massachusetts Institute of Technology, Cambridge, Mass

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): 2, Downloads (12 Months): 14, Citation Count: 20

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/113379.113402 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	S. Abraham and K. Padmanabhan, "Performance of the Direct Binary u-Cube Network for Multiprocessors", Proceedings of the 1986 International Conference on Parallel Processing.
	2	R. Aleliunas, Randomized parallel communication (Preliminary Version), Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.60-72, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806683]
	3	Dimitri P. Bertsekas , C. Özveren , G. D. Stamoulis , P. Tseng , J. N. Tsitsiklis, Optimal communication algorithms for hypercubes, Journal of Parallel and Distributed Computing, v.11 n.4, p.263-275, April 1991 [doi>10.1016/0743-7315(91)90033-6]
	4	Dimitri P. Bertsekas , John N. Tsitsiklis, Parallel and distributed computation: numerical methods, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
	5	C. Bourns, J. Garofalkis, P. Spirakis, and V. Triantafillou, "Queueing Delays in Buffered Multistage Interconnection Networks", Dept. of Computer Science, Technical Report 289, New York University, 1987.
	6	Yukon Chang , Janos Simon, Continuous routing and batch routing on the hypercube, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.272-281, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10614]
	7	A.G. Greenberg and J. Goodman, "Sharp Approximate Models of Adaptive Routing in Mesh Networks", preprint, 1986.
	8	A.G. Greenberg and B. Hajek, "Deflection Routing in Hypercube Networks", preprint, 1989.
	9	B. Hajek and R.L. Cruz, "Delay and Routing in Interconnection Networks", In A.R. Odoni, L. Bianco, and G. Szago (Eds.), Flow Control of Congested Networks, Springer-Verlag, 1987.
	10	S. Lennart Johnsson , Ching-Tien Ho, Optimum Broadcasting and Personalized Communication in Hypercubes, IEEE Transactions on Computers, v.38 n.9, p.1249-1268, September 1989 [doi>10.1109/12.29465]
	11	Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
	12	F.T. Leighton, "Average Case of Greedy Routing Algorithms on Arrays", preprint, 1900.
	13	D. Mitra , R. A. Cieslak, Randomized parallel communications on an extension of the omega network, Journal of the ACM (JACM), v.34 n.4, p.802-824, Oct. 1987 [doi>10.1145/31846.42226]
	14	A. Ranade, "How to Emulate Shared Memory", Proceedings of the ~Sth Annual IEEE Symposium on Foundations of Computer Science, pp. 185-194, 1988.
	15	Y. Sand and M.H. Schultz, "Data Communication in I'Iypercubes", Dept. of Computer Sciences, Research Report YALEU/DCS/RR-428, Yale University, 1985.
	16	G.D. Stamoulis and J.N. Tsitsiklis, "Efficient Routing Schemes for Multiple Broadcasts in Hypercubes", Proceedings of the 29th {EEE Conference on Decision and Control, pp. 1349-1354, 1990.
	17	G.D. Stamoulis and J.N. Tsitsiklis, "The Efficiency of Greedy Routing in Hypercubes and Butterflies", Report LIDS-P-1999, Laboratory for Information and Decision Systems, M.I.T., 1990.
	18	Eli Upfal, Efficient Schemes for Parallel Communication, Journal of the ACM (JACM), v.31 n.3, p.507-517, July 1984 [doi>10.1145/828.1892]
	19	L.G. Valiant, "A Scheme for Fast Parallel Communication", SIAM J. Comput., vol. 11, pp. 350-361, 1982.
	20	L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	21	L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]
	22	E.A. Varvarigos, "Optimal Communication Algorithms for Multiprocessor Computers", Report CICS-TH-192, Center for Intelligent Control Systems, M.I.T., 1990.
	23	J. Walrand, An Introduction to Queueing Networks, Prentice-Hall, 1988.

CITED BY 20

	Nabil Kahale , Tom Leighton, Greedy dynamic routing on arrays, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.558-566, January 22-24, 1995, San Francisco, California, United States
	Analytically Modeling a Fault-Tolerant Messaging Protocol, IEEE Transactions on Computers, v.53 n.7, p.870-878, July 2004
	Allan Borodin , Jon Kleinberg , Prabhakar Raghavan , Madhu Sudan , David P. Williamson, Adversarial queueing theory, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.376-385, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	G. D. Stamoulis , J. N. Tsitsiklis, Efficient Routing Schemes for Multiple Broadcasts in Hypercubes, IEEE Transactions on Parallel and Distributed Systems, v.4 n.7, p.725-739, July 1993
	Andrei Z. Broder , Alan M. Frieze , Eli Upfal, A general approach to dynamic packet routing with bounded buffers, Journal of the ACM (JACM), v.48 n.2, p.324-349, March 2001
	Michael Mitzenmacher, Constant time per edge is optimal on rooted tree networks, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.162-169, June 24-26, 1996, Padua, Italy
	L. D. Aronson, Homogeneous Routing for Homogeneous Traffic Patterns on Meshes, IEEE Transactions on Parallel and Distributed Systems, v.11 n.8, p.781-793, August 2000
	Christian Scheideler , Berthold Vöcking, Universal continuous routing strategies, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.142-151, June 24-26, 1996, Padua, Italy
	Michael Mitzenmacher, Constant time per edge is optimal on rooted tree networks, Distributed Computing, v.10 n.4, p.189-197, July 1997
	Mor Harchol-Balter , David Wolfe, Bounding delays in packet-routing networks, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.248-257, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Ralf Rehrmann , Burkhard Monien , Reinhard Lüling , Ralf Diekmann, On the communication throughput of buffered multistage interconnection networks, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.152-161, June 24-26, 1996, Padua, Italy
	Bruce M. Maggs , Ramesh K. Sitaraman, Simple algorithms for routing on butterfly networks with bounded queues, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.150-161, May 04-06, 1992, Victoria, British Columbia, Canada
	Micah Adler, Asynchronous shared memory search structures, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.42-51, June 24-26, 1996, Padua, Italy
	Suprakash Datta , Ramesh Sitaraman, The performance of simple routing algorithms that drop packets, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.159-169, June 23-25, 1997, Newport, Rhode Island, United States
	Christof Krick , Friedhelm Meyer auf der Heide , Harald Räcke , Berthold Vöcking , Matthias Westermann, Data management in networks: experimental evaluation of a provably good strategy, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.165-174, June 27-30, 1999, Saint Malo, France
	Michael Mitzenmacher, On the analysis of randomized load balancing schemes, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.292-301, June 23-25, 1997, Newport, Rhode Island, United States
	Michael Mitzenmacher, Analyses of load stealing models based on differential equations, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.212-221, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Micah Adler , Ramesh K. Sitaraman , Arnold L. Rosenberg , Walter Unger, Scheduling time-constrained communication in linear networks, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.269-278, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Allan Borodin , Jon Kleinberg , Prabhakar Raghavan , Madhu Sudan , David P. Williamson, Adversarial queuing theory, Journal of the ACM (JACM), v.48 n.1, p.13-38, Jan. 2001
	Tom Leighton, Methods for message routing in parallel machines, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.77-96, May 04-06, 1992, Victoria, British Columbia, Canada