Skip to main content
main-content

Über dieses Buch

This book constitutes the proceedings of the 11th European Workshop on Performance Engineering, EPEW 2014, held in Florence, Italy, in September 2014. The 18 full papers presented in this volume were carefully reviewed and selected from 30 submissions. The papers are organized in topical sections named: cloud performance modelling; queueing and fluid models; performance of computation and programming; fitting; urban traffic modelling; decision making; and Markovian models, above and beyond.

Inhaltsverzeichnis

Frontmatter

Cloud Performance Modelling

Optimal Hiring of Cloud Servers

Abstract
A host uses servers hired from a Cloud in order to offer certain services to paying customers. It must decide dynamically when and how many servers to hire, and when to release them, so as to minimize both the job holding costs and the server costs. Under certain assumptions, the problem can be formulated in terms of a semi-Markov decision process and the optimal hiring policy can be computed. Two situations are considered: (a) jobs are submitted in random batches and servers can be hired for arbitrary periods of time; (b) jobs arrive singly and servers must be hired for fixed periods of time. In both cases, the optimal policies are compared with some simple and easily implementable heuristics.
Andrew Stephen McGough, Isi Mitrani

Performance Evaluation of NoSQL Databases

Abstract
NoSQL databases have emerged as a backend to support Big Data applications. NoSQL databases are characterized by horizontal scalability, schema-free data models, and easy cloud deployment. To avoid overprovisioning, it is essential to be able to identify the correct number of nodes required for a specific system before deployment. This paper benchmarks and compares three of the most common NoSQL databases: Cassandra, MongoDB and HBase. We deploy them on the Amazon EC2 cloud platform using different types of virtual machines and cluster sizes to study the effect of different configurations. We then compare the behavior of these systems to high-level queueing network models. Our results show that the models are able to capture the main performance characteristics of the studied databases and form the basis for a capacity planning tool for service providers and service users.
Andrea Gandini, Marco Gribaudo, William J. Knottenbelt, Rasha Osman, Pietro Piazzolla

Queueing and Fluid Models

A Systematic Approach for Composing General Middleware Completions to Performance Models

Abstract
A software design often does not describe the software infrastructure it will need to run, but a performance analysis must account for its effects. “Performance completions” represent the infrastructure and must be incorporated in the application performance model. This paper considers completions for middleware. It proposes a unified framework for describing all kinds of middleware in the Layered Queuing Network (LQN) model, based on a generic template and elaborations for middleware features. The template is applied to several common request-reply middleware systems. A process is given for building a new middleware completion model and for incorporating it into a LQN model.
Adnan Faisal, Dorina Petriu, Murray Woodside

Vacation and Polling Models with Retrials

Abstract
We study a vacation-type queueing model, and a single-server multi-queue polling model, with the special feature of retrials. Just before the server arrives at a station there is some deterministic glue period. Customers (both new arrivals and retrials) arriving at the station during this glue period will be served during the visit of the server. Customers arriving in any other period leave immediately and will retry after an exponentially distributed time. Our main focus is on queue length analysis, both at embedded time points (beginnings of glue periods, visit periods and switch- or vacation periods) and at arbitrary time points.
Onno Boxma, Jacques Resing

Fluid Vacation Model with Markov Modulated Load and Exhaustive Discipline

Abstract
In this paper we analyze a fluid vacation model with exhaustive discipline, in which the fluid source is modulated by a background continuous-time Markov chain and the fluid is removed by constant rate during the service period. Due to the continuous nature of the fluid the state space of the model becomes continuous, which is the major novelty and challenge of the analysis. We adapt the descendant set approach used in polling models to the fluid vacation model. We provide steady-state vector Laplace Transform and mean of the fluid level at arbitrary epoch.
Zsolt Saffer, Miklós Telek

Performance of Computation and Programming

Use of a Levy Distribution for Modeling Best Case Execution Time Variation

Abstract
Minor variations in execution time can lead to out-sized effects on the behavior of an application as a whole. There are many sources of such variation within modern multi-core computer systems. For an otherwise deterministic application, we would expect the execution time variation to be non-existent (effectively zero). Unfortunately, this expectation is in error. For instance, variance in the realized execution time tends to increase as the number of processes per compute core increases. Recognizing that characterizing the exact variation or the maximal variation might be a futile task, we take a different approach, focusing instead on the best case variation. We propose a modified (truncated) Levy distribution to characterize this variation. Using empirical sampling we also derive a model to parametrize this distribution that doesn’t require expensive distribution fitting, relying only on known parameters of the system. The distributional assumptions and parametrization model are evaluated on multi-core systems with the common Linux completely fair scheduler.
Jonathan C. Beard, Roger D. Chamberlain

