On deciding stability of scheduling policies in queueing systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On deciding stability of scheduling policies in queueing systems

Full text

Pdf (1.03 MB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms table of contents

San Francisco, California, United States

Pages: 467 - 476

Year of Publication: 2000

ISBN:0-89871-453-2

Author

David Gamarnik

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

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 16, Citation Count: 1

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

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	D. Bertsimas, D. Gamarnik, and J. Tsitsildis. Stability conditions for multiclass fluid queueing networks. 1EBB Trans. Automat. Control, 41:1618-1631, November 1996.
	3	Vincent D. Blondel , Olivier Bournez , Pascal Koiran , Christos H. Papadimitriou , John N. Tsitsiklis, Deciding stability and mortality of piecewise affine dynamical systems, Theoretical Computer Science, v.255 n.1-2, p.687-696, March 28, 2001 [doi>10.1016/S0304-3975(00)00399-6]
	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. Instability of FIFO queueing networks. Ann. Appl. Probab., 2:414-431, 1994.
	6	J.G. Dai. On the positive Harris recurrence for multiclass queueing networks: A unified approach via fluid models. Ann. Appl. Probab., 5:49-77, 1995.
	7	J.G. Dai and J.H. Vande Vate. On the stability of two-station fluid networks. Submitted to Operations Research, 1997.
	8	J. G. Dai , G. Weiss, Stability and instability of fluid models for reentrant lines, Mathematics of Operations Research, v.21 n.1, p.115-134, Feb. 1996 [doi>10.1287/moor.21.1.115]
	9	D. Down , S. P. Meyn, Piecewise linear test functions for stability and instability of queueing networks, Queueing Systems: Theory and Applications, v.27 n.3-4, p.205-226, 1997 [doi>10.1023/A:1019166115653]
	10	Guy Fayolle, On random walks arising in queueing systems: ergodicity and transience via quadratic forms as Lyapunov functions—Part I, Queueing Systems: Theory and Applications, v.5 n.1-3, p.167-184, November 1989
	11	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
	12	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 [doi>10.1145/301250.301306]
	13	Ashish Goel, Stability of Networks and Protocols in the Adversarial Queueing Model for Packet Routing, Stanford University, Stanford, CA, 1997
	14	P. Hooper. The undecidability of the Turing machine immortality problem. The Journal of Symbolic Logic, 2:219-234, 1966.
	15	John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
	16	S. H. Lu and P. R. Kumar. Distributed scheduling based on due dates and buffer priorities. IEEE Trans. Automat. Control, 36:1406-1416, 1991.
	17	V. A. Malyshev. Classification of two-dimensional positive random walks and almost linear semimartingales. Dokl. Akad. Nauk SSSR, 202:526-528, 1972.
	18	M. V. Menshikov. Ergodicity and transience conditions for random walks in the positive octant of space. Soviet.Math.Dokl., 15, 1979.
	19	A. Rybko and A. Stolyar. On the ergodicity of stochastic processes describing open queueing networks. Problemi Peredachi Informatsii, 28:3-26, 1992.
	20	T. i. Seidman. First come first serve can be unstable. IEEB Trans. Aurora. Control, 39:2166-2170, 1994.