Universal continuous routing strategies

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Universal continuous routing strategies

Full text

Pdf (1.15 MB)

Source

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

Padua, Italy

Pages: 142 - 151

Year of Publication: 1996

ISBN:0-89791-809-6

Authors

Christian Scheideler	Department of Mathematics and Computer Science and Heinz Nixdorf Institute, University of Paderborn, 33095 Paderborn, Germany
Berthold Vöcking	Department of Mathematics and Computer Science and Heinz Nixdorf Institute, University of Paderborn, 33095 Paderborn, Germany

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): 12, 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/237502.237519 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.

	A87	D.J. Aldous, Ultimate instability of exponential back-off protocol for acknowledgment-based transmission control of random access communication channels, IEEE Transactions on Information Theory, v.33 n.2, p.219-223, March 1987 [doi>10.1109/TIT.1987.1057295]
	AM95	Ra'ed Y. Awdeh , H. T. Mouftah, Survey of ATM switch architectures, Computer Networks and ISDN Systems, v.27 n.12, p.1567-1613, Nov. 1995 [doi>10.1016/0169-7552(94)00081-4]
	BU96	Andrei Broder , Eli Upfal, Dynamic deflection routing on arrays (preliminary version), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.348-355, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237981]
	CMSV96	Robert Cypher , Friedhelm Meyer auf der Heide , Christian Scheideler , Berthold Vöcking, Universal algorithms for store-and-forward and wormhole routing, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.356-365, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237982]
	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]
	GO93	Ronald I. Greenberg , H.-C. Oh, Universal wormhole routing, University of Maryland at College Park, College Park, MD, 1993
	HLR87	J. Hastad , T. Leighton , B. Rogoff, Analysis of backoff protocols for multiple access channels, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.241-253, January 1987, New York, New York, United States [doi>10.1145/28395.28422]
	K85	F.P. Kelly. Stochastic Models of Computer Communication Systems. J. Royal Statistic Soc. 47, pp. 379-395, 1985.
	K88	R. Koch. Increasing the Size of a Network by a Constant Factor Can Increase Performance by More Then a Constant Factor. in Proc. of the 27th Symp. on Foundations of Computer Science, pp. 221-230, 1988.
	L92	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	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]
	MV95	F. Meyer auf der Heide, B. V5cking. A Packet Routing Protocol for Arbitrary Networks. In Proc. of the 12th Symp. on Theoretical Aspects of Computer Science, pp. 291-302, 1995.
	P81	J.H. Patel. Performance of Processor-Memory Interconnections for Multlprocessors. In IEEE Trans. Computers, vol. C-30, no. 10, pp. 771- 780, 1981.
	RMLD96	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 [doi>10.1145/237502.237521]
	RU95	Prabhakar Raghavan , Eli Upfal, Stochastic contention resolution with short delays, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.229-237, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225129]
	SM93	M. Settembre, F. Matera. All Optical Implementations of High Capacity TDMA Networks Fiber and integrated Optics 12, pp 173-186, 1993
	ST91	George D. Stamoulis , John N. Tsitsiklis, The efficiency of greedy routing in hypercubes and butterflies, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.248-259, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113402]
	TRH91	H.H. Theimer, E.P. Rathgeb, M.N. Huber, Performance Analysis of Buffered Banyan Networks. In IEEE Trans. Commumcatwns, vol. 39, no. 2, pp. 269- 277, 1991.
	YLL90	Hyunsoo Yoon, Performance Analysis of Multibuffered Packet-Switching Networks in Multiprocessor Systems, IEEE Transactions on Computers, v.39 n.3, p.319-327, March 1990 [doi>10.1109/12.48863]

CITED BY 13

	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
	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
	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
	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
	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
	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
	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
	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
	Analytically Modeling a Fault-Tolerant Messaging Protocol, IEEE Transactions on Computers, v.53 n.7, p.870-878, July 2004
	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
	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