On the Predictive Properties of Performance Models Derived through Input-Output Relationships

Abstract
Building an analytical performance model is a challenge when little is known about the functionality and behavior of the system being modeled and/or when obtaining model parameters through measurements is difficult. This paper addresses this problem by presenting an approach that derives analytic model parameters by observing the input-output relationships of a real system. More specifically, input (i.e., arrival rates for each job class) and output (i.e., average response time for each job class) measurements are used to estimate the per-class service demands and number of servers for a Queuing Network model of the system. This model, called the computed model (CM), provides the same output values for the same input values used to derive the CM. The important question is whether the CM has predictive power, i.e., can the CM predict the output values that would be observed in the real system for different values of the input? The CM’s parameters are obtained by solving a non-linear optimization problem. The paper shows through experiments that the CM is relatively robust and has predictive power over a range of input values.
Mahmoud Awad, Daniel A. Menascé

Deriving Work Plans for Solving Performance and Scalability Problems

Abstract
The performance of an enterprise application (e.g. response time, throughput, or resource utilization) is an important quality attribute that can have a significant impact on a company’s success. When a performance problem such as a performance bottleneck has been detected, the root cause identified and a solution proposed, developers have to identify the elements of the application often manually that will undergo changes and determine how these elements must be changed in order to implement the solution. Many existing approaches are able to identify the elements that have to be modified but only few are able to determine the necessary types of changes on these elements. Neither of the approaches supports developers with a work plan sketching the implementation steps. In this paper, we propose an approach to point developers the way torwards an implementation of a performance or scalability solution with an ordered set of work activities. Rules are used to derive a work plan sketching the implementation of a solution for the particular application based on an initial set of work activities. The rule-based approach identifies impacted elements and determines how they should be changed. We demonstrate the proposed approach with a solution of a performance bottleneck as an example.
Christoph Heger, Robert Heinrich

Fitting

Dealing with Zero Density Using Piecewise Phase-Type Approximation

Abstract
Every probability distribution can be approximated up to a given precision by a phase-type distribution, i.e. a distribution encoded by a continuous time Markov chain (CTMC). However, an excessive number of states in the corresponding CTMC is needed for some standard distributions, in particular most distributions with regions of zero density such as uniform or shifted distributions. Addressing this class of distributions, we suggest an alternative representation by CTMC extended with discrete-time transitions. Using discrete-time transitions we split the density function into multiple intervals. Within each interval, we then approximate the density with standard phase-type fitting. We provide an experimental evidence that our method requires only a moderate number of states to approximate such distributions with regions of zero density. Furthermore, the usage of CTMC with discrete-time transitions is supported by a number of techniques for their analysis. Thus, our results promise an efficient approach to the transient analysis of a class of non-Markovian models.
L’uboš Korenčiak, Jan Krčál, Vojtěch Řehák

Uncertainty in On-The-Fly Epidemic Fitting

Abstract
The modern world features a plethora of social, technological and biological epidemic phenomena. These epidemics now spread at unprecedented rates thanks to advances in industrialisation, transport and telecommunications. Effective real-time decision making and management of modern epidemic outbreaks depends on the two factors: the ability to determine epidemic parameters as the epidemic unfolds, and the ability to characterise rigorously the uncertainties inherent in these parameters. This paper presents a generic maximum-likelihoodbased methodology for online epidemic fitting of SIR models from a single trace which yields confidence intervals on parameter values. The method is fully automated and avoids the laborious manual efforts traditionally deployed in the modelling of biological epidemics. We present case studies based on both synthetic and real data.
Roxana Danila, Marily Nika, Thomas Wilding, William J. Knottenbelt

Urban Traffic Modelling

Performance Modeling of Intelligent Car Parking Systems

Abstract
The performance analysis of the car parking process in a parking lot with various levels of assistance is considered in the paper. The input of the model is the description of the parking lot and a Markovian description for the driver behavior, the set of computable performance measures contains the average time necessary for the user to reach the desired destination, the amount of cars moving in the parking lot at the same time (thus, the environmental strain), etc. To overcome the state space expansion, that makes the direct analysis of the model computationally infeasible, we apply a mean field limit based approximation whose accuracy is investigated with discrete event simulation.
Károly Farkas, Gábor Horváth, András Mészáros, Miklós Telek

Formal Punctuality Analysis of Frequent Bus Services Using Headway Data

Abstract
We evaluate the performance of frequent bus services in Edinburgh using the punctuality metrics identified by the Scottish Government. We describe a methodology for evaluating each of these metrics that only requires measurements of bus ‘headways’ — the time between subsequent bus arrivals. Our methodology includes Monte Carlo simulation and time series analysis. Since one metric is given in ambiguous language, we provide a formal description of the two most plausible interpretations. The automated nature of our method allows public transport operators to continuously assess whether the performance of their network meets the targets set by government regulators. We carry out a case study using Automatic Vehicle Location (AVL) data involving two frequent services, including the AirLink service to and from Edinburgh airport.
Daniël Reijsbergen, Stephen Gilmore

