AESOP home


Addressing the state space explosion problem for PEPA models through fluid-flow approximation

Richard Hayden

Undergraduate project
Imperial College London
June, 2007
Distinguished project

Markovian process algebras such as PEPA facilitate a powerful compositional approach to the modelling of complex computer networks. However, they are notoriously susceptible to the state space explosion problem. Systems of only modest sizes can result in models with so many states that they are all but intractable to the traditional methods of 'solving' the underlying continuoustime Markov chain.

There has been limited preliminary work in the literature aimed at addressing the state space explosion problem by employing fluid-flow approximation techniques through the generation of systems of coupled ordinary differential equations from certain symmetric classes of PEPA models. This work, although empirically promising, lacks formal justification. For the first time, we present a formal mathematical framework justifying the generation of such systems of coupled ODEs from a class of PEPA models, using the mathematical insight gained to extend this technique to higher-order moments and to identify its key limitations.

We proceed to address these limitations through the development of a novel hybrid fluid-flow approximation scheme for PEPA models based upon stochastic differential equations. This scheme is able to handle models consisting of both continuously and discretely behaving components - up to this point a continuous state space approximation had to be applied either to the entirety of a model or not at all. Furthermore, this scheme should easily generalise to other Markovian modelling formalisms since it does not rely on any specific aspect of PEPA.

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

Information from