Computing Publications

Publications Home » Automated formulation and solutio...

Automated formulation and solution of Markov modulated queues with geometric processes

Demetres D. Kouvatsos (Ed.), David Thornley, Harf Zatschler, Peter G. Harrison

Book Chapter
Traffic and performance engineering for heterogeneous networks
March, 2009
River Publishers, NY
ISBN 9788792329165

We present an automated formulation mechanism that generates systems of equations for efficiently solving for the equilibria of finite or infinite Markov modulated queues with geometrically batched Poisson arrivals and departures. In common with earlier work, the method benefits from its ability to generate equations which describe a homogeneous linear matrix recurrence relation of finite domain over the majority of the system. The new approach can do this for queues with arbitrary numbers of arrival processes of positive and negative customers of mixed types and service completion processes. Moreover, geometric distributions can be scaled and superimposed to produce a range of convex probability mass functions. We thereby provide a fully operational practical approach for the analytical modelling of many present day communication and computer systems, e.g. the Internet and mobile networks. The geometric distribution produces an infinite range of batch sizes, which creates unbounded transitions in queue length, leading to Kolmogorov balance equations with an unbounded, possibly infinite, number of terms. Our method constructs an equivalent ensemble of transformed Kolmogorov balance equations of finite range. The key contribution is the mechanical derivation of these transformed equations, for which we have a working implementation used to provide a range of examples. Previously, such equations had to be derived from first principles for every variant of every applicable queueing system in a manual procedure, which is highly error prone. An additional, crucial benefit is the ability to formulate and solve systems in which there may be inactive processes, or two or more processes with similar burstiness characteristics in a given modulation state. Such degenerate systems cannot be solved using these previous methods.


This paper can be viewed on Google Books at

BibTEX file for the publication built & maintained by Ashok Argent-Katwala.