Analysis and computation of the stationary distribution in a special class of Markov chains of level-dependent M/G/1-type and its application to BMAP/M/∞ and BMAP/M/c+M queues

摘要

This paper considers a special class of continuous-time Markov chains of level-dependent M/G/1-type, where block matrices representing downward jumps in the infinitesimal generator are nonsingular. This special class naturally arises in the analysis of BMAP/M/∞ queues and BMAP/M/c queues with exponential impatience times (BMAP/M/c+M). We first formulate the boundary probability vector in terms of a solution of a system of infinitely many linear inequalities. We then reveal that in the above special class, this infinite system is regarded as a nested sequence of simplices, and we identify their vertices. Based on these results, we develop a simple yet efficient computational algorithm for the stationary distribution conditioned that the level is not greater than a predefined N. Note that for a large N, the conditional distribution will provide a good approximation to the stationary distribution. Some numerical examples for BMAP/M/∞ and BMAP/M/c+M queues are shown.