Matrix Geometric Solutions in M/G/1 Type Markov Chains with Multiple Boundaries: A Generalized State-space Approach

摘要

In this paper, we present a computationally efficient algorithm for obtaining the steady-state probability vector of M/G/1 type Markov chains with multiple boundary levels which are used in performance evaluation of computer and communication systems. Our approach involves finding a particular generalized state-space realization of the associated probability generating function of the steady-state vector which is assumed to be rational. We show that the solution vector for level k, x_k, k>=N, has the simple matrix geometric form x_(k+N)=gF~kH, k >= 0, where the vector g and the matrix parameters F and H in the above representation can be obtained by finding bases for certain generalized invariant subspaces of a regular pencil lambdaE-A and N is the number of boundary levels. Such bases can efficiently be found using several generalized invariant subspace solvers of numerical linear algebra, in particular the matrix sign function iterations with quadratic convergence rates.