A performance analyser for the numerical solution of general Markov chains

Abstract

Despite many advances in queueing theory and other modelling paradigms, one persistenty discovers real life stochastic systems which do not yield neatly to existing methods for their performance analysis. In most such cases, the only alternative, other than simulation, is to resort to modelling the process as a Markov chain and to solve that. The immediate problem which presents itself, however, is the very familiar one of state-space explosion. In this paper we present a new probabilistic dynamic storage management technique based on hash-compaction which allows large state spaces to be explored with a low state omission probability. The other important consideration in the computation of the steady-state distribution of large Markov chains is the solution of large sparse sets of linear equations. Recent Krylov subspace techniques and new decompositional techniques address this problem in innovative ways. We provide an overview of these methods and implement them, together with our new hash-compaction technique, in a performance analysis tool called DNAmaca. We conclude by modelling a typical real-life example of a teletraffic switch and analysing it with DNAmaca.