Fluid computation of passage-time distributions in large Markov models

• Published in: Theoretical computer science 2012-01, Vol.413 (1), p.106-141
• Main Authors: Hayden, Richard A., Stefanek, Anton, Bradley, Jeremy T.
• Format: Article
• Language: English
• Subjects: Approximation; Computational fluid dynamics; Distribution functions; Fluid approximation; Fluid flow; Fluids; Markov models; Mathematical analysis; Mathematical models; Passage-time distribution; Scalability analysis; Service level agreement; Stochastic process algebra
• ISSN: 0304-3975; 1879-2294
• 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. 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, global 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, using the GPA tool, 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.