187 results found
Kulatunga H, Knottenbelt WJ, Kadirkamanathan V, 2010, Adaptive Planning of Staffing Levels in Health Care Organisations, 2nd Congress on Electronic Healthcare for the 21st Century, Publisher: SPRINGER-VERLAG BERLIN, Pages: 88-+, ISSN: 1867-8211
Mason AM, Dingle NJ, Knottenbelt WJ, et al., 2010, Modelling infection spread using location tracking, International Journal of Healthcare Technology and Management, Vol: 11, Pages: 442-461, ISSN: 1368-2156
The precision of location tracking technology has improved greatly over the last few decades. We aim to show that by tracking the locations of individuals in a closed environment, it is now possible to record the nature and frequency of interactions between them. Further, that it is possible to use such data to predict the way in which an infection will spread throughout such a population, given parameters such as transmission and recovery rates. We accordingly present a software package that is capable of recording and then replaying location data provided by a high-precision location tracking system. The software then employs a combination of SIR modelling and the epidemiological technique of contact tracing in order to predict the spread of an infection. We use this software to conduct a number of experiments using a sample data set, and compare the SIR graphs generated from these to similar graphs generated using the traditional SIR differential equations. Copyright © 2010 Inderscience Enterprises Ltd.
, 2010, Analytical and Stochastic Modeling Techniques and Applications, 17th International Conference, ASMTA 2010, Cardiff, UK, June 14-16, 2010. Proceedings, Publisher: Springer
, 2009, Proceedings of MASCOTS 2009, 17th Annual Meeting of the IEEE/ACM International Symposium on Modelling, Analysis and Simulation of Computer and Telecommunication Systems, MASCOTS 2009, International Symposium on Modelling, Analysis and Simulation of Computer and Telecommunication Systems, Imperial College London, Publisher: IEEE Computer Society Press
Message from the Programme Committee Chairs\r\n\r\nOn behalf of the Organising and Programme Committee, it is our pleasure to present to you the proceedings of MASCOTS 2009, the IEEE Computer SocietyÆs 17th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunications Systems, which will be held in London. Our society is ever more dependent on the reliable and high performance operation of complex combinations of computer and communication technologies. As existing technologies evolve and new ones emerge, it remains critical to understand, predict and enhance system reliability and performance using stochastic models, simulation and analytical methods. Experimental studies are also needed to parameterise, calibrate and validate models against real-world observations. These are precisely the themes of the MASCOTS conference series. We are very pleased that this yearÆs conference attracted 162 submissions fromall over the world, many of which were of the highest quality. Such a large number of submissions implied a correspondingly high reviewing load, and we are very grateful to the Programme Committee members and many external reviewers who provided between three and six reviews for each submission.\r\n\r\nBased on the critical reviews of the reviewers and discussions in the Programme Committee, we accepted 32 extended papers of the highest quality, 22 high-quality regular papers and 21 posters. The accepted submissions were from 25 countries spanning five continents, included submissions with industrial co-authors from 7 different companies, and covered a diverse set of research areas (e.g. workload modelling, load management and scheduling, performance optimisation and reliability/availability modeling), and diverse application contexts (e.g. parallel and multicore systems, wireless networks and storage systems). The conference programme has been organised broadly to reflect these themes and includes invited keynote tal
, 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
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.
Guenther MC, Bradley JT, Dingle NJ, et 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.
Guenther MC, Dingle NJ, Bradley JT, et 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
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
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 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
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.
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.
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
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
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
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.
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
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
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
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
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
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.
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.