Tag Archives: Performance Evaluation

23/04/2014 – Talk by V-T. Hoang and M. Hussain

Title: Performance evaluation of TCP congestion control mechanisms ECN/RED and SAP-LAW in presence of UDP traffic
Time: 13:00
Location: Meeting room
Type: Research Result
Speaker: V-T. Hoang and M. Hussain
Abstract:

Internetworking often requires a large amount of users to share a common gateway to obtain the connectivity to the Internet. Congestion avoidance mechanisms are used to prevent the saturation of the gateway which represents a bottleneck of the system. The most popular congestion avoidance mechanisms are the Explicit Congestion Notification (ECN) and the Random Early Detection (ECN). Recently, a new method for the congestion avoidance has been proposed: the Smart Access Point with Limited Advertised Window (SAPLAW). The main idea is to hijack at the gateway the acknowledge packets in the TCP connections in order to artificially reduce the advertised destination window according to some bandwidth allocation policy. Therefore, the flux control mechanism is artificially exploited to control the congestion at the bottleneck. The advantage of this approach is that it does not drop any packet and does not require any modification in the TCP implementations at the clients. In this paper we propose stochastic models for the ECN/RED and SAP-LAW mechanisms in order to compare their performances under different scenarios. The models are studied in mean field regime, i.e., under a great number of TCP connections and UDP based transmissions while considering TCP greedy and temporary connection. in this paper we consider the presence of UDP traffic with bursts, and the case of not greedy TCP connections. The models for SAP-LAW are totally new. The comparison is performed in terms of different performance indices including average queue length, system throughput, expected waiting time.

 

 

17.07.2013 – Talk by Gian-Luca dei Rossi

Title: On the solution of cooperating stochastic models
Time: 14:00
Location: Meeting room
Type: Research Result
Speaker: Gian-Luca dei Rossi
Abstract:

Stochastic models are widely used in the performance evaluation community. In particular, Markov processes, and more precisely, Continuous Time Markov Chains (CTMCs), often serve as underlying stochastic processes for models written in higher-level formalisms, such as Queueing Networks, Stochastic Petri Nets and Stochastic Process Algebras.. While compositionality, i.e., the ability to express a complex model as a combination of simpler components, is a key feature of most of those formalisms, CTMCs, by themselves, don’t allow for mechanisms to express the interaction with other CTMCs. In order to mitigate this problem various lower-level formalisms have been proposed in literature, e.g., Stochastic Automata Networks (SANs), Communicating Markov Processes, Interactive Markov chains and the labelled transition systems derived from PEPA models.
However, while the compositionality of those formalism is a useful property which makes the modelling phase easier, exploiting it to get solutions more efficiently is a non-trivial task. Ideally one should be able to either detect a product-form solution and analyse the components in isolation or, if a product form cannot be detected, use other techniques to reduce the complexity of the solution, e.g., reducing the state space of either the single components or the joint process. Both tasks raised considerable interest in the literature, e.g., the RCAT theorem for the product-form detection or the Strong Equivalence relation of PEPA to aggregate states in a component-wise fashion.This talk deals with the aforementioned problem of efficiently solving complex Markovian models expressed in term of multiple components. We restrict our analysis to models in which components interact using an active-passive semantics. The main contributions rely on automatic product-forms detection, in components-wise lumping of forward and reversed processes and in showing that those two problems are indeed related, introducing the concept of conditional product-forms.

29.05.2013 – Talk by Luca Bortolussi

Title: Mean field approximation for stochastic model checking
Time: 14:00
Location: Meeting room
Type: Research Result
Speaker: Luca Bortolussi
Abstract:
Mean field approximation techniques are well established approaches to analyse large-scale stochastic processes, especially population Markov models. Some years ago, they have entered the arena of quantitative formal methods, and they provided a consistent way to define fluid semantics for stochastic process algebras.
Here, we will discuss how mean field approximation can play a role in another successful area of quantitative formal methods, namely stochastic model checking. In particular, we will focus on a subclass of Continuous Stochastic Logic (CSL), considering formulae that expresses properties of single agents in a population model, and we will present an approximate model checking algorithm based on mean field approximation. We will also discuss model checking CSL formulae against time-inhomogeneous CTMC models, as this turns out to be the core procedure needed for fluid approximation.
Finally, we will consider a class of global properties that can be analysed by linear noise approximation, a higher order fluid approximation.

08.05.2013 – Lecture by Michele Mazzucco

Title: Tuning of large computer clusters to maximise performances
Time: 11:00
Location: Meeting room
Type: Lecture
Speaker: Michele Mazzucco
Abstract:
The lecture is part of the course of “Performance and reliability of computer systems” and “Foundations of programming languages”. The speaker works for Demonware and Activision Blizzard and is part of the team that is in charge of the capacity planning for the company’s data centres. In this lecture, Dr. Mazzucco will describe the data centre infrastructure and its requirements for acceptable online gaming experiences. Then, he will show how the capacity planning of these large and powerful infrastructures can be carried out by using formal models
such as queueing systems.

29.04.2013 – Talk by Erol Gelenbe

