242 results found
Harrison P, A semi-product-form for the equilibrium state probabilities in a pair of queues with finite batches, VALUETOOLS 2019, Publisher: ACM
A Markovian network of two queues, with finite size batch Poissonarrivals and departures, is solved approximately, but to arbitraryaccuracy, for its equilibrium state probabilities. Below a pair ofthresholds on the queue lengths, a modification of the SpectralExpansion Method is used to construct a semi-product-form at alllengths of one queue in a finite lattice strip defined by the thresh-old of the other queue. No additional special arrival streams arerequired, for example at empty queues, from which it is alreadyknown that a product-form can be constructed. Hence the firstexact closed form solution for the equilibrium probabilities in anunmodified Markovian queueing network with batches is obtained,the only constraint being finiteness of the batches. The methodis illustrated numerically, first in a tandem network and then in atwo-node network with feedback. Simulation results confirm theprecision of the method, lying almost on top of the those of themodel in plots. Partial batch forwarding and discarding are therebycompared quantitatively.
Harrison P, Patel N, Perez J, et al., Managing response time tails by sharding, ACM transactions on modeling and performance evaluation of computing systems, ISSN: 2376-3647
Matrix analytic methods are developed to compute the probability distribution of response times (i.e. data access times) in distributedstorage systems protected by erasure coding, which is implemented by sharding a data object into N fragments, only K < N of which are required to reconstruct the object. This leads to a partial-fork-join model with a choice of canceling policies for the redundant N − K tasks. The accuracy of the analytical model is supported by tests against simulation in a broad range of setups. At increasing workload intensities, numerical results show the extent to which increasing the redundancy level reduces the mean response time of storage reads and significantly flattens the tail of their distribution; this is demonstrated at medium-high quantiles, up to the 99th. The quantitative reduction in response time achieved by two policies for canceling redundant tasks is also shown: for cancel-at-finish and cancel-at-start, which limits the additional load introduced whilst losing the benefit of selectivity amongst fragment service times.
Harrison PG, 2018, Product-form queueing networks with batches, European Workshop on Performance Engineering, Publisher: Springer, Pages: 250-264, ISSN: 0302-9743
A Markovian queue, with both batch arrivals and batch departures, is first shown to have a geometric queue length probability distribution at equilibrium under certain conditions. From this a product-form solution follows directly for networks of such queues at equilibrium, by application of the reversed compound agent theorem (RCAT). The method is illustrated using small batches of sizes 1 and 2, as well as geometric sizes.
Harrison PG, Patel NM, 2018, Optimizing energy-performance trade-offs in solar-powered edge devices, ACM/SPEC International Conference on Performance Engineering, Publisher: ACM, Pages: 253-260
Power modes can be used to save energy in electronic devices but a low power level typically degrades performance. This trade-off is addressed in the so-called EP-queue model, which is a queue depth dependent M/GI/1 queue augmented with power-down and power-up phases of operation. The ability to change service times by power settings allows us to leverage a Markov Decision Process (MDP), which approach we illustrate using a simple fully solar-powered case study with finite states representing levels of battery charge and solar intensity.
Zamyatin A, Wolter K, Werner S, et al., Swimming with fishes and sharks: beneath the surface of queue-based ethereum mining pools, 25th Annual Meeting of the IEEE International Symposium on Modelling, Analysis and Simulation of Computer and Telecommunication Systems, Publisher: IEEE
Cryptocurrency mining can be said to be the modernalchemy, involving as it does the transmutation of electricityinto digital gold. The goal of mining is to guess the solutionto a cryptographic puzzle, the difficulty of which is determinedby the network, and thence to win the block reward andtransaction fees. Because the return on solo mining has a veryhigh variance, miners band together to create so-called miningpools. These aggregate the power of several individual miners,and, by distributing the accumulated rewards according to somescheme, ensure a more predictable return for participants.In this paper we formulate a model of the dynamics of a queue-based reward distribution scheme in a popular Ethereum miningpool and develop a corresponding simulation. We show that theunderlying mechanism disadvantages miners with above-averagehash rates. We then consider two-miner scenarios and show howlarge miners may perform attacks to increase their profits at theexpense of other participants of the mining pool. The outcomes ofour analysis show the queue-based reward scheme is vulnerableto manipulation in its current implementation.
Qiu Z, Perez JF, Birke R, et al., 2017, Cutting latency tail: analyzing and validating replication without canceling, IEEE Transactions on Parallel and Distributed Systems, ISSN: 1558-2183
Response time variability in software applications can severely degrade the quality of the user experience. To reduce this variability, request replication emerges as an effective solution by spawning multiple copies of each request and using the result of the first one to complete. Most previous studies have mainly focused on the mean latency for systems implementing replica cancellation, i.e., all replicas of a request are canceled once the first one finishes. Instead, we develop models to obtain the response-time distribution for systems where replica cancellation may be too expensive or infeasible to implement, as in “fast” systems, such as web services, or in legacy systems. Furthermore, we introduce a novel service model to explicitly consider correlation in the processing times of the request replicas, and design an efficient algorithm to parameterize the model from real data. Extensive evaluations on a MATLAB benchmark and a three-tier web application (MediaWiki) show remarkable accuracy, e.g., 7% (4%) average error on the 99th percentile response time for the benchmark (respectively, MediaWiki), the requests of which execute in the order of seconds (respectively, milliseconds). Insights into optimal replication levels are thereby gained from this precise quantitative analysis, under a wide variety of system scenarios.
Chis TS, Harrison PG, 2016, Performance-energy trade-offs in smartphones, 19th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems, Pages: 127-135
© 2016 ACM. In the literature, numerous works have modeled user activity on smartphones and the effects on battery life. Power-saving modes prolong battery life by saving energy, but application performance is limited as a result. We investigate performance-energy trade-ofs of smartphone applications by investigating three strategies: first, we propose an M/M/1 discriminatory processor sharing queue to act as a smartphone server and measure delays of Android applications; secondly, we form a performance-energy trade-of that takes into account cellular radio transfers using an objective cost function incorporating mean delay and power consumption; and thirdly, we build an online HMM to act as a power consumption model that predicts battery life given recent data transfers. For all three strategies we obtain logged smartphone activity of over 750 users via an open-source smartphone data-collection application. Hence, we obtain three hypotheses from our strategies: first, delay of applications is approximated well using the beta prime distribution; secondly, power consumption increases as mean delay decreases with battery life prolonged if adjustments are made to cellular radio usage; and thirdly, burstiness is captured by HMMs in both data transfers and rates of power consumption.
Harrison PG, Patel NM, Knottenbelt, 2016, Energy–performance trade-offs via the EP-queue, ACM Transactions on Modeling and Performance Evaluation of Computing Systems, Vol: 1, ISSN: 2376-3647
We introduce the EP queue -- a significant generalization of the MB/G/1 queue that has state-dependent service time probability distributions and incorporates power-up for first arrivals and power-down for idle periods. We derive exact results for the busy-time and response-time distributions. From these, we derive power consumption metrics during nonidle periods and overall response time metrics, which together provide a single measure of the trade-off between energy and performance. We illustrate these trade-offs for some policies and show how numerical results can provide insights into system behavior. The EP queue has application to storage systems, especially hard disks, and other data-center components such as compute servers, networking, and even hyperconverged infrastructure.
Harrison PG, Qiu Z, Perez JF, 2016, Variability-aware request replication for latency curtailment, 35th Annual IEEE International Conference on Computer Communications (IEEE INFOCOM 2016), Publisher: IEEE, Pages: 1-9
Processing time variability is commonplace in distributed systems, where resources display disparate performance due to, e.g., different workload levels, background processes, and contention in virtualized environments. However, it is paramount for service providers to keep variability in response time under control in order to offer responsive services. We investigate how request replication can be used to exploit processing time variability to reduce response times, considering not only mean values but also the tail of the response time distribution. We focus on the distributed setup, where replication is achieved by running copies of requests on multiple servers that otherwise evolve independently, and waiting for the first replica to complete service. We construct models that capture the evolution of a system with replicated requests using approximate methods and observe that highly variable service times offer the best opportunities for replication ¿¿¿ reducing the response time tail in particular. Further, the effect of replication is non-uniform over the response time distribution: gains in one metric, e.g., the mean, can be at the cost of another, e.g., the tail percentiles. This is demonstrated in wide range of numerical virtual experiments. It can be seen that capturing service time variability is key to the evaluation of latency tolerance strategies and in their design.
Harrison PG, Qiu Z, Perez JF, 2016, Tackling Latency via Replication in Distributed Systems, ACM/SPEC International Conference on Performance Engineering (ICPE), Publisher: ACM, Pages: 197-208
Consistently high reliability and low latency are twin requirementscommon to many forms of distributed processing;for example, server farms and mirrored storage access.To address them, we consider replication of requests withcanceling – i.e. initiate multiple concurrent replicas of a requestand use the first successful result returned, cancelingall outstanding replicas. This scheme has been studied recently,but mostly for systems with a single central queue,while server farms exploit distributed resources for scalabilityand robustness. We develop an approximate stochasticmodel to determine the response-time distribution in a systemwith distributed queues, and compare its performanceagainst its centralized counterpart. Validation against simulationindicates that our model is accurate for not only themean response time but also its percentiles, which are particularlyrelevant for deadline-driven applications. Further,we show that in the distributed set-up, replication with cancelinghas the potential to reduce response times, even atrelatively high utilization. We also find that it offers responsetimes close to those of the centralized system, especiallyat medium-to-high request reliability. These findingssupport the use of replication with canceling as an effectivemechanism for both fault- and delay-tolerance.
Harrison PG, Chis T, 2016, Higher response time moments for M/M/1 discriminatory processor sharing queues, 9th EAI International Conference on Performance Evaluation Methodologies and Tools, Publisher: ACM, Pages: 145-148
Obtaining response time moments in processor sharing (PS) queues is difficult due to serving of multiple jobs. Egalitarian PS (EPS) queues are limited to one class of arriving jobs. Discriminatory PS (DPS) assigns weights to different job classes and offers more diverse modeling capabilities than EPS. It is known that response time is the representative metric for delay as specified in service level agreements (SLAs), which consider higher moments important. Hence, we build an automated numerical algorithm for calculating higher moments of response time in M/M/1-DPS queues for multiple job classes and test two different case studies.
Harrison PG, Chis, 2015, Adapting Hidden Markov Models for Online Learning, Electronic Notes in Theoretical Computer Science, Vol: 318, Pages: 109-127, ISSN: 1571-0661
In modern computer systems, the intermittent behaviour of infrequent, additional loads affects performance. Often, representative traces of storage disks or remote servers can be scarce and obtaining real data is sometimes expensive. Therefore, stochastic models, through simulation and profiling, provide cheaper, effective solutions, where input model parameters are obtained. A typical example is the Markov-modulated Poisson process (MMPP), which can have its time index discretised to form a hidden Markov model (HMM). These models have been successful in capturing bursty behaviour and cyclic patterns of I/O operations and Internet traffic, using underlying properties of the discrete (or continuous) Markov chain. However, learning on such models can be cumbersome in terms of complexity through re-training on data sets. Thus, we provide an online learning HMM (OnlineHMM), which is composed of two existing variations of HMMs: first, a sliding HMM using a moving average technique to update its parameters “on-the-fly” and, secondly, a multi-input HMM capable of training on multiple discrete traces simultaneously. The OnlineHMM reduces data processing times significantly and thence synthetic workloads become computationally more cost effective. We measure the accuracy of reproducing representative traces through comparisons of moments and autocorrelation on original data points and HMM-generated synthetic traces. We present, analytically, the training steps saved through the OnlineHMM's adapted Baum-Welch algorithm and obtain, through simulation, mean waiting times of a queueing model. Finally, we conclude our work and offer model extensions for the future.
Osman R, Harrison P, 2015, Approximating closed fork-join queueing networks using product-form stochastic Petri-nets, Journal of Systems and Software, Vol: 110, Pages: 264-278, ISSN: 0164-1212
Computing paradigms have shifted towards highly parallel processing and massive replication of data. This entails the efficient distribution of requests and the synchronization of results provided to users. Guaranteeing SLAs requires the ability to evaluate the performance of such systems while taking the effect of non-parallel workloads into consideration. This can be achieved with performance models that are able to represent both parallel and sequential workloads. This paper presents a product-form stochastic Petri-net approximation of fork-join queueing networks with interfering requests. We derive the necessary conditions that guarantee the accuracy of the approximations and verify this through examples in comparison to simulation. We apply these approximate models to the performance evaluation of replication in NoSQL cloud datastores and illustrate the composition of large models from smaller models, thus facilitating the ability to model a range of deployment scenarios. We show the efficiency of our solution method, which finds the product-form solution of the models without the representation of the state-space of the underlying CTMC.
Harrison PG, Chis T, 2015, Moment-Generating Algorithm for Response Time in Processor Sharing Queueing Systems, European Performance Engineering Workshop 2015, Publisher: Springer, Pages: 80-95, ISSN: 0302-9743
Response times are arguably the most representative and important metric for measuring the performance of modern computer systems. Further, service level agreements (SLAs), ranging from data centres to smartphone users, demand quick and, equally important, predictable response times. Hence, it is necessary to calculate moments, at least, and ideally response time distributions, which is not straightforward. A new moment-generating algorithm for calculating response times analytically is obtained, based on M/M/1 processor sharing (PS) queueing models. This algorithm is compared against existing work on response times in M/M/1-PS queues and extended to M/M/1 discriminatory PS queues. Two real-world case studies are evaluated.
Qiu Z, Perez Bernal J, Harrison PG, 2015, Beyond the Mean in Fork-Join Queues: Efficient Approximation for Response-Time Tails, Performance Evaluation, Vol: 91, Pages: 99-116, ISSN: 0166-5316
Fork-join queues are natural models for various computer and communications systems that involve parallel multitasking and the splitting and resynchronizing of data, such as parallel computing, query processing in distributed databases, and parallel disk access. Job response time in a fork-join queue is a critical performance indicator but its exact analysis is challenging. We introduce a stochastic model for K-node homogeneous fork-join queues (K≥2) that focuses on the difference in length between any node-queue and the shortest one, truncating the state space such that the maximum difference is at most a constant C. Whilst most previous methods focus on the mean response time, our model is also able to evaluate the response time distribution , as well as accommodating phase-type processing times and Markovian arrival processes. In order to tackle scenarios with high loads, which require a large value of C to provide sufficient accuracy, we develop an efficient algorithm using matrix-analytic methods. Tests against simulation show that the proposed model yields accurate results for 2-node fork-join queues. As the model becomes numerically intractable for large values of K, we further propose an approximate approach, based on properties of order statistics and extreme values. The approximation gives a high degree of accuracy on response time tails, and has the advantage of being efficient and scalable, requiring only the analytical results for a single-node and 2-node fork-join queues, which we obtain with the aforementioned matrix-analytic model. Comparison with simulation results shows that our approximation yields good fits for the tails, even in very large cases with general processing and inter-arrival times.
Casale G, Tribastone M, Harrison PG, 2014, Blending randomness in closed queueing network models, PERFORMANCE EVALUATION, Vol: 82, Pages: 15-38, ISSN: 0166-5316
Chis T, Harrison PG, 2014, Modeling multi-user behaviour in social networks, IEEE 22nd International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, Publisher: IEEE, Pages: 168-173, ISSN: 1526-7539
Social networks, and the behaviour of groups of online users, are popular topics in modeling and classifying Internet traffic data. There is a need to analyze online network performance metrics through suitable workload benchmarks. We address this issue with a Multi-dimensional Hidden Markov Model (MultiHMM) to act as a Multi-User workload classifier. The MultiHMM is an adaptation of the original HMM, using clustering methods and multiple trace-training for the Baum-Welch algorithm. The goals of the MultiHMM are to classify multiple online user streams with minimal processing needs, represent burstiness and correlation among groups of users and to improve security measures in the social network. Experiments are carried out using multiple traces from Twitter data, where original traces are analysed and compared with the MultiHMM-generated traces. The metrics involved in validating our model include means, standard deviations, skew ness and autocorrelation, and we discuss applications and extensions of our model.
Tsimashenka I, Knottenbelt WJ, Harrison PG, 2014, Controlling variability in split-merge systems and its impact on performance, Annals of Operations Research, Vol: 239, Pages: 569-588, ISSN: 1572-9338
We consider split–merge systems with heterogeneous subtask service times and limited output buffer space in which to hold completed but as yet unmerged subtasks. An important practical problem in such systems is to limit utilisation of the output buffer. This can be achieved by judiciously delaying the processing of subtasks in order to cluster subtask completion times. In this paper we present a methodology to find those deterministic subtask processing delays which minimise any given percentile of the difference in times of appearance of the first and the last subtasks in the output buffer. Technically this is achieved in three main steps: firstly, we define an expression for the distribution of the range of samples drawn from nn independent heterogeneous service time distributions. This is a generalisation of the well-known order statistic result for the distribution of the range of nn samples taken from the same distribution. Secondly, we extend our model to incorporate deterministic delays applied to the processing of subtasks. Finally, we present an optimisation scheme to find that vector of delays which minimises a given percentile of the range of arrival times of subtasks in the output buffer. We show the impact of applying the optimal delays on system stability and task response time. Two case studies illustrate the applicability of our approach.
Chen X, Ho CP, Osman R, et al., 2014, Understanding, modeling and improving the performance of web applications in multi-core virtualized environments, International Conference on Performance Engineering, ICPE 2014
Harrison PG, Hayden RA, Knottenbelt WJ, 2013, Product-forms in batch networks: Approximation and asymptotics, PERFORMANCE EVALUATION, Vol: 70, Pages: 822-840, ISSN: 0166-5316
Harrison PG, Marin A, 2013, Product-Forms in Multi-Way Synchronizations, Computer Journal, Vol: 57, Pages: 1693-1710, ISSN: 1460-2067
A new algorithm is given to find product-form solutions for the joint equilibrium probabilities in a class of synchronized Markov processes. This is based on, and proved by, multiple applications of the Reversed Compound Agent Theorem (RCAT) and can describe multi-way synchronizations (seen as chains of pairwise synchronizations) that occur in a prescribed order. The length of the sequence is unbounded but finite with probability 1. Several applications are given to illustrate the methodology, which include various modes of resets in queueing networks with negative customers. In particular, it is shown that there is a type of reset that can propagate further transitions in a chain actively. Furthermore, a number of completely new product-form models, for example, where the transitions in a chain are non-homogeneous, are given.
Chis T, Harrison PG, 2013, iSWoM: The incremental Storage Workload Model based on Hidden Markov Models, 20th International Conference on Analytical and Stochastic Modelling Techniques and Applications (ASMTA 2013), Publisher: Springer, Pages: 127-141
Chis T, Harrison PG, 2013, Analysing and Predicting Patient Arrival Times, 28th International Symposium on Computer and Information Sciences (ISCIS), Publisher: SPRINGER, Pages: 77-85, ISSN: 1876-1100
Qiu Z, Harrison PG, 2013, A Model of Speculative Parallel Scheduling in Networks of Unreliable Sensors, 28th International Symposium on Computer and Information Sciences (ISCIS), Publisher: SPRINGER, Pages: 107-116, ISSN: 1876-1100
Harrison PG, Qiu Z, 2013, Performance enhancement by means of task replication, 10th European Performance Engineering Workshop (EPEW2013), Pages: 191-205
Casale G, Harrison PG, 2013, AutoCAT: Automated Product-Form Solution of Stochastic Models, Matrix-Analytic Methods in Stochastic Models, Editors: Latouche, Ramaswami, Sethuraman, Sigman, Squillante, Yao, ISBN: 978-1-4614-4908-9
Harrison PG, 2013, Sojourn time distributions in tandem batch-networks, Pages: 37-39
Harrison PG, Thomas N, 2013, Semi-Product-Form Solution for PEPA Models with Functional Rates, 20th International Conference on Analytical and Stochastic Modelling Techniques and Applications (ASMTA 2013), Publisher: Springer, Pages: 416-430
Chis TS, Harrison PG, 2012, Incremental HMM with an improved baum-welch algorithm, Pages: 29-34
There is an increasing demand for systems which handle higher density, additional loads as seen in storage workload modelling, where workloads can be characterized on-line. This paper aims to find a workload model which processes incoming data and then updates its parameters "on-the-fly." Essentially, this will be an incremental hidden Markov model (IncHMM) with an improved Baum-Welch algorithm. Thus, the benefit will be obtaining a parsimonious model which updates its encoded information whenever more real time workload data becomes available. To achieve this model, two new approximations of the Baum-Welch algorithm are defined, followed by training our model using discrete time series. This time series is transformed from a large network trace made up of I/O commands, into a partitioned binned trace, and then filtered through a K-means clustering algorithm to obtain an observation trace. The IncHMM, together with the observation trace, produces the required parameters to form a discrete Markov arrival process (MAP). Finally, we generate our own data trace (using the IncHMM parameters and a random distribution) and statistically compare it to the raw I/O trace, thus validating our model. © Tiberiu S. Chis and Peter G. Harrison.
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.