Thesis Defense — Pedro Silva

Everyone is welcome to attend Pedro Silva’s thesis defense, which will take place next Monday 11th December at 14h at Salle Place de l’Ecole (1, Place de l’École, 69003).

On the mapping of distributed applications onto multiple Clouds.

Christian Perez, Inria
Frédéric Desprez, Inria

Committee members:
Patricia PASCAL-STOLF, IUT de Blagnac, reviewer
Emmanuel Jeannot, Inria, reviewer
Christine Morin, Inria, examiner
Erik Elmroth, University of Umea – Sweden, examiner

You are also invited to the cocktail that follows the defense at the
LIP’s coffee area (coin café) (46 Allée d’Italie, 3rd floor).


The Cloud has become a very popular platform for deploying distributed applications. Today, virtually any credit card holder can have access to Cloud services. There are many different ways of offering Cloud services to customers. In this thesis we specially focus on the Infrastructure as a Service (IaaS), a model that, usually, proposes virtualized computing resources to costumers in the form of virtual machines (VMs).
Thanks to its attractive pay-as-you-use cost model, it is easier for customers to outsource hosting infrastructures and benefit of
savings related to upfront investments and maintenance costs. Also, customers can have access to features such as scalability, availability, and reliability, which previously were almost exclusive for large companies.

To place a distributed application on the Cloud, a customer must first consider the mapping between her application (or its parts) to the target infrastructure. She needs to take into consideration cost, resource, and communication constraints to select the most suitable set of VMs, from private and public Cloud providers. However, defining a mapping manually may be a challenge in large-scale or time constrained scenarios since the number of possible configuration explodes. The large offer of Cloud providers in the market and eventual advantages of having an application deployed over different Cloud sites, like redundancy and reachability, for example, make this challenge even more complex. Furthermore, when automating the mapping definition, scalability issues must be taken into account since this problem is a generalization of the graph homomorphism problem, which is NP-complete.

In this thesis we address the problem of calculating initial and reconfiguration placements for distributed applications over possibly multiple Clouds. Our objective is to minimize renting and migration costs while satisfying applications’ resource and communication constraints. We concentrate on the mapping between applications and Cloud infrastructures. Using an incremental approach, we split the problem into three different parts and propose efficient heuristics that can compute good quality placements very quickly for small and large scenarios. First we model the problem as a communication oblivious problem and propose vector packing based heuristics able to calculate initial placement solutions. Then, we extend our application and infrastructure models by introducing communication constraints, and propose a graph homomorphism based heuristic to calculate initial placement solutions. In the last part, we introduce application reconfiguration to our models and propose a heuristic able to calculate communication and reconfiguration aware placement solutions.

These heuristics have been extensively evaluated against state of the art approaches such as MIP solvers and meta-heuristics. We show through simulations that the proposed heuristics manage to compute solutions in a few seconds that would take many hours or days for other approaches to compute.