Home | Articles | Past volumes | About | Login | Notify | Contact | Search
 Stochastic Systems > Vol. 6 (2016) open journal systems 


Chattering and congestion collapse in an overload switching control

Ohad Perry, Northwestern University
Ward Whitt, Columbia University


Abstract
Routing mechanisms for stochastic networks are often designed to produce state space collapse (SSC) in a heavy-traffic limit, i.e., to confine the limiting process to a lower-dimensional subset of its full state space. In a fluid limit, a control producing asymptotic SSC corresponds to an ideal sliding mode control that forces the fluid trajectories to a lower-dimensional sliding manifold. Within deterministic dynamical systems theory, it is well known that sliding-mode controls can cause the system to chatter back and forth along the sliding manifold due to delays in activation of the control. For the prelimit stochastic system, chattering implies fluid-scaled fluctuations that are larger than typical stochastic fluctuations.
In this paper we show that chattering can occur in the fluid limit of a controlled stochastic network when inappropriate control parameters are used. The model has two large service pools operating under the fixed-queue-ratio with activation and release thresholds (FQR-ART) overload control which we proposed in a recent paper. The FQR-ART control is designed to produce asymptotic SSC by automatically activating sharing (sending some customers from one class to the other service pool) once an overload occurs. We have previously shown that this control is effective and robust, even if the service rates are less for the other shared customers, when the control parameters are chosen properly. We now show that, if the control parameters are not chosen properly, then delays in activating and releasing the control can cause chattering with large oscillations in the fluid limit. In turn, these fluid-scaled fluctuations lead to severe congestion, even when the arrival rates are smaller than the potential total service rate in the system, a phenomenon referred to as congestion collapse. We show that the fluid limit can be a bi-stable switching system possessing a unique nontrivial periodic equilibrium, in addition to a unique stationary point.

AMS 2000 subject classifications: Primary 60K25, 34C25, 34C55; secondary 60F1f7, 37G15.

Keywords: Stochastic networks, fluid models, overload control, congestion collapse, switching dynamical systems, bi-stability, periodicity.

Creative Common LOGO

Full Text: PDF


Perry, Ohad, Whitt, Ward, Chattering and congestion collapse in an overload switching control, Stochastic Systems, 6, (2016), 132-210 (electronic). DOI: 10.1214/15-SSY187.

References

[1]    Asmussen, S. (2003). Applied probability and queues. Springer. MR1978607

[2]    Bell, S. L. and Williams, R.J. (2001). Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: asymptotic optimality of a threshold policy. The Annals of Applied Probability, 11 (3) 608–649. MR1865018

[3]    Billah, K. Y. and Scanlan, R. H. (1991). Resonance, Tacoma Narrows bridge failure, and undergraduate physics textbooks, American Journal of Physics, 59 (2), 118–124.

[4]    Bramson, M. (1998). State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Systems, 30, (1–2), 89–140. MR1663763

[5]    Bramson, M. (1994). Instability of FIFO queueing networks. The Annals of Applied Probability 4 (2), 414–431. MR1272733

[6]    Bramson, M. (2008). Stability of queueing networks. Springer. MR2445100

[7]    Bramson, M. and Williams, R. J. (2000). On dynamic scheduling of stochastic networks in heavy traffic and some new results for the workload process Proceedings of the 39th IEEE Conference on Decisions and Control, 516–521.

[8]    Chase, C., Serrano, J., Ramadge, P. J. (1993). Periodicity and chaos from switched flow systems: contrasting examples of discretely controlled continuous systems. IEEE Transactions on Automatic Control 38 (1), 70–83. MR1201496

[9]    Dai, J. G. (1995). On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models. The Annals of Applied Probability 5 (1) 49–77. MR1325041

[10]    Durrett, R. (1991). Probability: theory and examples. Wadsworth and Brooks/Cole, Pacific Grove, California. MR1068527

[11]    Erramilli, A. and Forys, L. J. (1991). Oscillations and chaos in a flow model of a switching system. IEEE Journal on Selected Areas in Communications, 9 (2), 171–178.

[12]    Filippov, A. F. (1988) Differential Equations with Discontinuous Righthand Sides. Kluwer Academic Publishers, the Netherlands. MR1028776

[13]    Garnett, O., Mandelbaum, A. and Reiman, M. (2002). Designing a call center with impatient customers, Manufacturing & Service Operations Management, 4, (3), 208–227.

[14]    Gurvich, I. and Whitt, W. (2009). Scheduling Flexible Servers with Convex Delay Costs in Many-Server Service Systems. Manufacturing & Service Operations Management, 11 (2), 237-253.

[15]    Gurvich, I. and Whitt, W. (2009). Queue-and-Idleness-Ratio Controls in Many-Server Service Systems. Mathematics of Operations Research 34 (2), 363–396. MR2554064

[16]    Halfin, S. and Whitt, W. (1981). Heavy-traffic limits for queues with many exponential servers. Operations Research 29 (3) 567–588. MR0629195

[17]    Harrison, J. M. (1988). Brownian models of queueing networks with heterogeneous customer populations Stochastic differential systems, stochastic control theory and applications, 147–186. MR0934722

[18]    Harrison, J.M. (1998). Heavy traffic analysis of a system with parallel servers: asymptotic optimality of discrete-review policies. Annals of applied probability 8 (3) 822–848. MR1627791

[19]    Harrison, J. M. and Taskar, M. I. (1983). Instantaneous control of Brownian motion. Mathematics of Operations research, 8 (3) 439–453. MR0716123

