Guaranteed approximation of Markov chains with applications to multiplexer engineering in ATM networks

Discrete Markov chains are applied widely for analysis and design of high speed ATM networks due to their essentially discrete nature. Unfortunately, their use is precluded for many important problems due to explosion of the state space cardinality. In this paper the authors propose a new method for approximation of a discrete Markov chain by a chain of considerably smaller dimension which is based on the duality theory of optimization. A novel feature of the present approach is that it provides guaranteed upper and lower bounds for the performance indices defined on the steady state distribution of the original system. The authors apply the method to the problem of engineering multiplexers for ATM networks.