Adversarial queueing theory

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Adversarial queueing theory

Full text

Pdf (1.18 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: 376 - 385

Year of Publication: 1996

ISBN:0-89791-785-5

Authors

Allan Borodin	Department of Computer Science, University of Toronto, Toronto, Canada M5S 1A4
Jon Kleinberg	Laboratory for Computer Science, MIT, Cambridge, MA
Prabhakar Raghavan	IBM Almaden Research Center, 650 Harry Road, San Jose, CA
Madhu Sudan	IBM T.J. Watson Research Center, Box 218, Yorktown Heights, NY
David P. Williamson	IBM T.J. Watson Research Center, Box 218, Yorktown Heights, NY

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

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.237984 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	Baruch Awerbuch , Tom Leighton, Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.487-496, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195238]
	2	B. AWERBUCH AND F. T. LEIGHTON. personal communication.
	3	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
	4	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]
	5	K. Mani Chandy , John H. Howard, Jr. , Donald F. Towsley, Product Form and Local Balance in Queueing Networks, Journal of the ACM (JACM), v.24 n.2, p.250-263, April 1977 [doi>10.1145/322003.322009]
	6	Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
	7	E P. KELLY. Reversibility and Stochastic Networks. Wiley, New York, 1979.
	8	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
	9	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]
	10	Yishay Mansour , Boaz Patt-Shamir, Greedy packet scheduling on shortest paths (preliminary version), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.165-175, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112615]
	11	D. MITRA AND R. CIESLAK. Randomized parallel communications. Proceedings of the International Conjbrence on Parallel Processing, 1986.
	12	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]
	13	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]

CITED BY 36

	Micah Adler , Phillip B. Gibbons , Vijaya Ramachandran , Yossi Matias, Modeling parallel bandwidth: local vs. global restrictions, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.94-105, June 23-25, 1997, Newport, Rhode Island, United States
	Sanjeev Arora , Bo Brinkman, A randomized online algorithm for bandwidth utilization, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.535-539, January 06-08, 2002, San Francisco, California
	Elliot Anshelevich , David Kempe , Jon Kleinberg, Stability of load balancing algorithms in dynamic adversarial systems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	David Gamarnik, On deciding stability of constrained random walks and queueing systems, ACM SIGMETRICS Performance Evaluation Review, v.28 n.4, p.39-40, March 2001
	Ashish Goel, Stability of networks and protocols in the adversarial queueing model for packet routing, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.911-912, January 17-19, 1999, Baltimore, Maryland, United States
	Michael Mitzenmacher, Constant time per edge is optimal on rooted tree networks, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.162-169, June 24-26, 1996, Padua, Italy
	S. Muthukrishnan , Rajmohan Rajaraman, An adversarial model for distributed dynamic load balancing, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.47-54, 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
	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
	Matthew Andrews , Lisa Zhang, Stability results for networks with input and output blocking, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.369-377, May 24-26, 1998, Dallas, Texas, United States
	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
	David Gamarnik, Stability of adaptive and non-adaptive packet routing policies in adversarial queueing networks, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.206-214, May 01-04, 1999, Atlanta, Georgia, United States
	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
	Allan Borodin , Rafail Ostrovsky , Yuval Rabani, Stability preserving transformations: packet routing networks with edge capacities and speeds, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.601-610, January 07-09, 2001, Washington, D.C., United States
	Zvi Lotker , Boaz Patt-Shamir, Average-case analysis of greedy packet scheduling (extended astract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.31-40, July 16-19, 2000, Portland, Oregon, United States
	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
	David Gamarnik, On deciding stability of scheduling policies in queueing systems, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.467-476, January 09-11, 2000, San Francisco, California, United States
	Peter Sanders, Asynchronous scheduling of redundant disk arrays, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.89-98, July 09-13, 2000, Bar Harbor, Maine, United States
	Zvika Brakerski , Aviv Nisgav , Boaz Patt-Shamir, General perfectly periodic scheduling, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	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
	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
	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
	Matthew Andrews, Instability of FIFO in session-oriented networks, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.440-447, 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, 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
	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
	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
	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
	Michael Mitzenmacher, Constant time per edge is optimal on rooted tree networks, Distributed Computing, v.10 n.4, p.189-197, July 1997
	Peter Sanders, Asynchronous Scheduling of Redundant Disk Arrays, IEEE Transactions on Computers, v.52 n.9, p.1170-1184, September 2003
	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
	Yossi Azar , Yossi Richter, The zero-one principle for switching networks, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Rajmohan Rajaraman, Topology control and routing in ad hoc networks: a survey, ACM SIGACT News, v.33 n.2, June 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
	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
	Stefan Schmid , Roger Wattenhofer, A TCP with guaranteed performance in networks with dynamic congestion and random wireless losses, Proceedings of the 2nd annual international workshop on Wireless internet, p.9-es, August 02-05, 2006, Boston, Massachusetts