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


Clearing analysis on phases: Exact limiting probabilities for skip-free, unidirectional, quasi-birth-death processes

Sherwin Doroudi, University of Minnesota
Brian Fralix, Clemson University
Mor Harchol-Balter, Carnegie Mellon University


Abstract
A variety of problems in computing, service, and manufacturing systems can be modeled via infinite repeating Markov chains with an infinite number of levels and a finite number of phases. Many such chains are quasi-birth-death processes with transitions that are skip-free in level, in that one can only transition between consecutive levels, and unidirectional in phase, in that one can only transition from lower-numbered phases to higher-numbered phases. We present a procedure, which we call Clearing Analysis on Phases (CAP), for determining the limiting probabilities of such Markov chains exactly. The CAP method yields the limiting probability of each state in the repeating portion of the chain as a linear combination of scalar bases raised to a power corresponding to the level of the state. The weights in these linear combinations can be determined by solving a finite system of linear equations.

AMS 2000 subject classifications: 60J22, 60J27.

Keywords: Markov chains, quasi-birth-death processes.

Creative Common LOGO

Full Text: PDF


Doroudi, Sherwin, Fralix, Brian, Harchol-Balter, Mor, Clearing analysis on phases: Exact limiting probabilities for skip-free, unidirectional, quasi-birth-death processes, Stochastic Systems, 6, (2016), 420-458 (electronic). DOI: 10.1214/15-SSY183.

References

[1]    J. Abate and W. Whitt. Transient behavior of the M/M/1 queue via Laplace transforms. Advances in Applied Probability, pages 145–178, 1988. MR0932538

[2]    I. Adan and J. Resing. A class of Markov processes on a semi-infinite strip. Technical Report 99-03, Eindhoven University of Technology, Department of Mathematics and Computing Sciences, 1999.

[3]    S. Asmussen. Applied Probability and Queues, volume 51. Springer Science & Business Media, 2003. MR1978607

[4]    L. Bright and P. G. Taylor. Calculating the equilibrium distribution in level dependent quasi-birth-and-death processes. Stochastic Models, 11(3):497–525, 1995. MR1340970

[5]    C. W. Chan, V. F. Farias, and G. J. Escobar. The impact of delays on service times in the intensive care unit. Management Science, 2016.

[6]    G. Ciardo, W. Mao, A. Riska, and E. Smirni. ETAQA-MG1: an efficient technique for the analysis of a class of M/G/1-type processes by aggregation. Performance Evaluation, 57(3):235–260, 2004.

[7]    G. Ciardo and E. Smirni. ETAQA: an efficient technique for the analysis of QBD-processes by aggregation. Performance Evaluation, 36:71–93, 1999.

[8]    M. Delasay, A. Ingolfsson, and B. Kolfal. Modeling load and overwork effects in queueing systems with adaptive service rates. Operations Research, 2016. MR3532859

[9]    S. Doroudi, B. Fralix, and M. Harchol-Balter. Clearing analysis on phases: Exact limiting probabilities for skip-free, unidirectional, quasi-birth-death processes. arXiv preprint arXiv:1503.05899v3, 2015.

[10]    A. Gandhi, S. Doroudi, M. Harchol-Balter, and A. Scheller-Wolf. Exact analysis of the M/M/k/setup class of Markov chains via recursive renewal reward. In Proceedings of the ACM SIGMETRICS/international conference on Measurement and modeling of computer systems, pages 153–166. ACM, 2013.

[11]    A. Gandhi, S. Doroudi, M. Harchol-Balter, and A. Scheller-Wolf. Exact analysis of the M/M/k/setup class of Markov chains via recursive renewal reward. Queueing Systems, 77(2):177–209, 2014. MR3206189

[12]    A. Gandhi, M. Harchol-Balter, R. Raghunathan, and M. A. Kozuch. Autoscale: Dynamic, robust capacity management for multi-tier data centers. ACM Transactions on Computer Systems (TOCS), 30(4):14, 2012.

[13]    M. Harchol-Balter. Performance Modeling and Design of Computer Systems: Queueing Theory in Action. Cambridge University Press, 2013.

[14]    Q.-M. He. Fundamentals of Matrix-Analytic Methods. Springer, 2014. MR3112230

[15]    R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press, 2012.

[16]    S. Karlin and H. Taylor. A First Course in Stochastic Processes. Acadmic Press, New York, 1975.

[17]    G. Latouche and V. Ramaswami. A logarithmic reduction algorithm for quasi-birth-death processes. Journal of Applied Probability, pages 650–674, 1993.

[18]    G. Latouche and V. Ramaswami. Introduction to Matrix Analytic Methods in Stochastic Modeling. ASA-SIAM, Philadelphia, 1999.

[19]    Y. Levy and U. Yechiali. An M/M/s queue with servers’ vacations. INFOR, 14:153–163, 1976.

[20]    D. Liu and Y. Zhao. Determination of explicit solution for a general class of Markov processes. Matrix-Analytic Methods in Stochastic Models, page 343, 1996. MR1427280

[21]    I. Mitrani and R. Chakka. Spectral expansion solution for a class of Markov models: Application and comparison with the matrix-geometric method. Performance Evaluation, 23(3):241–260, 1995.

[22]    M. Neuts. Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. John Hopkins University Press, Baltimore, Maryland, 1981.

[23]    T. Phung-Duc. Exact solutions for M/M/c/setup queues. Telecommunication Systems, pages 1–16, 2014.

[24]    V. Ramaswami and G. Latouche. A general class of Markov processes with explicit matrix-geometric solutions. Operations-Research-Spektrum, 8(4):209–218, 1986.

[25]    A. Riska and E. Smirni. Exact aggregate solutions for M/G/1-type Markov processes. In ACM SIGMETRICS Performance Evaluation Review, volume 30, pages 86–96. ACM, 2002.

[26]    A. Riska and E. Smirni. ETAQA solutions for infinite Markov processes with repetitive structure. INFORMS Journal on Computing, 19(2):215–228, 2007.

[27]    J. Selen, I. J. Adan, V. G. Kulkarni, and J. van Leeuwaarden. The snowball effect of customer slowdown in critical many-server systems. Stochastic Models, 32:366–391, 2016. MR3505449

[28]    J. Selen, I. J. Adan, and J. S. Van Leeuwaarden. Product-form solutions for a class of structured multidimensional Markov processes. SIAM Journal on Applied Mathematics, 74(3):844–863, 2014.

[29]    A. Sleptchenko, J. Selen, I. Adan, and G.-J. van Houtum. Joint queue length distribution of multi-class, single-server queues with preemptive priorities. Queueing Systems, 81(4):379–395, 2015.

[30]    A. Stathopoulos, A. Riska, Z. Hua, and E. Smirni. Bridging ETAQA and ramaswami’s formula for the solution of M/G/1-type processes. Performance Evaluation, 62(1):331–348, 2005.

[31]    B. Van Houdt and J. van Leeuwaarden. Triangular M/G/1-Type and Tree-Like Quasi-Birth-Death Markov Chains. INFORMS Journal on Computing, 23(1):165–171, 2011.

[32]    J. van Leeuwaarden, M. Squillante, and E. Winands. Quasi-birth-and-death processes, lattice path counting, and hypergeometric functions. Journal of Applied Probability, 46(2):507–520, 2009.

[33]    J. van Leeuwaarden and E. Winands. Quasi-birth-and-death processes with an explicit rate matrix. Stochastic Models, 22(1):77–98, 2006.




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

Stochastic Systems. ISSN: 1946-5238