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

185 results found

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

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

Conference paper

Brien DK, Dingle NJ, Knottenbelt WJ, Kulatunga H, Suto Tet 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

Conference paper

Bradley JT, Hayden R, Knottenbelt WJ, Suto Tet 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.

Conference paper

Au-Yeung S, Knottenbelt W, Harrison P, 2007, Approximate Queueing Network Analysis of Patient Treatment Times, 2nd International Conference on Performance Evaluation Methodologies and Tools, Publisher: ICST, Pages: 1-12

We develop an approximate generating function analysis (AGFA) technique which approximates the Laplace transform of the probability density function of customer response time in networks of queues with class-based priorities. From the approximated Laplace transform, we derive the first two moments of customer response time. This technique is applied to a model of a large hospitalÆs Accident and Emergency department for which we obtain the mean and standard deviation of total patient service time. We experiment with different patient-handling priority schemes and compare the AGFA moments with the results from a discrete event simulation.

Conference paper

Bonet P, Puigjaner R, Lladó C, Knottenbelt Wet al., 2007, PIPE v2.5: A Petri Net Tool for Performance Modelling, 23rd Latin American Conference on Informatics (CLEI 2007), Pages: 1-12

The Petri net modeling formalism allows for the convenient graphical visualization of system models, as well as the analysis of correctness and performance properties. Petri Nets theory has been widely used to implement a variety of modeling and evaluation tools. This paper surveys various of these tools and describes some recent extensions to a freely available and open-source platform-independent Petri net tool called PIPE. The extensions comprise: an increase in modeling power through the introduction of inhibitor arcs, a new analysis module for generating siphons and traps, some new interface features and various presentation improvements. We will illustrate system modeling and analysis with inhibitor arcs in a case study of a token ring network.

Conference paper

Kulatunga H, Argent-Katwala A, Knottenbelt W, 2007, Cluster Grid based Response-time Analysis Module for the PIPE Tool, QEST 2007, 4th International Conference on the Quantitative Evaluation of Systems, Publisher: IEEE Computer Society, 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.

Conference paper

Lebrecht A, Knottenbelt W, 2007, Response Time Approximations in Fork-Join Queues, 23rd Annual UK Performance Engineering Workshop (UKPEW), Pages: 1-8

Fork-join queueing networks model a network of parallel servers in which an arriving job splits into a number of subtasks that are serviced in parallel. Fork-join queues can be used to model disk arrays. A response time approximation of the fork-join queue is presented that attempts to comply with the additional constraints of modelling a disk array. This approximation is compared with existing analytical approximations of the fork-join queueing network.

Conference paper

Knottenbelt W, Bradley J, 2007, Tackling Large State Spaces in Performance Modelling, Formal Methods for Performance Evaluation, Publisher: Springer, Pages: 318-370

Stochastic performance models provide a powerful way of capturing and analysing the behaviour of complex concurrent systems. Traditionally, performance measures for these models are derived by generating and then analysing a (semi-)Markov chain corresponding to the modelÆs behaviour at the state-transition level. However, and especially when analysing industrial-scale systems, workstation memory and compute power is often overwhelmed by the sheer number of states. This chapter explores an array of techniques for analysing stochastic performance models with large state spaces. We concentrate on explicit techniques suitable for unstructured state spaces and show how memory and run time requirements can be reduced using a combination of probabilistic algorithms, disk-based solution techniques and communication-efficient parallelism based on hypergraph-partitioning. We apply these methods to different kinds of performance analysis, including steady-state and passage-time analysis, and demonstrate them on case study examples.

Book chapter

Suto T, Bradley JT, Knottenbelt WJ, 2007, Performance trees: Expressiveness and quantitative semantics, 4th International Conference on the Quantitative Evaluation of Systems, Publisher: IEEE COMPUTER SOC, Pages: 41-+

Conference paper

Trifunovic A, Knottenbelt W, 2006, A General Graph Model for Representing Exact Communication Volume in Parallel Sparse Matrix-Vector Multiplication, 21st International Symposium on Computer and Information Sciences (ISCIS 2006), Pages: 813-824

