Scalable analysis of stochastic process algebra models
View/ Open
Date
2010Author
Tribastone, Mirco
Metadata
Abstract
The performance modelling of large-scale systems using discrete-state approaches is
fundamentally hampered by the well-known problem of state-space explosion, which
causes exponential growth of the reachable state space as a function of the number
of the components which constitute the model. Because they are mapped onto
continuous-time Markov chains (CTMCs), models described in the stochastic process
algebra PEPA are no exception. This thesis presents a deterministic continuous-state
semantics of PEPA which employs ordinary differential equations (ODEs) as the underlying
mathematics for the performance evaluation. This is suitable for models consisting
of large numbers of replicated components, as the ODE problem size is insensitive
to the actual population levels of the system under study. Furthermore, the ODE is
given an interpretation as the fluid limit of a properly defined CTMC model when the
initial population levels go to infinity. This framework allows the use of existing results
which give error bounds to assess the quality of the differential approximation. The
computation of performance indices such as throughput, utilisation, and average response
time are interpreted deterministically as functions of the ODE solution and are
related to corresponding reward structures in the Markovian setting.
The differential interpretation of PEPA provides a framework that is conceptually
analogous to established approximation methods in queueing networks based on meanvalue
analysis, as both approaches aim at reducing the computational cost of the analysis
by providing estimates for the expected values of the performance metrics of interest.
The relationship between these two techniques is examined in more detail in
a comparison between PEPA and the Layered Queueing Network (LQN) model. General
patterns of translation of LQN elements into corresponding PEPA components are
applied to a substantial case study of a distributed computer system. This model is
analysed using stochastic simulation to gauge the soundness of the translation. Furthermore,
it is subjected to a series of numerical tests to compare execution runtimes
and accuracy of the PEPA differential analysis against the LQN mean-value approximation
method.
Finally, this thesis discusses the major elements concerning the development of a
software toolkit, the PEPA Eclipse Plug-in, which offers a comprehensive modelling environment
for PEPA, including modules for static analysis, explicit state-space exploration,
numerical solution of the steady-state equilibrium of the Markov chain, stochastic
simulation, the differential analysis approach herein presented, and a graphical
framework for model editing and visualisation of performance evaluation results.