Skip to main content
main-content

Über dieses Buch

This book constitutes the refereed proceedings of the 16th European Workshop on Computer Performance Engineering, EPEW 2019, held in Milan, Italy, in November 2019.

The 10 papers presented in this volume together with one invited talk were carefully reviewed and selected from 13 submissions. The papers presented at the workshop reflect the diversity of modern performance engineering, with topics ranging from modeling and analysis of network/control protocols and high performance/BigData information systems, analysis of scheduling, blockchain technology, analytical modeling and simulation of computer/network systems.

Inhaltsverzeichnis

Frontmatter

Abandonment Attack on the LEACH Protocol

Abstract
Despite their popularity and widespread use, wireless sensor networks are vulnerable to different types of attacks due to their low energy consumption, simplicity and scalability constraints. This paper explores the possible network-layer attacks on WSN routing protocols. In addition, it proposes a comprehensive method for measuring the impact of network-layer attacks on WSNs. Moreover, it introduces a new network-layer attack – called “abandonment attack” – on one such WSN routing protocol, the low-energy adaptive clustering hierarchy protocol. Last, it measures the impact of the abandonment attack on the LEACH protocol. In the end, this paper finds that the abandonment attack increases the collision rate and the end-to-end delay on the LEACH protocol and decreases the network lifetime.
Albatool Alhawas, Nigel Thomas

Coherent Resolutions of Nondeterminism

Abstract
We study the impact that different ways of resolving nondeterminism within probabilistic automata have on the properties of probabilistic behavioral equivalences. Firstly, we provide a uniform definition of structure-preserving and structure-modifying resolutions of nondeterminism, respectively generated by different families of schedulers. Secondly, we exhibit a number of anomalies arising from the excessive power of the various families of schedulers, which affect the discriminating power, the compositionality, and the backward compatibility of probabilistic trace equivalence. Thirdly, we propose to remove those anomalies by enforcing coherency within resolutions of nondeterminism. This ensures that a scheduler cannot select different continuations in equivalent states of an automaton, so that also the states to which they correspond in any resolution of the automaton have equivalent continuations.
Marco Bernardo

Emulating Self-adaptive Stochastic Petri Nets

Abstract
Traditional Petri nets lack specific features to conveniently describe systems with an evolving structure. A model based on the Symmetric Net formalism has been recently introduced. It is composed of an emulator reproducing the behaviour of a Place/Transition net (encoded as a marking) and a basic set of net-transformation primitives to specify evolutionary behaviour. In this paper, we discuss the adoption of the stochastic extension of Symmetric Nets for performance analysis, considering important issues related to time specification and analysis complexity. We put into place theoretical aspects by using a running example consisting in a self-healing manufacturing system.
Lorenzo Capra, Matteo Camilli

Design and Evaluation of an Edge Concurrency Control Protocol for Distributed Graph Databases

Abstract
A new concurrency control protocol for distributed graph databases is described. It avoids the introduction of certain types of inconsistencies by aborting vulnerable transactions. An approximate model that allows the computation of performance measures, including the fraction of aborted transactions, is developed. The accuracy of the approximations is assessed by comparing them with simulations, for a variety of parameter settings.
Paul Ezhilchelvan, Isi Mitrani, Jack Waudby, Jim Webber

A Novel Data-Driven Algorithm for the Automated Detection of Unexpectedly High Traffic Flow in Uncongested Traffic States

Abstract
We present an algorithm to identify days that exhibit the seemingly paradoxical behaviour of high traffic flow and, simultaneously, a striking absence of traffic jams. We introduce the notion of high-performance days to refer to these days. The developed algorithm consists of three steps: step 1, based on the fundamental diagram (i.e. an empirical relation between the traffic flow and traffic density), we estimate the critical speed by using robust regression as a tool for labelling congested and uncongested data points; step 2, based on this labelling of the data, the breakdown probability can be estimated (i.e. the probability that the average speed drops below the critical speed); step 3, we identify unperturbed moments (i.e. moments when a breakdown is expected, but does not occur) and subsequently identify the high-performance days based on the number of unperturbed moments. Identifying high-performance days could be a building block in the quest for traffic jam reduction; using more detailed data one might be able to identify specific characteristics of high-performance days. The algorithm is applied to a case study featuring the highly congested A15 motorway in the Netherlands.
Bo Klaasse, Rik Timmerman, Tessel van Ballegooijen, Marko Boon, Gerard Eijkelenboom

A Network Aware Resource Discovery Service

