AESOP home


Steady-State and Response Time Analysis of Modulated Queues and Networks with Batches

Harf Zatschler

PhD Thesis
University of London
July, 2004

Rapid growth in size and complexity of communication networks such as the Internet during the past thirty years is imposing pressure on performance analysts to provide reliable Quality of Service performance metrics. Analytical models are the preferred route to performance prediction in view of their precision and efficient execution, but tend to require overly restrictive assumptions, which we relax dramatically. We extend the M/M/1 Markovian queue specification to include geometrically distributed batches to model bursty processes, Markov modulation to model autocorrelation in traffic and model switching between modes of operation, service breakdowns and repairs, negative customers to model losses and load balancing as well as multiple streams of all types described in these terms. We propose a solution mechanism, derived from the well-known spectral expansion and matrix geometric methods, that provides accurate state occupation probability (SOP) solutions for queues of this type at equilibrium. The development of our method first demonstrates and then overcomes weaknesses inherent in these basic methods when applied to our, more complex, queueing model. An automated implementation of the solution process allows for rapid deployment of what would otherwise be a cumbersome and error-prone process.

Quantiles on sojourn times, given by probability distribution functions, have recently become recognised as a critical metric for quality of service in computer networks as well as many other logistical systems. Using our equilibrium SOP results, we derive explicit expressions in the time domain for the sojourn (or response) time probability distribution, whereas previously, sojourn time distributions have not been obtained even for an MMPP/M/1 queue. We modify a previous result for their Laplace transform which we then show takes a rational form and can be inverted to give a mixture of exact distributions without the need for numerical inversion or approximation.

Single queue results are then deployed in a network setting with probabilistic routing, where an iterative algorithm for the approximate joint equilibrium state occupation probabilities for all queues is developed. Numerical results for both SOP and sojourn time distributions are provided that show good accuracy with respect to simulation in most networks and characteristics of networks where accuracy is poor are identified.

PDF of full publication (860.3 kilobytes)
(need help viewing PDF files?)
GZipped Postscript of full publication (785.4 kilobytes)
(need help viewing GZipped Postscript files?)

Information from