Approximate product-forms and reversed processes for performance analysis (APROPOS)

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 .

Although the focus of the proposal is on theoretical research, we also anticipate that benefits will arise from general exploitation of the efficient, compositional, performance analysis methodology that is implicit in the whole approach. In the longer term, its specific application in models of real systems, abstractions of which we consider as case studies in Task 5, will assist users and developers of such systems in carrying out efficient management and optimisation of performance. Further downstream, indirect benefits would also then accrue to the competitiveness of the UK ICT industry, the environment and the public at large, in part through the training of people to contribute to the knowledge economy. In particular, the project will provide excellent training in research for the RA as well as for PhD students (funded from other sources), who should emerge from the project with a good knowledge of the theory and practice of performance engineering. System designers and capacity planners in industry will be able to apply compositional techniques of the kind we use and propose to construct rapidly performance models for a wide variety of complex distributed systems, e.g. computer and communication systems, workflow processing systems (such as patient-flow in hospitals) and sensor networks. Our RCAT-based methodology can then be applied to either solve the models efficiently (in a separable manner) or to give guidance on how the model might be modified in such a way as to yield an efficient, approximate solution. This represents a significant advance over traditional analysis methods, either based on solution of explicit Markov chains (computationally intractable for large systems) or queueing network theory (highly restricted in its application). Cloud technologies in particular need to make scheduling decisions in real time and so require models that quantify performance rapidly, on-the-fly. Reasonable approximations are usually quite adequate and our methodology appears ideal for this purpose. As capacity planning consultants to a wide range of businesses, our industrial partner Metron will be in the best position to exploit the more practical output directly in the longer term. Communication of project outputs to a wider audience and engagement of relevant interested third parties with the project will take place through a variety of channels: (i) Events will be arranged locally, including the hosting of the primary international conference of our research field, the Joint Sigmetrics/Performance 2012 conference; (ii) Metron will host a workshop during the second half of the project, which will feature a selection of national and international participants from both academia and industry; (iii) A (virtual) project web server will be set up to promote and communicate the goals of the project, and to encourage wider collaboration; (iv) Project results and case studies will be published openly in major international journals, as referred to in Academic beneficiaries ; (v) Dissemination will also occur through travelling to relevant research institutions throughout the world (see Academic beneficiaries ). As outlined in their letter of support, we have set up six monthly meetings with Metron at which we will review progress and obtain input into future objectives. Further, Metron will assist us with integrating our techniques into their Athene capacity planning software, as well as in the provision of real-world test case scenarios. The PI has a good record of managing research grants and knowledge transfer activities, having been an investigator on over 20 EPSRC grants (15 as PI). These included in particular the grant Performance Modelling Of Client-Server Systems (PERMOCS) (GR/L06744/01), which featured Metron as a project partner. Outputs from that project were jointly published with Metron, and were incorporated into subsequent versions of the Athene toolset.