Title: Towards energy efficient QoS
Time: 13:00
Location: Meeting room
Type: Research Result
Speaker: Erol Gelenbe
Abstract:
Often, papers regarding energy savings in computer systems
and networks discuss average power consumption (in watts) which is
easier to measure and understand than actual energy consumption
(in joules or watt-hours). Furthermore not much attention has yet been devoted
to energy efficiency in conjunction with the quality of service (QoS) delivered
to users. Based on our own work on different architectures including
packet network routing, systems that include multiple servers, cloud computing
and mobile devices, we will show how energy consumption together with
QoS can be optimised for end users.

Brief Bio:
Erol Gelenbe’s curent projects, funded by EU FP7, UK EPSRC and UK MoD,
cover both energy savings in ICT and network security. His recent papers in the
Physical Review and ACM/IEEE journals and conferences, deal with performance and
energy considerations, but also with gene regulatory networks and protein alignment.
He is an IEEE and ACM Fellow, and a member of several national academies
of science and of engineering. He received the ACM SIGMETRICS Life-Time
Achievement Award, the France-Telecom Prize of the French Academy of Sciences,
and several honoris causa doctorates, and decorations from France and Italy.

16.01.2013 – Talk by Maria Grazia Vigliotti

Title: Separable solution for interacting stochastic automata

Date: 16/01/2013
Time: 1:30 pm
Location: Sala riunioni
Type: research talk
Speaker: Maria Grazia Vigliotti (Imperial College, London)

Abstract:
We present product-form solutions from the point of view of stochastic process algebra. In previous work  we have shown how to  derive
product-form solutions for a formalism called Labelled Markov Automata (LMA). LMA are very useful as their relation  with  the Continuous Time Markov Chains is very direct. The disadvantage  of using LMA is that the proofs of properties  are  cumbersome. In fact,  in LMA it is not possible  to use the inductive structure of the language in a proof.   In this paper we consider a simple stochastic process algebra that has the great advantage of simplifying  the  proofs. This simple language has been  inspired by PEPA, however,
detailed analysis of  the semantics of  cooperation  will  show the differences between  the two formalisms. It will  also  be shown that  the semantics of the cooperation in process algebra influences the correctness of the derivation of the product-form solutions.

18.12.2012 – Talk by Michele Mazzucco

Title: Revenue Maximization Problems in Commercial Data Centers

Date: 18/12/2012
Time: 1:00 pm
Location: Sala riunioni
Type: industrial application
Speaker: Michele Mazzucco (Demonware, Dublin)

Abstract:

As IT systems are becoming more and more important, one of the main concerns is that users may face major breakdowns and eventually incur major costs if computing systems do not meet the expected performance requirements: customers expect reliability and performance guarantees, while under-performing systems loose revenues. For example, it has been reported that Amazon tried delaying the page generation by 100 ms and found out that even very small delays would result in substantial and costly drops in revenue (1% sales drop for 100 ms delay). In this talk I will discuss some performance models aiming at optimizing the revenue earned by IT providers running ‘jobs’ subject to Quality of Service (QoS) constraints. The presentation is divided into two parts. In the first part I will analyze a business model where the QoS guarantees are formally defined through Service Level Agreements (SLAs), and thus the provider is liable to pay a penalty every time the promised performance level is not met. Experimental results show that revenues can be dramatically improved by imposing suitable conditions for accepting incoming traffic, and that the proposed policies perform well under different traffic conditions.

In the second part of the presentation I will discuss two queueing models for power and performance. The main difference compared to the first part of the talk is that now the QoS is implicit, and thus customers simply leave the system (or wait) if it under-performs, while the provider also takes into account the energy consumed by servers when deciding how many servers to allocate.

Michele Mazzucco graduated in Computer Science at the University of Bologna and obtained his PhD at the University of Newcastle under the supervision of prof. Mitrani. His main reserach interests include models for the performance evaluation and optimization of data centers. He has published in major conferences and journals on topics such as cloud computing and green computing. Since 2012, he works for Demonware.

DemonWare is an Irish software development company and a subsidiary of Activision Blizzard. DemonWare’s products enable games publishers to outsource their networking requirements, allowing them to concentrate on playability. The organisation has offices in Dublin, Ireland; and Vancouver, Canada.Primary products developed by DemonWare include the “DemonWare State Engine” and “Matchmaking+”. The State Engine is a high-performance state synchronization C++ programming framework that eliminates the need to reinvent netcode multiplayer games. Matchmaking+ provides services for multiplayer games such as matchmaking, user profiling, and gaming statistics. DemonWare’s main product has been used to support the development of several online games of success, among which Call of Duty.


07.11.2012 – Tutorial by Andrea Marin

Title: From M/M/1 queues to Quasi Birth and Death Processes
Date: 7 November, 2012 – 12.30
Type: tutorial
Speaker: Andrea Marin (Ca’ Foscari, Venice)

Abstract: Markov chains are an important framework for studying queueing systems. However, deriving the steady-state behavior of a queue may be a really hard task because of the large number of states (possibly infinite) of the process. Indeed, the brute-force numerical algorithms quickly become numerically unstable and time-expensive. This tutorial aims at showing how the geometric structure of the Markov chains underlying a class of queues called “Quasi Birth and Death” can be exploited to derive its stationary state probabilities and performance indices.

Prerequisites: Matrix manipulation (product, sum, transposed), solution of linear systems in matrix form (including matrix inversion), rank of a matrix, continuous/discrete time Markov chains (stationary analysis)