Matrix geometric method

In probability theory, the matrix geometric method is a method for the analysis of quasi-birth–death processes, continuous-time Markov chain whose transition rate matrices with a repetitive block structure.^[1] The method was developed "largely by Marcel F. Neuts and his students starting around 1975."^[2]

Method description

The method requires a transition rate matrix with tridiagonal block structure as follows

Q={\begin{pmatrix}B_{00}&B_{01}\\B_{10}&A_{1}&A_{2}\\&A_{0}&A_{1}&A_{2}\\&&A_{0}&A_{1}&A_{2}\\&&&A_{0}&A_{1}&A_{2}\\&&&&\ddots &\ddots &\ddots \end{pmatrix}}

where each of B₀₀, B₀₁, B₁₀, A₀, A₁ and A₂ are matrices. To compute the stationary distribution π writing π Q = 0 the balance equations are considered for sub-vectors π_i

{\begin{aligned}\pi _{0}B_{00}+\pi _{1}B_{10}&=0\\\pi _{0}B_{01}+\pi _{1}A_{1}+\pi _{2}A_{0}&=0\\\pi _{1}A_{2}+\pi _{2}A_{1}+\pi _{3}A_{0}&=0\\&\vdots \\\pi _{i-1}A_{2}+\pi _{i}A_{1}+\pi _{i+1}A_{0}&=0\\&\vdots \\\end{aligned}}

Observe that the relationship

\pi _{i}=\pi _{1}R^{i-1}

holds where R is the Neut's rate matrix,^[3] which can be computed numerically. Using this we write

{\begin{aligned}{\begin{pmatrix}\pi _{0}&\pi _{1}\end{pmatrix}}{\begin{pmatrix}B_{00}&B_{01}\\B_{10}&A_{1}+RA_{0}\end{pmatrix}}={\begin{pmatrix}0&0\end{pmatrix}}\end{aligned}}

which can be solve to find π₀ and π₁ and therefore iteratively all the π_i.

Computation of R

The matrix R can be computed using cyclic reduction^[4] or logarithmic reduction.^[5]^[6]

Matrix analytic method

Main article: Matrix analytic method

The matrix analytic method is a more complicated version of the matrix geometric solution method used to analyse models with block M/G/1 matrices.^[7] Such models are harder because no relationship like π_i = π₁ R^i – 1 used above holds.^[8]

External links

Performance Modelling and Markov Chains (part 2) by William J. Stewart at 7th International School on Formal Methods for the Design of Computer, Communication and Software Systems: Performance Evaluation

References

↑ Harrison, Peter G.; Patel, Naresh M. (1992). Performance Modelling of Communication Networks and Computer Architectures. Addison-Wesley. pp. 317–322. ISBN 0-201-54419-9.
↑ Asmussen, S. R. (2003). "Random Walks". Applied Probability and Queues. Stochastic Modelling and Applied Probability. 51. pp. 220–243. doi:10.1007/0-387-21525-5_8. ISBN 978-0-387-00211-8.
↑ Ramaswami, V. (1990). "A duality theorem for the matrix paradigms in queueing theory". Communications in Statistics. Stochastic Models. 6: 151–161. doi:10.1080/15326349908807141.
↑ Bini, D.; Meini, B. (1996). "On the Solution of a Nonlinear Matrix Equation Arising in Queueing Problems". SIAM Journal on Matrix Analysis and Applications. 17 (4): 906. doi:10.1137/S0895479895284804.
↑ Latouche, Guy; Ramaswami, V. (1993). "A Logarithmic Reduction Algorithm for Quasi-Birth-Death Processes". Journal of Applied Probability. Applied Probability Trust. 30 (3): 650–674. JSTOR 3214773.
↑ Pérez, J. F.; Van Houdt, B. (2011). "Quasi-birth-and-death processes with restricted transitions and its applications" (PDF). Performance Evaluation. 68 (2): 126. doi:10.1016/j.peva.2010.04.003.
↑ Alfa, A. S.; Ramaswami, V. (2011). "Matrix Analytic Method: Overview and History". Wiley Encyclopedia of Operations Research and Management Science. doi:10.1002/9780470400531.eorms0631. ISBN 9780470400531.
↑ Bolch, Gunter; Greiner, Stefan; de Meer, Hermann; Shridharbhai Trivedi, Kishor (2006). Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications (2 ed.). John Wiley & Sons, Inc. p. 259. ISBN 0471565253.

Queueing theory

Single queueing nodes	D/M/1 queue M/D/1 queue M/D/c queue M/M/1 queue Burke's theorem M/M/c queue M/M/∞ queue M/G/1 queue Pollaczek–Khinchine formula Matrix analytic method M/G/k queue G/M/1 queue G/G/1 queue Kingman's formula Lindley equation Fork–join queue Bulk queue

Arrival processes	Poisson process Markovian arrival process Rational arrival process

Queueing networks	Jackson network Traffic equations Gordon–Newell theorem Mean value analysis Buzen's algorithm Kelly network G-network BCMP network

Service policies	FIFO LIFO Processor sharing Round-robin Shortest job first Shortest remaining time

Key concepts	Continuous-time Markov chain Kendall's notation Little's law Product-form solution Balance equation Quasireversibility Flow-equivalent server method Arrival theorem Decomposition method Beneš method

Limit theorems	Fluid limit Mean field theory Heavy traffic approximation Reflected Brownian motion

Extensions	Fluid queue Layered queueing network Polling system Adversarial queueing network Loss network Retrial queue

Information systems	Data buffer Erlang (unit) Erlang distribution Flow control (data) Message queue Network congestion Network scheduler Pipeline (software) Quality of service Scheduling (computing) Teletraffic engineering

Category

This article is issued from Wikipedia - version of the 9/4/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.