Universal O(congestion + dilation + log1+&egr;N) local control packet switching algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Universal O(congestion + dilation + log1+&egr;N) local control packet switching algorithms

Full text

Pdf (1.64 MB)

Source

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

El Paso, Texas, United States

Pages: 644 - 653

Year of Publication: 1997

ISBN:0-89791-888-6

Authors

Rafail Ostrovsky	Bell Communications Research, MCC-1C365B, Morristown, NJ
Yuval Rabani	Computer Science Department, Technion IIT, Haifa 32000, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 14, Citation Count: 22

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/258533.258659 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	M. Andrews, B. Awerbuch, A. Fern$.ndez, J. Kleinberg, F.T. Leighton, and Z. Liu. Universal stability results for greedy contention-resolution protocols. In FOCS '96.
	2	M. Andrews, A. FernAndez, M. Harchol-Balter, F.T. Leighton, and L. Zhang. General dynamic routing with per-packet delay guarantees of O( distance + I / session rate ). Unpublished manuscript, February 1997.
	3	ATM UNI Specification Version 3.0, ATM Forum, September 1993.
	4	J. Beck. An Algorithmic Approach to the Lov~sz Local Lemma. Random Structures and Algorithms, 2(4):367- 378, 1991.
	5	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]
	6	A.Z. Broder, A.M. Frieze, and E. Upfal. A general approach to dynamic packet routing with bounded buffers. In STOC '96.
	7	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]
	8	Inder Gopal, Multimedia networking: applications and challenges, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.9-12, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.197934]
	9	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 [doi>10.1145/129712.129721]
	10	F.T. Leighton, B.M. Maggs, and S.B. Rao. Packet routing and job-shop scheduling in O(congestion + dilation) steps. Combinatorica, 14(2):167-186, 1994 (preliminary version in FOCS '88).
	11	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]
	12	F.T. Leighton, B.M. Maggs, and A.W. Richa. Fast algorithms for finding O(congesting+dilation) packet routing schedules. Technical report CMU-CS-96-152, School of Computer Science, Carnegie-Mellon University, 1996. Combinatorica, to appear.
	13	F. Meyer auf der Heide and B. V6cking. A packet routing protocol for arbitrary networks. In STA CS '95.
	14	Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks: the single-node case, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.344-357, June 1993 [doi>10.1109/90.234856]
	15	Abhay K. Parekh , Robert G. Gallagher, A generalized processor sharing approach to flow control in integrated services networks: the multiple node case, IEEE/ACM Transactions on Networking (TON), v.2 n.2, p.137-150, April 1994 [doi>10.1109/90.298432]
	16	S. Plotkin. Competitive routing of virtual circuits in ATM networks. IEEE J. Selected Areas in Communications, 1995.
	17	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]
	18	Aravind Srinivasan , Chung-Piaw Teo, A constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.636-643, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258658]

CITED BY 22

	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
	Imrich Chlamtac , Hongbiao Zhang , András Faragó , Andrea Fumagalli, A deterministic approach to the end-to-end analysis of packet flows in connection-oriented networks, IEEE/ACM Transactions on Networking (TON), v.6 n.4, p.422-431, Aug. 1998
	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
	Uriel Feige , Christian Scheideler, Improved bounds for acyclic job shop scheduling (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.624-633, May 24-26, 1998, Dallas, Texas, United States
	Aravind Srinivasan , Chung-Piaw Teo, A constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.636-643, May 04-06, 1997, El Paso, Texas, 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
	Matthew Andrews , Lisa Zhang, The effects of temporary sessions on network performance, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.448-457, January 09-11, 2000, San Francisco, California, United States
	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 , Lisa Zhang, Packet routing with arbitrary end-to-end delay requirements, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.557-565, May 01-04, 1999, Atlanta, Georgia, United States
	V. S. Anil Kumar , Madhav V. Marathe , Srinivasan Parthasarathy , Aravind Srinivasan, End-to-end packet-scheduling in wireless ad-hoc networks, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	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
	Matthew Andrews , Lisa Zhang, Minimizing end-to-end delay in high-speed networks with a simple coordinated schedule, Journal of Algorithms, v.52 n.1, p.57-81, July 2004
	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
	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
	Costas Busch , Malik Magdon-Ismail , Jing Xi, Oblivious routing on geometric networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	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
	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
	Eric Angel , Evripidis Bampis , Fanny Pascual, The impact of local policies on the quality of packet routing in paths, trees, and rings, Journal of Scheduling, v.11 n.5, p.311-322, October 2008
	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