In this paper, we present a new graph model of sparse matrix decomposition for parallel sparse matrixûvector multiplication. Our model differs from previous graph-based approaches in two main respects. Firstly, our model is based on edge colouring rather than vertex partitioning. Secondly, our model is able to correctly quantify and minimise the total communication volume of the parallel sparse matrixûvector multiplication while maintaining the computational load balance across the processors. We show that our graph edge colouring model is equivalent to the fine-grained hypergraph partitioning-based sparse matrix decomposition model. We conjecture that the existence of such a graph model should lead to faster serial and parallel sparse matrix decomposition heuristics and associated tools.

Conference paper

Knottenbelt W, Harrison P, 2006, Quantiles of Sojourn Times, Computer System Performance Modeling in Perspective: A Tribute to the Work of Prof Kenneth C Sevcik, Publisher: Imperial College Press, Pages: 156-194

Fast response times and the satisfaction of response time quantile targets are important performance criteria for almost all transaction processing, computer-communication and other operational systems. However, response time quantiles tend to be difficult to obtain in stochastic models, even when the mean value of the response time has a relatively simple mathematical expression. Expressions have been obtained for the Laplace transform of the probability density function of sojourn times in many queueing models, including some complex single queues and networks of simple queues. These can sometimes be inverted analytically, giving an explicit expression for the density as a function of time, but more often numerical inversion is necessary. More generally, interesting sojourn times can be expressed in terms of passage times between states in continuous time Markov and semi-Markov chains. Quantiles for these can be computed in principle but can require extensive computational resources, both in terms of processing time and memory. Consequently, until recently, only trivial problems could be solved by this direct method. With recent technological advances, including the widespread use of clusters of workstations and limited availability of parallel supercomputers, very large Markov and semi-Markov chains can be solved directly for passage time densities, allowing many realistic systems to be investigated. This paper reviews the various approaches taken to compute sojourn time quantiles in systems ranging from simple queues to arbitrary semi-Markov chains, by the authors and others, over the past twenty years and more.\r\n

Book chapter

Suto T, Bradley JT, Knottenbelt WJ, 2006, Performance Trees: A New Approach to Quantitative Performance Specification, MASCOTS'06, 14th IEEE International Symposium on Modelling, Analysis, and Simulation of Computer and Telecommunication Systems, Publisher: IEEE Computer Society

Conference paper

Suto T, Bradley J, Knottenbelt W, 2006, Performance Trees: A New Approach to Quantitative Performance Specification, MASCOTS'06, 14th IEEE International Symposium on Modelling, Analysis, and Simulation of Computer and Telecommunication Systems, Publisher: IEEE Computer Society

Conference paper

Au-Yeung SWM, Harrison PG, Knottenbelt WJ, 2006, A queueing network model of patient flow in an accident and emergency department, 20th European Simulation and Modelling Conference (ESM 2006), Publisher: EUROSIS, Pages: 60-+

Conference paper

Bradley J, Dingle N, Harder U, Harrison P, Knottenbelt Wet al., 2006, Response Time Densities and Quantiles in Large Markov and Semi-Markov Models, Performance Evaluation of Parallel, Distributed and Emergent Systems, Publisher: Nova Science Publishers, Inc, Pages: 3-41, ISBN: 1-59454-817-X

Response time quantiles reflect user-perceived quality of service more accurately than mean or average response time measures. Consequently, on-line transaction processing benchmarks, telecommunications Service Level Agreements and emergency services legislation all feature stringent 90th percentile response time targets. This chapter describes a range of techniques for extracting response time densities and quantiles from large-scale Markov and semi-Markov models of real-life systems. We describe a method for the computation of response time densities or cumulative distribution functions which centres on the calculation and subsequent numerical inversion of their Laplace transforms. This can be applied to both Markov and semi-Markov models. We also review the use of uniformization to calculate such measures more efficiently in purely Markovian models. We demonstrate these techniques by using them to generate response time quantiles in a semi-Markov model of a high-availability web-server. We show how these techniques can be used to analyse models with state spaces of 10^7 states and above.

Book chapter

Bradley JT, de Jager DV, Knottenbelt WJ, Trifunovic Aet al., 2005, Hypergraph Partitioning for Faster Parallel PageRank Computation, EPEW'05, Proceedings of the 2nd European Performance Evaluation Workshop, Publisher: Springer-Verlag, Pages: 155-171, ISSN: 0302-9743

