Dynamic deflection routing on arrays (preliminary version)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Dynamic deflection routing on arrays (preliminary version)

Full text

Pdf (676 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-eighth annual ACM symposium on Theory of computing table of contents

Philadelphia, Pennsylvania, United States

Pages: 348 - 355

Year of Publication: 1996

ISBN:0-89791-785-5

Authors

Andrei Broder	Digital Systems Research Center, 130 Lytton Avenue, Palo Alto, CA
Eli Upfal	IBM Almaden Research Center, San Jose, CA and Department of Applied Mathematics, The Weizmann Institute of Science, Rehovot, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 11, Citation Count: 13

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/237814.237981 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	Amotz Bar-Noy , Prabhakar Raghavan , Baruch Schieber , Hisao Tamaki, Fast deflection routing for packets and worms, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.75-86, August 15-18, 1993, Ithaca, New York, United States [doi>10.1145/164051.164062]
	2	H. Chernoff. A measure for asymptotic efficiency of a hypothesis based on the sum of observations. Ann. Math. Statist., 23:493-507, 1952.
	3	U. Feige and P. Raghavan. Exact analysis of hot potato routing. Proceedings of the 33rd Annum Symposium on Foundations of Computer Science, pp. 553-562, 1992.
	4	Mor Harchol-Balter , Paul E. Black, Queueing analysis of oblivious packet-routing networks, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.583-592, January 23-25, 1994, Arlington, Virginia, United States
	5	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 [doi>10.1145/225058.225133]
	6	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
	7	J. Keller and J. Wolfowitz. On the theory of queues with many servers. Transaction of the American Math. Society, 78:1-18, 1955.
	8	Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
	9	A.G. Greenberg and B. Hajek. Deflection routing in hypercube networks. IEEE Transaction on Communications, 1992.
	10	B. Hajek, Bounds on evacuation time for deflection routing, Distributed Computing, v.5 n.1, p.1-6, June 1991 [doi>10.1007/BF02311228]
	11	F. T. Leighton, Average case analysis of greedy routing algorithms on arrays, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.2-10, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97448]
	12	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	13	N.F. Maxemchuk. Comparisons of deflection and store and forward techniques in the Manhattan street and shuffle exchange networks. Proceedings of IEEE INFOCOM, pages 800-809, 1989.
	14	Michael Mitzenmacher, Bounds on the greedy routing algorithm for array networks, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.346-353, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181446]
	15	B. Smith. Architecture and applications of the HEP multiprocessor computer system. Proceedings of Real Time Signal Processing IV, pages 241-248, 1981.
	16	G.D. Stamoulis and J.N. Tsitsiklis. The efficiency of greedy routing in hypercubes and butterflies. Proceedings of the 6th Annual A CM Symp. on Parallel Algorithms and Architectures. Pages 346-353, 1994.
	17	T. Tzymanski. An analysis of "Hot Potato" routing in a fiber optic p~ckct switches hypcrcubc. Proceedings IEEE INFOCOM, pages 918-925, 1990.

CITED BY 13

	Costas Busch, Õ(congestion + dilation) hot-potato routing on leveled networks, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	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
	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
	Costas Busch , Maurice Herlihy , Roger Wattenhofer, Randomized greedy hot-potato routing, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.458-466, January 09-11, 2000, San Francisco, California, United States
	Costas Busch , Maurice Herlihy , Roger Wattenhofer, Routing without flow control, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.11-20, July 2001, Crete Island, Greece
	Uriel Feige, Nonmonotonic phenomena in packet routing, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.583-591, May 01-04, 1999, Atlanta, Georgia, United States
	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
	Petra Berenbrink , Christian Scheideler, Locally efficient on-line strategies for routing packets along fixed paths, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.112-121, January 17-19, 1999, Baltimore, Maryland, United States
	Matthew Andrews , Baruch Awerbuch , Antonio Fernández , Tom Leighton , Zhiyong Liu , Jon Kleinberg, Universal-stability results and performance bounds for greedy contention-resolution protocols, Journal of the ACM (JACM), v.48 n.1, p.39-69, Jan. 2001
	Micah Adler , Adi Rosén, Tight bounds for the performance of longest in system on DAGs, Journal of Algorithms, v.55 n.2, p.101-112, May 2005
	William Aiello , Rafail Ostrovsky , Eyal Kushilevitz , Adi Rosén, Dynamic routing on networks with fixed-size buffers, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	William Aiello , Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosén, Adaptive packet routing for bursty adversarial traffic, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.359-368, May 24-26, 1998, Dallas, Texas, United States
	Costas Busch , Malik Magdon-Ismail , Marios Mavronicolas, Efficient bufferless packet switching on trees and leveled networks, Journal of Parallel and Distributed Computing, v.67 n.11, p.1168-1186, November, 2007