Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-24T16:53:02.787Z Has data issue: false hasContentIssue false
  • English
  • Français

A logarithmic reduction algorithm for quasi-birth-death processes

Part of: Special processes Markov processes

Published online by Cambridge University Press:  14 July 2016

Guy Latouche  and
V. Ramaswami
Guy Latouche*
Affiliation:
Université Libre de Bruxelles
V. Ramaswami*
Affiliation:
Bellcore
*
∗ Postal address: Université Libre de Bruxelles, Département d'Informatique, CP212, Boulevard du Triomphe, 1050 Bruxelles, Belgium.
∗∗ Postal address: Bellcore, 331 Newman Springs Road, Red Bank, NJ 07701–7030, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

Quasi-birth-death processes are commonly used Markov chain models in queueing theory, computer performance, teletraffic modeling and other areas. We provide a new, simple algorithm for the matrix-geometric rate matrix. We demonstrate that it has quadratic convergence. We show theoretically and through numerical examples that it converges very fast and provides extremely accurate results even for almost unstable models.

Keywords

QUEUEING THEORYMATRIX METHODSCOMPUTATIONAL PROBABILITYQUADRATIC CONVERGENCEFIRST-PASSAGE TIMES

MSC classification

Primary: 60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
Secondary: 60J05: Discrete-time Markov processes on general state spaces 60K25: Queueing theory
Type
Research Papers
Information
Journal of Applied Probability , Volume 30 , Issue 3 , September 1993 , pp. 650 - 674
Copyright
Copyright © Applied Probability Trust 1993 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Asmussen, S. and Ramaswami, V. (1990) Probabilistic interpretations of some duality results for the matrix paradigms in queueing theory. Commun. Statist. Stoch. Models 6, 715–733.Google Scholar
[2] Buzbee, B. L., Golub, G. H. and Nielson, C. W. (1970) On direct methods for solving Poisson's equation. SIAM J. Numer. Anal. 7, 627–656.Google Scholar
[3] Daigle, J. N. and Lucantoni, D. M. (1991) Queueing systems having phase-dependent arrival and service rates. In Numerical Solution of Markov Chains, ed. Stewart, William J., pp. 161–202. Marcel Dekker, New York.Google Scholar
[4] Evans, R. V. (1967) Geometric distribution in some two-dimensional queueing systems. Operat. Res. 15, 830–846.Google Scholar
[5] Grassmann, W. and Heyman, D. (1990) Equilibrium distribution of block-structured Markov chains with repeating rows. J. Appl. Prob. 27, 557–576.Google Scholar
[6] Grassmann, W. and Heyman, D. (1991) Computation of steady-state probabilities for infinite Markov chains with repeating rows. Bellcore Technical Memorandum, 1991.Google Scholar
[7] Gün, L. (1989) Experimental results on matrix-analytical solution techniques - Extensions and comparisons. Commun. Statist. Stoch. Models 5, 669–682.Google Scholar
[8] Hajek, B. (1982) Birth-and-death processes on the integers with phases and general boundaries. J. Appl. Prob. 19, 488–499.Google Scholar
[9] Kao, E. P. (1991) Using state reduction for computing steady state probabilities of queues of GI/PH/1 types. ORSA J. Computing 3, 231–240.Google Scholar
[10] Latouche, G. (1981) Algorithmic analysis of a multiprogramming-multiprocessor computer system. J. Assoc. Comp. Mach. 28, 662–679.Google Scholar
[11] Latouche, G. (1987) A note on two matrices occurring in the solution of quasi-birth-and-death processes. Commun. Statist. Stoch. Models 3, 251–257.Google Scholar
[12] Latouche, G. (1992) Algorithms for infinite Markov chains with repeating columns. IMA Workshop on Linear Algebra, Markov Chains and Queuing Models, January 1992.Google Scholar
[13] Latouche, G. (1992) Algorithms for evaluating the matrix G in Markov chains of PH/G/1 type. Bellcore, Technical Report.Google Scholar
[14] Latouche, G. (1992) Newton's iterations for nonlinear equations in Markov chains. Bellcore, Technical Report.Google Scholar
[15] Lucantoni, D. M. and Ramaswami, V. (1985) Efficient algorithms for solving the non-linear matrix equations arising in phase type queues. Commun. Statist. Stoch. Models 1, 29–52.Google Scholar
[16] Nelson, R. D. (1990) A performance evaluation of a general parallel processing model. Perform. Eval. Rev. 18, 13–26.Google Scholar
[17] Nelson, R. D. and Iyer, B. R. (1985) Analysis of a replicated data base. Perfor. Eval. 5, 133–148.Google Scholar
[18] Neuts, M. F. (1976) Moment formulas for the Markov renewal branching process. Adv. Appl. Prob. 8, 690–711.Google Scholar
[19] Neuts, M. F. (1978) The M/M/1 queue with randomly varying arrival and service rates. Opsearch 15, 139–157.Google Scholar
[20] Neuts, M. F. (1978) Further results on the M/M/1 queue with randomly varying rates. Opsearch 15, 158–168.Google Scholar
[21] Neuts, M. F. (1981) Matrix-Geometric Solutions in Stochastic Models. An Algorithmic Approach. The Johns Hopkins University Press, Baltimore MD.Google Scholar
[22] Neuts, M. F. (1986) The caudal characteristic curve of queues. Adv. Appl. Prob. 18, 221–254.Google Scholar
[23] Neuts, M. F. and Lucantoni, D. M. (1979) A Markovian queue with N servers subject to breakdowns and repairs. Management Sci. 25, 849–861.Google Scholar
[24] Ortega, J. M. and Rheinboldt, W. C. (1970) Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, New York.Google Scholar
[25] Ramaswami, V. (1988) Nonlinear matrix equations in applied probability - Solution techniques and open problems. SIAM Rev. 30, 256–263.Google Scholar
[26] Ramaswami, V. (1990) A duality theorem for the matrix paradigms in queueing theory. Commun. Statist. Stoch. Models 6, 151–161.Google Scholar
[27] Ramaswami, V. and Latouche, G. (1989) An experimental evaluation of the matrix-geometric method for the GI/PH/1 queue. Commun. Statist. Stoch. Models 5, 629–667.Google Scholar
[28] Ramaswami, V. and Neuts, M. F. (1980) A duality theorem for phase type queues. Ann. Prob. 8, 974–985.Google Scholar
[29] Rao, B. M. S. and Posner, M. J. M. (1987) Algorithmic and approximation analyses of the shorter queue model. Naval Res. Logist. Quart. 34, 381–398.Google Scholar
[30] Squillante, M. S. and Nelson, R. D. (1991) Analysis of task migration in shared-memory multiprocessor scheduling. IBM Research Report RC 16484.Google Scholar
[31] Wallace, V. (1969) The solution of quasi birth and death processes arising from multiple access computer systems. Ph.D. dissertation, Systems Engineering Laboratory, University of Michigan, Tech. Rept. No. 07742-6-T.Google Scholar
[32] Ye, J. and Li, S. (1991) Analysis of multi-media traffic queues with finite buffer and overload control - Part I: Algorithm. Proc. IEEE Infocom '91, Bal Harbour, 1464–1474.Google Scholar
[33] Zukerman, M. (1989) Applications of matrix-geometric solutions for queueing performance evaluation of a hybrid switching system. J. Austral. Math. Soc. B31, 219–239.Google Scholar
[34] Zukerman, M. and Kirton, P. (1988) Applications of matrix-geometric solutions to the analysis of the bursty data queue in a B-ISDN switching system. Proc. GLOBECOM '88, 1635–1639.Google Scholar