Universal algorithms for store-and-forward and wormhole routing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Universal algorithms for store-and-forward and wormhole routing

Full text

Pdf (1.08 MB)

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: 356 - 365

Year of Publication: 1996

ISBN:0-89791-785-5

Authors

Robert Cypher	Department of Computer Science, Johns Hopkins University, Baltimore, MD
Friedhelm Meyer auf der Heide	Department of Mathematics and Computer Science and Heinz Nixdorf Institute, University of Paderborn 33102 Paderborn, Germany
Christian Scheideler	Department of Mathematics and Computer Science and Heinz Nixdorf Institute, University of Paderborn 33102 Paderborn, Germany
Berthold Vöcking	Department of Mathematics and Computer Science and Heinz Nixdorf Institute, University of Paderborn 33102 Paderborn, Germany

Sponsor

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: 18

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.237982 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.

	AS92	A. Acampora, S. Shah. Multihop Lightwave Networks: a Comparison of Store-and-Forward and Hot- Potato Routing. IEEE Transaction on Communications, pp. 1082-1090, 1992.
	BFU92	Andrei Z. Broder , Alan M. Frieze , Eli Upfal, Existence and construction of edge disjoint paths on expander graphs, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.140-149, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129727]
	BRST93	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]
	D90	William J. Dally, Virtual-channel flow control, Proceedings of the 17th annual international symposium on Computer Architecture, p.60-68, May 28-31, 1990, Seattle, Washington, United States
	DS87	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]
	FR92	U. Feige, P. Raghavan. Exact Analysis of Hot-Potato Routing~ In Proc. of the 33rd Syrup. on Foundations of Computer Science, pp. 553-562, 1992.
	FRU92	S. Felperin, P. Raghavan, E. Upfal. A Theory of Wormhole Routing in Parallel Computers. In Proc. of the 33rd Syrup. on Foundations of Computer Science, 1992.
	GH92	A. Greenberg, B. Hajek. Deflection Routing in Hypercube Networks. IEEE 7Yansactions on Communications, pp. 1070-1081, 1992.
	GO93	Ronald I. Greenberg , H.-C. Oh, Universal wormhole routing, University of Maryland at College Park, College Park, MD, 1993
	L92	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	LMR94	T. Leighton, B. Maggs, S. Rao. Packet Routing and Job-Shop Scheduling in O(Congestion + Dilation) Steps. Combinatorica 14, pp. 167-186, 1994.
	LMRR94	F. T. Leighton , Bruce M. Maggs , Abhiram G. Ranade , Satish B. Rao, Randomized routing and sorting on fixed-connection networks, Journal of Algorithms, v.17 n.1, p.157-205, July 1994 [doi>10.1006/jagm.1994.1030]
	M89	N. Maxemchuk. Comparison of Deflection and Storeand-Forward Techniques in the Manhattan Street and Shuffle-Exchange Networks. In Proc. of the IEEE INFOCOM, pp. 800-809, 1989.
	MS95	Friedhelm Meyer auf der Heide , Christian Scheideler, Routing with Bounded Buffers and Hot-Potato Routing in Vertex-Symmetric Networks, Proceedings of the Third Annual European Symposium on Algorithms, p.341-354, September 25-27, 1995
	MV95	F. Meyer auf der Heide, B. VScking. A Packet Routing Protocol for Arbitrary Networks. In Proc. of the l~th Syrup. on Theoretical Aspects of Computer Scierrce, pp. 291-302, 1995.
	MW95	F. Meyer auf der Heide, M. Westermann. Hot-Potato Routing on Multi-Dimensional q~)ri. To appear in Int. Workshop on Distributed Algorithms, 1995.
	P84	N. Pippenger. Parallel Communication with Limited Buffers. In Proc. of the 25th Syrup. on Foundations of Computer Science, pp. 127-136~ 1984.
	RSW94	A. Ranade, S. Schleimer, D.S. Wilkerson. Nearly Tight Bounds for Wormhole Routing. In Proc. of the 35th Syrup. on Foundations of Computer Science, pp. 347-355, 1994.
	SM93	M. Settembre, F. Matera. All Optical Implementations of High Capacity TDMA Networks. Fiber and Integrated Optics 12, pp. 173-186, 1993.
	V82	L.G. Valiant. A Scheme for Fast Parallel Communication. SIAM Journal of Computing 11/2, pp. 350- 361, 1982.

CITED BY 18

	Micah Adler , Christian Scheideler, Efficient communication strategies for ad-hoc wireless networks (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.259-268, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Richard Cole , Bruce M. Maggs , Friedhelm Meyer auf der Heide , Michael Mitzenmacher , Andréa W. Richa , Klaus Schröder , Ramesh K. Sitaraman , Berthold Vöcking, Randomized protocols for low-congestion circuit routing in multistage interconnection networks, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.378-388, May 24-26, 1998, Dallas, Texas, United States
	Berthold Vöcking, Almost optimal permutation routing on hypercubes, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.530-539, July 2001, Hersonissos, Greece
	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
	Richard J. Cole , Bruce M. Maggs , Ramesh K. Sitaraman, On the benefit of supporting virtual channels in wormhole routers, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.131-141, 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
	Matthias Westermann, Distributed caching independent of the network size, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	Rafail Ostrovsky , Yuval Rabani, Universal O(congestion + dilation + log1+&egr;N) local control packet switching algorithms, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.644-653, May 04-06, 1997, El Paso, Texas, United States
	Michele Flammini , Christian Scheideler, Simple, efficient routing schemes for all-optical networks, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.170-179, June 23-25, 1997, Newport, Rhode Island, United States
	Christian Scheideler , Berthold Vöcking, From static to dynamic routing: efficient transformations of store-and-forward protocols, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.215-224, 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
	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
	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
	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
	F. Meyer auf der Heide , H. Räcke , M. Westermann, Data management in hierarchical bus networks, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.109-118, July 09-13, 2000, Bar Harbor, Maine, United States
	Costas Busch , Rajgopal Kannan , Athanasios V. Vasilakos, Quality of routing congestion games in wireless sensor networks, Proceedings of the 4th Annual International Conference on Wireless Internet, November 17-19, 2008, Maui, Hawaii
	Costas Busch , Malik Magdon-Ismail, Atomic routing games on maximum congestion, Theoretical Computer Science, v.410 n.36, p.3337-3347, August, 2009