|dc.description.abstract||We present an analysis framework for performance evaluation of large-scale resource-bound
(LSRB) computer systems. LSRB systems are those whose resources are continually
in demand to serve resource users, who appear in large populations and cause
high contention. In these systems, the delivery of quality service is crucial, even in
the event of resource failure. Therefore, various techniques have been developed for
evaluating their performance. In this thesis, we focus on the technique of quantitative
modelling, where in order to study a system, first its model is constructed and then the
system’s behaviour is analysed via the model.
A number of high level formalisms have been developed to aid the task of model
construction. We focus on PEPA, a stochastic process algebra that supports compositionality
and enables us to easily build complex LSRB models. In spite of this advantage,
however, the task of analysing LSRB models still poses unresolved challenges.
LSRB models give rise to very large state spaces. This issue, known as the state
space explosion problem, renders the techniques based on discrete state representation,
such as numerical Markovian analysis, computationally expensive. Moreover,
simulation techniques, such as Gillespie’s stochastic simulation algorithm, are also
computationally demanding, as numerous trajectories need to be collected.
Furthermore, as we show in our first contribution, the techniques based on the
mean-field theory or fluid flow approximation are not readily applicable to this case.
In LSRB models, resources are not assumed to be present in large populations and
models exhibit highly noisy and stochastic behaviour. Thus, the mean-field deterministic
behaviour might not be faithful in capturing the system’s randomness and is
potentially too crude to show important aspects of their behaviours. In this case, the
modeller is unable to obtain important performance indicators, such as the reliability
measures of the system. Considering these limitations, we contribute the following
analytical methods particularly tailored to LSRB models.
First, we present an aggregation method. The aggregated model captures the evolution
of only the system’s resources and allows us to efficiently derive a probability
distribution over the configurations they experience. This distribution provides full
faithfulness for studying the stochastic behaviour of resources. The aggregation can be
applied to all LSRB models that satisfy a syntactic aggregation condition, which can
be quickly checked syntactically. We present an algorithm to generate the aggregated
model from the original model when this condition is satisfied.
Second, we present a procedure to efficiently detect time-scale near-complete decomposability
(TSND). The method of TSND allows us to analyse LSRB models at
a reduced cost, by dividing their state spaces into loosely coupled blocks. However,
one important input is a partition of the transitions defined in the model, categorising
them into slow or fast. Forming the necessary partition by the analysis of the model’s
complete state space is costly. Our process derives this partition efficiently, by relying
on a theorem stating that our aggregation preserves the original model’s partition and
therefore, it can be derived by an efficient reachability analysis on the aggregated state
space. We also propose a clustering algorithm to implement this reachability analysis.
Third, we present the method of conditional moments (MCM) to be used on LSRB
models. Using our aggregation, a probability distribution is formed over the configurations
of a model’s resources. The MCM outputs the time evolution of the conditional
moments of the marginal distribution over resource users given the configurations of
resources. Essentially, for each such configuration, we derive measures such as conditional
expectation, conditional variance, etc. related to the dynamics of users. This
method has a high degree of faithfulness and allows us to capture the impact of the
randomness of the behaviour of resources on the users.
Finally, we present the advantage of the methods we proposed in the context of a
case study, which concerns the performance evaluation of a two-tier wireless network
constructed based on the femto-cell macro-cell architecture.||en
|dc.relation.hasversion||A. Pourranjbar, J. Hillston, and L. Bortolussi. Don’t just go with the flow: Cautionary tales of fluid flow approximation. In Mirco Tribastone and Stephen Gilmore, editors, Computer Performance Engineering, volume 7587 of Lecture Notes in Computer Science, pages 156–171. Springer Berlin Heidelberg, 2013.||en