[20]    Harrison, J. M. and Williams, R. J. (2005). Workload reduction of a generalized Brownian network. The Annals of Applied Probability, 15 (4), 2255–2295. MR2187295

[21]    Khalil, H. K. (2002). Nonlinear Systems. Prentice Hall, New Jersey.

[22]    Kontoyiannis I. and S.P. Meyn. (2003). Spectral Theory and Limit Theorems for Geometrically Ergodic Markov Processes. The Annals of Applied Probability, Vol. 13, 304–362. MR1952001

[23]    Liberzon, D. (2003). Switching in Systems and Control. Birkhäuser, Boston. MR1987806

[24]    Liu, Y. and Whitt, W. (2011). Nearly Periodic Behavior in the The Overloaded G∕D∕S + GI Queue. Stochastic Systems, 1 (2), 340–410. MR2949544

[25]    Lu S.H., Kumar P.R. (1991). Distributed scheduling based on due dates and buffer priorities. IEEE Trans. Automat. Control.36(12), 1406–1416.

[26]    Matveev, A. S., Savkin, A. V. (2000). Qualitative theory of hybrid dynamical systems. Birkhäuser, Boston.

[27]    Pang, G., Talreja, R., Whitt, W., (2007). Martingale proofs of many-server heavy-traffic limits for Markovian queues. Probability Surveys, 4, 193–267. MR2368951

[28]    Perry, O., W. Whitt. (2009). Responding to unexpected overloads in large-scale service systems. Management Sci., 55 (8), 1353–1367.

[29]    Perry, O., W. Whitt. (2011a). A fluid approximation for service systems responding to unexpected overloads. Oper. Res., 59 (5), 1159–1170. MR2864331

[30]    Perry, O., W. Whitt. (2011b). An ODE for an overloaded X model involving a stochastic averaging principle. Stochastic Systems, 1 (1), 17–66. MR2948918

[31]    Perry, O., W. Whitt. (2013). A fluid limit for an overloaded X model via an averaging principle. Math, Oper. Res., 38 (2), 294–349. MR3062009

[32]    Perry, O., W. Whitt. (2015a). Achieving rapid recovery in an overload control for large-scale service systems. Forthcoming in INFORMS Journal on Computing. Available at: http://www.columbia.edu/~ww2040/allpapers.html MR3382939

[33]    Perry, O., W. Whitt. (2015b). Online Supplement to Achieving rapid recovery in an overload control for large-scale service systems. Forthcoming in INFORMS Journal on Computing. Available at: http://www.columbia.edu/~ww2040/allpapers.html MR3382939

[34]    Reiman, M. I. (1984). Some diffusion approximations with state space collapse in Modelling and performance evaluation methodology. 207–240, Springer. MR0893658

[35]    Robert, P. (2003). Stochastic networks and queues, Springer-Verlag. MR1996883

[36]    Rudin, W. (1991). Functional Analysis, McGraw-Hill, Inc., New York. MR1157815

[37]    Rybko A.N., Stolyar A.L. (1992). Ergodicity of stochastic processes describing the operations of open queueing networks. Problems Inform. Transmission 28, 3–26 (in Russian). MR1189331

[38]    Sastry, S.S. and Desoer, C. A. (1981). Jump behavior of circuits and systems. IEEE Transactions on Circuits and Systems 28 (12) 1109–1124. MR0643025

[39]    Shah, D., D. Wischik. (2011). Fluid models of congestion collapse in overloaded switched networks. Queueing Systems 69 121–143. MR2836736

[40]    Schaft, V.D. and Schumacher, H. (2000). An introduction to hybrid dynamical systems Springer Lecture Notes in Control and Information Sciences, Vol. 251. Springer-Verlag, London. MR1734638

[41]    Shakkottai, S, R. Srikant, A. L. Stolyar. (2004). Pathwise optimality of the exponential scheduling rule for wireless channels. Adv. Appl. Prob. 36 1021–1045. MR2119854

[42]    Stewart, D.E. (2000). Rigid-body dynamics with friction and impact. SIAM review 42 (1) 3–39. MR1738097

[43]    Stolyar, A. L. (2004). Maxweight scheduling in a generalized switch: state space collapse and workload minimization in heavy traffic. Ann. Appl. Prob. 14 (1) 1–53. MR2023015

[44]    Teschl, G. (2009). Ordinary Differential Equations and Dynamical Systems, Universität Wien. Available online: http://www.mat.univie.ac.at/~gerald/ftp/book-ode/ode.pdf MR2961944

[45]    Tezcan, T. and Dai, J. G. (2010). Dynamic control of N-systems with many servers: Asymptotic optimality of a static priority policy in heavy traffic. Operations Research, 58 (1) 94–110. MR2668929

[46]    Whitt, W. (1971). Weak Convergence Theorems for Priority Queues: Preemptive-Resume Discipline. Journal of Applied Probability 8 (1) 74–94. MR0307389

[47]    Whitt, W. (1981). Comparing counting processes and queues. Adv. Appl. Prob. 13 (1) 207–220. MR0595895

[48]    Whitt, W. (2002). Stochastic-Process Limits, New York, Springer. MR1876437

[49]    Williams, R. J. (1998). Diffusion approximations for open multiclass queueing networks: sufficient conditions involving state space collapse. Queueing systems 30 (1–2) 27–88. MR1663759




Home | Articles | Past volumes | About | Login | Notify | Contact | Search

Stochastic Systems. ISSN: 1946-5238