From static to dynamic routing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

From static to dynamic routing: efficient transformations of store-and-forward protocols

Full text

Pdf (1.02 MB)

Source

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

Atlanta, Georgia, United States

Pages: 215 - 224

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

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

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 20, Citation Count: 5

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/301250.301307 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	A. Fernandez, Universal stability results for greedy contention-resolution protocols, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.380, October 14-16, 1996
	2	M. Andrews , A. Fernandez , M. Harchol-Balter , T. Leighton , L. Zhang, General dynamic routing with per-packet delay guarantees of O(distance+1/session rate), Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.294, October 19-22, 1997
	3	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 [doi>10.1145/237814.237984]
	4	A. Z. Broder , A. M. Frieze, A general approach to dynamic packet routing with bounded buffers, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.390, October 14-16, 1996
	5	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]
	6	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	7	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]
	8	E T Leighton, B. M. Maggs, and S. B. Rao. Packet muting and job-shop scheduling in O(congestion + dilation) steps. Combinatorica, 14(2): 167-186, 1994.
	9	F. Meyer auf der Heide and B. VOcking. A packet muting protocol for arbitrary networks. In Proc. of the 12th Syrup. on Theoretical Aspects of Computer Science (STACS), pages 291-302, 1995.
	10	Friedhelm Meyer auf der Heide , Berthold Vöcking, Shortest-path routing in arbitrary networks, Journal of Algorithms, v.31 n.1, p.105-131, April 1999 [doi>10.1006/jagm.1998.0980]
	11	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 [doi>10.1145/258533.258659]
	12	Yuval Rabani , Éva Tardos, Distributed packet switching in arbitrary networks, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.366-375, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237983]
	13	Abhiram G. Ranade, How to emulate shared memory, Journal of Computer and System Sciences, v.42 n.3, p.307-326, June 1991 [doi>10.1016/0022-0000(91)90005-P]
	14	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 [doi>10.1145/237502.237519]
	15	C. Scheideler and B. Vtcking. Universal continuous routing strategies. Theory of Computing Systems, 31:425-449, 1998.

CITED BY 5

	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
	Ami Litman , Shiri Moran-Schein, Fast, minimal and oblivious routing algorithms on the mesh with bounded queues, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.21-31, July 2001, Crete Island, Greece
	Lujun Jia , Rajmohan Rajaraman , Christian Scheideler, On local algorithms for topology control and routing in ad hoc networks, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Kishore Kothapalli , Christian Scheideler, Information gathering in adversarial systems: lines and cycles, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Dimitrios Koukopoulos , Marios Mavronicolas , Paul Spirakis, Performance and stability bounds for dynamic networks, Journal of Parallel and Distributed Computing, v.67 n.4, p.386-399, April, 2007