Imperial College London

ProfessorWilliamKnottenbelt

Faculty of EngineeringDepartment of Computing

Professor of Applied Quantitative Analysis
 
 
 
//

Contact

 

+44 (0)20 7594 8331w.knottenbelt Website

 
 
//

Location

 

E363ACE ExtensionSouth Kensington Campus

//

Summary

 

Publications

Publication Type
Year
to

182 results found

, 2009, Practical Applications of Stochastic Modelling 2009, PASM 2009, Practical Applications of Stochastic Modelling, Imperial College London

Welcome to the Fourth International Workshop on Practical Applications of Stochastic Modelling, held in conjunction with MASCOTS. PASM is organised as a friendly and inclusive event at which to share interesting and novel applications and developments in modelling theory. We strive to maintain an air of informality to the workshop which we hope fosters discussion and potential collaboration. This volume is the æon-the-dayÆ proceedings for delegates only. In common with previous PASM workshops, the official proceedings will be published later in ElsevierÆs Electronic Notes in Theoretical Computer Science. If you wish to cite a paper from the workshop, please use the ENTCS citation which we will place on the PASM website when it is available. The workshop organisers would like to take this opportunity to extend their thanks to Michael Mislove, executive editor of ENTCS, for his continued support for PASM.\r\n\r\nThis is the fourth time PASM has been held, previous events were held in London in 2004, Newcastle in 2005, Palma de Mallorca in 2008. On each occasion PASM has been collocated with a different host conference. This year we are delighted to be associated with MASCOTS for the first time. We would like to thank Tony Field for inviting us and for his help in organising PASM. Jeremy, Will and Nigel would like to thank Nick for doing all the practical work. The organisation of an event like PASM is a team effort and weÆve learnt to choose our team carefully. Particular thanks must go to the programme committee, who thoroughly refereed all the submissions and made some difficult choices easier by their detailed comments.\r\n\r\nFinally we would like to thank you, the authors and delegates. Without you there would be no papers, no presentations, no questions, no discussion and consequently no PASM. This is your workshop, we hope you enjoy it!\r\n\r\nJeremy Bradley, Nick Dingle, William Knottenbelt and Nigel Thomas\r\nPASM Co-chairs.\r\n

Conference paper

Haggarty O, Knottenbelt WJ, Bradley JT, 2009, Distributed Response Time Analysis of GSPN Models with MapReduce, SIMULATION, Vol: 85, Pages: 497-509

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.\r\n\r\n 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.

Journal article

Guenther MC, Bradley JT, Dingle NJ, Knottenbelt WJet al., 2009, Truncation of Passage-time Calculations in Semi-Markov Models, UKPEW'09, 25th UK Performance Engineering Workshop, Pages: 17-28

Calculation of passage time distributions in large semi-Markov models can be accomplished by means of a previously-presented iterative algorithm, the core of which is repeated sparse matrix-vector multiplication. The algorithm's performance is therefore highly dependent on the number of multiplications of matrix and vector elements that must be performed during each iteration. At the same time, the products of matrix and vector elements that are very small contribute little to the overall result of the multiplication. In this paper, we investigate the effect of ignoring these values on both the performance and accuracy of the iterative passage time algorithm. We show that in the models we analyse here this truncation significantly reduces the number of multiplications which must be performed, and hence significantly reduces the running time of the algorithm, with little effect on the accuracy of the final result.

Conference paper

Guenther MC, Dingle NJ, Bradley JT, Knottenbelt WJet al., 2009, Aggregation strategies for large semi-Markov processes, 3rd International Symposium on Semi-Markov Models: Theory and Applications

High-level semi-Markov modelling paradigms such as semi-Markov stochastic Petri nets and process algebras are used to capture realistic performance models of computer and communication systems but often have the drawback of generating huge underlying semi-Markov processes. Extraction of performance measures such as steady-state probabilities and passage-time distributions therefore relies on sparse matrix-vector operations involving very large transition matrices. The computational complexity of such operations depends on the number of rows and non-zeros in the matrix.\r\n\r\nPrevious studies have shown that exact state-by-state aggregation of semi-Markov processes can be applied to reduce the number of states. However, it is important to select the order in which states are aggregated judiciously so as to avoid a dramatic increase in matrix density caused by the creation of additional transitions between remaining states. Our paper addresses this issue by presenting the concept of state space partitioning for aggregation. Partitioning the state space entails dividing it into a number of non-intersecting subsets. In contrast to previous algorithms that perform state-by-state aggregation on the global unpartitioned graph, our new algorithm works on a local partition-by-partition basis which allows more space-efficient aggregation. We introduce different partitioning methods for this purpose. Furthermore we discuss partition sorting methods that determine the order in which partitions should be aggregated. This order has a significant impact on the connectivity of the aggregate state space, and thus the density of the transition matrix.\r\n\r\nAggregation of partitions can be done in one of two ways. The first way is to use exact state-by-state aggregation to aggregate each individual state within a partition. For this purpose, we present a new state ordering algorithm, which takes into account the exact number of new transitions that are created when aggregating a pa

Conference paper

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.

Conference paper

Au-Yeung SWM, Harder U, Mccoy EJ, Knottenbelt WJet al., 2009, Predicting patient arrivals to an accident and emergency department, EMERGENCY MEDICINE JOURNAL, Vol: 26, Pages: 241-244, ISSN: 1472-0205

Journal article

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.

Book chapter

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

Book

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.

Journal article

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.

Journal article

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

Journal article

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

Book chapter

Lebrecht AS, Dingle NJ, Harrison PG, Knottenbelt WJ, Zertal Set 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.

Conference paper

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

Conference paper

Bond HA, Dingle NJ, Franciosi F, Harrison PG, Knottenbelt WJet al., 2009, DATA PLACEMENT AND MIGRATION STRATEGIES FOR VIRTUALISED DATA STORAGE SYSTEMS, European Simulation and Modelling Conference (ESM 2009), Publisher: EUROSIS, Pages: 231-237

Conference paper

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

Conference paper

Argent-Katwala A, Bradley J, Dingle N, Harder U, Knottenbelt Wet al., 2009, Editorial: Performance engineering, Publisher: Institution of Engineering and Technology (IET), Pages: 443-443, ISSN: 1751-8806

Conference paper

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.

Journal article

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.

Conference paper

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.

Conference paper

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

Journal article

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

Conference paper

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

Conference paper

Bradley JT, Hayden RA, Suto T, Knottenbelt WJet 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

Conference paper

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

Journal article

Suto T, Knottenbelt W, Dingle N, Kulatunga H, Brien Det 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.

Conference paper

Wan F, Dingle NJ, Knottenbelt WJ, Lebrecht ASet al., 2008, SIMULATION AND MODELLING OF RAID 0 SYSTEM PERFORMANCE, European Simulation and Modelling Conference, Publisher: EUROSIS, Pages: 145-149

Conference paper

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

Conference paper

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

Conference paper

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

Conference paper

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.

Request URL: http://wlsprd.imperial.ac.uk:80/respub/WEB-INF/jsp/search-html.jsp Request URI: /respub/WEB-INF/jsp/search-html.jsp Query String: id=00159431&limit=30&person=true&page=4&respub-action=search.html