Piecewise linear test functions for stability and instability of queueing networks
| SpringerLink
This service is more advanced with JavaScript available, learn more at http://activatejavascript.org
Piecewise linear test functions for stability and instability of queueing networksD. DownS.P. MeynArticleDOI:
10.1023/A:3Cite this article as: Down, D. & Meyn, S. Queueing Systems (5. doi:10.1023/A:3
We develop the use of piecewise linear test functions for the analysis of stability of multiclass queueing networks and their associated fluid limit models. It is found that if an associated LP admits a positive solution, then a Lyapunov function exists. This implies that the fluid limit model is stable and hence that the network model is positive Harris recurrent with a finite polynomial moment. Also, it is found that if a particular LP admits a solution, then the network model is transient.multiclass queueing networksergodicitystabilityperformance analysis[1]F. Baccelli and S. Foss, Ergodicity of Jackson-type queueing networks, Queueing Systems 17 (.[2]D. Bertsimas, D. Gamarnik and J.N. Tsitsiklis, Stability conditions for multiclass fluid queueing networks, Technical Report, Massachusets Institute of Technology (1995).[3]D. Bertsimas, I.Ch. Paschalidis and J.N. Tsitsiklis, Scheduling of multiclass queueing networks: Bounds on achievable performance, in: Workshop on Hierarchical Control for Real-Time Scheduling of Manufacturing Systems (Lincoln, NH, 1992).[4]A.A. Borovkov, Limit theorems for queueing networks, Theory Probab. Appl. 31 (–427.[5]D.D. Botvich and A.A. Zamyatin, Ergodicity of conservative communication networks, Rapports de Recherche No. 1772, INRIA, Rocquencourt, France (1992).[6]M. Bramson, Instability of FIFO queueing networks, Ann. Appl. Probab. 4 (–431.[7]H. Chen and A. Mandelbaum, Discrete flow networks: Bottlenecks analysis and fluid approximations, Math. Oper. Res. 16 (–446.[8]H. Chen and H. Zhang, Stability of multiclass queueing networks under priority service disciplines, Preprint (1996).[9]J.G. Dai and S.P. Meyn, Stability and convergence of moments for multiclass queueing networks via fluid models, IEEE Trans. Automat. Control 40 (–1904.[10]J.G. Dai and Y. Wang, Nonexistence of Brownian models for certain multiclass queueing networks, Queueing Systems 13 (.[11]J.G. Dai and G. Weiss, Stability and instability of fluid models for reentrant lines, Math. Oper. Res. 21 (–134.[12]J.G. Dai, On the positive Harris recurrence for multiclass queueing networks: A unified approach via fluid limit models, Ann. Appl. Probab. 5 (.[13]J.G. Dai, A fluid-limit model criterion for instability of multiclass queueing networks, Ann. Appl. Probab. (1996) 6.[14]J.G. Dai and J.H. Vande Vate, Global stability of two-station queueing networks, in: Proceedings of Workshop on Stochastic Networks: Stability and Rare Events (Springer, New York, 1996).[15]D. Down and S.P. Meyn, The structure of fluid models and instability of queueing networks, in: Proceedings of the European Control Conf., Rome, Italy (1995).[16]D.G. Down and S.P. Meyn, A survey of Markovian methods for stability of networks, in: 11th Internat. Conf. on Analysis and Optimization of Systems, Sophia-Antipolis, France (1994).[17]D.G. Down and S.P. Meyn, Piecewise linear test functions for stability of queueing networks, in: Proceedings of the 33rd Conf. on Decision and Control, Buena Vista, FL (1994).[18]V. Dumas, A multiclass network with non-linear, non-convex, non-monotonic stability conditions, Technical Report, INRIA, Rocquencourt (1995).[19]V. Dumas, Approches fluides pour la stabilité et l'instabilité de réseaux de files d'attente stochastiques à plusieurs classes de clients, Ph.D. thesis, L'Ecole Polytechnique (1996).[20]P. Dupuis and R.J. Williams, Lyapunov functions for semimartingale reflecting Brownian motions, Ann. Probab. 22 (–702.[21]G. Fayolle, On random walks arising in queueing systems: Ergodicity and transience via quadratic forms as Lyapunov functions – Part I, Queueing Systems 5 (–184.[22]G. Fayolle, V.A. Maly?ev, M.V. Men'?ikov and A.F. Sidorenko, Lyapunov functions for Jackson networks, Technical Report, INRIA, Rocquencourt (1991).[23]S.G. Foss, Ergodicity of queueing networks, Siberian Math. J. (–705. Translated from Sibirskii Matematicheskii Zhurnal 32 (–203.[24]F.G. Foster, On the stochastic matrices associated with certain queueing processes, Ann. Math. Statist. 24 (–360.[25]J.M. Harrison and V. Nguyen, Brownian models of multiclass queueing networks: Current status and open problems, Queueing Systems 13 (.[26]C. Humes Jr., A regulator stabilization technique: Kumar and Seidman revisited, IEEE Trans. Automat. Control 39 (–196.[27]R.Z. Khas'minskii, Stochastic Stability of Differential Equations (Sijthoff & Noordhoff, Alphen aan den Rija, Netherlands, 1980).[28]J.F.C. Kingman, The ergodic behaviour of random walks, Biometrika 48 (.[29]P.R. Kumar and S.P. Meyn, Stability of queueing networks and scheduling policies, IEEE Trans. Automat. Control 40 (–260.[30]P.R. Kumar and S.P. Meyn, Duality and linear programs for stability and performance analysis of queueing networks and scheduling policies, IEEE Trans. Automat. Control 41 (.[31]P.R. Kumar, Re-entrant lines, Queueing Systems 13 (0.[32]P.R. Kumar and T.I. Seidman, Dynamic instabilities and stabilization methods in distributed real-time scheduling of manufacturing systems, IEEE Trans. Automat. Control 35 (–298.[33]S. Kumar and P.R. Kumar, Performance bounds for queueing networks and scheduling policies, IEEE Trans. Automat. Control 39 (–1611.[34]S. Kumar and P.R. Kumar, Fluctuation smoothing policies are stable for re-entrant lines, to appear in Discrete Event Dynamical Systems.[35]J. LaSalle and S. Lefshetz, Stability by Liapunov's Direct Method (Academic Press, New York, NY, 1961).[36]S.H. Lu and P.R. Kumar, Distributed scheduling based on due dates and buffer priorities, IEEE Trans. Automat. Control 36 (–1416.[37]V.A. Maly?ev, Classification of two-dimensional positive random walks and almost linear semimartingales, Soviet Math. Dokl. 13 (–139.[38]V.A. Maly?ev, Networks and dynamical systems, Adv. in Appl. Probab. 25 (–175.[39]V.A. Maly?ev and M.V. Men'?ikov, Ergodicity, continuity and analyticity of countable Markov chains, Trans. Moscow Math. Soc. 1 (.[40]M.V. Men?ikov, Ergodicity and transience conditions for random walks in the positive octant of space, Soviet Math. Dokl. 15 (–1121.[41]S.P. Meyn, Transience of multiclass queueing networks via fluid limit models, Ann. Appl. Probab. 5 (–957.[42]S.P. Meyn and D. Down, Stability of generalized Jackson networks, Ann. Appl. Probab. 4 (–148.[43]S.P. Meyn and R.L. Tweedie, Markov Chains and Stochastic Stability (Springer, London, 1993).[44]S.P. Meyn and R.L. Tweedie, Stability of Markovian processes III: Foster–Lyapunov criteria for continuous time processes, Adv. in Appl. Probab. 25 (–548.[45]S.P. Meyn and R.L. Tweedie, A survey of Foster–Lyapunov techniques for general state space Markov processes, in: Proceedings of the Workshop on Stochastic Stability and Stochastic Stabilization, Metz, France (1993).[46]J.R. Perkins, C. Humes Jr. and P.R. Kumar, Distributed control of flexible manufacturing systems: stability and performance, IEEE Trans. Robotics Automat. 37 (–141.[47]A.N. Rybko and A.L. Stolyar, On the ergodicity of stochastic processes describing open queueing networks, Technical Report, Moscow (1992).[48]T.I. Seidman, First come first serve can be unstable, IEEE Trans. Automat. Control 39 (–2170.[49]K. Sigman, The stability of open queueing networks, Stochastic Process. Appl. 35 (.D. Down1S.P. Meyn11.Coordinated Science LaboratoryUrbanaUSA
Buy (PDF)EUR&34,95
Unlimited access to full article
Instant download (PDF)
Price includes local sales tax if applicable
Export citation
Share article
We use cookies to improve your experience with our site.}