A method for calculating successive approximate solutions for a class of block banded M/G/1 type Markovian models

Citation
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
Citations number
29
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
PERFORMANCE EVALUATION
ISSN journal
0166-5316 → ACNP
Volume
44
Issue
1-4
Year of publication
2001
Pages
97 - 119
Database
ISI
SICI code
0166-5316(200104)44:1-4<97:AMFCSA>2.0.ZU;2-4
Abstract
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.