AESOP home

Publications

Quantiles of Sojourn Times

Peter G. Harrison, William J. Knottenbelt

Book Chapter
Computer System Performance Modeling in Perspective: A Tribute to the Work of Prof Kenneth C Sevcik
pp.156–194
August, 2006
Imperial College Press
Abstract

Fast response times and the satisfaction of response time quantile targets are important performance criteria for almost all transaction processing, computer-communication and other operational systems. However, response time quantiles tend to be difficult to obtain in stochastic models, even when the mean value of the response time has a relatively simple mathematical expression. Expressions have been obtained for the Laplace transform of the probability density function of sojourn times in many queueing models, including some complex single queues and networks of simple queues. These can sometimes be inverted analytically, giving an explicit expression for the density as a function of time, but more often numerical inversion is necessary. More generally, interesting sojourn times can be expressed in terms of passage times between states in continuous time Markov and semi-Markov chains. Quantiles for these can be computed in principle but can require extensive computational resources, both in terms of processing time and memory. Consequently, until recently, only trivial problems could be solved by this direct method. With recent technological advances, including the widespread use of clusters of workstations and limited availability of parallel supercomputers, very large Markov and semi-Markov chains can be solved directly for passage time densities, allowing many realistic systems to be investigated. This paper reviews the various approaches taken to compute sojourn time quantiles in systems ranging from simple queues to arbitrary semi-Markov chains, by the authors and others, over the past twenty years and more.

Notes

Chapter 10

PDF of full publication (768.6 kilobytes)
(need help viewing PDF files?)
GZipped Postscript of full publication (436.7 kilobytes)
(need help viewing GZipped Postscript files?)

Information from pubs.doc.ic.ac.uk/sevcik-volume.