The PageRank algorithm is used by search engines such as Google to order web pages. It uses an iterative numerical method to compute the maximal eigenvector of a transition matrix derived from the web's hyperlink structure and a user-centred model of web-surfing behaviour. As the web has expanded and as demand for user-tailored web page ordering metrics has grown, scalable parallel computation of PageRank has become a focus of considerable research effort. In this paper, we seek a scalable problem decomposition for parallel PageRank computation, through the use of state-of-the-art hypergraph-based partitioning schemes. These have not been previously applied in this context. We consider both one and two-dimensional hypergraph decomposition models. Exploiting the recent availability of the Parkway 2.1 parallel hypergraph partitioner, we present empirical results on a gigabit PC cluster for three publicly available web graphs. Our results show that hypergraph-based partitioning substantially reduces communication volume over conventional partitioning schemes (by up to three orders of magnitude), while still maintaining computational load balance. They also show a halving of the per-iteration runtime cost when compared to the most effective alternative approach used to date.

Conference paper

Harder U, Johnson MW, Bradley JT, Knottenbelt WJet al., 2005, Observing internet worm and virus attacks with a small network telescope, Proceedings of PASM 2005 proceedings of the 2nd workshop on practical applications of stochastic modelling, Publisher: Elsevier, Pages: 47-59, ISSN: 1571-0661

Conference paper

, 2005, Proceedings of PASM 2004, 1st International Workshop on Practical Applications of Stochastic Modelling, Publisher: Elsevier

Recent years have seen not only significant theoretical advances in stochastic modelling and associated formalisms but also the increasing availability of high-powered computing facilities in academia and industry alike. The workshop on Practical Applications of Stochastic Modelling (PASM) was created out of a desire to harness these developments by encouraging the application of stochastic modelling formalisms to large-scale real-world systems.\r\n\r\nThe first PASM workshop was held in the Royal Society, London, in September 2004 and we were very pleased to be able to showcase some excellent examples of how formalisms such as stochastic Petri nets, stochastic process algebras, queueing networks and SANs can be used to tackle realistic and diverse stochastic modelling problems.\r\n\r\nThe contributions presented here covered examples of practical and topical interest such as peer-to-peer (P2P) file sharing networks, security protocols, electronic voting systems, parallel programming environments and RAID arrays.\r\n\r\nIt takes a great deal of effort and imagination to tackle the problems inherent in complex systems. We would like to thank everyone who submitted a paper - accepted or not - for taking on this challenge and for helping to contribute to a vibrant workshop. We would also like to thank Joost-Pieter Katoen for an excellent invited presentation on stochastic behaviour of agent negtiation in autonomous wireless devices and Michael Mislove of ENTCS for help and advice in preparing this volume.\r\n\r\nAlso due recognition are the programme committee who put in a stalwart effort to ensure a high quality refereeing process (every submission received at least four reviews):\r\n\r\n- Marco Bernardo\r\n- Mario Bravetti\r\n- Gianfranco Ciardo\r\n- Tod Courtney\r\n- David Daly\r\n- Dan Deavours\r\n- Tony Field\r\n- Stephen Gilmore\r\n- Roberto Gorrieri\r\n- Boudewijn Haverkort\r\n- Graham Horton\r\n- Pieter Kritzinger\r\n- Gethin Norman\r\n- Mohamed Ould-Khaoua\r\n

Book

Thomas N, Bradley JT, Knottenbelt WJ, 2004, Stochastic Analysis of Scheduling Strategies in a Grid-based Resource Model, Publisher: IEE, Pages: 232-239

In this paper, we consider a model inspired by a scenario found in Grid-based scheduling systems. Scheduling is performed remotely without access to up-to-date resource availability and usage information. We model this system as a collection of queues where servers break down and are subsequently repaired. There is a delay before the scheduler learns of failures, as such requests may continue to arrive into a resource queue for some time after active service has ceased. We consider the queues to be persistent under failure, however these queues have finite capacity; therefore there is the possibility that queues become full, causing job-loss. We use stochastic process algebra and stochastic probes to analyse this model to find steady state measures and passage time distributions. The effect of the duration of any delay on information propagation on the system response time and job loss is investigated and evaluated numerically.