Abstract
Internet in recent years has become a huge set of channels for content distribution highlighting limits and inefficiencies of the current protocol suite originally designed for host-to-host communication. In this paper we exploit recent advances in Information Centric Networks in the attempt to reshape the actual Internet infrastructure from a host-centric to a name-centric paradigm where the focus is on named data instead of machine name hosting those data. In particular, we propose a Content Name System Service that provides a new network aware Content Discovery Service. The CNS behavior and architecture uses the BGP inter-domain routing information. In particular, the service registers and discovers resource names in each Autonomous System: contents are discovered by searching through the augmented AS graph representation classifying ASes into customer, provider, and peering, as the BGP protocol does. Performance of CNS can be characterized by the fraction of Autonomous Systems that successfully locate a requested content and by the average number of CNS Servers explored during the search phase. A C-based simulator of CNS is developed and is run over real ASes topologies provided by the Center for Applied Internet Data Analysis to provide estimates of both performance indexes. Preliminary performance and sensitivity results show the CNS approach is promising and can be efficiently implemented by incrementally deploying CNS Servers.
Luigi Liquori, Rossano Gaeta, Matteo Sereno

EthExplorer: A Tool for Forensic Analysis of the Ethereum Blockchain

Abstract
This paper presents EthExplorer, a graph-based tool for analysing the Ethereum blockchain. EthExplorer has been designed for the assessment of Ethereum transactions, which represent diverse and complex activities in a large-scale distributed system. EthExplorer shows Ethereum addresses as nodes and transactions as directed arcs between addresses. The graph is annotated in several ways: arcs are scaled according to the amount of Ether they carry and the nodes are colour encoded to indicate types of addresses, such as exchanges, miners or mining pools. Ether transfer transactions and smart contracts are distinguished by line styles. EthExplorer can be used to trace the flow of Ether between addresses. For a given address all its output or input transactions with the corresponding receiver or sender addresses can be found. The set of considered addresses can be increased by adding selected addresses to the set of analysed addresses.
Yuriy Marchenko, William J. Knottenbelt, Katinka Wolter

A Queueing Model that Works Only on the Biggest Jobs

Abstract
We consider a queueing system with capacity 1 and subject to a Poisson arrival process. Jobs consists of a random number of tasks and at each arrival, the system will continue to work on the current job if the number of its tasks is higher or equal than the number of tasks of the job just arrived, otherwise the job in the queue leaves the system and the one just arrived begins its service. The service time of each task is independent and exponentially distributed with the same parameter.
We give an explicit solution for the stationary distribution of the queue by resorting to time-reversed analysis and we observe that this approach gives a much more elegant and constructive way to obtain the result than the traditional approach based on the verification of the system of global balance equations. For geometric distribution of the number of tasks, we use the q-algebra to make the results numerically tractable. The queueing system finds applications in contexts in which the size of jobs is known or partially known and schedulers or dispatchers can take decisions based on this information to improve the overall performance (e.g., reducing the mean response time).
Andrea Marin, Sabina Rossi

Performance Evaluation of Thermal-Constrained Scheduling Strategies in Multi-core Systems

Abstract
The increasing usage of multi-cores in safety-critical applications, such as autonomous control, demands high levels of reliability, which crucially depends on the temperature. On the other hand, there is a natural trade-off between reliability and performance. The scheduling of tasks is one of the key factors which determine the resulting system performance as well as reliability. Commonly used techniques, such as simulation based on benchmarks, can simulate only a limited number of input sequences of system runs and hardly optimize the performance-reliability trade-off. In order to accurately evaluate the schedulers and provide formal guarantees suitable in early design stages, we use formal methods for a quantitative performance-reliability trade-off analysis. Specifically, we propose to use energy-utility quantiles as a metric to evaluate the effectiveness of a given scheduler. For illustration, we evaluate TAPE, a state-of-the-art thermal-constrained scheduler, with theoretical optimal ones.
Muhammad Usama Sardar, Clemens Dubslaff, Sascha Klüppelholz, Christel Baier, Akash Kumar

Bounding the Rate of Convergence for One Class of Finite Capacity Time Varying Markov Queues

Abstract
Consideration is given to the two finite capacity time varying Markov queues: the analogue of the well-known time varying M/M/S/0 queue with S servers each working at rate \(\mu (t)\), no waiting line, but with the arrivals happening at rate \(\lambda (t)\) only in batches of size 2; the analogue of another well-known time varying \(M/M/1/(S-1)\) queue, but with the server, providing service at rate \(\mu (t)\) if and only if there are at least 2 customers in the system, and with the arrivals happening only in batches of size 2. The functions \(\lambda (t)\) and \(\mu (t)\) are assumed to be non-random non-negative analytic functions of t. The new approach for the computation of the upper bound for the rate of convergence is proposed. It is based on the differential inequalities for the reduced forward Kolmogorov system of differential equations. Feasibility of the approach is demonstrated by the numerical example.
Alexander Zeifman, Yacov Satin, Rostislav Razumchik, Anastasia Kryukova, Galina Shilova

Backmatter

Weitere Informationen