Publications Home » Fluid computation of passage time...
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
- pp.106–141
- January, 2012
- Elsevier
- DOI 10.1016/j.tcs.2011.07.017
- Abstract
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.
- Keywords
- AESOP
- Fluid and ODE analysis
- Performance Modelling and Analysis
- Process Algebra
- Notes
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?)
BibTEX file for the publication - N.B.
- Conditions for downloading publications from this site.
pubs.doc.ic.ac.uk: built & maintained by Ashok Argent-Katwala.