Conference paper

, 2004, Proceedings of PASM 2004, the 1st International Workshop on Practical Applications of Stochastic Modelling

Conference paper

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

Recent years have seen not only significant theoretical advances in stochastic modelling and associated formalisms but also the increasing availability of high-powered computing facilities in academia and industry alike. The workshop on Practical Applications of Stochastic Modelling (PASM) was created out of a desire to harness these developments by encouraging the application of stochastic modelling formalisms to large-scale real-world systems.\r\n\r\nWe are, therefore, pleased to showcase in the very first workshop proceedings some excellent examples of how formalisms such as stochastic Petri nets, stochastic process algebras, queueing networks and SANs can be applied to diverse topical systems of practical interest such as peer-to-peer (P2P) file sharing networks, security protocols,electronic voting systems, parallel programming environments and RAID arrays.\r\n\r\nIt takes a great deal of effort and imagination to tackle the problems inherent in complex systems. We would like to thank everyone who submitted a paper - accepted or not - for taking on this challenge and for helping to contribute to a vibrant workshop.\r\n\r\nWe would also like to thank our invited speaker, Joost-Pieter Katoen, not to mention the programme committee who put in a stalwart effort to ensure a high quality refereeing process (with every submission receiving at least four reviews):\r\n\r\n * Marco Bernardo\r\n * Mario Bravetti\r\n * Gianfranco Ciardo\r\n * Tod Courtney\r\n * David Daly\r\n * Dan Deavours\r\n * Tony Field\r\n * Stephen Gilmore\r\n * Roberto Gorrieri\r\n * Boudewijn Haverkort\r\n * Graham Horton\r\n * Pieter Kritzinger\r\n * Gethin Norman\r\n * Mohamed Ould-Khaoua\r\n * Dave Parker\r\n * Nigel Thomas

Conference paper

Dingle N, Harrison P, Knottenbelt W, 2004, Uniformization and Hypergraph Partitioning for the Distributed Computation of Response Time Densities in Very Large Markov Models, Journal of Parallel and Distributed Computing, Vol: 64, Pages: 908-920

Journal article

Dingle N, Harrison P, Knottenbelt W, 2004, Uniformization and Hypergraph Partitioning for the Distributed Computation of Response Time Densities in Very Large Markov Models, Journal of Parallel and Distributed Computing, Vol: 64, Pages: 908-920

Journal article

Bradley JT, Dingle NJ, Knottenbelt WJ, Wilson HJet al., 2004, Hypergraph-based Parallel Computation of Passage Time Densities in Large Semi-Markov Models, Linear Algebra and Its Applications, Vol: 386, Pages: 311-334

Passage time densities and quantiles are important performance and quality of service metrics, but their numerical derivation is, in general, computationally expensive. We present an iterative algorithm for the calculation of passage time densities in semi-Markov models, along with a theoretical analysis and empirical measurement of its convergence behaviour. In order to implement the algorithm efficiently in parallel, we use hypergraph partitioning to minimise communication between processors and to balance workloads. This enables the analysis of models with very large state spaces which could not be held within the memory of a single machine. We produce passage time densities and quantiles for very large semi-Markov models with over 15 million states and validate the results against simulation.

Journal article

Trifunovic A, Knottenbelt WJ, 2004, A parallel algorithm for multilevel k-way hypergraph partitioning, 3rd International Symposium on Parallel and Distributed Computing (ISPDC 2004), Publisher: IEEE Computer Soc, Pages: 114-121

Conference paper

Trifunovic A, Knottenbelt WJ, 2004, Towards a parallel disk-based algorithm for multilevel k-way hypergraph partitioning, Proceedings of 18th international parallel and distributed processing symposium (IPDPS'04), 2004, Pages: 236-242

Conference paper

Thomas N, Bradley JT, Knottenbelt WJ, 2004, Semi-blind scheduling in a finite capacity system, Proceedings of 20th UK performance engineering workshop (UKPEW 2004), Bradford, UK, July 2004, Pages: 38-47

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=5&respub-action=search.html