M. Meo et al., A method for calculating successive approximate solutions for a class of block banded M/G/1 type Markovian models, PERF EVAL, 44(1-4), 2001, pp. 97-119
This paper presents an efficient equilibrium solution algorithm for a class
of infinite block banded M/G/1 type Markov chains. By re-blocking the stat
es, these are a class of the so-called quasi-birth-and-death (QBD) type cha
ins. The proposed algorithm is not based on an iterative approach, so that
the exact solution can be computed in a known finite number of steps. The k
ey point on which the algorithm is based is the identification of a linear
dependence among variables. This dependence is expressed in terms of a comp
anion matrix. The equilibrium solution of the Markov chain is obtained oper
ating on this matrix.
An attractive feature of the algorithm is that it allows the computation of
a succession of approximate solutions with growing accuracy, until the exa
ct solution is obtained in a finite number of steps. The class of block-ban
ded M/G/1 type Markov chains we consider requires that the lower diagonal b
lock is invertible and that the chain is ergodic. However, many models aris
ing from telecommunication systems satisfy this restriction. Results for a
case study show that the proposed algorithm is efficient and quite accurate
, even when providing approximate solutions. (C) 2001 Elsevier Science B.V.
All rights reserved.