Publications
254 results found
Harrison PG, 2009, Product-forms and functional rates, PERFORMANCE EVALUATION, Vol: 66, Pages: 660-663, ISSN: 0166-5316
- Author Web Link
- Cite
- Citations: 9
Harrison PG, Llado CM, Puigjaner R, 2009, A unified approach to modelling the performance of concurrent systems, SIMULATION MODELLING PRACTICE AND THEORY, Vol: 17, Pages: 1445-1456, ISSN: 1569-190X
- Author Web Link
- Cite
- Citations: 4
Harrison P, Zertal S, 2009, Bus Modelling in Zoned Disks RAID Storage Systems, Electronic Notes in Theoretical Computer Science, Vol: 232, Pages: 5-16, ISSN: 1571-0661
Harrison PG, Vigliotti MG, 2009, Response time distributions and network perturbation into product-form
Two new methodological results are obtained: first, a way to perturb a network into one with a product-form solution for its equilibrium state probabilities, and secondly, a new compositional approach to deriving corresponding response time distributions. The Reversed Compound Agent Theo- rem (RCAT) is used to construct suitable perturbations in near-product-form networks that render them separable by satisfying the conditions of this theorem. Response time calculations in stochastic networks are usually developed in terms of sample path analyses beginning in an equilibrium state. We consider the joint probability distribution of the sojourn times of a tagged task at each node of a path in a network and observe that this is the same in both the forward and reversed processes. Therefore if the reversed process is known, each node-sojourn time can be taken from either process. In particular, the reversed process can be used for the first node in a path and the forward process for the other nodes in a recursive analysis. This approach derives, quickly and systematically, existing results for re- sponse time probability densities in tandem, open and closed tree-like, and overtake-free Markovian networks of queues. An example shows that the technique is far more widely applicable, constructing a perturbed network with product- form, a new result in its own right, and then finding a very simple expression for its response time probability density function. Copyright © 2009 ICST.
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.
Thornley DJ, Zatschler H, Harrison PG, 2009, Automated Formulation and Solution of Markov Modulated Queues with Geometric Processes, TRAFFIC AND PERFORMANCE ENGINEERING FOR HETEROGENEOUS NETWORKS, Editors: Kouvatsos, Publisher: RIVER PUBLISHERS, Pages: 419-457
Zertal S, Harrison PG, 2009, Investigating Flash memory wear levelling and execution modes, International Symposium on Performance Evaluation Computer and Telecommunication Systems, Publisher: SOC MODELING SIMULATION INT-SCS, Pages: 81-+, ISSN: 0735-9276
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
Harrison PG, Patel NM, Zertal S, 2008, Response time distribution of flash memory accesses
Flash memory is becoming an increasingly important stor- Age component among non-volatile storage devices. Its cost is decreasing dramatically, which makes it a serious competi- Tor of disks and a candidate for being the storage device of the future. Consequently, there is an urgent need for models and tools to analyse its behaviour and evaluate its effects on a system's performance. We propose a fluid model with pri- ority to investigate the response time characteristics of Flash memory accesses. This model can represent well the Flash access operations, respecting the erase/write/read relative priorities. © 2008 ICST ISBN.
Gupta V, Harrison PG, 2008, Fluid level in a reservoir with an on-off source, Performance Evaluation Review, Vol: 36, Pages: 128-130, ISSN: 0163-5999
We obtain the Laplace transform of the fluid level probability density function, in terms of the on-period density function, for a fluid queue (or reservoir) with on-off input at equilibrium. We further obtain explicit expressions for the moments of fluid level in terms of the moments of the on-period and hence derive an algorithm for the moments of fluid level at every queue in a tandem network. It turns out that to calculate the kth moment at the ith queue, only the first k + 1 moments of the on-period of the input process to the first queue are required.
Field T, Harrison P, 2007, Approximate Analysis of a Network of Fluid Queues, Workshop on Mathematical performance Modeling and Analysis (MAMA), June 2007, Publisher: ACM
Fluid models have for some time been used to approximate stochastic networks with discrete state. These range from traditional æheavy trafficÆ approximations to the recent advances in bio-chemical system models. Here we use an approximate compositional method to analyse a simple feedforward network of fluid queues which comprises both probabilistic branching and superposition. This extends our earlier work that showed the approximation to yield excellent results for a linear chain of fluid queues. The results are compared with those from a simulation model of the same system. The compositional approach is shown to yield good approximations, \r\ndeteriorating for nodes with high load when there is correlation between their immediate inputs. This correlation arises when a common set of external sources feeds more than one queue, directly or indirectly.
Harrison P, Field T, 2007, An Approximate Compositional Approach to the Analysis of Fluid Queue Networks, To appear, IFIP WG 7.3 International Symposium on Computer Performance, Modeling, Measurements, and Evaluation, Publisher: Elsevier, Pages: 1137-1152, ISSN: 0166-5316
Fluid models have for some time been used to approximate stochastic networks with discrete state. These range from traditional `heavy traffic' approximations to the recent advances in bio-chemical system models. Here we present a simple approximate compositional method for analysing a network of fluid queues with Markov-modulated input processes at equilibrium. The idea is to approximate the on/off process at the output of a queue by an $n$-state Markov chain that modulates its rate. This chain is parameterised by matching the moments of the resulting process with those of the busy period distribution of the queue. This process is then used, in turn, as a separate Markov-modulated on/off process that feeds downstream queue(s). The moments of the busy period are derived from an exact analytical model. Approximation using two- and three-state intermediate Markov processes are validated with respect to an exact model of a tandem pair of fluid queues --- a generalisation of the single queue model. The analytical models used are rather simpler and more accessible, albeit less general, than previously published models, and are also included. The approximation method is applied to various fluid queue networks and the results are validated with respect to simulation. The results show the three-state model to yield excellent approximations for mean fluid levels, even under high load.\r\n
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.
Zertal S, Harrison P, 2007, Queueing models of RAID systems with maxima of waiting times, Performance Evaluation, Vol: 64, Pages: 664-689
A queueing model is developed that approximates the effect of synchronizations at parallel service completion instants. Exact results are first obtained for the maxima of independent exponential random variables with arbitrary parameters, and this is followed by a corresponding approximation for general random variables, which reduces to the exact result in the exponential case. This approximation is then used in a queueing model of RAID (Redundant Array of Independent Disks) systems, in which accesses to multiple disks occur concurrently and complete only when every disk involved has completed. We consider the two most common RAID variants, RAID0-1 and RAID5, as well as a multi-RAID system in which they coexist. This can be used to model adaptive multi-level RAID systems in which the RAID level appropriate to an application is selected dynamically. The random variables whose maximum has to be computed in these applications are disk response times, which are modelled by the waiting times in M / G / 1 queues. To compute the mean value of their maximum requires the second moment of queueing time and we obtain this in terms of the third moment of disk service time, itself a function of seek time, rotational latency and block transfer time. Sub-models for these quantities are investigated and calibrated individually in detail. Validation against a hardware simulator shows good agreement at all traffic intensity levels, including the threshold for practical operation above which performance deteriorates sharply.
Harrison P, Zertal S, 2007, Multi-RAID Queueing Model with Zoned Disks \r\n, 2007 High Performance Computing & Simulation Conference (HPCS 2007) June 4 - 6, 2007 Prague, Czech Republic
Gulpinar N, Harder U, Harrison P, et al., 2007, Mean-variance performance optimization of response time in a tandem router network with batch arrivals, Publisher: Springer Verlag, Pages: 203-216, ISSN: 1386-7857
The end-to-end performance of a simple wireless router network with batch arrivals is optimized in an M/G/1 queue-based, analytical model. The optimization minimizes both the mean and variance of the transmission delay (or æresponse timeÆ), subject to an upper limit on the rate of losses and finite capacity queueing and recovery buffers. Losses may be due to either full buffers or corrupted data. The queueing model is also extended to higher order moments beyond the mean and variance of the response time. The trade-off between mean and variance of response time is assessed and the optimal ratio of arrival-buffer size to recovery-buffer size is determined, which is a critical quantity, affecting both loss rate and transmission time. Graphs illustrate performance in the near-optimal region of the critical parameters. Losses at a full buffer are inferred by a time-out whereas corrupted data is detected immediately on receipt of a packet at a router, causing a N-ACK to be sent upstream. Recovery buffers hold successfully transmitted packets so that on receiving a N-ACK, the packet, if present, can be retransmitted, avoiding an expensive resend from source. The impact of the retransmission probability is investigated similarly: too high a value leads to congestion and so higher response times, too low and packets are lost forever.
Au-Yeung SWM, Harrison PG, Knottenbelt WJ, 2007, Approximate queueing network analysis of patient treatment times
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. Copyright 2007 ICST.
Van Do T, Chakka R, Harrison PG, 2007, An Integrated Analytical Model for Computation and Comparison of the Throughputs of the UMTS/HSDPA User Equipment Categories, 10th ACM/IEEE International Symposium on Modeling Analysis and Simulation of Wireless and Mobile Systems, Publisher: ASSOC COMPUTING MACHINERY, Pages: 45-51
- Author Web Link
- Cite
- Citations: 8
Zhang Y, Harrison PG, 2007, Performance of a Priority-Weighted Round Robin mechanism for differentiated service networks, 16th International Conference on Computer Communications and Networks, Publisher: IEEE, Pages: 1198-1203, ISSN: 1095-2055
- Author Web Link
- Cite
- Citations: 48
Gulpinar N, Harrison P, Rustem B, 2006, Worst-case Analysis of Router Networks with Rival Queueing Models, 21st Int. Symp. on Computer and Information Sciences, Istanbul, Turkey, Publisher: Springer-Verlag, LNCS
Gulpinar N, Harrison P, Rustem B, 2006, Worst-case Analysis of Router Networks with Rival Queueing Models, 21st Int. Symp. on Computer and Information Sciences, Istanbul, Turkey, Publisher: Springer-Verlag, LNCS
Harrison P, Llado C, 2006, A General Performance Model Interchange Format, Valuetools 2006, Publisher: ACM
Gulpinar N, Harrison P, Rustem B, et al., 2006, Optimization of a Tandem Router Network Using a Fluid Model, 9th ACM/IEEE International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM 2006), Publisher: ACM
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
Harrison P, 2006, Process algebraic non-product-forms, Electronic Notes in Theoretical Computer Science, Vol: 151, Pages: 61-76, ISSN: 1571-0661
A generalization of the Reversed Compound Agent Theorem of Markovian process algebra is derived that yields separable, but non-product-form solutions for collections of interacting processes such as arise in multi-class queueing networks with Processor Sharing servers. It is based on an analysis of the minimal cycles in the state space of a multi-agent cooperation, which can be simply identified. The extended methodology leads to what we believe are new separable solutions and, more generally, the results represent a viable practical application of the theory of Markovian process algebras in stochastic modelling.\r\n
Rustem B, Harrison P, Gulpinar N, et al., 2006, Performance Optimization of a Tandem Router Network Using a Fluid Model, International MultiConference of Engineers and Computer Scientists 2006, (IMECS'06), June 20-22, 2006, Hong Kong
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-+
- Author Web Link
- Cite
- Citations: 13
Vigliotti M, Harrison P, 2006, Stochastic Ambient Calculus, Vol: 164, Pages: 169-186
Mobile Ambients (MA) have acquired a fundamental role in modelling\r\nmobility in systems with mobile code and mobile devices, and in computation over\r\n administrative domains. We present the stochastic version of\r\n Mobile Ambients, called Stochastic Mobile Ambients (Sma), \r\n where we extend\r\nMA with time and probabilities. Inspired by previous models, Pepa and \\Spi,\r\n we enhance the prefix of the capabilities with a rate and the\r\n ambient with a {\\em linear function} that operates on the rates of processes\r\nexecuting inside it.\r\n The linear functions associated with ambients\r\nrepresent the delays that govern particular administrative domains. \r\nWe derive performance measures from the labelled transition semantics as in\r\nstandard models. We also define a strong Markov bisimulation in the style of reduction semantics known as barbed bisimulation. We argue that performance measures are of vital importance in\r\ndesigning any kind of distributed system, and that Sma can be useful in the design\r\n of the complicated mobile systems.
Bradley J, Dingle N, Harder U, et 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.
Harrison P, Lee T, 2005, Separable equilibrium state probabilities via time reversal in Markovian process algebra, Publisher: Elsevier, Pages: 161-182, ISSN: 0304-3975
The Reversed Compound Agent Theorem (RCAT) is a compositional result that uses Markovian process algebra (MPA) to derive the reversed process of certain interactions between two continuous time Markov chains at equilibrium. From this reversed process, together with the given, forward process, the joint state probabilities can be expressed as a product-form, although no general algorithm has previously been given. This paper first generalizes RCAT to multiple (more than two) cooperating agents, which removes the need for multiple applications and inductive proofs in cooperations of an arbitrary number of processes. A new result shows a simple stochastic equivalence between cooperating, synchronised processes and corresponding parallel, asynchronous processes. This greatly simplifies the proof of the new, multi-agent theorem, which includes a statement of the desired product-form solution itself as a product of given state-probabilities in the parallel components. The reversed process and product-form thus derived rely on a solution to certain rate equations and it is shown, for the first time, that a unique solution exists under mild conditions - certainly for queueing networks and G-networks.
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.