AESOP home


APROPOS: Approximate product-forms and reversed processes for performance analysis

Prof. Peter Harrison
EPSRC project EP/I030921/1
Started in March 2012
Completed in February 2015
Funded value

The need for models in the quantitative design of complex computer and communicaton systems is indisputable but their construction is hampered by the lack of a uniform methodology for building large models from smaller component-models - mirroring the design process of the systems themselves. Various specific, often ad hoc, techniques have been developed over the last four decades in response to contemporary design features, beginning with queueing networks that modeled multiprogrammed mainframe systems through to network-calculus descriptions of mobile networks and stochastic models of telecommunication systems and the internet. Unfortunately, such models are prone to exponential (or higher) growth in computational complexity, a phenomenon often referred to as state-space explosion. The present proposal aims to provide techniques and tools for deriving efficient, mainly approximate, solutions to models of modern networks. As in almost all analyses of such complex systems, the aim is to find separable solutions, which allow subsystems (components) to be solved separately and their solutions to then be combined in a simple way. More specifically, we propose to develop the recent significant results obtained by the proposer and Dr Andrea Marin through a three-year project supporting Marin as the RA. The said results have led to a number of research and tutorial papers that have been accepted and/or presented at the highest quality international venues in our research area. It is the proposer's view that the research is at a knee in an upward curve and the opportunity to work directly with a rising-star such as Marin is one not to be missed if at all possible; in addition to the above papers and tutorials, Marin has won best paper awards at two international conferences for his work in this area in the last 12 months. Furthermore, the presentation at Sigmetrics 2010 in New York was well received and led to several discussions with leading international researchers and plans for specific collaboration - see the Case for Support. The theoretical research proposed will supplement existing analytical techniques, such as queueing network modeling (QNM), which are still relevant but are lacking in expressive power for modeling today's systems. For example, Stochastic Petri Nets (SPNs) are suitable for describing virtual resource systems, as used in cloud computing for example, which is not the case for standard queueing networks. Similarly, (non-standard) networks with batch movements are important in models of energy-efficient systems (see the Case for Support), but in general do not have separable (or other efficient) solutions; preliminary results relating to this will be presented as a poster at Performance'10 in November. Last, optimisation is facilitated by the ability of our unique approach, using the Reversed Compound Agent Theorem (RCAT), to perturb specifications so as to create separable solutions, admitting the possibility of searching for a best-fit product-form solution.Based on these theoretical and practical developments, the first objective of the proposed project is to enhance the RCAT-approach to product-forms and semi-product-forms for application in models with SPN specifications and in networks with batch-movements. Perhaps even more importantly, the probability density function of the response time of tasks in passing along a path will be investigated in a new class of networks; preliminary results have already been obtained and will also be presented in the aforementioned poster. This work is a substantial advance on established approaches, such as Boxma and Daduna's as well as that of the proposed PI previously. We believe that three years of uninterrupted collaboration between the proposer and Marin in the AESOP research group will attain the goals summarised above and listed under Objectives.