AESOP home


Passage Time Distributions in Large Markov Chains

Peter G. Harrison, William J. Knottenbelt

Conference or Workshop Paper
SIGMETRICS'02, ACM SIGMETRICS conference on Measurement and Modeling of Computer Systems
May, 2002
ACM SIGMETRICS Performance Evaluation Review
Volume 30
Issue 1
ACM Press
DOI 10.1145/511399.511345

Probability distributions of response times are important in the design and analysis of transaction processing systems and computer communication systems. We present a general technique for deriving such distributions from high-level modelling formalisms whose state spaces can be mapped onto finite Markov chains. We use a load-balanced, distributed implementation to find the Laplace transform of the first passage time density and its derivatives at arbitrary values of the transform parameters. Setting s = 0 yields moments while the full passage time distribution is obtained using a novel distributed Laplace transform inverter based on the Laguerre method. We validate our method against a variety of simple densities, cycle time densities in certain overtake-free (tree-like) queueing networks and a simulated Petri net model. Our implementation is thereby rigorously validated and has already been applied to substantial Markov chains with over 1 million states. Corresponding theoretical results for semi-Markov chains are also presented.

PDF of full publication (212.8 kilobytes)
(need help viewing PDF files?)
GZipped Postscript of full publication (167.9 kilobytes)
(need help viewing GZipped Postscript files?)

Information from