Publications
240 results found
Dingle N, Jackson A, Knottenbelt W, 2009, Towards The Automated Inference Of Queueing Network Models From High-Precision Location Tracking Data, 23rd European Conference on Modelling and Simulation (ECMS 2009), Pages: 664-674
Traditional methods for deriving performance models of customer flow in real-life systems are manual, time-consuming and prone to human error. This paper proposes an automated four-stage data processing pipeline which takes as input raw high-precision location tracking data and which outputs a queueing network model of customer flow. The pipeline estimates both the structure of the network and the underlying interarrival and service time distributions of its component service centres. We evaluate our method's effectiveness and accuracy in four experimental case studies.
Au-Yeung SWM, Harder U, Mccoy EJ, et al., 2009, Predicting patient arrivals to an accident and emergency department, EMERGENCY MEDICINE JOURNAL, Vol: 26, Pages: 241-244, ISSN: 1472-0205
- Author Web Link
- Cite
- Citations: 19
Knottenbelt W, Dingle N, Suto T, 2009, Performance Trees: A Query Specification Formalism for Quantitative Performance Analysis, Parallel, Distributed and Grid Computing for Engineering, Editors: Ivanyi, Topping, Publisher: Saxe-Coburg Publications, Pages: 165-198, ISBN: 978-1-874672-418
Finding a way to specify complex performance queries on models of systems in a way that is both accessible and expressive is a major challenge in performance analysis. This paper describes our attempts to address this challenge through the development of Performance Trees, a formalism for the graphical specification of complex performance queries on stochastic models. Performance Trees are designed to be accessible by providing more intuitive query specification, expressive by being able to reason about a broader range of concepts than current alternatives, extensible by supporting additional user-defined concepts, and versatile through their applicability to multiple modelling formalisms.\r\n\r\nTool support is implemented in the form of a module for the PIPE2 Petri net tool, which provides Performance Tree query design capabilities through both a graphical user interface and a natural language query builder. Query evaluation is supported by a set of integrated parallel and distributed analysis tools, which are hosted on a dedicated cluster. The application of Performance Trees is demonstrated in the context of a case study of an online transaction system. We also illustrate their flexibility with extensions that permit the specification and monitoring of Service Level Agreements.
Thomas N, Bradley JT, Knottenbelt WJ, 2009, Proceedings of PASM 2008, 3rd International Workshop on the Practical Application of Stochastic Modelling, Publisher: Elsevier
This issue contains papers that were originally presented at the Third International Workshop on the Practical Application of Stochastic Modelling (PASM), held at the Universitat de les Illes Balears, Palma de Mallorca, in September 2008. The workshop was collocated with the 5th European Performance Engineering Workshop.\r\n\r\n PASM follows in a long tradition of the application of stochastic modelling to real-world problems. Such models have led to significant advances in modelling theory, as well as insights into the specific problem areas concerned. Coming from a computer science background, PASM is particularly concerned with applications of specification and analysis techniques and tools developed for computer science, as well as computing and communications applications. In particular, the aim of PASM is to give a forum for which applies current well-developed formalisms (stochastic Petri nets, stochastic process algebras, layered queueing networks, etc) to real-world case-studies.\r\n
Knottenbelt W, Dingle N, 2009, Automated Customer-Centric Performance Analysis of Generalised Stochastic Petri Nets Using Tagged Tokens, Electronic Notes in Theoretical Computer Science, Vol: 232, Pages: 75-88, ISSN: 1571-0661
Since tokens in Generalised Stochastic Petri Net (GSPN) models are indistinguishable, it is not always possible to reason about customer-centric performance measures. To remedy this, we propose ôtagged tokensö û a variant of the ôtagged customerö technique used in the analysis of queueing networks. Under this scheme, one token in a structurally restricted net is ôtaggedö and its position tracked as it moves around the net. Performance queries can then be phrased in terms of the position of the tagged token.\r\n\r\nTo date, the tagging of customers or tokens has been a time-consuming, manual and model-specific process. By contrast, we present here a completely automated methodology for the tagged token analysis of GSPNs. We first describe an intuitive graphical means of specifying the desired tagging configuration, along with the constraints on GSPN structure which must be observed for tagged tokens to be incorporated. We then present the mappings required for automatically converting a GSPN with a user-specified tagging structure into a Coloured GSPN (CGSPN), and thence into an unfolded GSPN which can be analysed for performance measures of interest by existing tools. We further show how our methodology integrates with Performance Trees, a formalism for the specification of performance queries.\r\n\r\nWe have implemented our approach in the open source PIPE Petri net tool, and use this to illustrate the extra expressibility granted by tagged tokens through the analysis of a GSPN model of a hospital's Accident and Emergency department.
Thomas N, Bradley J, Knottenbelt W, 2009, Preface: Proceedings of the Third International Workshop on the Practical Application of Stochastic Modelling (PASM 2008), Electronic Notes in Theoretical Computer Science, Vol: 232, Pages: 1-3, ISSN: 1571-0661
Dingle N, Knottenbelt W, Suto T, 2009, PIPE2: A Tool for the Performance Evaluation of Generalised Stochastic Petri Nets, ACM SIGMETRICS Performance Evaluation Review, Vol: 36, Pages: 34-39, ISSN: 0163-5999
This paper presents an overview of Platform-Independent Petri Net Editor 2 (PIPE2 ), an open-source tool that supports the design and analysis of Generalised Stochastic Petri Net (GSPN) models. PIPE2 Æs extensible design enables developers to add functionality via pluggable analysis modules. It also acts as a front-end for a parallel and distributed performance evaluation environment. With PIPE2, users are able to design and evaluate performance queries expressed in the Performance Tree formalism.
Lebrecht AS, Dingle NJ, Harrison PG, et al., 2009, Using bulk arrivals to model i/o request response time distributions in zoned disks and raid systems
Useful analytical models of storage system performance must support the characteristics exhibited by real I/O workloads. Two essential features are the ability to cater for bursty arrival streams and to support a given distribution of I/O request size. This paper develops and applies the theory of bulk arrivals in queueing networks to support these phenom- ena in models of I/O request response time in zoned disks and RAID systems, with a specific focus on RAID levels 01 and 5. We represent a single disk as an MX/G/1 queue, and a RAID system as a fork-join queueing network of MX/G/1 queues. We find the response time distribution for a ran- domly placed request within a random bulk arrival. We also use the fact that the response time of a random request with size sampled from some distribution will be the same as that of an entire batch whose size has the same distribution. In both cases, we validate our models against measurements from a zoned disk drive and a RAID platform. Copyright © 2009 ICST.
Bond HA, Dingle NJ, Franciosi F, et al., 2009, DATA PLACEMENT AND MIGRATION STRATEGIES FOR VIRTUALISED DATA STORAGE SYSTEMS, European Simulation and Modelling Conference (ESM 2009), Publisher: EUROSIS, Pages: 231-237
Lebrecht AS, Dingle NJ, Knottenbelt WJ, 2009, A Performance Model of Zoned Disk Drives with I/O Request Reordering, 6th International Conference on the Quantitative Evaluation of Systems, Publisher: IEEE COMPUTER SOC, Pages: 97-106
- Author Web Link
- Cite
- Citations: 6
Knottenbelt WJ, Dingle NJ, Suto T, 2009, Performance Trees: A Query Specification Formalism for Quantitative Performance Analysis, Editors: Topping, Ivanyi, Publisher: SAXE-COBURG PUBLICATIONS, Pages: 165-198, ISBN: 978-1-874672-41-8
- Author Web Link
- Cite
- Citations: 1
Lebrecht AS, Dingle NJ, Knottenbelt WJ, 2009, Modelling Zoned RAID Systems Using Fork-Join Queueing Simulation, 6th European Performance Engineering Workshop, Publisher: SPRINGER-VERLAG BERLIN, Pages: 16-29, ISSN: 0302-9743
- Author Web Link
- Cite
- Citations: 6
Argent-Katwala A, Bradley J, Dingle N, et al., 2009, Editorial: Performance engineering, Publisher: Institution of Engineering and Technology (IET), Pages: 443-443, ISSN: 1751-8806
Haggarty OJ, Knottenbelt WJ, Bradley JT, 2008, Distributed Response Time Analysis of GSPN models with MapReduce, Proceedings of the 2008 - International Symposium on Performance Evaluation of Computer and Telecommunication Systems, SPECTS 2008, Pages: 82-90
Generalised Stochastic Petri nets (GSPNs) are widely used in the performance analysis of computer and communications systems. Response time densities and quantiles are often key outputs of such analysis. These can be extracted from a GSPN's underlying semi-Markov process using a method based on numerical Laplace transform inversion. This method typically requires the solution of thousands of systems of complex linear equations, each of rank n, where n is the number of states in the model. For large models substantial processing power is needed and the computation must therefore be distributed. This paper describes the implementation of a Response Time Analysis module for the Platform Independent Petri net Editor (PIPE2) which interfaces with Hadoop, an open source implementation of Google's MapReduce distributed programming environment, to provide distributed calculation of response time densities in GSPN models. The software is validated with analytically calculated results as well as simulated ones for larger models. Excellent scalability is shown.
Lebrecht A, Dingle N, Knottenbelt W, 2008, Modelling and Validation of Response Times in Zoned RAID, 16th Annual Meeting of the IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS) \r\n
We present and validate an enhanced analytical queueing network model of zoned RAID. The model focuses on RAID levels 01 and 5, and yields the distribution of I/O request response time. Whereas our previous work could only support arrival streams of I/O requests of the same type, the model presented here supports heterogeneous streams with a mixture of read and write requests. This improved realism is made possible through multiclass extensions to our existing model. When combined with priority queueing, this development also enables more accurate modelling of the way subtasks of RAID 5 write requests are scheduled. In all cases we derive analytical results for calculating not only the mean but also higher moments and the full distribution of I/O request response time. We validate our model against measurements from a real RAID system.
Knottenbelt W, Dingle N, 2008, Automated Customer-Centric Performance Analysis of Generalised Stochastic Petri Nets Using Tagged Tokens, Third International Workshop on Practical Applications of Stochastic Modelling (PASM'08), Publisher: Elsevier
Since tokens in Generalised Stochastic Petri Net (GSPN) models are indistinguishable, it is not always possible to reason about customer-centric performance measures. To remedy this, we propose "tagged tokens" - a variant of the "tagged customer" technique used in the analysis of queueing networks. Under this scheme, one token in a structurally restricted net is "tagged" and its position tracked as it moves around the net. Performance queries can then be phrased in terms of the position of the tagged token.\r\n\r\nTo date, the tagging of customers or tokens has been a time-consuming, manual and model-specific process. By contrast, we present here a completely automated methodology for the tagged token analysis of GSPNs. We first describe an intuitive graphical means of specifying the desired tagging configuration, along with the constraints on GSPN structure which must be observed for tagged tokens to be incorporated. We then present the mappings required for automatically converting a GSPN with a user-specified tagging structure into a Coloured GSPN (CGSPN), and thence into an unfolded GSPN which can be analysed for performance measures of interest by existing tools. We further show how our methodology integrates with Performance Trees, a formalism for the specification of performance queries.\r\n\r\nWe have implemented our approach in the open source PIPE Petri net tool, and use this to illustrate the extra expressibility granted by tagged tokens through the analysis of a GSPN model of a hospital's Accident and Emergency department.
Kulatunga H, Knottenbelt WJ, 2008, Efficient computation of passage time densities and distributions in Markov chains using Laguerre method, ELECTRONICS LETTERS, Vol: 44, Pages: 935-937, ISSN: 0013-5194
Knottenbelt W, Dingle N, 2008, State-Space Size Estimation By Least-Squares Fitting, 24th UK Performance Engineering Workshop (UKPEW 2008), Pages: 347-357
We present a method for estimating the number of states in the continuous time Markov chains (CTMCs) underlying high-level models using least-squares fitting. Our work improves on existing techniques by producing a numerical estimate of the number of states rather than classifying the state space into on of three types. We demonstrate the practicality and accuracy of our approach on a number of CTMCs generated from three Generalised Stochastic Petri Net (GSPN) models with up to 11 million states.\r\n
Lebrecht A, Dingle N, Knottenbelt W, 2008, Validation of Large Zoned RAID Systems, 24th UK Performance Engineering Workshop (UKPEW 2008), Pages: 246-261
Building on our prior work we present an improved model for for large partial stripe following full stripe writes in RAID 5. This was necessary because we observed that our previous model tended to underestimate measured results. To date, we have only validated these models against RAID systems with at most four disks. Here we validate our improved model, and also our existing models for other read and write configurations, against measurements taken from an eight disk RAID array.\r\n
Bradley JT, Hayden RA, Suto T, et al., 2008, Extracting Fluid Response times from PEPA models, PASTA'08, 7th Workshop on Process Algebra and Stochastically Timed Activities
Recent developments in the analysis of stochastic process algebra models allow for transient measures of very large models to be extracted. By performing so-called fluid analysis of stochastic process algebra models, it is now feasible to analyse systems of size 10^1000 states and beyond. This paper seeks to extend the type of measure that can be extracted from this style of fluid analysis. We present a systematic transformation of a PEPA model that will allow us to extract measures analogous to response times.\r\n
Trifunovic A, Knottenbelt WJ, 2008, Parallel multilevel algorithms for hypergraph partitioning, JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, Vol: 68, Pages: 563-581, ISSN: 0743-7315
- Author Web Link
- Open Access Link
- Cite
- Citations: 37
Suto T, Knottenbelt W, Dingle N, et al., 2008, Performance Trees: Implementation And Distributed Evaluation, PDMC'08, 7th International Workshop on Parallel and Distributed Methods in Verification
In this paper, we describe the first realisation of an evaluation environment for Performance Trees, a recently proposed formalism for the specification of performance properties and measures. In particular, we present details of the architecture and implementation of this environment that comprises a client-side model and performance query specification tool, and a server-side distributed evaluation engine, supported by a dedicated computing cluster. The evaluation engine combines the analytic capabilities of a number of distributed tools for steady-state, passage time and transient analysis, and also incorporates a caching mechanism to avoid redundant calculations. We demonstrate in the context of a case study how this analysis pipeline allows remote users to design their models and performance queries in a sophisticated yet easy to use framework, and subsequently evaluate them by harnessing the computing power of a Grid cluster back-end.
Bradley JT, Hayden R, Knottenbelt WJ, et al., 2008, Extracting response times from fluid analysis of performance models, SPEC International Performance Evaluation Workshop (SIPEW 2008), Publisher: Springer Verlag, Pages: 29-43
Recent developments in the analysis of stochastic process algebra models allow for transient measures of very large models to be extracted. By performing so-called fluid analysis of stochastic process algebra models, it is now feasible to analyse systems of size 101000 states and beyond. This paper seeks to extend the type of measure that can be extracted from this style of fluid analysis. We present a systematic transformation of a PEPA model that will allow us to extract measures analogous to response times. We end by extracting these response-time measures from a PEPA model of a healthcare system.
Wan F, Dingle NJ, Knottenbelt WJ, et al., 2008, SIMULATION AND MODELLING OF RAID 0 SYSTEM PERFORMANCE, European Simulation and Modelling Conference, Publisher: EUROSIS, Pages: 145-149
- Author Web Link
- Open Access Link
- Cite
- Citations: 1
Haggarty OJ, Knottenbelt WJ, Bradley JT, 2008, Distributed Response Time Analysis of GSPN Models with MapReduce, International Symposium on Performance Evaluation Computer and Telecommunication Systems, Publisher: SOC MODELING SIMULATION INT-SCS, Pages: 82-90
- Author Web Link
- Cite
- Citations: 1
Dingle NJ, Knottenbelt WJ, Wang L, 2008, SERVICE LEVEL AGREEMENT SPECIFICATION, COMPLIANCE PREDICTION AND MONITORING WITH PERFORMANCE TREES, European Simulation and Modelling Conference, Publisher: EUROSIS, Pages: 137-144
- Author Web Link
- Open Access Link
- Cite
- Citations: 3
Wang L, Dingle NJ, Knottenbelt WJ, 2008, Natural Language Specification of Performance Trees, 5th European Performance Engineering Workshop, Publisher: SPRINGER-VERLAG BERLIN, Pages: 141-151, ISSN: 0302-9743
- Author Web Link
- Cite
- Citations: 1
Brien DK, Dingle NJ, Knottenbelt WJ, et al., 2008, A Parallel and Distributed Analysis Pipeline for Performance Tree Evaluation, 5th International Conference on the Quantitative Evaluation of Systems, Publisher: IEEE COMPUTER SOC, Pages: 237-238
Lebrecht AS, Dingle NJ, Knottenbelt WJ, 2008, A response time distribution model for zoned RAID, 15th International Conference on Analytical and Stochastic Modelling Techniques and Applications, Publisher: SPRINGER-VERLAG BERLIN, Pages: 144-157, ISSN: 0302-9743
- Author Web Link
- Cite
- Citations: 4
Kulatunga H, Argent-Katwala A, Knottenbelt W, 2007, Cluster grid based response-time analysis module for the PIPE tool, Pages: 51-52
Generalized Stochastic Petri Nets (GSPNs) are a widely used high-level formalism used for modelling discrete-event systems. The Platform Independent Petri net Editor (PIPE) is an open source software project that allows creation, analysis and simulation of Petri Nets. This tool paper presents a PIPE module for response-time analysis of a Petri net's underlying Continuous Time Markov Chain (CTMC). Jobs are submitted via a web interface, from within PIPE or from a browser. The parallel computations are run using Grid Engine on a cluster hosted at Imperial College London. © 2007 IEEE.
This data is extracted from the Web of Science and reproduced under a licence from Thomson Reuters. You may not copy or re-distribute this data in whole or in part without the written consent of the Science business of Thomson Reuters.