Home | Articles | Past volumes | About | Login | Notify | Contact | Search
 Stochastic Systems open journal systems 


Detecting Markov chain instability: A Monte Carlo approach

Michel R. H. Mandjes, University of Amsterdam
Brendan J. Patch, The University of Queensland
Neil S. Walton, The University of Manchester


Abstract
We devise a Monte Carlo based method for detecting whether a non-negative Markov chain is stable for a given set of parameter values. More precisely, for a given subset of the parameter space, we develop an algorithm that is capable of deciding whether the set has a subset of positive Lebesgue measure for which the Markov chain is unstable. The approach is based on a variant of simulated annealing, and consequently only mild assumptions are needed to obtain performance guarantees. The theoretical underpinnings of our algorithm are based on a result stating that the stability of a set of parameters can be phrased in terms of the stability of a single Markov chain that searches the set for unstable parameters. Our framework leads to a procedure that is capable of performing statistically rigorous tests for instability, which has been extensively tested using several examples of standard and non-standard queueing networks.

AMS 2000 subject classifications: 68M20; 90B15; 60J22; 65C05

Keywords: Markov chains, stability, Monte Carlo simulation, queueing networks

Creative Common LOGO

Full Text: PDF


Mandjes, Michel R. H., Patch, Brendan J., Walton, Neil S., Detecting Markov chain instability: A Monte Carlo approach, Stochastic Systems, 7, (2017), 1-45 (electronic). DOI: 10.1214/16-SSY220.

References

[1]    Andrews, M. and Zhang, L. (2003). Achieving stability in networks of input-queued switches. Networking, IEEE/ACM Transactions on 11, 5, 848–857.

[2]    Baccelli, F. and Bonald, T. (1999). Window flow control in FIFO networks with cross traffic. Queueing Systems 32, 1, 195–231. MR1720554

[3]    Baskett, F., Chandy, K. M., Muntz, R. R., and Palacios, F. G. (1975). Open, closed, and mixed networks of queues with different classes of customers. Journal of the ACM 22, 2, 248–260. MR0365749

[4]    Bordenave, C., McDonald, D., and Proutiรจre, A. (2012). Asymptotic stability region of slotted ALOHA. Information Theory, IEEE Transactions on 58, 9, 5841–5855. MR2966060

[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 Berlin Heidelberg, New York. MR2445100

[7]    Dai, J. (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

[8]    Ghaderi, J., Borst, S., and Whiting, P. (2014). Queue-based random-access algorithms: fluid limits and stability issues. Stochastic Systems 4, 1, 81–156. MR3353215

[9]    Hairer, M. (2010). Convergence of Markov processes. Lecture notes. Available at http://www.hairer.org/notes/Convergence.pdf.

[10]    Jackson, J. R. (1963). Jobshop-like queueing systems. Management Science 10, 1, 131–142.

[11]    Kelly, F. P. (1975). Networks of queues with customers of different types. Journal of Applied Probability 12, 3, 542–554. MR0388571

[12]    Kelly, F. P. (1979). Reversibility and Stochastic Networks. Wiley, Chichester. MR0554920

[13]    Kirkpatrick, S. and Vecchi, M. P. (1983). Optimization by simulated annealing. Science 220, 4598, 671–680. MR0702485

[14]    Kumar, P. R. and Seidman, T. I. (1990). Dynamic instabilities and stabilization methods in distributed real-time scheduling of manufacturing systems. Automatic Control, IEEE Transactions on 35, 3, 289–298. MR1044023

[15]    Leahu, H. and Mandjes, M. (2016). A numerical approach to stability of multiclass queueing networks. (preprint).

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

[17]    MacPhee, I., Menshikov, M., Petritis, D., and Popov, S. (2007). A Markov chain model of a polling system with parameter regeneration. The Annals of Applied Probability 17, 5/6, 1447–1473. MR2358630

[18]    McKeown, N., Mekkittikul, A., Anantharam, V., and Walrand, J. (1999). Achieving 100% throughput in an input-queued switch. Communications, IEEE Transactions on 47, 8, 1260–1267.

[19]    Meyn, S. and Tweedie, R. (2012). Markov Chains and Stochastic Stability. Communications and Control Engineering. Springer London. MR1287609

[20]    Nazarathy, Y., Taimre, T., Asanjarani, A., Kuhn, J., Patch, B., and Vuorinen, A. (2015). The challenge of stabilizing control for queueing systems with unobservable server states. In Control Conference (AUCC), 2015 5th Australian. Engineers Australia, Gold Coast, 342–347.

[21]    Rybko, A. and Stolyar, A. L. (1993). Ergodicity of stochastic processes describing the operation of open queueing networks. Problemy Peredachi Informatsii 28, 3, 3–26. MR1189331

[22]    Tassiulas, L. and Ephremides, A. (1992). Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. Automatic Control, IEEE Transactions on 37, 12, 1936–1948. MR1200609

[23]    Tassiulas, L. and Ephremides, A. (1993). Dynamic server allocation to parallel queues with randomly varying connectivity. Information Theory, IEEE Transactions on 39, 2, 466–478. MR1224342

[24]    Wieland, J. R., Pasupathy, R., and Schmeiser, B. W. (2003). Queueing network simulation analysis: queueing-network stability: simulation-based checking. In Proceedings of the 35th conference on Winter simulation: driving innovation. Winter Simulation Conference, 520–527.

[25]    Williams, D. (1991). Probability with Martingales. Cambridge University Press, Cambridge. MR1155402




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

Stochastic Systems. ISSN: 1946-5238