Matrix-geometric solutions of M/G/1-Type Markov chains: A unifying generalized state-space approach

In this paper, we present an algorithmic approach to find the stationary probability distribution of M/G/1-type Markov chains which arise frequently in performance analysis of computer and communication networks. The approach unifies finite- and infinite-level Markov chains of this type through a generalized state-space representation for the probability generating function of the stationary solution. When the underlying probability generating matrices are rational, the solution vector for level k, x(k), is shown to be in the matrix-geometric form x(k+l) = gF(k)H, k greater than or equal to 0, for the infinite-level case, whereas it takes the modified form x(k+l) = g(l)F(1)(k)H(1) + g(2)F(2)(K-k-1)H(2), 0 less than or equal to k < K, for the 'finite-level case. The matrix parameters in the above two expressions can be obtained by decomposing the generalized system into forward and backward subsystems, or, equivalently, by finding bases for certain generalized invariant subspaces of a regular pencil lambda E - A. We note that the computation of such bases can efficiently be carried out using advanced numerical linear algebra techniques including matrix-sign function iterations,vith quadratic convergence rates or ordered generalized Schur decomposition. The simplicity of the matrix-geometric.form of the solution allows one to obtain various performance measures of interest easily, e.g., overflow probabilities and the moments of the level distribution, which is a significant advantage over conventional recursive methods.