AESOP home


Fluid computation of passage time distributions in large Markov models

Richard Hayden, Anton Stefanek, Jeremy T. Bradley

Journal Article
Theoretical Computer Science
Volume 413
Issue 1
January, 2012
DOI 10.1016/j.tcs.2011.07.017

Recent developments in the analysis of large Markov models facilitate the fast approximation of transient characteristics of the underlying stochastic process. So called fluid analysis makes it possible to consider previously intractable models whose underlying discrete state space grows exponentially as model components are added. In this work, we show how fluid approximation techniques may be used to extract passage-time measures from performance models. We focus on two types of passage measure: passage times involving individual components; as well as passage times which capture the time taken for a population of components to evolve.

Specifically, we show that for models of sufficient scale, passage-time distributions can be well approximated by a deterministic fluid-derived passage-time measure. Where models are not of sufficient scale, we are able to generate upper and lower approximations for the entire cumulative distribution function of these passage-time random variables, using moment-based techniques. Additionally, we show that, for passage-time measures involving individual components, the cumulative distribution function can be directly approximated by fluid techniques.

Finally, we take advantage of the rapid fluid computation of passage times to show how a multi-class client--server system can be optimised to satisfy multiple service level agreements.


Submitted to TCS November 2010. Accepted July 2011. Available online August 2011.

Extended version of June 2009 technical report entitled "Fluid passage-time calculation in large Markov models"

PDF of full publication (1.1 megabytes)
(need help viewing PDF files?)

Information from