Decision Making

Markov Decision Process and Linear Programming Based Control of MAP/MAP/N Queues

Abstract
We investigate the control problem of the optimal choice of idle server (if any) for arriving customer in order to minimize the mean system time (waiting time + service time). The considered MAP/MAP/N queue consists of a common infinite buffer and multiple identical servers with MAP service processes whose phases (internal states) are known. Customers arrive according to a MAP (whose phase is also known) and are served with work conserving policy. Idle servers preserve their phases.
We transform the obtained infinite state optimization problem to a finite state one and apply two optimization procedures, policy iteration of finite state MDP and linear programming.
András Mészáros, Miklós Telek

A Decision Making Model of Influencing Behavior in Information Security

Abstract
Information security decisions typically involve a trade-off between security and productivity. In practical settings, it is often the human user who is best positioned to make this trade-off decision, or in fact has a right to make its own decision (such as in the case of ‘bring your own device’), although it may be responsibility of a company security manager to influence employees choices. One of the practical ways to model human decision making is with multi-criteria decision analysis, which we use here for modeling security choices. The proposed decision making model facilitates quantitative analysis of influencing information security behavior by capturing the criteria affecting the choice and their importance to the decision maker.Within this model, we will characterize the optimal modification of the criteria values, taking into account that not all criteria can be changed. We show how subtle defaults influence the choice of the decision maker and calculate their impact. We apply our model to derive optimal policies for the case study of a public Wi-Fi network selection, in which the graphical user interface aims to influence the user to a particular security behavior.
Iryna Yevseyeva, Charles Morisset, Thomas Groß, Aad van Moorsel

Automated Capacity Planning for PEPA Models

Abstract
Capacity planning is concerned with the provisioning of systems in order to ensure that they meet the demand or performance requirements of users. Currently for PEPA models, a modeller who wishes to solve a capacity planning problem has to either carry out a manual search for an optimal configuration or work outside the provided tool suite. We present a new extension to the Eclipse Plug-in for PEPA which integrates automated capacity planning into the functionality of the tool, thus allowing optimal configurations of large scale PEPA models to be found.
Christopher D. Williams, Jane Hillston

Markovian Models, Above and Beyond

Stochastic Approximation of Global Reachability Probabilities of Markov Population Models

Abstract
Complex computer systems, from peer-to-peer networks to the spreading of computer virus epidemics, can often be described as Markovian models of large populations of interacting agents. Many properties of such systems can be rephrased as the computation of time bounded reachability probabilities. However, large population models suffer severely from state space explosion, hence a direct computation of these probabilities is often unfeasible. In this paper we present some results in estimating these probabilities using ideas borrowed from Fluid and Central Limit approximations. We consider also an empirical improvement of the basic method leveraging higher order stochastic approximations. Results are illustrated on a peer-to-peer example.
Luca Bortolussi, Roberta Lanciani

Explicit State Space and Markov Chain Generation Using Decision Diagrams

Abstract
Various forms of decision diagrams have been successfully used for quite some time to generate the state space and Markov chain from models expressed in some high-level formalism. A variety of efficient, “symbolic” algorithms, which manipulate sets of states instead of individual states, are known for this purpose. However, there are cases where explicit generation algorithms are still used. This paper seeks to efficiently use decision diagrams as replacement data structures within an existing explicit generation implementation. The necessary decision diagram algorithms are presented, and small changes to the explicit generation algorithm are suggested to improve the overall generation process. The efficiency of the new algorithms is illustrated using several models.
Junaid Babar, Andrew S. Miner

Non-Markovian Modeling of a BladeCenter Chassis Midplane

Abstract
In distributed contexts such as Cloud computing, the reliability and availability of the provided resources and services have to be assured in order to meet user requirements. At the infrastructure level, this specification is translated into tighter ones on the datacenter hosting physical resources. In this paper, starting from a real case study of the IBM BladeCenter, we provide a technique for the quantitative evaluation of datacenter infrastructure availability. The proposed technique allows one to take into account both aging phenomena and multiple operating conditions. In particular, one subsystem of the BladeCenter, the chassis midplane, is studied. Indeed, based on the stochastic characterization of the midplane reliability through statistic measurements, a model dealing with the non-exponential failure time distribution thus obtained is evaluated to demonstrate the suitability and the effectiveness of the proposed technique.
Salvatore Distefano, Francesco Longo, Marco Scarpa, Kishor S. Trivedi

Backmatter

Weitere Informationen