Stability of adaptive and non-adaptive packet routing policies in adversarial queueing networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Stability of adaptive and non-adaptive packet routing policies in adversarial queueing networks

Full text

Pdf (723 KB)

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: 206 - 214

Year of Publication: 1999

ISBN:1-58113-067-8

Author

David Gamarnik

T.J. Watson Research Center, IBM Yorktown Heights, NY

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): 17, Citation Count: 17

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.301306 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	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 [doi>10.1145/276698.276788]
	2	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
	3	Dimitris Bertsimas , David Gamarnik, Asymptotically optimal algorithms for job shop scheduling and packet routing, Journal of Algorithms, v.33 n.2, p.296-318, Nov. 1999 [doi>10.1006/jagm.1999.1047]
	4	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]
	5	M. Bramson. Convergence to equilibria for fluid models of FIFO queueing networks. Queueing Systems, 22(1):5-45, 1996.
	6	R. Cru~. A calculus for network delay, part II: network analysis. {EEE Trans. Information Theory, 37:132-141, 1991.
	7	David Gamarnik, Stability of Adversarial Queues via Fluid Models, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.60, November 08-11, 1998
	8	Ashish Goel, Stability of Networks and Protocols in the Adversarial Queueing Model for Packet Routing, Stanford University, Stanford, CA, 1997
	9	J. Kleinberg. Personal communication. 1998.
	10	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]
	11	P. Tsaparas. Stability in A dversarial Queueing Theory. M.Sc. Thesis, University of Toronto, 1997.

CITED BY 17

	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
	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
	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
	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
	Zvi Lotker , Boaz Patt-Shamir , Adi Rosén, New stability results for adversarial queuing, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	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
	Adi Rosén, A note on models for non-probabilistic analysis of packet switching networks, Information Processing Letters, v.84 n.5, p.237-240, 16 December 2002
	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
	Micah Adler , Adi Rosén, Tight bounds for the performance of longest in system on DAGs, Journal of Algorithms, v.55 n.2, p.101-112, May 2005
	Adi Rosén , Michael S. Tsirkin, On delivery times in packet networks under adversarial traffic, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	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
	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
	Matthew Andrews , Antonio Fernández , Ashish Goel , Lisa Zhang, Source routing and scheduling in packet networks, Journal of the ACM (JACM), v.52 n.4, p.582-601, July 2005
	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
	Carme Àlvarez , Maria Blesa , Maria Serna, Universal stability of undirected graphs in the adversarial queueing model, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	Michael J. Neely , Eytan Modiano , Yuan-Sheng Cheng, Logarithmic delay for N × N packet switches under the crossbar constraint, IEEE/ACM Transactions on Networking (TON), v.15 n.3, p.657-668, June 2007
	Gagan R. Gupta , Sujay Sanghavi , Ness B. Shroff, Node weighted scheduling, Proceedings of the eleventh international joint conference on Measurement and modeling of computer systems, June 15-19, 2009, Seattle, WA, USA