This thesis would not have been possible without the help,

Foreword

Following a joint consultation and brainstorming with both Cedric Brandily and Djamal Zeghlache, we observed that there existed an operational problem within cloud This thesis represents the learning and acquired know how over a period of nearly three years (2013)(2014)(2015)(2016). The first questions were raised when providers of cloud platforms realized that infrastructure costs and energy consumption in data centers can be reduced significantly through smarter resource allocation and placement. However, due to problem complexity and scalability issues, optimal placement and allocation have turned out to be more difficult to achieve than expected. This has been especially exacerbated by the amount of available resources in large data centers, the heterogeneity in terms cloud resources and services themselves and the presence of multiple stakeholders. Fully optimizing the use and exploitation of cloud infrastructure remains for these reasons a challenge that we nevertheless believe can be partially addressed by unified models and appropriate optimization methods and approaches to remove some of the hurdles and barriers.

In order to derive a unified view and/or model of the general cloud resources allocation problem, the first goal has been to analyze, understand and classify existing resource allocation mechanisms and schedulers in the current literature, in open source communities and in commercial solutions. My primary objective was consequently to analyze xii Foreword xiii optimal and suboptimal resource allocation algorithms and to develop a methodology, a model and tools for new and evolved placement algorithms that can take into account usage and exploitation costs, heterogeneous resources and quality of service.

Chapter One is an introduction to dynamic resource provisioning in cloud computing. This chapter presents the cloud computing paradigm and the general concepts of cloud schedulers and describes the context and ensuing objectives and organization of the thesis.

Chapter Two describes the background and the methods available in the literature in the first section. The chapter presents the metrics used in cloud environments, the related multi-dimensional packing and scheduling problems and the algorithms proposed by the current literature to solve them. The first section gives a complete description of multi-dimensional packing and scheduling problems. The notion of permutation in combinatorics used to resolve these problems is described in section one. Section two is a review of the metrics used in a cloud to compare the scheduling methods. The third and final section lists some relevant algorithms for the cloud resource allocation problem.

Chapter Three introduces a new and generic model for cloud placement and resource allocation. The problem is modeled as a packing problem. We outline and apply a single objective and multiple objectives to these problems while defining constraints for the allocation.

Chapter Four develops a genetic algorithm to solve the addressed cloud resource allocation problem. We express a graph breakdown method for a more efficient data structure for solving the problem. We describe all the operators of our proposed genetic algorithm Chapter 1

Introduction

Abstract. We first describe cloud computing and the problems raised by cloud resources allocation in an infrastructure as a service context. We then summarize our contributions to this allocation problem and present the organization of the manuscript. This first section is a general overview of cloud computing to gain knowledge on its principles, properties and resource allocation and placement challenges. The notion of scheduler essential in planning end users' cloud computing jobs and tasks, and central in organizing resource allocation in the time dimension, is also presented.

Dynamic Resource Provisioning in Cloud Computing

Scheduling of jobs in shared infrastructures first appeared in mainframe computers and servers and moved thanks to advances in the IT world into computer grids involving distributed servers and hosting platforms across multiple and geographically spread sites.

However, in these infrastructures the jobs and tasks scheduling and associated compute, storage and communications resources allocations do not take into account the complex business relationships and interactions between end users, consumers and providers as envisioned by cloud computing. The latter is a paradigm shift from the servers, clusters and grids services model. Cloud computing introduces more flexibility in consumers and providers interactions by introducing a dynamic and on demand resources and services provisioning and management grounded on a pay per use principle.

In cloud computing various resources such as infrastructure resources or software components are provided as a service are provided, consumed and billed on a need and use basis. In public clouds, services or capacity are leased following subscriptions or via a Pay-per-Use principle for customers using these services. Customers interact with the cloud platform through a user interface or a programming interface (API: Application Programming Interface) managed by the provider.

There are multiple definitions of cloud computing in the current literature but a definition commonly adopted is that of the National Institute of Standards and Technology (NIST). In the NIST definition, Peter Mell and Tim Grance define cloud computing as follows: "Cloud computing is a model for enabling ubiquitous, convenient, on-demand network access to a shared pool of configurable computing resources (e.g., networks, servers, storage, applications, and services) that can be rapidly provisioned and released with minimal management effort or service provider interaction. This cloud model is composed of five essential characteristics, three service models, and four deployment models." [2] The essential characteristics [3] of cloud model are on-demand resources and services provisioning with guaranteed Quality of Service (QoS). Cloud resources or services can be automatically reconfigured, orchestrated and consolidated to present a single users' access to the cloud platform. Cloud computing platforms are flexible to adapt to various requirements of a potentially large number of users.

There are several deployment models [4] such as private cloud dedicated exclusively to single organization. Cloud technology is called a "Public Cloud" when the services are rendered over a network that is open for public use. Community clouds share infrastructure resources for several organizations from a specific community with common concerns (security, compliance or jurisdiction). Finally, hybrid cloud is a composition of two or more distinct cloud infrastructures (private, community, or public).

There are three cloud services models [START_REF] Andrikopoulos | Collaborative, dynamic and complex systems -modeling, provision and execution[END_REF]. Software as a Service, SaaS, which provides customers with applications running on a cloud infrastructure. Platform as a Service, PaaS, allowing the customer to deploy onto the cloud infrastructure customer created or acquired applications using programming languages, libraries, services, and tools supported by the provider. Infrastructure as a Service, IaaS, that offers additional resources such as a virtual-machines, disk image library, raw (block) and file-based storage, firewalls, load balancers, IP addresses, virtual local area networks (VLANs), and software bundles [START_REF] Amies | Developing and Hosting Applications on the Cloud[END_REF]. IaaS-cloud providers supply these resources on-demand from their large resources pools installed in data centers. For wide-area connectivity, customers can use either the Internet or carrier clouds (dedicated virtual private networks).

Clouds involve multiple stakeholders but this thesis focuses on two key players that are the customers and providers. This focus is justified by the fact that the client server model will apply to all combinations of pairs of stakeholders in the value and business chains. The consumer typically customize their resources and services via service templates presented by resource providers. The providers share and rent their infrastructures and provide IaaS, PaaS and SaaS services. The customers rely on the providers *aaS offers to transparently design or compose their services thanks to the providers' presented abstractions.

There are, in our view and in our thesis focus, two generic players (see Figure 1.1)) involved: the provider and the consumer. We are particularly concerned by the different interests and objectives of these two key players. The users aim at reliable, resilient and guaranteed services at lowest possible cost while the providers want to minimize their own costs and maximize their revenues. These partly conflicting interests have not been addressed jointly and simultaneously in the current resource allocation and management research. The objective of the thesis is to find balanced solutions that can conciliate these potentially conflicting objectives and interests. Customer needs are constantly changing, cloud computing customers are expected to bear the costs related to their new business models. In addition to the costs of compliance, there are the costs generated by the remote infrastructure going off-line or becoming unavailable. That is the reason why some cloud customers are turning to private or hybrid infrastructures instead. The term "private" refers to the fact that a cloud computing platform is not shared and cause less concerns in terms of data protection and security. The public clouds or provider models are not well suited for certain consumers and service providers requirements. The consumers and providers relationships need to evolve beyond the current providers business models that constrain the consumers to a specific contract, restrict the consumers possibilities and impose both the service usage and the associated costs.

Therefore, demanding customers are turning to private cloud-based infrastructure solutions which allow to operate an automated service development process. Automation is an essential process in a cloud computing platform because it enables faster delivery of services to customers, while avoiding the risk of human error. This automation can be performed on different processes such as checking compliance of the service with SLAs (Service Level Agreement), patch deployment, service version upgrade or resource allocation (resource provisioning and deprovisioning).

Cloud computing where resources and services are provided on demand on a pay-peruse basis offers the advantage of avoiding capital expenses and reducing considerably operational expenses to customers. These advantages come also with the drawback of lock in to the cloud providers model and application programming interfaces. Even if some of the issues have been addressed by cloud brokerage and portability solutions to move across cloud providers and aggregate their services, the business interests of the customers have not been taken sufficiently into account. The business contracts and APIs imposed by the providers continue to constrain the users that have to adapt to the providers' models. In fact, there is a variety of customer-provider relationships with different technical and business objectives to cater for and to include in the way cloud resources and services are acquired, used and managed. Our objective in this work is to provide cloud resources allocation solution that address the interests of the providers and customers jointly by reflecting these goals in the model. The approach consists in integrating the technical and business requirements and constraints from the customers in addition to that of the providers.

Today, in order to manage customer requests and the whole infrastructure, a cloud platform will use a "scheduler". The "Scheduler" is designed to manage allocation of resources and services on the provider layers (*aaS). For example, within IaaS layer, a placement is decided by the scheduler on the available hypervisors for each virtual machine.

If an error occurs on a given system, schedulers can trigger placement of the impacted resources onto another hosts without any human interaction. Sometimes it may be preferable to operate maintenance on a daily basis as the scheduler brings much more improvement in preserving a resource group. But how can the scheduler choose the most suitable host? And how does it react in case of failure?

In cloud platforms, schedulers on boot read out the general settings and cloud configuration files and enter standby mode until customers request services. Some schedulers take into account information coming from embedded monitoring systems. Some schedulers process requests in batch or using queuing systems but most schedulers treat the demands successively, one at a time, as they occur.

In grids and clouds, resource allocation focused primarily on consolidation and load balancing objectives. More recently there have been attempts to introduce the notion of workflows in the allocation but turned out hard to achieve in heterogeneous clouds. The same can be said of the integration of business and technical constraints despite some of the progress and the improvements in resource allocation (using for example minimum cost maximum flow approaches).

As often in the field of cloud computing, work has been carried out originally in the field of high performance computing. The aim is to successfully place statically computation tasks represented as graphs on multiprocessors grids [START_REF] Kwok | Static scheduling algorithms for allocating directed task graphs to multiprocessors[END_REF]. Based on previous work, exact and heuristic methods were provided by [START_REF] Chekuri | On multi-dimensional packing problems[END_REF] to allocate virtual networks using subgraphs within a service delivery architecture.

Research Problems and Objectives

The thesis as previously stated focuses on resource allocation onto physical infrastructures shared and offered as a service (i.e, for a IaaS context. The resource allocation problem is addressed with the consumer and provider centric objectives in mind that require answering some key underlying questions:

• How to measure the performance of a resource allocation algorithm in a cloud computing platform?

• How to represent the provider's resources and the resources requested by the users?

• How to obtain a feasible allocation solution in a suitable/practical time for large infrastructure sizes?

These objectives lead us to address key scientific challenges to derive and propose efficient resource allocation solutions or algorithms:

• Suggest a template definition generalizing carrier cloud infrastructures descriptions.

• Identify relevant indicators to describe the state of the carrier infrastructure and define the information aggregation process to support the decision and allocation process.

• Solve the related NP-hard optimization problem through efficient dynamic allocation algorithms taking into account consumers' and providers' intrerests.

Contributions

We summarize for the reader convenience the contributions of the thesis with respect to the consumer and provider centric resource allocation in clouds in a IaaS context. We also take this opportunity to describe, in the sequel, the manuscript chapter organization.

The first contribution is a new generic resource model capable of describing and integrating the costs of resources offered as a service in clouds and capable on reflecting both the consumers' and providers' objectives and interests and related constraints. The proposed data representation is an extension of Open cloud computing Interface (OCCI) model for cloud resources. We mainly worked on the description of a resource component properties. The represented resources in our work are infrastructures services but the model applies equally well to the Platform as a Service (PaaS) and Software as a Service (SaaS) paradigms. The representation includes cost of management, service interruptions, workload on cloud resources and the hosted user requests.

The second contribution is the identification and expression of affinity and anti-affinity constraints between the provider resources and the users' requested resources. These affinity and anti-affinity constraints enable tradeoffs and flexibility in the overall costs and in users' quality of service. The framework facilitates differentiation and prioritization of resources allocation to take into account critical user resources by hosting for instance these sensitive virtual resources on secure provider resources. These constraints are expressed as allocation (mapping) constraints of virtual resources onto the provider infrastructure.

The third contribution, that relies on the two previous contributions to describe and define the problem, is an evolutionary algorithm, specifically a genetic algorithm, that can meet simultaneously the conflicting users' and providers' objectives and constraints.

The proposed genetic algorithm can find in practical/reasonable time (< 30 seconds) good solutions for the resource allocation problem for scenarios involving midsize clouds (in the order of 2000 virtual machines and 500 hypervisors). We are in favor of genetic algorithms because they can find multiple near optimal solutions, if well configured and tuned, solutions have chosen to use a genetic algorithm, in sufficiently short durations.

Our genetic algorithm has been modified to improve convergence time of the produced populations towards a feasible solution. We improved the initialization process of the population so each new generated individual respects the constraints and this speeds the convergence to a viable solution.

Thesis Organization

The thesis manuscript is organized in chapters depicted in Figure 1.2. Chapter 4 presents our proposed approach that uses a genetic algorithm to find solutions to the resource allocation problem while taking into account the stakeholders' objectives and constraints. The chapter describes the decomposition of the consumer or user requests and the provider physical infrastructure into graphs for a more efficient matrix representation of the problem. The genetic algorithm parameters and modified operators are specified along with our introduction of our own genetic algorithm will be described along with our own initialization and crossover operators to improve the solutions. We assess performance and compare with a state of the art commercial and industrial solution (section 2.4) using the metric defined in Section 2.2.

In the final chapter 5 we summarize our contributions to the cloud resource allocation problem and sketch perspectives for future research and investigations.

Allocation Problem Definition and Resolution

Since resource allocation and scheduling both rely on combinatorial optimization, we review briefly the history of this field. Indeed, allocation and scheduling have been the subject of combinatorial optimization for quite a long time in past work such as [START_REF] Schrijver | On the history of combinatorial optimization[END_REF] [10] [START_REF] Rinaldi | Integer Programming and Combinatorial Optimization -IPCO III[END_REF] [START_REF] Jünger | Combinatorial Optimization and Integer Programming[END_REF]. The resource allocation and scheduling problems had a major role at the beginning of World War II for instance where there was a need to optimally place military equipment in cargos. Linear programming was used for the purpose in the 1930s [START_REF] Nicola | Mainstream Mathematical Economics in the 20th Century, chapter Linear Programming and Extensions[END_REF] [START_REF] Murty | Linear Programming[END_REF]. In the late 1930s, applications of linear programming were first seriously attempted by Leonid Kantorovich (a Soviet mathematician) and by Wassily Leontief (an American economist) respectively for manufacturing schedules in economics.

Leonid Kantorovich obtained the 1975 Nobel Prize in economics for his contribution to the optimal resource allocation problem [START_REF] Kantorovich | On the calculation of production inputs[END_REF]. The Sveriges Riksbank Prize in Economic Sciences, in Memory of Alfred Nobel, was awarded jointly to Leonid Vitaliyevich Kantorovich and Tjalling C. Koopmans "for their contributions to the theory of optimum allocation of resources" [START_REF] Tjalling | A Note About Kantorovich's Paper, "Mathematical Methods of Organizing and Planning Production&quot[END_REF] [START_REF] Tjalling | On the Evaluation of Kantorovich's Work of 1939[END_REF]. They were able to solve these problems with linear programming which consequently gained momentum in 1947 with the introduction of the simplex method by George Dantzig that has since simplified considerably the resolution of linear programs [START_REF]dantzig: Operations research icon[END_REF] [START_REF] Dantzig | Linear Programming 1: Introduction[END_REF].

The mathematical definition of these problems has evolved over time and several approaches and mathematical tools can be used to address resource allocation and scheduling such as: linear programming, integer programming, decision analysis, dynamic programming or network analysis with critical path method to cite a few.

A typical mathematical problem is to maximize profits or reduce costs by using a single objective function with an associated set of constraints. In the case of a linear program, the objective function and constraints are all linear functions. The allocation problem of virtual resources in a cloud computing platform is a more recent topic and challenge that is similar to the problems of load balancing and storage in a multidimensional knapsack.

The objective functions and constraints are becoming increasingly complex, however, in the context of clouds characterized by allocation and provisioning flexibility and highly dynamic operation.

We now specialize the description, analysis and presentation to our central problem: resource allocation and scheduling in d-dimensions corresponding to the cloud computing resource provisioning and management. We outline a general definition for the resource allocation and scheduling and present vector bin packing, vector scheduling and view the entire problem as "Packing Integer Problem". We pay special attention to combinatorial partial-permutations that are used to address these problems.

Multi-dimensionnal Packing Problems

In this thesis, we study multi-dimensional generalizations of bin packing, load balancing and knapsack problems. Indeed, the generalization of resource allocation problems within a cloud computing platform is an aggregate of these well-known generalizations.

We provide a definition of the multi-dimensional bin packing and the load balancing generalizations. We examine the generalization of the knapsack problem. For each definition, we give an example using an integer programming formulation.

Vector Bin Packing

Vector bin packing, very well known in operational research [START_REF] Johnson | Vector bin packing[END_REF] [START_REF] Bansal | Bin packing in multiple dimensions: Inapproximability results and approximation schemes[END_REF], is a static model representing resource allocation problem with known service demands and a set of servers with known capacities [START_REF] Bobroff | Dynamic placement of virtual machines for managing sla violations[END_REF]. The capacity of the servers and the service demands span several dimensions. There is a renewed interest in this problem because it adapts well to the virtual machine allocation problem in clouds. The objective is to minimize the number of bins needed to allocate n resources. Resources must be allocated only once and the allocation must comply with the bins capacity limits. We can write this problem with an integer programming formulation [START_REF] Mauro | On the generalized bin packing problem[END_REF]. We use boolean variable x ij to indicate that resource i is allocated on bin j and set

x ij = 1, ∀i ∈ [0, n]; ∀j ∈ [0, m].
W I d,i x i,j ≤ W B d,j U j (2.2) ∀i m j=1 x i,j = 1 (2.3) x ∈ {0, 1}, U ∈ {0, 1} 2.1.1.

Vector Scheduling

Scheduling is commonly used to address allocation problems in many areas such as allocating tasks to processors [START_REF] Blazewicz | Scheduling multiprocessor tasks to minimize schedule length[END_REF] or managing gates at airports [START_REF] Merve | Stochastic optimization models for the airport gate assignment problem[END_REF]. The objective is to find an assignment of the tasks that minimizes load over all bins.

Definition 2.2. Vector Scheduling [START_REF] Conway; Richard | Theory of scheduling[END_REF]. Given a set of n rational vector of tasks T = {t 1 , . . . , t n } from [0, 1] d where d is the number of dimension, we have to find a partition of the set into sets B = {B 1 , . . . , B m } with maximum load on any bin in any dimension is at most equal to 1, m t∈T j T ∞ ≤ 1 where T j is the set of tasks assigned to bin j.

The objective is to find an assignment of the tasks that minimizes load over all bins.

We can write this problem in the form of a generalized load balancing problem with an integer program formulation. Let T = {t 1 , . . . , t n } be a set of tasks and B = {B 1 , . . . , B m } be a set of bins with d dimensions [0, 1] d . Define x ij as a boolean variable with x ij = 1 if task i is allocated on bin j. Matrix x ∈ {0, 1} |T |×|B| represents the assignment matrix.

If task i is assigned to bin j, there is non-negative cost C ijj associated to machine j .

The objective is to minimize load over all bins. x i,j Boolean variable indicating whether task i is assigned to bin j C ijj Non-negative cost of machine j if task i is assigned to bin j

We obtain a description of Vector Scheduling problem as an integer program [START_REF] David | An integer programming approach to scheduling. Computer scheduling of public transport urban passenger vehicle and crew scheduling[END_REF]:

min x max j n i=1 m j=1 x i,j C ijj (2.4) subject to: ∀i m j=1
x i,j = 1 (2.5)

x ∈ {0, 1}, ∀i ∈ T, j ∈ B

Packing Integer Program

The Packing Integer Problem is equivalent to the knapsack problem with multiple dimensions [8] [28]. The knapsack problem consists in filling a bag with items. A natural constraint is that the aggregated size of all selected items cannot exceed the capacity of the knapsack. Another constraint is that each item must be allocated only once.

The objective is to transport the maximum number of items to maximize profit. The multidimensional knapsack problem arises in several practical contexts such as capital budgeting, cargo loading, cutting stock problems and processors allocation in huge distributed systems. We can formulate this problem as an integer program. There are n items available for selection each with a profit and a weight. The set of items is noted I = {i 1 , . . . , i n } with profit P i and weight W I i for item i. K = {k 1 , . . . , k m } is a set of knapsack. W K j is the capacity of knapsack j. The boolean variable x ij is set to x ij = 1 to indicate that item i is packed into knapsack j. The objective is to maximize the profit while respecting the capacity constraints.

Definition 2.3. Packing Integer Program [29]. Given A ∈ [0, 1] n×m , b ∈ [1, ∞) n and c ∈ [0, 1] m with max j c j =

Capacity of knapsack j

The Packing Integer problem can be represented as an integer program [START_REF] Robert | Integer programming[END_REF]:

max m j=1 n i=1 P i x i,j (2.6)
subject to:

∀j n i=1 W I i x i,j ≤ W K j (2.7) ∀i m j=1 x i,j ≤ 1 (2.8) x ∈ {0, 1}, ∀i ∈ T, j ∈ B
Packing Integer Problem is an important class of integer problems because it generalizes the notion of filling in various containers and helps in solving complex problems such as graph isomorphism or hypergraph matching.

Partial Permutations

Multi-dimensionnal Packing can be solved through combinatorial computation. Combinatorial analysis [START_REF] Kullaaok | An introduction to combinatorial analysis (john riordan)[END_REF] is the mathematical study of permutations and combinations of finite sets of objects. These problems can be modeled through partial permutations [32] [33]. By extension we can solve scheduling problems with permutations [START_REF] Naderi | The distributed permutation flowshop scheduling problem[END_REF]. The aim of this subsection is to list the methods for counting sets in various conditions. Many books and articles describe the different combinatorial representations [START_REF] Sedgewick | Permutation generation methods[END_REF] [36] [37] [START_REF] Chase | Algorithm 382: Combinations of m out of n objects [g6]. Commun[END_REF].

We focus on Partial Permutation and more specifically on Partial Permutation with repetition that is used to represent the cloud resource allocation problem.

First, we give a definition of Partial Permutation without repetition with proofs. We show that this representation does not perfectly match with our allocation problem. For p > n we have A p n = 0, which represents the pigeonhole principle. This principle states that if n discrete objects occupy p containers, with at least one container hosting at least n p objects. The number of partial permutations without repetition is given by:

A p n = n(n -1) . . . (n -p + 1) = n! (n -p)!
(2.9) For an example with one group V M S = {vm 1 , vm 2 , vm 3 }, we have n! (n-p)! = 6 partial permutations without repetition. Partial permutations without repetition of two selected items from V M S are shown in Table 2.4. Note that this representation does not correspond to the structure of our resource allocation problem in a cloud platform.

Partial Permutation with repetition

A partial permutation [Def. 2.10] is an arrangement of a number of k items chosen from n distinct items with repetition. For example, the words 'top' and 'oot' represent two different permutations (or arrangements) of the same three letters with repetition. Definition 2.5. Partial Permutation with repetition Let E = {e 1 , e 2 , . . . , e n } be a set of n distinct items, we call partial permutation with repetition of these n items p to p, any group ordered of p items (e i1 , e i2 , . . . , e ip ) chosen from n items of E with repetition.

The number of partial permutations on n item p to p with repetition is n p .

The expression of Partial permutations with repetition is given as:

A p n = n p (2.10)
Let us consider the example of a resource allocation within a cloud platform where we want to place three virtual machines V M S = {vm 1 , vm 2 , vm 3 } on two hypervisors HY P S = {hyp 1 , hyp 2 } in an IaaS platform. We have 2 3 = 8 partial permutations with repetition.

cloud computing: Key Performance Indicators

It is difficult to precisely measure the performance of cloud platform components because the key performance indicators (KPIs) are heterogeneous and do not use the same metrics. The KPIs are used to make decisions about moving to the cloud based on the data measurement capabilities (quality of service, availability and reliability) [START_REF] Galán | Service specification in cloud environments based on extensions to open standards[END_REF]. Obviously, these indicators have an essential role as they enable measurement of the impact of decisions made by IT managers. Key Performance Indicators come up with WHAT the results of the measurement are, but not HOW the measurement was performed.

As mentioned, the difficulty lies in the fact that the indicators are heterogeneous with definitions that may vary from one provider to another. As of today, there are several indicators for energy management, formalized and defined differently, [START_REF] Hoon | Power-aware provisioning of cloud resources for real-time services[END_REF] [41], QoS [START_REF] Kourtesis | Semantic-based qos management in cloud systems: Current status and future challenges[END_REF],

costs [43][44] or business [45] [46] .

There is an attempt by NIST to standardize KPI and metrics in cloud environments [START_REF]Cloud computing service metrics description[END_REF].

NIST defines an abstract measurement standard used to assess resource properties. This abstraction is interesting since it aims at the integration of these metrics in a unified model describing a cloud platform. But this attempt is only a draft at this time.

What are the performance indicators within a cloud environment? We classify these indicators into three major categories:

• Technical indicators (network access, availability of resources);

• Strategic and business indicators;

• Tarification indicators.

Technical indicators

The technical section is the simplest to assess because these indicators are following the traditional IT. For solution providers who offer hosted applications and services, measuring and tracking utilization rates is crucial. We present is this sub-section Infrastructure capacity indicator with energy and bandwidth, availability rates, and convergence and reconfiguration time of scheduling process.

Infrastructure Capacity

We can measure the capacity of an infrastructure with hardware capacity and utilization rates. Hardware capacity is measured by storage, CPU cycles, network bandwidth or workload memory capacity as indicators of performance. Infrastructure utilization is measured by uptime availability and volume of usage as indicators of activity and usability.

Managing capacity ensures that there is always available capacity to meet service demands. Service providers develop horizontal and vertical scalability [START_REF] Vaquero | Dynamically scaling applications in the cloud[END_REF] with business forecast, project pipelines and use data from capacity monitoring to avoid resource shortage. Horizontal scaling consists of adding more machines into your pool of resources whereas "Vertical scaling" implies the addition of more power (CPU, RAM) to your existing machines.

In a cloud world horizontal-scaling is often based on adding new hypervisors, in verticalscaling increasing the capacity is done through a multi-core process, balancing the load over both the CPU and RAM resources of machines or adding such ability to the original features.

Horizontal-scaling often makes it easier to scale dynamically by adding more machines into the existing pool -Vertical-scaling is often limited to the capacity of a single machine, scaling beyond that capacity often involves downtime and comes with an upper limit.

In short, we can cite some examples of capacity indicators:

• Hypervisors utilization;

• Application utilization;

• Bandwidth utilization between hypervisors;

• Bandwidth utilization between application.

Availability Rates

High-availability is the ultimate aim of a cloud platform. Indeed, the idea to be able to access our services, our tools or our data from anywhere at anytime, it is the essence of the cloud computing paradigm. But it is very difficult to define high-availability in a cloud environment. What is the availability? Is it consistent with network devices reliability? Does it correspond to downtime of virtual resources?

In the case of Infrastructure as a Service (IaaS), high-availability is the availability of provider's hardware platform: in other words, we are dealing with failures in the datacenter. But it can also be downtime of virtual resources. Generally speaking, the availability is displayed as a percentage. In its classic form, availability is represented as a fraction of total time that a service needs to be up. Let us take a 99.99% SLA, for instance. This means that the service can only be offline for about 50 minutes per year.

We can cite some examples of availability indicators:

• reliability rates;

• downtime rates.

Convergence Time

A rapid provisioning of resources provides a higher elasticity within cloud platform. This means that customers will have faster access to their services. Resources are scaled up and down to follow business activity as it expands and grows or is redirected. Provisioning time can go from hours to minutes.

When the convergence time of an allocation algorithm exceeds execution time of a reconfiguration plan, then it means that the cloud platform will run in a degraded state where resources will appear as unstable.

Reconfiguration Time

Current virtualization techniques can support dynamic reconfigurations of virtual machines. Reconfiguration plans implement the required configurations actions on the selected hosting cloud platforms. It includes the provisioning and instantiation of the proposed solution by the allocation optimization process. The reconfiguration time is the time taken by the reconfiguration plan to execute completely. This is an important indicator because if the reconfiguration plan takes too much time to perform compared to the feed-back loop, then the cloud platform will be in a state of permanent configuration. This will cause downtime and unwanted side effects.

Strategic and business indicators

Key performance indicators can help the managers to track their business. This is what is called business intelligence. Business intelligence is the ability to slice and dice the information contained within a business into meaningful data. It is a way for entrepreneurs to drill through the organization and get the information that is needed to efficiently manage their business. Business indicators cannot be found that easily due to both infrastructure heterogeneity and the fact that these concepts are subject to personal interpretation. The business indicators we quote are only samples chosen for their relevance.

Security Awareness

If you wish to store information virtually, you must consider the added risk that your information may be accessible to other people who you do not wish to have access. We also need to ask the right questions to find out whether your information is safe.

We can cite some examples of security indicators:

• Risk level shows to what extent intrusion or service halt may happen following an incorrect operation or status vulnerability;

• Incident level shows to what extent intrusion or service halt have already occurred;

• Influence range level shows how much one incident of a component will affect other components over the cloud.

Cost Of Goods Sold

Cost of goods sold (COGS) is the consolidated total of all direct costs used to produce and deliver a product or service, which has been charged. In a service business, the cost of goods sold is considered to be the manpower, payroll taxes, and benefits of those people who generate billable hours (though the term may be changed to "cost of services"). A cloud service provider must know what their operational costs are for their physical IT resources, so as to assess the COGS.

Return On Investment

Cloud computing is changing the IT purchase from the investment, or capital expenditure (CAPEX) to operating expenses (OPEX). RoI measures or assesses, for a service provider, whether the investment spent in infrastructure does not exceed the benefits (profit) provided by the pricing of services paid by customers.

Earnings before interest and taxes

Earnings before interest, taxes, depreciation, and amortization (EBITDA) [START_REF] Achleitner | Structure and determinants of financial covenants in leveraged buyouts -evidence from an economy with strong creditor rights[END_REF]. To calculate EBITDA, a business must know its income, expenses, interest, taxes, deprecation (the loss in value of operational assets, such as equipment) and amortization, which is expenses for intangible assets, such as patents, that are spread out over a number of years. The problem is that EBITDA is not a standardized indicator, the content can differ from one company to another.

Tarification indicators

Usually regarded as less obscure than the technical or business indicators, price indicators are in reality equally complex to handle. If we take into consideration all parameters, including storage, virtual machines or network availability, there are thousands of possible prices attribuable onto the use of a cloud platform. Considering offers all different from one provider to another (template servers, size and performance of storage drives, sizing virtual machines), the comparison looks either very difficult or simply impossible.

The billing method issue appears to be a crucial point: do customers pay for power consumption per hour, per month or per year?

An IaaS provider can determine the IaaS pricing for their services by first calculating their hourly operational costs per server, per hour and then adding the desired amount of mark-up, to meet organizational revenue targets.

Problem Resolution and Algorithm Implementation

We list in this section the algorithms we have studied in this thesis and that can be found in popular cloud platforms.

Branch and Bound

The Branch and Bound [START_REF] Doig | An automatic method of solving discrete programming problems[END_REF] algorithm is classified as an exact method. This method is one of the most popular methods for the resolution of NP-hard combinatorial optimization problems. They use the divide and conquer strategy by partitioning the search space solutions into sub-problems to process individually. This method is based on a tree search of an optimal solution with separation and evaluation. A sub-problem can also be divided into sub-problems so that this process is similar to the construction of a tree.

Note that the list of all the elements is frequently unrealistic due to the size of search space to be covered.

The Branch and Bound is based on three principles:

• Separation principle

• Evaluation principle • Path strategy principle
The separation principle is, to split the problem into sub-problems. Each of them presenting a set of feasible solutions. By solving all sub-problems and retaining the best solution we end up solving the initial problem. The principle of separation is applied sequentially or recursively to each subset while there are solutions. The process for separating a branch stops when we know the best solution of all sub-problems or when we know that one sub-problem does not contain any feasible solution.

The evaluation principle relies on the quality of nodes. If a node is considered inappropriate, improved algorithms do not explore, anymore, other solutions associated with this node.

This method was used to solve common small problems and many researchers have im-

Round-Robin

The Round-Robin algorithm is very interesting as it has given birth to many more sophisticated algorithms . Round-Robin [START_REF] Hahne | Round-robin scheduling for max-min fairness in data networks. Selected Areas in Communications[END_REF] [54] is one of the oldest, simplest, fairest and most widely used scheduling algorithms, especially designed for time-sharing systems.

It can be viewed as a load balancing algorithm. This is the simplest algorithm; a request is sent to the server first, then the second and so on and so forth up to the last, and then a round is started with a first query to the first server... It's designed to give a better convergence time but the worst turnaround and waiting time. The basic algorithm uses time quantum to execute a process for a given time. A time quantum [START_REF] Alam | Finding time quantum of round robin cpu scheduling algorithm using fuzzy logic[END_REF] is a time slice.

The algorithm can be modified to allocate resources within a cloud platform. The Round-Robin scheduling algorithm for cloud resources is given by following steps:

1. The scheduler maintains a queue of ready virtual machine to allocate and a list of hypervisors hosting resources;

MatchMaking

For the scope of our problem, a "rating system" for a resource allocation problem will refer to any method used to assess the containers and assign them a numerical value.

Matchmaking system are typically paired with a "rating systems", which will refer to a system that attempts to select high rated containers during the allocation process. A rating system does not necessarily need to be very complex or have a statistical basis.

For example, each hypervisor could simply be assigned a rating equal to their ratio of acceptance/rejection user requests. These simplistic methods, however, might not accurately reflect the true capability of a hypervisor to host resources. Naturally, there are very complex models of resource allocation problems using matchmaking algorithms.

Some are decentralized matchmaking algorithms [START_REF] Raman | Matchmaking: An extensible framework for distributed resource management[END_REF] [61] [START_REF] Raman | Resource management through multilateral matchmaking[END_REF].

The general idea of this algorithm is to allocate consumer resources or user requests one by one on infrastructure. Then, algorithm iterates on filters using as parameters the infrastructure resources and user request. Filters are generally associated with one and only one characteristic to be filtered. For example, there are filters managing RAM capacity, other filters managing downtime, etc... Each filter associates scores to containers. The worst containers are removed after the scores are calculated by the filters.

Containers with the best scores are selected.

Constraint Programming

Constraint programming is a powerful concept for solving combinatorial search problems that draws on a wide range of techniques from operations research, algorithms or graph theory. The basic idea in constraint programming [START_REF] Apt | Principles of Constraint Programming[END_REF] is that the user states the constraints and a solver is used to solve them. Constraints are just relations, and a constraint satisfaction problem (CSP) states which relations should hold among the given decision variables. More formally, a constraint satisfaction problem consists of a set of variables, each with some domain of values, and a set of relations on subsets of these variables [START_REF] Rossi | Handbook of Constraint Programming (Foundations of Artificial Intelligence)[END_REF]. The goal in constraint satisfaction problems is to assign values to variables such that all constraints are satisfied. We can take as an example, the definition of a basic bin packing problem. Let B a set of bins and I a set of items. Each bin j is associated with the capacity C B j and each item i is associated with the capacity C I i . In the basic model membership variables are used, that is for each bin j and each item i, a boolean variable x i,j is defined. If the variable is equal to 1 then it means that iteam i is assigned to bin j, else the variable is equal to 0. The variable U j is a boolean variable stating that the bin j has been used. The problem can be formulated as follows:

min m j=1 U j (2.11) ∀j n i=1 C I i x i,j ≤ C B j U j (2.12) ∀i m j=1 x i,j = 1 (2.13) x ∈ {0, 1}, U ∈ {0, 1}
To solve this problem, we can use constraint propagation methods. Constraint propagation is central to the process of solving a constraint problem. Constraint propagation is a very general concept that appears under different names depending on both periods and authors. Among these names, we can find constraint relaxation, filtering algorithms, local consistency enforcing, narrowing algorithms, constraint inference, or rules iteration.

Standard Evolutionary Algorithm

Physical and biological phenomena have been the source and inspiration of many algorithms. Simulated annealing [START_REF] Aarts | Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing[END_REF] [66] is inspired by thermodynamics, artificial neural networks [START_REF] Poggio | Networks for approximation and learning[END_REF] [68] by the human brain and Evolutionary Algorithms (the most famous are the genetic algorithms) of Darwinian evolution of biological populations [69] [70].

Evolutionary algorithms are mainly stochastic global optimization methods.

Evolutionary algorithms are said to be flexible as they allow to define irregular objective functions [START_REF] Azarbonyad | A genetic algorithm for solving quadratic assignment problem(qap)[END_REF] [72] within non-standard search spaces [START_REF] Guttman | R-trees: A dynamic index structure for spatial searching[END_REF] [74] such as vectors or ddimensional graphs.

Genetic Algorithms (GA) were initially developed by Bremermann in 1958 [START_REF] Bremermann | The evolution of intelligence. the nervous system as a model of its environment[END_REF] but popularized by Holland who applied GAs to formally study adaptation in nature to apply the mechanisms in computer science [START_REF] Holland | Hierarchical descriptions, universal spaces and adaptive systems[END_REF]. This work led to the development of the principle starting in 1968 [START_REF] Holland | Hierarchical descriptions, universal spaces and adaptive systems[END_REF] which was explained in detail in his 1975 book Adaptation in Natural and Artificial Systems [START_REF] Holland | Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence[END_REF].

Genetic Algorithms encode the decision variables of a search problem into finite-length strings of alphabets of certain cardinality. The strings which are candidate solutions to the search problem are referred to as chromosomes, the alphabets are referred to as genes and the values of genes are called alleles. Once the problem is encoded in a chromosomal manner and a fitness measure for discriminating good solutions from bad ones has been chosen, we can start to evolve solutions to the search problem using the following steps [START_REF] Sastry | Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, chapter Genetic Algorithms[END_REF]:

1. Initialization. The initial population of candidate solutions is usually generated randomly across the search space. However, domain-specific knowledge or other information can be easily incorporated 2. Evaluation. Once the population is initialized or an offspring population is created, the fitness values of the candidate solutions are evaluated.

3.

Selection. The principle of selection is to choose individuals to evolve the population composed of better individuals. The main idea of selection is to choose better solutions over worse ones, and many selection procedures have been proposed to accomplish this idea, including roulette-wheel selection, stochastic universal selection, ranking selection and tournament selection, some of which are described in the next section.

4.

Crossover. Crossover combines parts of two or more parental solutions to create new, possibly better solutions. There are many ways of accomplishing this and competent performance depends on a properly designed recombination mechanism.

5.

Mutation. While crossover operates on two or more parental chromosomes, mutation locally but randomly modifies a solution.

6. Replacement. Replace the parent population with new generation.

7. Repeat steps. Go through steps 2 to 6 until the termination criteria are met.

Evolution stops when the desired level of performance is achieved, or a fixed number of generations has passed without improving the most powerful individual.

The key aspect for the algorithm is the choice of the representation of individuals or the choice of the search space. At each step of the algorithm, there is generally a tradeoff between exploring the search space, to avoid getting stuck in a local optimum, and exploit the best individuals obtained in order to produce better populations. It is often difficult to find the parameter values of a genetic algorithm. There are various parameters such as population size, mutation rate, number of generations and many more. For example, if the population is too small, the improvement per iteration in the fitness function will be low (measured as the best candidate solutions or the average of solutions). If you increase the population size and the fitness function increases faster then you have a sign that the result is suboptimal. There is also a point where increasing the population size does not improve the rate of increase in the fitness function.

The number of generations is related to improvement in the fitness function. A fitness function usually shows major improvement in early generations and then asymptotically approaches an optimum. The algorithm parameter settings have to be configured correctly to find good solutions quickly. Finding the right age settings is a very complex problem subject of "meta-optimization" [81] [82]. Where the objective is to find suitable parameter settings for a particular evolutionary search algorithm (for a specific problem), and the search is done by another "upper-level evolutionary" process.

Decentralized Scheduling

Usually, industrial and business companies IT infrastructure are hosted in multiple data centers, utilizing state-of-the-art practices for fault tolerance at each level of the system infrastructure, including power, cooling and backbone connectivity. As the infrastructure is composed of several data centers, each data center is responsible for resource allocation in its own realm. But using several algorithms in the different zones leads to inconsistencies in the global resource allocation [START_REF] Endo | Resource allocation for distributed cloud: concepts and research challenges[END_REF].

To solve this problem and provide global coherence in their infrastructure, businesses decided to search for algorithms that can solve the resource allocation process across different data centers [START_REF] Buyya | Algorithms and Architectures for Parallel Processing[END_REF]. These algorithms must be coherent and independent from each other [85] [86]. This is what we can call decentralized and distributed algorithms. In decentralized scheduling, organizations maintain (limited) control over their schedules.

Jobs are submitted locally, but they can be migrated to another cluster, if the local cluster is overloaded. A distributed system is a collection of independent computers that appear to the users of the system as a single consistent system.

Summary of Existing Algorithms

In the tables below we summarize the advantages and disadvantages of existing algorithms :

Scheduling in the industry

Resource management and scheduling are very important processes in industry that affect cost, performance and functionality that are the three basic criteria for the evaluation of a system. Resource allocation and scheduling is an essential element of the automation process. Scheduling decides how to allocate system resources such as CPU cycles, memory, secondary storage space, I/O and network bandwidth, between users and tasks.

Cloud resource management requires complex policies and decisions for single or multiobjective optimization. This process can be affected by unpredictable interactions with the environment, system failures, attacks, for example. Cloud service providers are faced with large fluctuating loads that challenges meeting their claim of cloud elasticity. The scheduling process must be able to manage these load fluctuations.

OpenStack scheduler

The main component of OpenStack is Nova. Nova seeks to provide a framework for the large-scale provisioning and management of virtual compute instances. Similar in functionality and scope to Amazon's EC2 service, it allows you to create, manage, and destroy virtual servers based on your own system images through a programmable API. The nova-scheduler [START_REF]Nova documentation[END_REF] process is conceptually the simplest piece of code in Nova: it takes a virtual machine instance request from the queue and determines where it should run (specifically, which compute server host it should run on). In practice, however, this will grow to be the most complex component, as it needs to factor in the current state of the entire cloud infrastructure and apply complicated algorithms to ensure efficient usage. To that end, nova-scheduler implements a pluggable architecture [START_REF]Nova architecture documentation[END_REF] that lets you choose (or write) your own algorithm for scheduling.

There are three types of scheduling algorithm implemented in nova-scheduler [START_REF]Openstack community[END_REF]. Simple algorithm that attempts to find the least loaded host. This is the default scheduler.

Chance algorithm that chooses randomly available hosts from a service table. Finally, Zone algorithm that picks randomly hosts from within an availability zone.

Simple and Zone algorithms are equivalent to a matchmaking algorithm. During its work Filter Scheduler iterates over all found compute nodes, evaluating each against a set of filters. The list of resulting hosts is sorted by weighers [Fig. 2.7]. The Scheduler then chooses hosts for the requested number of instances, choosing the most weighted hosts. Filter Scheduler uses the so-called weights during its work. A weigher is a way to select the best suitable host from a group of valid hosts by giving weights to all the hosts in the list. In order to prioritize one weigher over another, all the weighers have to define a multiplier that will be applied before computing the weight for a node. For a specific filter to succeed for a specific host, the filter matches the user request against the state of the host and other criteria as defined by each filter. Filter Scheduler makes a local list of acceptable hosts by repeated filtering and weighing. We can focus on these The list of filters and their explanation is given in the official documentation [START_REF]Openstack community[END_REF]. Amazon EC2 is hosted in multiple locations world-wide. These locations are composed of regions and Availability Zones [START_REF]Amazon Elastic Compute Cloud Documentation. Regions and availability zones[END_REF]. Each region is a separate geographic area [Fig. Zones. These mechanisms are not made public as the cost of a VM or the scheduling algorithm. However, we obtained indications by viewing keynotes [START_REF] Aws | Aws innovation at scale keynote[END_REF] and participating in sessions AWS re: Invent [START_REF]AWS re:Invent 2015. It strategy & migration session[END_REF].

Amazon EC2 Scheduling

Through the descriptions provided in the AWS keynotes, the input parameters requested from users and the response time to queries in relation to the size of the Regions and Availability zones, we can suspect that Amazon EC2 has set up a scheduling process using a matchmaking algorithm.

VMware, Distributed Resource Scheduler

VMware is based in Palo Alto, California and was founded in 1998. The company is a producer of virtualization software and cloud services [START_REF]Vmware: The trusted industry leader[END_REF]. To allocate user resources to infrastructure, system administrators can manually allocate the resources on hosts. But system admins cannot predict the future workloads nor can they keep their eyes tracking ups, downs and imbalanced distribution of loads in a virtual infrastructure. Dynamic Resource Scheduler (DRS) [START_REF] Gulati | Vmware distributed resource management: Design, implementation, and lessons learned[END_REF] is the VMware solution to this problem that aims to give every virtual machine the resources it needs, and not necessarily to make the utilization equal on all hosts in the Dynamic Resource Scheduler cluster. Chapter 3

Mathematical model for Cloud Placement Problem

Abstract. This chapter presents single and multiple objectives, criteria and constraints algorithm for cloud resource allocation taking into account both the tenant (customer)

and infrastructure provider interests. Current cloud placement algorithms are provider centric or biased, limit the optimization scope and force customers to accept the providers' business models. We propose a matrix-based model to represent both the customer needs and provider infrastructure to come up with a problem formulation that leads to joint customer and provider based optimization.

Our goal is to propose a sufficiently generic model for the cloud resource allocation problem even if the analysis and performance evaluation will be focused on the provisioning of IaaS services. The selection of adequate hypervisors will be emphasized with respect to the service request, the compute resources (virtual machines), storage and networking services.

Cloud Resource Mapping Problem

The approach adopted to ensure joint customer and provider centric resource allocation is to use matrices to describe the service requests and service offers in a form compatible with evolutionary algorithms known to be more appropriate for multi-objectives and multi-constraints optimization problems. • Data parser that analyzes and transforms requests from users, such as required resources and relationships, into the matrices that will be used by the model to represent the demand and the available resources from the providers' infrastructures;

• Output Matrices composed of a set, of integers and real matrices, that describes the request and infrastructure resources, their relationships and their associated constraints;

• Allocation optimization that find solutions for the resource allocation problem using exact or heuristic algorithms;

• Placement solution is a feasible solution for the resource allocation problem that fulfills the multiple objectives and respects the resources relationships and constraints;

• Reconfiguration plan that implements the required configurations actions on the selected hosting cloud platforms. It includes the provisioning and instantiation of the proposed solution by the allocation optimization process or block.

In this thesis we operate on both the customer and the provider layers and describe the resources in each layer in matrix form that can be easily used by evolutionary algorithms. The user service requests are also broken down into matrices and stay in line with a matrix-based model for the cloud resource allocation problem.

Most operating networks today are based on the so-called 3-Tier model where the data traffic is assumed to follow a north to south path and meant to leave the data center.

For some applications that require est-west communications within the data center or between data centers, the 3-Tier model is not appropriate since it induces many hops.

Consequently, other architectures have been proposed to balance the number of hops or leaps and achieve homogeneous latency across all servers [START_REF] Montero Moreno-Vozmediano | IaaS Cloud Architecture: From Virtualized Datacenters to Federated Cloud Infrastructures Computer[END_REF].

Advanced data centers use an architecture that is far more suitable for managing both redundancy [START_REF] Al-Fares | Commodity Data Center Network Architecture SIGCOMM Comput Vahdat, A. A Scalable[END_REF] and bandwidth [START_REF] Alizadeh | On the Data Path Performance of Leaf-Spine Datacenter Fabrics[END_REF] known as the Core/Leaf-Spine distributed network architecture [START_REF] Greenberg | Towards a Next Generation Data Center Architecture: Scalability and Commoditization Proceedings of the ACM Workshop on Programmable Routers for Extensible Services of Tomorrow[END_REF] as described in Figure 3.2.

Data centers, when hosting cloud computing platforms, tend to opt for this type of architecture with stronger resilience through three access levels:

• Spine layer acting a datacenter distribution system. As suggested by its name, a spine layer serves as backbone to an infrastructure. Each node is connected to each switch on the Leaf layer;

• Leaf layer represents the layer that manages access to different hypervisors and connections to the distribution network. This way, each switch is connected to each node on the distribution spine layer, but each resource from Spine and Leaf layers are not directly connected to each other; Note that the Core/Leaf-Spine architecture avoids the use of the Spanning Tree Protocle(STP) [START_REF] Duffield | A flexible model for resource management in virtual private networks SIGCOMM comput[END_REF] and facilitates the addition of extra hardware peripherals and enhances system capacity.

Datacenters provide ever-upgrading architectures in the face of new challenges to take [START_REF] Sivakumar | Spine Routing in Ad Hoc Networks ACM/Baltzer Cluster Computing Journal[END_REF] such as mobile datacenters. Mobile datacenters are designed to be deviced to a mobile environment, like a shipping cargo container [START_REF] Rasmussen Rimler | Mobile data center Google Patents[END_REF][103] or a sea freighter [START_REF] Aigner Whitted | Modular data center Google Patents[END_REF].

As stated previously, a cloud computing platform offers services to customers. This platform is installed on a infrastruture managed by a provider. This service provider strives to meet the requirements from the users' perpesctive while ensuring the overall sustainability of the provided services. Thanks to virtualization, a single server can simultaneously run multiple virtual components, each embedded in a virtual machine, if their total demand in each resource does not exceed the server capacity.

Figure 3.3 shows the composition of an IaaS-type cloud computing system with its different layers. An IaaS platform consists of a layer of hardware resource and another one of virtual resource. The hardware layer consists of servers and switches connected together using the leaf-spine architecture in most cutting-edge datacenters. The virtual layer is made up of virtual machines, virtual switches and networks most often in the form of VLAN. These virtual resources are assigned on hypervisors from the hardware layer.

Virtual switches are allocated through calculation nodes and are set to accommodate different VLAN users. You can define connections between resources like affinity or anti-affinity constraints while allocating. This new modeling with business relations allows implementation of services while keeping an overview of the system and this leads to easier end-to-end automation of failurefree services production.

Our goal is to reduce operating costs for an IaaS platform. Matrices are used here to represent and manage these multiple constraints and objectives. The use of a matrix representation to define the operating costs, performance objectives and constraints all lead us naturally to the use of a constraint solver in order to settle our general resource allocation issue within a cloud platform and to validate our model.

Therefore we offer a method that reflects the requests from customers and we describe a provider's infrastructure shown in the form of matrices in order to solve the cloud resource allocation issues.

Our algorithm solves the cloud resource allocation problem using the users' and providers' layers with the objective of placing (optimally or near optimally) the demands to minimize cost, service unavailability and the need to migrate or move resources in the infrastructures. Without loss of generality we assign equal weights to these objectives, that can otherwise be tuned and configured differently by the stakeholders. The objectives are specified as follows:

• Operating cost determines the full cost of an infrastructure integrating operating (consumption) cost of customer resources and the operating cost for the provider;

• Downtime cost represents the cost due to the unavailability of customer resources;

• Migration cost represents the cost of migrating customer resources using the reconfiguration plan.

We identify five major relationships and constraints to describe the user affinity/antiaffinity requirements between resources expressed by the users and providers:

• Co-localization in same datacenter tenants and applications impose the colocation in the same data center of their virtual resources;

• Co-localization on same server this constraint imposes the location of the customer or tenant virtual resources in the same server or host;

• Total separation customer resources have to be separated and mapped onto distinct servers and distinct datacenters for security reasons for example or simply due to tenant requirements or application constraints;

• Separation on different datacenters: this is a separation of customer resources onto different datacenters;

• Separation on different servers the customer resources need to be separated into different servers.

There is also one last constraint, the resource capacity constraint related to the maximum amount of available resources from the providers.

• Resource capacity constraint this is a limit used to make sure that the total amount of allocated resources does not exceed available maximum capacity virtual machines, virtual switches and interrelations between resources. Attributes to a virtual machine and a server are alike. Relations between resources mean affinity/antiaffinity constraints or a described VLAN-like newtork. A virtual switch takes the same attributes as a physical switch do. Our study mainly focuses on virtual machine allocation onto servers in order to compare performance benchmarks from various placement algorithms (tabu search, constraint programming, evolutionary algorithms)

The modeling of the user resource requests and the provider physical infrastructure through matrices is meant to be generic enough to be reused and generalized to other types of services.

Single Objective Definition

The number of provider datacenters is noted g, the number of servers defined as m, total requested resources n and the number of attributes is represented by h. In our model, the number of provider's resource attributes and the number of customer's resource attributes are the same. The mapping is on identical attributes with respect to the demand. The resource capacities (maximum available resource per node or link) are represented also by two matrices. The first matrix [Eq. 3.1] represents the capacity of each attribute of the provider resources.

P jl 1 ≤ j ≤ m, 1 ≤ l ≤ h P jl ∈ R + m × h (3.1)
The second matrix [Eq.3.2] represents the capacity limit of each customer resources attribute.

C kl 1 ≤ k ≤ n, 1 ≤ l ≤ h C kl ∈ R + n × h (3.2)
The number of attributes for provider and customer resources should be the same for both types of resources (h = h ). We also define a factor on the attributes that corresponds to the ratio between the consumed physical capacities of an attribute and the virtual capacities. This factor is also described using the matrix of [Eq.3.3] of size m × h.

F jl 1 ≤ j ≤ m, 1 ≤ l ≤ h F jl ∈ R + m × h (3.3)
We note X ijk , a boolean variable, which is true when a customer resource k is hosted by provider server j in datacenter i. We define a constraint on the capacity limit on provider resources not to be exceed in [Eq. 3.4]. This constraint includes the virtual to physical resource consumption factor for each requested attribute.

n k=1 C kl × X ijk ≤ P jl F jl , ∀l = 1...h, ∀i = 1...g (3.4)
To represent the operation expenditure of each provider resource, we introduce the vector [Eq.3.5] whose elements are costs representing the direct costs associated to the use of a server: power, floor space, storage, and IT operations for resource management.

E j 1 ≤ j ≤ m, E j ∈ R + (3.5)
In addition to operating expenditure, provider resources have an operating cost for each customer resource they host. We use a vector [Eq. 3.6] for these operating costs.

U j 1 ≤ j ≤ m, U j ∈ R + (3.6)
Each attribute on each provider resource has a maximum load before quality of service deterioration or degradation occurs for the hosted virtual resources. We note L M jl the maximum loading before degradation and L jl the current load on server j for an attribute l. These servers have a current and a maximum achievable quality of service Q jl and

Q M
jl respectively. This level of service guarantee is noted C Q k and if it is not respected the provider pays a downtime penalty defined as a cost C U k . The service provider must guarantee that there will be no interruption in service. We define these load and quality of service matrices in [Eq.3.7]:

L M jl 0 ≤ L M jl < 1 L jl 0 ≤ L jl < 1 Q M jl 0 ≤ Q M jl < 1 Q jl 0 ≤ Q jl < 1 (3.7)
All the variables and constants used in our model are listed for easy reference in Table 3.1.

The model is augmented with all the required relationships and constraints expressed in the user requests and the valid equalities and inequalities relative to the demand and hosting infrastructures.

The co-localization on same datacenter constraint expressed in [Eq. 3.8] ensures that resources subject to this constraint are hosted in the same data center: The co-localization on same server constraint is achieved if the sum of the products on the customer allocated resources meets [Eq. 3.9]. This guarantees co-localization in the same server:

g i=1 n k=1 X ijk = 1, ∀j = 1...m (3.8)
g i=1 m j=1 n k=1 X ijk = 1 (3.9)
The total separation constraint is expressed via the sum of resources, allocated to all datacenters and servers, that has to be equal to one as indicated in [Eq. 3.10]:

n k=1 X ijk = 1, ∀i = 1...g, ∀j = 1...m (3.10)
The separation on different datacenters constraint is substantially identical to the previous one, except that the sum on the datacenters and requested resources as well has to meet [Eq. 3.11]:

g i=1 n k=1 X ijk = 1, ∀j = 1...m (3.11)
The separation on different servers constraint involves the sum of the datacenters, servers and requested resources as expressed in [Eq. 3.12].

g i=1 m j=1 n k=1 X ijk = 1 (3.12)
All these relationships and constraints are implemented in our linear programming model that will be used to provide solutions to the cloud resource allocation problem addressed in this work.

Allocation problem solving

We solve the resource allocation problem according to the operating costs, the affinity/antiaffinity relations between resources and the required quality of service on the assigned cloud computing resources. The approach takes into account multiple constraints, relationships and objectives but the multiple objectives are aggregated in the overall objective function as described in the sequel. Since our optimization problem is similar to the multidimensional bin packing and the knapsack problems that have been shown to be NP-Hard, our problem is also NP-Hard. The multidimensional bin packing problem is a vector scheduling problem with d dimensions proven to be NP-Hard in [START_REF] Hochbaum | Using dual approximation algorithms for scheduling problems: Theoretical and practical results[END_REF]. As our objective is to minimize costs, service interruptions and reconfiguration plan sizes, we introduce several objective functions to compute namely, the costs in [Eq. 3.13], the quality of services of resources through [Eq. 3.14] and the approximate evaluation of the reconfiguration plan sizes using [Eq. 3.15]. Our resource allocation problem can be summarized by lumping all the objective functions with all the constraints and conditions into the following set of equations:

min Z = min[ m j=1 E j × X ijk + n k=1 U j × X ijk , ∀i=1...g (3.13) + n k=1 C U k ( Q jl C Q k ) × X ijk , ∀i=1...g ∀j=1...m ∀l=1...h (3.14) + n k=1 (X t ijk -X t+1 ijk )M k , ∀i=1...g ∀j=1...m ] (3.15)
Subject To according to the request: The objective functions and the metrics are all converted to an equivalent monetary cost so they can be aggregated into a global objective function. We detail all objective functions. We aggregate all objective functions by converting these different values in pecuniary cost. The first function is the full cost calculation given by [Eq. 3.13]. This function comprises operating costs. For each provider resource, E is the operating cost of provider resource j. For each customer resources, variable U represents the customer resource customption cost k.

Second objective [Eq.3.14] represents the costs of temporary service disruptions or penalty for lower quality of service experienced in hosting resources from the providers.

On the basis of performance assessments, authors [START_REF] Antoniou | Performance evaluation of cloud infrastructure using complex workloads[END_REF] [107] prove with empirical investigations that the quality of service of customer resources decreases exponentially with increasing workload in provider resources. The total dowtime cost is the sum of each downtime cost C U k on customer resources k when the quality of service guarantee C Q k is not respected.

We need to calculate the quality of service [Eq. 3.22] for each attribute l on provider resource j. We note this variable as Q jl . The quality of service as a function of load behaves as a piecewise function where each provider resource has a maximum load before deterioration L M jl . This is reflected in [Eq. 3.22]:

Q jl =      Q M jl if L jl ≤ L M jl Q M jl e L M jl -L jl 1-L jl if L jl > L M jl (3.22)
The workload on provider resource j for a specific attribute l is calculated [Eq.C.17] as the sum of the values of the attributes of the resources located on the servers divided by the provider resource capabilities.

L jl = n k=1 C kl × X ijk P jl ∀i=1...g ∀j=1...m ∀l=1...h (3.23)
The last objective is the sum of the costs of implementing the reconfiguration plan [Eq. 3.15]. The size of reconfiguration plan is an estimate based on the current allocation X t ijk and the next allocation X t+1 ijk provided by the optimization process.

Multi Objectives Definition

Multi-objectives problems have the characteristic of being much more difficult to process than their single-objective equivalent. Thus, we initially described our problem in the form of a single-objective problem using a scalar approach where we used an aggregation of goals with equal weight. The multi-objectives definition challenge lies in the lack of ordered relations between the solutions. One solution may be better than another on certain objectives and worse on others. So there is generally no one solution that simultaneously provides the optimum solution for all objectives. That is why the concept of optimal solution becomes less relevant in multi-objective optimization. In this case the optimal or good solution is not a single solution, but a set of compromise solutions We convert our current single objective genetic algorithm in multi-objective optimization problem [Eq. 3.24]. This consists in writing a vector containing the previous objectives.

minZ =      m j=1 E j × X ijk + n k=1 U j × X ijk , ∀i=1...g n k=1 C U k ( Q jl C Q k ) × X ijk , ∀i=1...g ∀j=1...m ∀l=1...h n k=1 (X t ijk -X t+1 ijk )M k , ∀i=1...g ∀j=1...m      (3.24)
where the first row of the vector represents the calculation of costs [Eq. 3.13], second row, the quality of services of resources [Eq. 3.14] and the last line is approximate evaluation of the reconfiguration plan size [Eq. 3.15].

In the context of this thesis we only talk about the search for best compromise solutions.

To select the best compromise on the Pareto front, we use the Goldberg NSGA Ranking.

Graph Decomposition

To describe the consumer requests and the provider infrastructure resources we transform the initial description of the virtual and physical resources as depicted in Figure

            1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1             (4.1)
The second matrix 4.2 is an adjacency matrix for anti-affinity relations.

           
0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

            (4.2)
The third matrix 4.3 takes into account the connectivity and relationships in the provider's infrastructure. Note that connectivity of the servers to switches in the provider infrastructure are also included in the representation.

            0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1             (4.3)
Besides the description of the topologies and connectivity in the networks requested by the users and in the provider infrastructure, we also need to describe the resources themselves to find matching nodes and links to the requested resources. The resources are specified using attributes and the notion of characteristics to indicate their type and provided service such as compute, storage and communications resources or services.

This representation is illustrated in We prefer good suboptimal solutions that can be found in reasonably short execution times and are capable of fulfilling practical requirements. To scale and provide solutions in reasonable resolution and execution times, we resort to the set NSGA II [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: Nsga-ii[END_REF] genetic algorithm to solve the cloud resource allocation problem addressed in this work. NSGA II is a popular non-domination based genetic algorithm for multi objective optimization and is hence an appropriate choice for the considered problem.

The NSGA II complexity is O(M N 2 ) where M is the number of objectives and N is the population size. To accelerate the execution time of the algorithm and reduce the impact of this complexity, we modify the algorithm as depicted in Fig. 4.4 and develop a specific initialization algorithm (Algorithm 1) based on the observations on the outcomes of random drawing of solutions and their tuning according to the success rate in finding viable and acceptable solutions, those that meet all the capacity constraints. We use a probability derived from these observations to control and drive future drawings and thus speed up the exploration towards good solutions. Basically, we exploit the past observations in order to fine-tune future explorations. is assigned to the provider resource j. The chromosome is composed of genes with each gene being a real number representing the id of the provider resource j. We want an algorithm that converges faster to an approximate solution and that respects the constraints (Fig. 4.5). To this end, we check at population initialization all the constraints described in Algorithm 3. The size of the population is fixed and is an input to the algorithm. We note P op the population, p an individual and S the variable set of one solution.

Variable s is just one allocation solution. Variable P jl represents a matrix of provider resource capacities and C kl is a matrix of requested resource capacities.

We introduce three variables: DC j specifies the datacenter where server j resides. The booleans N ODEused j and DCused i indicate if a node or a datacenter is used. These variables are used to implement the constraints and relationships between resources.

The variables used in the definition of our algorithm are listed for easy reference in Table 4.1: The next subsections describe the initialization operator that we have improved and the used crossover and mutation operators.

Initialization Operator

Population initialization is achieved through an initialization operator. The initialization operator is a crucial task in evolutionary algorithms because it can affect the convergence speed and also the quality of the final solution. Random initialization is the most commonly used method to generate candidate solutions (initial population) but this method does not meet the constraints. We propose a random drawing initialization (Fig. 4.6), guided by the ability of provider resources to host customer requests, to generate the initial population including the satisfaction of constraints. First time, we want to obtain random solutions which respect constraints. To initialize the population, we proceed for each individual to a random drawing (Algorithm 1) on their genes, by randomly selecting the resource that will host each gene. As long as the obtained solution is not valid, does not respect the constraints and relationships expressed in the original requests, the process is repeated, i.e. the drawing continues until valid solutions are found. The drawing is not a simple random drawing since it is guided by the ability of provider resources to host customer requests. We introduce a vector R j that stores the number of failed tests on provider resource j to capture and estimate this capability and use it to drive ensuing explorations.

Algorithm 2 Random draw Require: R j Ensure: p ∈ P op List greatLocation for each j ∈ P jl do if j == Collections.min(R j ) then greatLocation.add(j) end if end for p = Random.select(greatLocation) return p Algorithm 2 provides as output a viable provider resource (one that can host the request and respect the constraints and the relationships) to be used for the initialization process in Algorithm 1. We retain and store in a list the best provider resources, those that are part of the minimum values of R j . The R j values keep updating during the constraints checking process (Algorithm 3). Finally, we randomly draw a resource from the produced list of best provider resources and send it to the initialization process.

Crossover Operator

We use a Simulated Binary Crossover (SBX) for our crossover operator. SBX is based on One-point crossover. A single crossover point on both parents string is selected. All data beyond that crossover point in either parent is swapped between the two parent organisms. There are two important properties of One-Point Crossover :

• the average of the decoded parameter values is the same before and after the crossover (Figure 4.7); In order to implement this crossover operator for any two parent solutions p1 and p2, a dimensionless spread factor β has been defined as the ratio of the spread of created children solutions c1 and c2 to that of the parent solutions as follows:

β = c1 -c2 p1 -p2 (4.4)
We use the Simulated Binary Crossover (SBX) proposed by Deb and Agrawal in 1995 [START_REF] Deb | Simulated Binary Crossover for Continuous Search Space[END_REF]. SBX was designed with respect to the one-point crossover properties in binary-coded GA.

• Average Property: The average of the decoded parameter values is the same before and after the crossover operation;

• Spread Factor Property: The probability of occurrence of spread factor β ≈ 1 is more likely than any other β value;

Constraints validation

The point with evolutionary algorithms is, they can hardly handle strict constraints.

Technically, there exist different possible methods to have his issue bypassed: A weakness of evolutionary algorithms is: they can hardly handle strict constraints. Technically, there exist different methods to address this weakness:

• by excluding the individuals that are not in line with (or violate) the constraints;

• by fixing faulty individuals through a repair process;

• by preserving the correct individuals through special operators;

• by modifying the search space and guiding the algorithm all the way through (via hyperplanes).

This work focused on the first two methods and assessed their efficiency to eventually select them. Method 1, which excludes out-of-limit individuals, reveals to be inefficient as too many individuals end up excluded. Method 2, that we retain, is designed to fix faulty individuals by running a tabu search algorithm on them (Figure 4.8). The repair process through a tabu search enhanced with a genetic algorithm (NSGA III) is described on Figure 4.9.

The repair process through the tabu search is made possible through the browsing of a list of potential hosts for the virtual machines (Figure 4.10) currently hosted on overloaded servers. The repair process is launched whenever invalid individuals are identified. The fixing method aims at making them comply with the constraints. Every faulty gene found within an individual will then be processed and modified accordingly.

Performance Evaluation

We evaluate the performance of the proposed algorithm at high load when the system is under stress in order to reveal the limitations and capabilities of our genetic algorithm.

We assess performance in terms resolution time, downtime cost, global resource usage, exploitation cost and the size of the induced reconfigurations plans. These simulations are performed on an Intel NUC computer with Intel Celeron 847 (1.1 GHz -2 MB Cache) and 4GB DDR3 RAM.

For each algorithm, we perform simulations on linear and random scenarios. The linear scenarios consists in allocating consumer resources (Virtual Machines) on provider resources (Hypervisors) that can host only two consumer resources. The random scenarios is to host virtual machines that have a random capacity on random capacity hypervisors.

Round Robin Evaluation

We evaluate in this section the Round Robin algorithm. This algorithm checks the pool of hypervisors by cycling through them and allocating virtual machines on each hypervisor during each visit. For each scenario, we study the resolution time, operating and usage costs generated, the number of allocated customer resources, the number of hypervisors used and the filling rates of the hypervisors.

Linear scenario

First we study the resolution time for a solution. Under the linear scenario, we present the resolution time of the Round Robin algorithm in Fig. 4.11. We observe a resolution or execution time that grows exponentially with problem size and hence an algorithm that does not scale. Finally, we show the percentage of hosted virtual machines and the proportion of hypervisor consumed for hosting in Fig. 4. [START_REF] Tjalling | A Note About Kantorovich's Paper, "Mathematical Methods of Organizing and Planning Production&quot[END_REF]. We find that all customers resources are hosted but the provider infrastructure is not consolidated. Indeed, under normal circumstances the round robin algorithm must use all the provider resources. This is explained by the fact that resources are heterogeneous and that the algorithm does not allocate optimally the resources.

Conclusion

The advantage of the Round Robin algorithm is that it can quickly respond to customer requests but unfortunately, the allocation of virtual resources makes it impossible to manage costs efficiently if the demands are heterogeneous. Moreover with 3000 virtual machines and 1500 hypervisors, resolution time is exponential compared to smallest values. The Round Robin algorithm does not efficiently allocate resources in the case of random scenarios either.

Constraint Programming Evaluation

We evaluate in this section the constraint programming method. For each scenario, we study the resolution time, operating and usage costs generated, the number of allocated customer resources, the number of hypervisor used and the filling rates of the hypervisors.

Linear scenario

We report the resolution time of the constraint programming algorithm Fig. 4.17 for the linear scenario and observe as expected an exponential increase in execution time with problem size and consequently the typically scalability issues.

Conclusion

The Constraint Programming method provides an exact solution to the allocation problem but the time resolution is exponential as a function of the problem size. The resolution of the resource allocation problem using constraint programming improves this result but has the same scalability problems. These algorithms provide an exact solution in the case of linear and random scenarios. The limit of constraint programming is approximately around 10000 virtual machines and 5000 hypervisors. Beyond this limit resolution time is excessive for practical purposes and typical applications. The algorithm requires also more memory to run. In addition, these algorithms are not suitable for solving optimization problems with multiple objectives.

Genetic Algorithm Evaluation

This section reports the results of performance evaluation of our modified NSGA II algorithm. The evaluated performance indicators are again: the resolution time, the generated operating and usage costs, the number of allocated customer resources, the number of hypervisor used and the rates at which these hypervisors are consumed. Table 4.2 describes the parameters settings used for this evaluation of NSGA II. We similarly conduct the evaluations for linear and random scenarios. The generated costs or cost performance of NSGA II is depicted in Fig. 4.24 for the linear scenarios. Some customer resources are not served since some hosting resources are not used by the algorithm. NSGA II does not always find optimal solutions. The costs penalty for the NSGA II for the random scenarios is reported in Fig. 4.27. Some customer requests are not served because the algorithm does not always find solutions.

Conclusion

In conclusion, the NSGA II algorithm has a quasi-polynomial resolution time and is more appropriate for heterogeneous environments.

Algorithms comparison

We compare the performance of all the algorithms for the linear and random scenarios.

Linear scenario

The relative resolution time performance of the Constraint programming, the Round Robin and NSGA II is depicted in Fig. 4.29. NSGA II is faster than both Round Robin and Constraint Programming for the linear scenarios. Recall that NSGA II in very few cases does not find a hosting solution while the other algorithms accepted all the user requests as reported in the previous sections. The same behaviour for the algorithms can be observed in Fig. 4.32 where both the Constraint Programming and the Round Robin use all resources and host all the demands while NSGA II becomes less efficient when increasing problem size. In the random scenario, the provider resources and customer requests are drawn with random requested resource requirements and the infrastructure with random capacities.

We use the same metrics to make the comparison: resolution time, cost and resource utilization or consumption.

Extended performance comparison

The performance analysis and evaluation is extended by including the NGSA III contribution of the thesis with the previously evaluated algorithms. The scenarios used for the evaluation involve up to 800 servers (provider resources) and 1600 virtual machines (consumer requested resources). This setting is selected because it corresponds to typical infrastructure sizes most commonly managed by known and popular cloud computing platforms such as: OpenStack, OpenNebula, CloudStack, etc. Providers tend to cluster their infrastructures into domains and data centers and will not use the complete or entire cloud (in thousands of nodes) when searching for placement solutions. they will typically decompose the problem into reasonably sized domains or clusters. We consequently selected viable infrastructure sizes to pursue the performance evaluation.

We also include the genetic algorithm approaches and variants in the assessment and performance comparison: . This is a price penalty to pay for the integration of multi objectives, criteria and constraints in the optimization process compared to Constraint Programming and Round Robin for which the integration of such features is not only complicated but will also degrade execution time for very diminished return.

The genetic algorithms are inherently build for the purpose and turn out to be globally more efficient and capable of trade-offs between the various performance metrics. This is illustrated in Figures 4.38

Conclusion

To conclude, in the case of a linear scenario with provider and customer homogeneous resources, both Round Robin and constraint programming algorithms provide optimal solutions. However, the resolution time is exponential. Our modified NSGA II algorithm is outperformed by these more optimal solutions, depending on problem size.

In the case of random scenario with provider and customer heterogeneous resources, the Constraint Programming algorithm provides optimal solutions. However, it remains relatively slow for a dynamic and flexible system for practical cloud computing platforms.

The Round Robin algorithm is not efficient in heterogeneous environments because resolution time is very high and generates a lot of overall costs compared to the optimal.

Our modified NSGA III algorithm with the Tabu search, one of the key contributions of this thesis, provides the best possible tradeoff of all criteria and can cater for both the user and providers interests.

In the tables below we summarize the advantages and disadvantages of existing algorithms :

Conclusions and Perspectives

Abstract. This chapter summarizes the contributions of the thesis on the cloud resource allocation problem.We describe a number of foreseen perspectives beyond the thesis results and contributions. within a cloud computing platform.

We summarize the research work and contributions of our thesis on resource provisioning over IaaS cloud. This chapter outlines some perspectives for future investigations.

Conclusion et discussions

This thesis addresses cloud resource (services) allocation in relation to the IaaS layer of cloud services. We can summarize the thesis contributions as:

• We have reviewed the existing methods allowing to solve the resource allocation problem within a cloud computing platform. We have focused mainly on combinatorial optimization permutations theory and algorithms performing this type of action. We have identified different metrics to compare these allocation algorithms. The indicators are divided into three groups: technical indicators, business indicators and pricing indicators. We also presented resource allocation algorithms used by the industry (See Chapter 2).

• We have identified the key points of the users and providers business models to consider their affinity constraints and anti affinity between their resources (See Chapter 3).

• We proposed a representation model of a cloud platform equivalent to an extension to the model suggested by Open Cloud Computing Interfaces (OCCI). Our extension is more general description of the properties of compute and network resources.

We have defined affinity and anti-affinity constraints on these resources in order to provide higher availability of the infrastructure resources without degradation (See Chapter 3).

• A genetic algorithm has been modified to speed up convergence to good solutions.

We have improved variation operators (initialization and crossover) through initialization of the individuals respecting the capacity constraints (See Chapter 4).

• We have a feedback loop to check the resource allocation at regular time intervals, resulting in minimized reconfiguration costs.

Future Research Directions

Beyond the main contributions of this thesis, we plan to explore other research areas and improvements of our algorithm.

The tool we have developed to allocate resources in a cloud computing platform supports a set of user requests and infrastructure provider representing the substrate parameters.

We named this tool "HAWKS", standing for Heterogeneous Algorithmic Wide Knowledge Scheduler. HAWKS provides user requests allocation solution optimizing pecuniary costs and downtime costs. The implementation of the model and algorithms was done via the Java 8 language.

HAWKS provides two features. Feature One is an issue-pattern generator whereas Feature Two comes up with a model-based solver.

• Pattern generator is a process generating models describing provider infrastructure and user requests. We can generate problems with random parameters or through a linear distribution.

• Optimization process finds a resource allocation solution in a cloud computing platform. It is possible to use several resolution algorithms like Round Robin, Branch and Bound or genetic algorithms.

• Showing results is a process of recording results such as the fill rate of the hypervisor or the global cost of the cloud computing platform.

These two processes are detailed in the following sections.

B.1 Pattern generator

First program is a Jar file. When executed without defined parameters, help is displayed.

The following command displays "help" while opening a user prompt for input: The following command displays the main menu of pattern generation program:

• Global Cost The costs of the Cloud platform.

• Downtime The service degradation cost on user resources.

• Percent Consumer Hosted Percentage of client resources hosted.

• Percent Provider Used Percentage of provider resources used.

• Fill Rate Average The rate of average filling of the provider resources.

• Fill Rate Median The rate of median filling of the provider resources.

• Fill Variance The variance of the filling rate of provider resources.

• Fill Rate Standard Deviation The standard deviation of the filling rate of provider resources.

• TurnOver The sales turnover generated by the platform.

Sample results of Round Robin algorithm: Comme souvent en Cloud Computing, des travaux ont été repris dans le domaine du calcul haute performance. Ces travaux ont été réalisés pour réussir à placer de manière statique des tâches de calculs représentés sous forme de graphes sur des grilles de multiprocesseurs [START_REF] Kwok | Static scheduling algorithms for allocating directed task graphs to multiprocessors[END_REF]. En se basant sur les travaux précédents, des auteurs ont fourni des méthodes exactes et heuristiques [START_REF] Chekuri | On multi-dimensional packing problems[END_REF] pour allouer des réseaux virtuels à l'aide de sousgraphes au sein d'une architecture de prestation de services.

L'adoption grandissante des solutions de Cloud pour externaliser les couches informa- • Entrées du système représentent les requêtes des utilisateurs qui devront être allouées sur l'infrastructure du fournisseur ainsi que les données du système de monitoring du substrat collecté sur la plate-forme.

• Analyseur de données est un composant qui analyse et transforme les requêtes des utilisateurs composées de ressources et de relations en matrices. Les matrices sont utilisées par le modèle afin de représenter les demandes et les ressources disponibles au sein de l'infrastructure du fournisseur ;

P jl 1 ≤ j ≤ m, 1 ≤ l ≤ h P jl ∈ R + m × h (C.1)
La seconde matrice [Eq.C.2] représente la capacité de chaque attribut d'une ressource de l'utilisateur.

C kl 1 ≤ k ≤ n, 1 ≤ l ≤ h C kl ∈ R + n × h (C.2)
Le nombre d'attributs pour les ressources du fournisseur et des utilisateurs sont les mêmes pour les deux types de ressources (h = h ).

De plus, nous définissons un facteur sur les attributs qui correspond au ratio entre les capacités des ressources matérielles et les capacités des ressources virtuelles. Ces facteurs sont décrits en utilisant une matrice [Eq.C.3] de taille m × h.

F jl 1 ≤ j ≤ m, 1 ≤ l ≤ h F jl ∈ R + m × h (C.
M jl 0 ≤ L M jl < 1 L jl 0 ≤ L jl < 1 Q M jl 0 ≤ Q M jl < 1 Q jl 0 ≤ Q jl < 1 (C.
min Z = min[ m j=1 E j × X ijk + n k=1 U j × X ijk , ∀i=1...g (C.7) + n k=1 C U k ( Q jl C Q k ) × X ijk , ∀i=1...g ∀j=1...m ∀l=1...h (C.8) + n k=1 (X t ijk -X t+1 ijk )M k , ∀i=1...g ∀j=1...m ] (C.9)
Subject To en fonction des demandes utilisateurs:

k=1 C U k ( Q jl C Q k ) × X ijk , ∀i=1

C.4 Conclusion

Ce chapitre résume les travaux de recherche et les contributions de la thèse sur le placement de ressource au sein d'une plate-forme de Cloud Computing. Nous mettons aussi en évidence les points importants qui serviront de base pour de futurs axes de recherche.

C.4.1 Conclusion et discussions

  platforms. Cedric Brandily is a research engineer at Thales European Research Centre for eGov and Secured information Systems (ThereSIS) based in Palaiseau, France. He is also my supervisor at the company. Professor Djamal Zeghlache of Telecom Sud Paris is my thesis advisor and a member of the R3S team of the SAMOVAR UMR 5157 research unit. The CNRS (Centre National de la Recherche Scientifique) research unit SAMOVAR (Distributed Services, Architectures, Modeling, Validation and Network Administration) regroups around 50+ full time faculty and 100 research assistants, from Télécom SudParis and CNRS, working in the field of services, networks and telecommunications. ThereSIS is a private research laboratory involved in research, development and innovation in cloud computing, parallel and distributed computing.

Figure 1 . 1 :

 11 Figure 1.1: Various players within Cloud platform

Figure 1 . 2 :

 12 Figure 1.2: Thesis organization

  of the art Abstract. This chapter reviews the relevant state of the art for the resource allocation and scheduling problem addressed in this thesis. The multi-dimensional packing and scheduling problems and their current academic and industrial implementations and combinatorial partial permutations used to treat such resource allocation problems are presented. Typical performance indicators used to assess and evaluate solutions for cloud resources allocation and scheduling are described. The indicators are classified into three main categories: technical, business and pricing indicators. We present the most commonly used exact and heuristic algorithms with or without constraints to set the background for our proposals and include the commercial or cloud services providers solutions.

Definition 2 . 1 .

 21 Vector Bin Packing. Given a set of n rational vectors V = {v 1 , . . . , v n } from [0, 1] d where d is the number of dimension. We have to find a partition of the set into sets B = {B 1 , . . . , B m } whose sum of its vectors is at most equal to 1 in every dimension, m j=1 v ∈ B v j ≤ 1 ∀v ∈ V . The objective is to minimize the number of bins needed to allocate n resources.

  We have two capacity variables for items and for bins. W I d,m representing the weight of item n on the dimension d. W B d,m representing the weight of bin m on the dimension d. U j = 1 if bin j is used.

  1, a packing (resp. covering) integer program PIP (resp. CIP) seeks to maximize (resp. minimize) c T .x subject to x ∈ Z m + and A x ≤ b (resp. A x ≥ b). Furthermore if A ∈ {0, 1} n×m , we assume that each entry of b is integral. We also define B = min i b i .

  proved the algorithm over time. Other algorithms such as the Branch and Cut (Padberg et Rinaldi, 1991) [51], Branch and Price (M. Desrochers, F.M. Solomon. 1989) [52] were proposed. Combining these two techniques leads to the "Branch and Cut and Price" method.

Figure 2 . 1 :

 21 Figure 2.1: Branch And Bound Decomposition

Figure 2 .

 2 Figure 2.1 shows a branch and bound example of the cloud resource allocation resolution with three consumer and two provider resources.

2 .

 2 It scans hypervisors one by one and allocates resources when possible; 3. Algorithm stops when the queue is empty or when hypervisors are full. This is an allocation and scheduling algorithm so simple but it can be improved to address workloads or other more complex models[START_REF] Perez-Espinoza | Distribution and load balancing strategies in private cloud monitoring[END_REF] [57] [58][START_REF] Alnowiser | Enhanced weighted round robin (ewrr) with dvfs technology in cloud energy-aware[END_REF].

Figure 2 . 2 :

 22 Figure 2.2: Round Robin concept

Figure 2 .

 2 Figure 2.3 shows an example of the resolution with four provider resources.

Figure 2 . 3 :

 23 Figure 2.3: Filter algorithm concept

Figure 2 . 4 :

 24 Figure 2.4: Allocation Problem Representation with GA

Figure 2 . 5 :

 25 Figure 2.5: Distributed algorithm concept

Figure 2 .

 2 [START_REF] Andrikopoulos | Collaborative, dynamic and complex systems -modeling, provision and execution[END_REF] shows an example with four data centers and one user request composed of three resources. This request is processed by a serving node and resources are allocated in a transparent manner on different data centers.

Figure 2 . 6 :

 26 Figure 2.6: Nova Logical Architecture

Figure 2 . 7 :

 27 Figure 2.7: Filter Scheduler in nova-scheduler

2. 8 ]

 8 . Each region has multiple, isolated locations known as Availability Zones. Amazon EC2 provides you the ability to place resources, such as instances, and data in multiple locations. Resources are not replicated across regions unless you do so specifically.

Figure 2 . 8 :

 28 Figure 2.8: AWS Regions and Availability zones

Figure 2 . 9 :

 29 Figure 2.9: vSphere Dynamic Resource Scheduler principle

Figure C. 3

 3 Figure C.3 depicts the modules that compose a typical cloud resource allocation system.

Figure 3 . 1 :

 31 Figure 3.1: Cloud Resource Allocation process

Figure 3 . 2 :

 32 Figure 3.2: Spine and Leaf Modern Architecture of datacenter

Figure 3 . 3 :

 33 Figure 3.3: Virtual resource allocation through Cloud Computing layers

Figure 3 .

 3 Figure 3.4 describes the resource attributes to a datacenter. Attributes to servers and network liaisons and switches come to be detailed here. This way, modeling a server will be expressed in CPU number and capacity, RAM and HDD capacities, and NIC maximum bandwith. The server will be linked to specific operating costs. Network liaisons are described through bandwidth and flow rate. Switches feature attributes like RAM capacity, switching bandwith and forwarding rate.

Figure 3 .

 3 Figure 3.5 shows resource attributes to a user request. A request is a user query involving

Figure 3 . 4 :Figure 3 . 5 :

 3435 Figure 3.4: Infrastructure Resources Attributes

CXX

  kl × X ijk ≤ P jl F jl , ∀l = 1...h, ∀i = 1...g (3.16) ijk = 1, ∀i = 1...g, ∀j = 1.ijk = 1, ∀j = 1...m (3.20) could solve the problem as an integer linear programming using the model proposed to minimize the costs in equations 3.13 to 3.15 subject to the constraints specified in equations 3.16 to 3.21. But we favor the use of heuristic and evolutionary algorithms since the ILP solutions will not scale with problem size.

  between the different objectives to optimize. It is vital to identify the best compromise to define an ordered relationship between these elements. The most famous and most used is the dominance relation in the Pareto sense. All the best compromise is called the Pareto front, the surface of compromise or all effective solutions. This set of solutions is a balance because no improvement can be made on an objective without degradation of at least one other objective. Pareto solution is to get the Pareto front P F or approximate the Pareto frontier P F * .

  This chapter presents our proposed cloud (IaaS) resource allocation algorithm to address jointly the requirements and interests of consumers and providers. We first describe the graph representing the user request and the provider infrastructure and decompose in a second stage the graph into the matrices proposed in the previous chapter.The chapter describes finally our genetic algorithm (based on NSGA III) and the associated operators and reports the results of performance evaluation and comparison with state of the art algorithms such as Round Robin and Branch-and-Bound.This chapter presents the initial problem model in the form of a user-modifiable graph used as a starting point by our genetic algorithm based on NSGA II. The initialization operator proposed to improve convergence of the population towards a viable solution is also presented. The chapter describes the used Crossover and mutation operators, specifically simulated binary crossover (SBX) and polynomial mutation (PM), and their generic operation. The performance of the proposed genetic algorithm is compared with state of the art resource allocation algorithms. This chapter is divided into three sections. Section 4.1 describes how a graph is broken down into the modeling matrices as explained in Chapter 3. The implementation of the NSGA II and NSGA III genetic algorithms is explained in Section 4.2. Section 4.3 provides an assessment of performance of selected algorithms to be compared with our NSGA III algorithm enhanced with a tabu search. The performance evaluation of each algorithm is reported on a per section basis for the Round Robin, the Constraint Programming, NSGA II, NSGA III, NSGA III with constraint solver and NSGA III enhanced with a tabu search (our advocated and retained solution and also one of our main contributions). The last section conducts the actual comparison of the algorithms, readers familiar with the basic algorithms can skip the first sections and proceed directly to Section 4.3.4 for the comprehensive performance comparison between our enhanced NSGA III algorithm and the other algorithms.

4. 1 .

 1 This graph provides the connectivity and the topologies of the requests and infrastructure graphs. The graph representation specifies three types of relationships between resources: standard connectivity between nodes, affinity and anti-affinity relationships between nodes. This graph representation (right side of Figure 4.1) is in turn converted into adjacency matrices as shown in the matrices example below that reflect the connectivity and topology of the example depicted previously in 4.1. The algorithms use the matrix representations as input to find a viable resource allocation solution to host the requests in the provider infrastructure. To facilitate to the users the specification of their requests, we designed a graphical user and administrator interface as shown in Figure 4.2. The interface uses the Neo4j NoSQL (Not only SQL) data base to visualize the infrastructure and hosted resources graphs and charts comparing quality of a new resource allocation with previous allocations.

Figure 4 . 1 :Figure 4 . 2 :

 4142 Figure 4.1: Graph representation example

  Figure 4.3.

Figure 4 . 3 :

 43 Figure 4.3: Matrix representation of resources

Figure 4 . 4 :

 44 Figure 4.4: Genetic Algorithm Principle

Figure 4 . 5 :

 45 Figure 4.5: New Genetic Algorithm Principle

Figure 4 . 6 :

 46 Figure 4.6: New Initialization Operator Principle

Figure 4 . 7 :

 47 Figure 4.7: From the article Simulated Binary Crossover for Continuous Search Space [1] describing the crossover process

  no value outside the specified range [a, b] is created by the mutation operator where a and b are lower and upper bounds of the variable. Polynomial mutation (PM) operator attempts to simulate the offspring distribution of binary-encoded bit-flip mutation on real-valued decision variables. Similar to SBX, PM favors offspring nearer to the parent. The distribution index controls the shape of the offspring distribution. Larger values for the distribution index generates offspring closer to the parents.

Figure 4 . 8 :Figure 4 . 9 :

 4849 Figure 4.8: Tabu Search integration within NSGA

Figure 4 . 10 :

 410 Figure 4.10: Finding the nearest valid neighbor

Figure 4 . 11 :

 411 Figure 4.11: Round Robin Resolution Time with linear scenarios

Figure 4 . 12 :

 412 Figure 4.12: Round Robin Global Cost with linear scenarios

Figure 4 . 13 :

 413 Figure 4.13: Round Robin Resource Utilization with linear scenarios

Figure 4 . 14 :

 414 Figure 4.14: Round Robin Resolution Time with random scenarios

Figure 4 . 15 :

 415 Figure 4.15: Round Robin Resolution Time with random scenarios

Figure 4 . 16 :

 416 Figure 4.16: Round Robin Resolution Time with random scenarios

Figure 4 . 17 :

 417 Figure 4.17: Constraint Programming Resolution Time Comparison with linear scenarios

Figure 4 . 18 :Fig. 4 .

 4184 Figure 4.18: Constraint Programming Global Cost with linear scenarios

Figure 4 . 19 :

 419 Figure 4.19: Constraint Programming Resource Used with linear scenarios

Figure 4 . 20 :

 420 Figure 4.20: Constraint Programming Resolution Time with random scenarios

Figure 4 . 21 :

 421 Figure 4.21: Constraint Programming Global Cost with random scenarios

Figure 4 . 22 :

 422 Figure 4.22: Constraint Programming Resource Used with random scenarios

4. 3 . 3 . 1 Fig. 4 .

 3314 Fig. 4.23 depicts the results of performance evaluation for the NSGA II resolution time for the linear scenario. The resolution time is quasi-polynomial in problem size and this is in line with its O(M N 2 ) complexity where M is number of objectives and N the size of the population.

Figure 4 . 23 :

 423 Figure 4.23: Modified NSGA II Resolution Time with linear scenarios

Figure 4 . 24 :Fig. 4 .

 4244 Figure 4.24: Modified NSGA II Global Cost with linear scenarios

Figure 4 . 25 :

 425 Figure 4.25: Modified NSGA II Resource Used with linear scenarios

Figure 4 . 26 :

 426 Figure 4.26: Modified NSGA II Resolution Time with random scenarios

Figure 4 . 27 :Fig. 4 .

 4274 Figure 4.27: Modified NSGA II Global Cost with random scenarios

Figure 4 . 28 :

 428 Figure 4.28: Modified NSGA II Resource Used with random scenarios

Figure 4 . 29 :

 429 Figure 4.29: Modified NSGA II Resolution Time comparison with linear scenarios

Figure 4 . 30 :

 430 Figure 4.30: Modified NSGA II Global Cost comparison with linear scenarios

Figure 4 . 31 :

 431 Figure 4.31: Modified NSGA II Customer Resource Hosted comparison with linear scenarios

Figure 4 . 32 :

 432 Figure 4.32: Modified NSGA II Provider Resource Used comparison with linear scenarios

Fig. 4 .

 4 Fig. 4.33 depicts the results of the resolution time (execution time) comparison and shows that the Round Robin becomes less efficiency than in the linear case. Constraint Programming and Round Robin have exponential resolution time and do not scale. The NSGA II resolution time is polynomial with problem size and has improved scalability especially if we recall that it uses multiple objectives while the other algorithms are single objective algorithms.

Figure 4 . 33 :

 433 Figure 4.33: Resolution Time comparison with random scenarios

Figure 4 . 34 :

 434 Figure 4.34: Global Cost comparison with random scenarios

Figure 4 . 35 :

 435 Figure 4.35: Customer Resource Hosted comparison with random scenarios

Figure 4 . 36 :

 436 Figure 4.36: Provider Resource Used comparison with random scenarios

Figure 4 .

 4 Figure 4.37 indicates that the Constraint Programming is the fastest algorithm capable of finding solutions in fractions of seconds since it uses constraints that considerable speed up execution or resolution time. The Round Robin method is slower because it cycles through the providers resources to achieve allocation of resources in a systematic fashion and hence the process takes more time. The genetic algorithms are even slower because they need to generate populations iteratively. The NSGA III with the tabu search, our advocated and proposed algorithm, improves performance compared to the NSGA III with Constraints Programming with execution times in the order of tens of seconds (12.5 sec for the largest problem size). This is a price penalty to pay for the integration

  , 4.39 and 4.40 where the genetic algorithms do not use all the infrastructure resources to serve the user requests, host all the requests and for the NSGA III with Constraints Programming and NSGA III with the Tabu search do not violate any constraint. This is confirmed by Figures 4.42and 4.41 where the NSGA-III with the Tabu search achieves the best performance metrics trade off since its induced cost performance is close to the Constraints Programming cost (the smallest cost) and more importantly NSGA III has the smallest rejection rate (around 10% for NSGA III versus 40% to 90% for all other algorithms. Note also that the genetic algorithms embed multiple objectives in their optimization process and thus fulfill the requirements for the joint optimization of customers and providers objectives whose interests are taken into account in the model.

Figure 4 . 37 :Figure 4 . 38 :

 437438 Figure 4.37: Comparison of means of Resolution Time with random scenarios

Figure 4 . 39 :

 439 Figure 4.39: Consumer Resources Hosted with random scenarios

Figure 4 . 40 :

 440 Figure 4.40: Comparison of means of Exceeding constraints with random scenarios

Figure 4 . 41 :

 441 Figure 4.41: Rejection rate comparison with increasing problem size

Figure 4 . 42 :

 442 Figure 4.42: Comparison of means of costs generated by algorithms

Table 4 . 4 :

 44 Performance Comparison of allocation algorithms

$

  java -jar GenAllocProb . jar Generate file with problem + -------HELP -------+ GenAllocProb . jar -file p a t h T o F u tu r e P r o b l e m -file p at h T o F u t u r e P r o b l e m When user provides the name of the future model file, the program displays the main menu. From the main menu, you can save resources describing the provider's infrastructure, user requests and the business model of resources. Action Number Four can generate a completely random pattern without saving resources as before; Or it is possible to generate a model with a linear distribution with the previously saved resources.

C. 1 Introduction

 1 c e n t C o n s u m e r H o s t e d P e r c e n t P r o v i d e r U s e d F i l l R a t e s A v e r a g e F i l l R a t e s M e d i a n F i l l R a t e s V a r i a n c e F i l l R a t e sLa recherche opérationnelle dans le domaine de l'allocation de ressource informatique est ancienne et vaste. Les premières questions à ce sujet se sont posées sur l'allocation des bytes sur une plate-forme physique au sein d'un disque dur. Depuis, et suivant les évolutions du monde de l'informatique, les problèmes de placement de ressources ont migré vers des ressources représentant des tâches de calculs sur des grilles de serveurs. Ces méthodes d'allocation de tâches fonctionnent efficacement, mais elles ne peuvent pas intégrer les relations complexes qui peuvent exister entre les consommateurs et les fournisseurs dans un environnement métier. Un nouveau changement de paradigme a alors été opéré entre les plate-formes mainframe et les grilles de serveurs distribués pour tenter d'obtenir plus de flexibilité tout en gérant la complexité des contraintes métiers. Ce nouveau paradigme a pris le nom commercial de : Cloud Computing. Le Cloud Computing est un nouveau paradigme, dans lequel diverses ressources telles que les infrastructures ou les composants logiciels sont fournis en tant que services, et qui connaît une grande popularité. Dans une infrastructure Cloud de type public, les fournisseurs louent des services ou de la capacité suivant des abonnements ou via un principe de paiement à l'utilisation à des clients qui consomment ces services. Les consommateurs de ces services interagissent avec la plate-forme Cloud grâce à une interface utilisateur ou une interface de programmation (API : Application Programming Interface) gérées par le fournisseur. Le Cloud Computing a eu de multiples définitions en fonction de l'évolution du paradigme et des personnes le décrivant comme les chercheurs ou l'industrie. Ainsi, la définition la plus couramment utilisée est celle du National Institute of Standards and Technology (Institut national des normes et des technologies, NIST). Ainsi, Peter Mell et Tim Grance définissent le Cloud Computing comme suit: "Cloud Computing is a model for enabling ubiquitous, convenient, on-demand network access to a shared pool of configurable Computing resources (e.g., networks, servers, storage, applications, and services) that can be rapidly provisioned and released with minimal management effort or service provider interaction. This Cloud model is composed of five essential characteristics, three service models, and four deployment models." [2]. Cette définition peut trouver son équivalent en français ainsi : "Le Cloud Computing est l'accès via un réseau de télécommunications, à la demande et en libre-service, à des ressources informatiques partagées configurables.". Les cinq caractéristiques [3] d'une plate-forme de Cloud Computing sont le provisionnement à la demande des ressources et des services où la Qualité de Services est garantie aux utilisateurs. Les ressources ou les services au sein d'une plate-forme peuvent être configurés automatiquement, orchestrés et consolidés pour présenter un point d'accès unique rendu aux utilisateurs de la plate-forme. Une plate-forme de Cloud Computing doit être souple pour s'adapter aux diverses exigences d'un nombre potentiellement important d'utilisateurs. Il existe plusieurs modèles de déploiement [4] tels que le Cloud privé qui fonctionne uniquement pour une seule organisation. Un nuage est appelé "Public Cloud" lorsque les services sont rendus sur un réseau qui est ouvert au public. Une fédération de Cloud partage l'infrastructure parmi plusieurs organisations d'une communauté spécifique avec des préoccupations communes (la sécurité, la conformité ou la juridiction). Enfin, un Cloud hybride est une composition de deux ou plus, d'infrastructures distinctes de Cloud (privé, communautaire ou public). Les trois modèles de services [5] sont Software as a Service, SaaS, qui offre aux consommateurs des applications fonctionnant sur une infrastructure de Cloud. Le modèle de service suivant, Platform as a Service, PaaS, permet aux consommateurs de déployer grâce à l'infrastructure Cloud du fournisseur des applications créées en utilisant des langages de programmation, des bibliothèques, des services et des outils pris en charge par le fournisseur. Le dernier modèle est l'infrastructure en tant que service, IaaS. Il offre des ressources supplémentaires, comme une bibliothèque de machines virtuelles avec des images disques, brutes (bloc) et du stockage de fichiers, les pare-feu, les équilibreurs de charge, les adresses IP, les réseaux locaux virtuels (VLANs) tout ceci dans un paquetage vendu aux clients [6]. Les fournisseurs de plate-formes Cloud de type IaaS fournissent des ressources à la demande grâce à leurs bassins d'hyperviseur installés dans leurs centres de données. Mais les clients et les fournisseurs n'ont pas les mêmes objectifs sur la plate-forme. Pour la connectivité à ces plate-formes de Cloud, les clients peuvent utiliser Internet ou des réseaux porteurs (réseaux privés virtuels dédiés). Dans ce mémoire et notre thèse, mise en oeuvre et tests de recherche seront menés au sein d'une plate-forme de Cloud Computing de type IaaS privé. Cependant, le point crucial dans le paradigme Cloud Computing se trouve dans la ressource mise en commun avec d'autres acteurs ; et cette élasticité rapide n'est pas d'évidence. Malgré l'argument voulant qu'une plate-forme de Cloud Computing fonctionne automatiquement et sans exiger d'interaction humaine, la multiplicité de clients et des contraintes de la part des fournisseurs l'a rendue de plus en plus difficile à gouverner et il est devenu malaisé de contrôler l'infrastructure entière ainsi que la totalité des exigences, en temps réel, venant des clients. Les nouveaux défis du paradigme Cloud vont s'orienter vers la sécurité, la disponibilité et la gestion des ressources qui doivent être soigneusement considérées pour répondre à des exigences d'instanciation et d'hébergement ainsi qu'au besoin d'évolutivité et de temps réel prenant en considération les intérêts de tous les utilisateurs. Au sein d'une plate-forme de Cloud, les divers acteurs peuvent agir l'un sur l'autre à différents niveaux et sur différentes couches. Désormais, il y a deux acteurs majeurs pouvant interagir entre eux. Le client, qui consomme des ressources et des services, et le fournisseur, qui partage ou loue son infrastructure tout en fournissant l'entretien de celle-ci. Typiquement, un utilisateur placera des services ou des ressources sur demande sur différentes couches telles que le IaaS, PaaS ou SaaS. En termes simples, dans une infrastructure de Cloud Computing, il y a deux acteurs génériques (Voir C.1). En premier lieu, il y a le fournisseur de services. En second lieu, le client de ces services. Malheureusement, les enjeux stratégiques pour chaque acteur sont différents. En outre, les consommateurs veulent des services de plus en plus complexes tout en payant moins. D'autre part, les fournisseurs doivent relever le défi de l'informatique écologique, tout en réduisant les frais d'exploitation et assurant une infrastructure plus gouvernable.

Figure C. 1 :

 1 Figure C.1: Organisation du mémoire

Figure C. 3 :•

 3 Figure C.3: Architecture du module d'allocation de ressource au sein d'une plateforme Cloud

Figure C. 4 :•••••••

 4 Figure C.4: Architecture d'un datacenter en Spine / Leaf

Figure C. 5 :

 5 Figure C.5: Allocation des ressources virtuelles au sein d'une plateforme de Cloud Computing

Figure C. 6 :

 6 Figure C.6: Attributs des Ressources d'Infrastructure

6 )X

 6 Toutes les variables et les constantes du modèle utilisé sont listées dans le tableau C.1. Le modèle est amélioré avec toutes les relations nécessaires décrivant des liens entre les ressources et des contraintes exprimées grâce à des inégalités et des égalités. La contrainte de Colocalisation au sein d'un même datacenter est défini par [Eq.C.11] et s'assure que les ressources consommateurs sont hébergées au sein d'un même datacenter. ijk = 1, ∀j = 1...m (C.11) La contrainte de Colocalisation au sein d'un même serveur vérifie si la somme des produits des ressources consommateurs allouées est strictement égale à un [Eq.C.12]. Elle garantit la colocalisation au sein d'un même serveur : séparation totale est exprimée grâce à la somme des ressources consommateurs allouées sur les datacenters et les serveurs. Cette contrainte doit être égale à un comme indiqué par [Eq. C.13] :

CXXX

  kl × X ijk ≤ P jl F jl , ∀l = 1...h, ∀i = 1.ijk = 1, ∀j = 1...m (C.11) ijk = 1, ∀i = 1...g, ∀j = 1...m (C.13) ijk = 1, ∀j = 1...m (C.15) Les fonctions objectifs et les paramètres sont tous convertis à un coût monétaire équivalent afin qu'ils puissent être regroupés en une fonction "objectif global" Nous détaillons toutes les fonctions objectives. Nous rassemblons toutes les fonctions objectives en convertissant ces différentes valeurs en un coût pécunier. La première fonction est le calcul du coût global d'une plateforme donnée par [Eq.C.7]. Cette fonction prend en compte les coûts d'exploitation et d'utilisation des ressources. Pour chaque ressource du fournisseur, E est le coût d'exploitation d'un hyperviseur j. Pour chaque ressource du consommateur, la variable U représente le coût de consommation d'une ressource k. m j=1 E j × X ijk + n k=1 U j × X ijk , ∀i=1...g (C.7) Le second objectif [Eq.C.8] représente les coûts d'une interruption de service ou la pénalité en cas de baisse du niveau de service demandé par l'utilisateur sur les ressources du fournisseur hébergeant les services. Sur la base des évaluations de la performance, les auteurs [110] [111] prouvent, par une démarche empirique, que la qualité du service des ressources consommateur diminue de façon exponentielle avec l'augmentation de la charge de travail des ressources du fournisseur. Le coût total d'indisponibilité est la somme de chaque coût d'indisponibilité C U k de la ressource consommateur k quand le niveau de service C Q k garanti n'est pas respecté.

  n

Figure C. 9 :

 9 Figure C.9: Recherche tabou pour la réparation des individus de NSGA

Figure C. 10 :

 10 Figure C.10: Trouve le plus proche voisin respectant les contraintes

Figure C. 11 :

 11 Figure C.11: Comparaison du temps de résolution avec des scénarios linéaire

Figure C. 12 :

 12 Figure C.12: Comparaison des coûts globaux avec des scénarios linéaire

Figure C. 13 :

 13 Figure C.13: Comparaison du pourcentage de ressources du consommateur hébergées avec des scénarios linéaires

Figure C. 14 :

 14 Figure C.14: Comparaison du pourcentage de ressources du fournisseur utilisées avec des scénarios linéaires

Figure C. 17 :

 17 Figure C.17: Comparaison du pourcentage de ressources du consommateur hébergées avec des scénarios aléatoires

Figure C. 18 :Table C. 3 :

 183 Figure C.18: Comparaison du pourcentage de ressources du fournisseur utilisées avec des scénarios aléatoires

Figure C. 19 :

 19 Figure C.19: Comparaison de la moyenne du temps de Résolution avec des scenarios aléatoire

Figure C. 20 :Figure C. 23 :

 2023 Figure C.20: Taux d'tilisation des serveurs avec des Scenarios aléatoires

Figure C. 24 :

 24 Figure C.24: Comparaison des moyennes de coûts générés par algorithmes

•

  Ce mémoire de thèse aborde les enjeux de recherche dans le domaine du placement de ressource (Services) au sein d'une plate-forme de Cloud Computing de type Infrastructure as a Service (IaaS).Nous mettons en évidence dans les prochains paragraphes nos principales contributions de recherche effectuées durant ces années de travaux :• Nous avons passé en revue les méthodes existantes permettant de résoudre les problèmes d'allocation au sein d'une plate-forme de Cloud Computing. Nous nous sommes intéressés principalement à la théorie des permutations en optimisation combinatoire et aux algorithmes effectuant ce type d'action. Nous avons identifié les différentes métriques permettant de comparer ces algorithmes de placement entre eux. Ces indicateurs sont divisés en trois groupes : les indicateurs techniques, les indicateurs business et les indicateurs de tarification. Nous terminons en présentant les algorithmes de placement qui sont actuellement utilisés par les industriels. (Voir Chapitre 2 ) • Nous avons identifié les points-clés du modèle d'affaires des utilisateurs et du fournisseurs permettant de prendre en compte leurs contraintes d'affinité et d'antiaffinité entre leurs ressources (Chapitre 3 ou en français C.2). • Nous proposons un modèle de représentation d'une plate-forme de Cloud comme une extension au modèle proposé par l'Open Cloud Computing Interface (OCCI). Notre extension apporte une description plus généraliste de ce que sont les propriétés d'une ressource de calcul ou de réseaux. Nous n'établissons pas de distinctions entre ces deux types de ressource dans la définition de leur capacité. Nous définissons des contraintes d'affinité et d'anti-affinité sur ces ressources afin d'obtenir, grâce à elles, une meilleure disponibilité des ressources sans dégradation (Chapitre 3 ou en français C.2).• Un algorithme génétique modifié afin de permettre une convergence plus rapide.Nous avons amélioré les opérateurs de variation (initialisation et croisement) en permettant une initialisation des individus qui respectent les contraintes de capacité (Chapitre 4 ou en français C.3).• Nous introduisons une boucle de rétroaction afin de vérifier le placement des ressources à des temps réguliers en minimisant les coûts de déplacements.C.4.2 Perspectives et axes futurs de rechercheAu-delà des principales contributions de cette thèse, nous prévoyons d'explorer un certain nombre d'axes de recherche et d'améliorations.• L'axe de recherche important pour la suite de nos travaux repose sur la proposition d'un plan de reconfiguration optimale entre le placement actuel des ressources sur la plate-forme de Cloud Computing et le nouveau placement fourni par notre algorithme. C'est un problème aussi complexe que de trouver le placement des ressources. Nous utilisons un algorithme génétique pour trouver une solution approchée prenant en compte les intérêts de chaque acteur. L'inconvénient des algorithmes génétiques est leur lenteur de convergence. Il conviendrait de réaliser des expérimentations avec d'autres algorithmes d'optimisation. L'avantage des algorithmes génétiques, est qu'ils sont plus facilement parallélisables en parcourant l'espace des solutions sur différents serveurs. • Nous avons choisi d'utiliser dans nos travaux une représentation vectorielle et matricielle des ressources et de l'allocation. Cette méthode de représentation des informations est bas-niveau. Une représentation plus générique et plus haut niveau sous la forme de graphe de Johnson est une piste à prendre en compte afin d'améliorer la complexité en temps d'un algorithme de placement des ressources. • Nous pourrions définir et modéliser les besoins business grâce à une prise en compte des capacités réseaux dans l'application des contraintes d'affaires des utilisateurs et du fournisseur de service au niveau du placement des ressources.

Table 2 .

 2 1 lists the Vector Bin Packing

	Problem variables:

Table 2 . 1 :

 21 Vector Bin Packing Problem Variables

	x i,j Boolean variable indicating whether item i is assigned to bin j
	W I d,i	Weight of item i on the dimension d
	W B d,j	Weight of bin j on the dimension d
	U j	Boolean variable indicating that Bin j is used

Table 2

 2

.2 gives an example of the Vector Scheduling Problem variables:

Table 2 . 2

 22

: Vector Scheduling Problem variables

Table 2 .

 2 3 provides an example of the Packing Integer Program variables:

Table 2 . 3 :

 23 Packing Integer Program variablesx i,j Boolean variable indicating whether item i is assigned to knapsack j P i

		Profit of item i
	W I i W K j	Weight of item i

Table 2 . 4 :

 24 Example solutions of partial permutation without repetition{vm 1 , vm 2 } {vm 2 , vm 3 } {vm 3 , vm 1 } {vm 2 , vm 1 } {vm 3 , vm 2 } {vm 1 , vm 3 }

Table 2 . 5 :

 25 Example solutions of partial permutation with repetition{hyp 2 , hyp 2 , hyp 2 } {hyp 1 , hyp 1 , hyp 1 } {hyp 1 , hyp 2 , hyp 2 } {hyp 1 , hyp 1 , hyp 2 } {hyp 2 , hyp 1 , hyp 1 } {hyp 2 , hyp 2 , hyp 1 } {hyp 2 , hyp 1 , hyp 2 } {hyp 1 , hyp 2 , hyp 1 }

	This partial permutation with repetition is a design that best represents our resource
	allocation problem in a cloud platform.

Table 2 .

 2 6 below describes variables of Constraint Programming Problem example:

Table 2 . 6 :

 26 Variables description of Constraint Programming Problemx i,j Boolean variable indicating whether item i is assigned to bin j C I

	i C B j	Capacity of item i Capacity of bin j
	U

j Boolean variable indicating that Bin j is used

Table 2 . 7 :

 27 Comparison of allocation algorithms

	Round Robin	Constraint Programming	NSGA-II	Filtering Algorithm	Decentralized Scheduling
	Compliance
	with cons-
	traints
	Resource
	Scalability
	Integrity of
	customer
	requests
	Control
	over infra-
	structure

  The company has the notable accomplishment of having produced the first x86 architecture virtualization that was workable and suitable for consumer use. VMware virtualization is based on the ESX/ESXi bare metal hypervisor, supporting virtual machines. ESXi (Elastic sky X Integrated) is also the VMware's enterprise server virtualization platform. The term "VMware" is often used in reference to specific VMware Inc. products such as vSphere and VMware Workstation.

Table 3 . 1 :

 31 Cloud resources allocation model variables Provider substrate and requested resources G Set of available datacenters G = {1, ..., g} M Set of available servers M = {1, ..., m} N Set of requested resources N = {1, ..., n} H Set of available attributes for each resource H = {1, ..., h} Capacities matrices P jl Capacity of provider resource j for attribute l C kl Capacity of requested resource k for attribute l F jl Capacity factor of attribute l on provider resource j Mapping model X ijk Boolean variable indicating whether requested resource k is assigned to provider resource j in datacenter i Quality of service matrices and vectors L jl Load of attribute l on provider resource j L M jl Maximum load of attribute l on provider resource j Q M jl Maximum quality of service for attribute l on provider resource j Q jl Quality of service for attribute l on provider resource j C Q

k

  Quality of service guaranteed by the provider on customer resource kCosts vectors E j Operational expense for a provider resource j U j Usage cost for each customer resources hosted on a provider resource j C U

k

  Cost of downtime for a resource k M k Migration cost of a customer resource k

Table 4 . 1 :

 41 Variables used in our algorithm

		Algorithm variables
	P op	Set of individual P op = {1, ..., p}
	S	Chromosome: Set of gene N = {1, ..., s}
	DC j	specifies the datacenter from server j
	N ODEused

j Boolean variable if a node is used DCused i Boolean variable if a datacenter is used

Table 4 . 2 :

 42 NSGA II Default parameter

	Parameter	Value
	populationSize	100
	sbx.rate	0.70
	sbx.distributionIndex 15.00
	pm.rate	0.20
	pm.distributionIndex 15.00
	maxEvaluations	10000

  The parameters used by NSGA II and NSGA III are listed inTable 4.3.

	Parameter	Value
	populationSize	100
	Number of evaluations 10000
	sbx.rate	0.70
	sbx.distributionIndex	15.00
	pm.rate	0.20
	pm.distributionIndex	15.00
	Table 4.3: NSGA II and III settings
	The performance results are reported in Figures 4.37, 4.38, 4.39, 4.40, 4.41 and 4.42 for
	respectively resolution (or execution) time, percentage of used infrastructure resources
	(or hosts/servers), amount of hosted consumer resources (VMs), number of constraints
	violations (when limits are exceeded), rejection rate and costs induced by each algorithm.
	1. Constraint Programming
	2. Round Robin
	3. NSGA II
	4. NSGA III
	5. NSGA III with tabu search
	6. NSGA with constraints solver

  tiques "non-métier" pour les clients amène de nouveaux usages et de nouvelles opportunités sur les infrastructures porteuses. Dans l'optique d'intégrer ses nouvelles opportunités, les fournisseurs de services doivent mettre à disposition des solutions de plus en plus complexes afin de fournir un haut niveau de qualité de service tout en tentant de réduire les coûts, du fait de l'accroissement du nombre d'acteurs sur le marché de l'infrastructure en nuage qui induit une concurrence accrue. La gestion de ces nouveaux usages et de ces nouvelles opportunités est une problématique majeure pour les fournisseurs de services. En effet, les clients recherchent la plus haute disponibilité possible, ce qui est antinomique avec la forte concurrence sur le marché du Cloud Computing qui impose aux fournisseurs de services de réduire leurs coûts. Dès lors que critères et objectifs du problème sont connus, le problème peut être modélisé. Pour atteindre cet objectif, il faudra dans un premier temps dresser un état de l'art des La première contribution est un nouveau modèle de représentation des ressources se voulant générique et que nous appliquons à une plate-forme de Cloud Computing de type Infrastructure as a Service. Notre représentation des données est une extension de l'interface proposée par l'Open Cloud Computing Interface (OCCI) qui permet de décrire Notre objectif est de fournir une solution d'allocation des ressources au sein d'une plateforme de Cloud Computing en intégrant les intérêts des différents acteurs. Pour atteindre cet objectif, nous avons besoin de créer un nouveau modèle matriciel de représentation des ressources. Ce modèle devra prendre en compte l'ensemble des besoins des consommateurs de service et le substrat décrivant l'infrastructure du fournisseur. Nous fournirons une formulation mathématique du problème en intégrant les relations entre les ressources tout en respectant les intérêts de l'ensemble des acteurs d'une plate-forme de Cloud Computing sans failles ni comportement paradoxal. Nous proposons un modèle suffisament générique décrivant des ressources de l'ensemble des couches d'une plate-forme de Cloud Computing comme Infrastructure as a Service (IaaS), Platform as a Service (PaaS) ou Software as a Service (SaaS). Mais nous nous concentrons principalement sur le placement de ressources au sein d'un IaaS. Nous étudierons la performance du placement au sein d'un IaaS qui permet d'allouer des ressources de calcul (machine virtuelle), de stockage ou de services réseaux sur des hyperviseurs. En outre, l'accent se porte sur la satisfaction des objectifs des consommateurs et du fournisseur tout en assurant la qualité de service requise pour les clients.

	définies dans la section 2.2 et avec un autre algorithme utilisé dans l'industrie (section C.2 Modélisation des problèmes de placement
	2.4).
	Dans le dernier Chapitre 5 nous résumons nos contributions dans le domaine de l'allocation
	Nous définissons par la suite, les problèmes et les défis pour améliorer les ordonnanceurs de ressources sur les plate-formes de Cloud Computing ainsi que les objectifs que nous visons. C.1.1 Problèmes et objectifs de recherche Conformément à ce qui a été défini dans l'élaboration du sujet, ce mémoire de thèse se concentre sur l'allocation de ressources sur une plate-forme de type Infrastructure as a Service (IaaS) et décrit le développement d'un moteur d'optimisation permettant une allocation intelligente et dynamique des ressources clientes en mettant l'accent sur les principaux défis suivants : • Comment mesurer les performances d'un algorithme de placement des scription des propriétés composant une ressource. Ainsi, nos ressources représentent des services d'infrastructure, mais pourraient aussi représenter des services plus com-plexes dans le domaine du Platform as a Service (PaaS) ou du Software as a Service (SaaS). Nous nous sommes attachés à la gestion des coûts sur une plate-forme et à la modélisation de l'interruption de service en corrélation avec la charge de travail des ressources du fournisseur hébergeant les demandes des utilisateurs. La seconde contribution est l'identification et l'expression des contraintes d'affinité et d'anti-affinité entre les ressources du fournisseur et les ressources demandées par les utilisateurs. Ces contraintes d'affinité et d'anti-affinité permettent d'obtenir plus de flexibilité dans la gestion des coûts globaux de l'infrastructure et la qualité de service rendu aux utilisateurs. De plus, elles permettent de s'assurer que certaines ressources sensibles des utilisateurs soient allouées sur des ressources du fournisseur sécurisées. Ces contraintes s'expriment sous la forme de contraintes de placement des ressources virtuelles sur l'infrastructure du fournisseur. La dernière contribution réside dans le développement d'un algorithme génétique capable de répondre et de converger en un temps convenable pour le domaine métier du place-ment de ressource au sein d'une plate-forme de Cloud Computing de type Infrastruc-ture as a Service (< 30 secondes pour des problèmes de taille moyenne, 2000 machines virtuelles et 500 hyperviseurs). Il est aussi complexe de trouver le bon paramétrage d'ensemble des opérateurs, car cela dépend du problème traité. Il est aussi complexe de trouver le bon paramétrage d'ensemble des opérateurs, car il dépend du problème traité. Nous avons choisi d'utiliser un algorithme génétique, car celui-ci permet de trouver de court. De plus, ils peuvent être plus facilement parallélisables ce qui, dans le domaine du placement sur une plate-forme de Cloud Computing, peut devenir intéressant même si nous n'en traiterons pas dans ce mémoire. Notre algorithme génétique a été modifié afin d'améliorer le temps de convergence de la population vers une solution viable. Nous avons amélioré le processus d'initialisation de la population afin que chaque nouvel indi-vidu respecte la contrainte de capacité, ce qui a permis de faire converger la population plus rapidement vers une solution viable. de ressource au sein d'une plate-forme de Cloud Computing puis nous décrivons les fu-turs axes de recherche sur le sujet et les perspectives relatives à ceux-ci. Notre conclusion se trouve résumée en français dans la section C.4. L'approche que nous adoptons pour trouver une solution de placement des ressources au sein d'un IaaS en fonction des objectifs des consommateurs et du fournisseur et des relations entre les ressources est une approche fondée sur une modélisation matricielle. Nous proposons d'utiliser des matrices pour décrire les demandes de service et les offres de service sous une forme compatible avec l'utilisation d'algorithmes évolutionnaires plus appropriés pour des problèmes avec des objectifs multiples en tenant compte de multiples contraintes. La Figure C.3 décrit les processus internes qui composent généralement le module al-ressources au sein d'une plate-forme de Cloud Computing ? des ressources de type "infrastructure". Nous avons principalement travaillé sur la de-multiples optima potentiellement proches de la solution idéale en un temps relativement louant les ressources au sein d'une plate-forme de Cloud Computing.

  j 1 ≤ j ≤ m, U j ∈ R + (C.5) Chaque attribut sur chaque ressource du fournisseur a une charge maximum avant que la qualité de service se détériore ou soit dégradée pour les ressources virtuelles des clients. Nous notons L M jl la charge maximale avant dégradation et L jl la charge courante du serveur j pour l'attribut l. Ces serveurs ont une qualité de service courante et maximum définis respectivement par Q jl and Q M jl . Le niveau de service garanti est noté C Q k et s'il n'est pas respecté le fournisseur paie une pénalité d'indisponibilité définis comme un coût C U k . Le prestataire de services doit garantir qu'il n'y aura pas d'interruption de service. Nous définissons ces charges et la qualité de services à l'aide de matrices

	utilisons un vecteur [Eq. C.5] pour représenter ces coûts d'utilisation.
	[Eq.C.6]:
	L
	.g	(C.10)
	Afin de représenter les coûts d'exploitation des ressources du fournisseur, nous intro-
	duisons un vecteur [Eq.C.4] dont les éléments sont des coûts qui représentent les coûts
	directs associés à l'utilisation d'un serveur : la puissance, l'espace au sol, le stockage et
	les opérations informatiques courantes de gestion.
	E j 1 ≤ j ≤ m, E j ∈ R +	(C.4)
	Au-delà des coûts d'exploitation, chaque ressource du fournisseur dispose d'un coût
	d'utilisation qui sera appliqué pour chaque ressource du consommateur hébergée. Nous

3) Nous notons X ijk , une variable booléenne qui est vraie quand une ressource consommateur k est hébergée pour le serveur du fournisseur j dans un datacenter i. Nous définissons une contrainte qui s'assure que la capacité d'une ressource du fournisseur [Eq.C.10]. Cette contrainte inclut la consommation des ressources virtuelles sur les ressources matérielles du fournisseur en incluant le facteur sur chaque attribut défini précédemment. n k=1 C kl × X ijk ≤ P jl F jl , ∀l = 1...h, ∀i = 1..U

Table C . 1 :

 C1 Variables du modèle d'allocation de ressource CloudToutes ces relations et les contraintes sont mises en oeuvre dans notre algorithme qui sera utilisé pour fournir des solutions au problème de l'allocation des ressources au sein d'une plate-forme de Cloud Computing abordées dans ce travail.

		Substrat du fournisseur et les ressources demandées
	G	Ensemble de datacenter disponibles G = {1, ..., g}
	M	Ensemble de serveur disponibles M = {1, ..., m}
	N Nous résolvons le problème d'allocation des ressources en fonction des coûts d'exploitation Ensemble des ressources demandées N = {1, ..., n}
	H et d'utilisation, les relations d'affinité / anti-affinité entre les ressources et la qualité de Ensemble des attributs disponibles pour chaque ressource H = {1, ..., h} Matrices des capacités P jl Capacités de la ressource du fournisseur j pour l'attribut l service requise sur les ressources allouées sur la plate-forme de Cloud Computing . Notre
	C kl approche prend en compte de multiples contraintes, des relations et des objectifs, mais Capacités de la ressource consommateur k pour l'attribut l
	F jl les multiples objectifs sont agrégés au sein d'une fonction d'objectif global tel que décrit Facteur de capacité pour l'attribut l sur la ressource du fournisseur j
	Modèle d'allocation Variable booléenne indiquant que la ressource du consommateur k est assignée par la suite. X ijk
	à la ressource du fournisseur j dans le datacenter i Notre problème d'optimisation est similaire au problème de "bin packing" multi-dimension Vecteurs et matrices pour la qualité de service L jl Charge de l'attribut l sur la ressource du fournisseur j et au problème de sac à dos qui ont été montrés comme étant NP-Difficile, notre
	L M jl problème est effectivement NP-Difficile. Le problème de bin packing multi-dimension Charge maximum d'un attribut l sur la ressource du fournisseur j
	Q M jl est un problème d'allocation de vecteur avec d dimension et il a été prouvé comme étant Qualité de service maximum d'un attribut l sur la ressource du fournisseur j
	Q jl C Q k NP-Difficile dans [105]. Qualité de service d'un attribut l sur la ressource du fournisseur j Qualité de service garantie par le fournisseur pour une ressource consommateur
		k
		Vecteurs des coûts
	E j	Coût d'exploitation de la ressource du fournisseur j
	U j	Coût d'utilisation pour chaque ressource consommateur hébergée sur la
		ressource du fournisseur j
	C U k	Coût d'indisponibilité pour la ressource consommateur k
	M k	Coût de migration de la ressource consommateur k
		n
		X ijk = 1, ∀i = 1...g, ∀j = 1...m	(C.13)
		k=1
	La contrainte de séparation sur différents datacenters est sensiblement identique	à
	la précédente, sauf que la somme s'effectue sur les centres de données et les ressources
	demandées et elle est formulée ainsi [Eq. C.15] :
		g	n
				X ijk = 1, ∀j = 1...m	(C.15)
		i=1	k=1
	La contrainte de séparation sur différents serveurs implique une somme sur les
	centres de données, les serveurs et les ressources demandées et elle est exprimée par [Eq.
	C.14].
			g	m	n
				X ijk = 1	(C.14)
			i=1	j=1	k=1

Comme notre objectif est de minimiser les coûts, les interruptions de service et la taille du plan de reconfiguration, nous introduisons plusieurs fonctions objectives comme les coûts globaux générés par la plate-forme de Cloud Computing [Eq. C.7], la qualité de service des ressources [Eq. C.8] et la taille approximative du plan de reconfiguration [Eq.C.9]. Notre problème d'allocation de ressource au sein d'une plate-forme de Cloud Computing peut être résumé en regroupant toutes les fonctions objectives avec toutes les contraintes et les conditions grâce à l'ensemble des équations suivantes :

  Dans un premier temps, nous savons que résoudre le problème d'allocation des ressources sur une plate-forme de Cloud Computing grâce à un solveur de résolution de contrainte comme le solveur CPLEX, entraîne un temps de résolution exponentielle, ce qui implique que les solutions ne passent pas à l'échelle en fonction de la taille du problème. De plus, ces méthodes ne sont pas adaptées pour les problèmes multi-objectifs et multi-critères. Nous notons P op la population, p un individu et S un ensemble de variables représentant les solutions. La variable s est juste une solution d'allocation. La variable P jl représente la matrice des capacités des ressources fournisseur et C kl est la matrice des capacités des ressources clientes. Le tirage n'est pas un simple tirage aléatoire simple, car il est guidé par la capacité des ressources de fournisseur d'accueillir les demandes des consommateurs. DC j qui spécifie le datacenter où le serveur j se trouve. Les variables booléennes N ODEused j et DCused i indiquent si un serveur ou un datacenter est utilisé. Ces variables sont utilisées afin d'implémenter les contraintes et les relations entre les ressources. Les variables utilisées dans la définition de notre algorithme sont listées ci-dessous pour que le lecteur puisse y faire référence plus rapidement : C.2:

	Algorithm 4 Initialize population
	Require: P op, S, R j
	for each p ∈ P op do
	initialize R j
	for each s ∈ S do
	repeat
	s = randomDraw(p, R j ) Afin de fournir un algorithme permettant de passer une mise à l'échelle et de fournir des until isPossible(p) solutions dans des délais raisonnables, nous avons recours à l'algorithme NSGA II [108] end for
	qui est un algorithme génétique permettant de résoudre notre problème d'allocation des end for
	ressources au sein d'une plate-forme de Cloud Computing que nous avons adressé dans ce
	mémoire. NSGA II est un algorithme génétique populaire fondé sur la non-domination fournisseur j pour capturer et estimer cette capacité d'accueil et l'utiliser pour conduire
	de Pareto pour l'optimisation multi-objectifs et il constitue donc un choix approprié les futures explorations de l'espace de recherche.
	pour le problème que nous considérons ici.
	Table C.2: Variables de l'algorithme
		Variables de l'algorithme
	P op	Ensemble	des	individus
	P op = {1, ..., p} nous le décrivons dans l'algorithme 6. La taille de la population est fixe et constitue croisement utilisé est un opérateur de croisement binaire simulé du nom de Simulated S Chromosome: Ensemble de une entrée de l'algorithme. Pour initialiser la population, nous procédons pour chaque binary crossover [1] (SBX). L'opérateur de croisement SBX reproduit les mécanismes du gène N = {1, ..., s} individu à un tirage au sort (Algorithme 4) sur leur gène, en choisissant au hasard la croisement standard à un point utilisé lorsque les variables objets sont représentés sous ressource qui sera l'hôte de chaque gène. Tant que la solution obtenue n'est pas valable, spécifie le datacenter du DC j la forme de chaînes binaires. Nous utilisons l'opérateur de mutation polynomiale (PM). serveur j ou ne respecte pas les contraintes et les relations exprimées dans les demandes initiales, Il est fondé sur l'échange de bit au sein d'un gène. Semblable à SBX, PM favorise les nous répétons le processus. Le tirage au sort se poursuit jusqu'à ce que des solutions N ODEused j Variable booléenne si un descendants les plus proches des parents. valables soient trouvées. serveur est utilisé
	Le choix de la population initiale d'individus conditionne fortement la rapidité de l'algo-DCused i Variable booléenne si un dat-
		...g ∀j=1...m acenter est utilisé	(C.8)
			∀l=1...h

La complexité en temps de l'algorithme NSGA II est O(M N 2 ) où M est le nombre d'objectifs et N est la taille de la population. Afin d'accélérer le temps d'exécution de l'algorithme et réduire l'impact de cette complexité, nous modifions l'algorithme comme décrit dans la figure Fig.C.8 et nous développons une méthode spécifique d'initialisation (Algorithme 4) fondé sur les observations des résultats du tirage au sort des gènes composant les solutions en fonction du taux de succès permettant de trouver des solutions viables et acceptables, c'est-à-dire celles qui répondent favorablement aux contraintes de capacité. Nous utilisons une probabilité dérivée de ces observations pour améliorer les futurs tirages et permettre d'accélérer l'exploration vers de bonnes solutions. En substance, nous exploitons les observations passées pour affiner les futures explorations. La Figure C.8 montre la structure générale de notre algorithme NSGA II modifié. L'initialisation de la population se fonde sur un tirage au sort aléatoire. L'opérateur de sélection est un opérateur de sélection pour tournoi binaire utilisant la domination de Pareto. Le principe de la sélection par tournoi augmente les chances pour les individus de piètre qualité de participer à l'amélioration de la population. L'opérateur de rithme. Un individu est constitué d'un chromosome et est une solution de placement des ressources. Un chromosome correspond à une variable booléenne X jk indiquant que la ressource demandée k est assigné à la ressource du fournisseur j. Le chromosome est

Figure C.8: Principe de notre algorithme génétique composé de gènes où chaque gène étant un nombre réel représentant l'identifiant de la ressource de fournisseur j. Nous voulons un algorithme qui converge rapidement vers une solution approchée. A cette fin, nous vérifions que la contrainte de capacité est respectée à l'initialisation comme Le tirage n'est pas un simple tirage aléatoire simple, car il est guidé par la capacité des ressources de fournisseur d'accueillir les demandes des consommateurs. Nous introduisons un vecteur R j qui enregistre le nombre de tests échoués sur la ressource du

tiser le placement des ressources ou des tâches. Si une erreur se produit sur la plate-forme de Cloud Computing, ils peuvent placer les ressources touchées par la panne sur un autre emplacement de l'infrastructure du fournisseur sans interaction humaine. Parfois, il peut être préférable d'effectuer des maintenances quotidiennes pendant que l'ordonnanceur apporte des améliorations dans le placement des ressources afin de préserver un groupe de ressource commune (Service identique ou machine virtuelle composant un même projet). Mais comment l'ordonnanceur peut-il choisir le centre de données et l'hyperviseur le plus approprié ? Et comment réagit-il en cas d'échec ? Initialement, dans des environnements Cloud ou de grille de serveurs, les méthodes d'allocation de ressources consistaient à faire de la consolidation et de la répartition de charge ce qui est un héritage des méthodes d'allocation de bytes sur des disques physique. Ces dernières années, nous constatons l'introduction des workflows dans les méthodes de placement. Cependant, il est difficile d'appliquer ces principes sur des plate-formes de Cloud Computing du fait de l'hétérogénéité de celle-ci. Concernant les contraintes business et technique au sein d'une plate-forme de Cloud Computing, il y a eu des avancées et des améliorations dans l'implémentation d'algorithmes de résolution des problèmes d'allocation permettant leur intégration. En effet, des travaux ont été effectués afin d'intégrer les "workflows" entre les consommateurs et les fournisseurs de services. Un de ces travaux utilise un algorithme de résolution du problème du flot

Acknowledgements

Abbreviations

NIST Algorithm 3 Checks whether the solution is valid

Require: p, P jl , R j Ensure: p ∈ P op // Capacity constraint [Eq. 3.4] below for each q ∈ Q p do capacityProvider = getVariable(q) for each j ∈ P jl do capacityProvider = capacityProvider -capacityCustomer end for if capacityProvider < 0 then increaseAmount(R j ); return failureConstraint end if end for // All relationship constraints below switch RelationshipConstraints do case ColocalizationSameDC : // [Eq. 3.8] for each q ∈ Q p do if DC[q] ! = anyDC then return failureConstraint end if end for end case case ColocalizationSameNode : // [Eq. 3.9] for each q ∈ Q p do if q ! = anyNode then return failureConstraint end if end for end case case TotalSeparation : // [Eq. 3.10] for each q ∈ Q p do if DCused[DC [q]] == true OR NODEused[q] == true then return failureConstraint else NODEused[q] = true end if end for end case case SeparationOnDifferentNode : // [Eq. 3.12] for each q ∈ Q p do if NODEused[q] == true then We implemented this Simulated Binary Crossover (SBX) function in compliance with the philosophy of the proposed method in 1995. SBX uses a probability distribution of β in SBX [Eq. 4.5] that should be similar to the probability distribution of β in Binary-coded crossover.

ρ(β) = 0.5(n + 1)β n , if β ≤ 1; 0.5(n + 1)

SBX is a real-coded crossover operator that create two children solutions from two parent solutions. It uses a probability distribution centering the parent solutions and two children solutions are created based on that probability distribution. Creating children solutions using a fixed probability distribution, which does not depend on the location of the parent solutions, makes the search adaptive. In order to create two children solutions c1 and c2 from the parent solutions p1 and p2 using the above probability distribution, the following procedure is used.

• Create a unified random number u between 0 and 1.

• Find a β for which the cumulative probability respects [Eq. 4.6]

• Knowing the value of β , the children points are calculated using [Eq. 4.7] :

As previously mentioned, our implementation of SBX is based on the article written by the authors in 1995 [START_REF] Deb | Simulated Binary Crossover for Continuous Search Space[END_REF] and which is implemented in NSGA II by Deb. We observed that the crossover operator SBX is most appropriate for our resource allocation problem (See section 4.3).

Mutation Operator

Deb and Agrawal [START_REF] Deb | Artificial Neural Nets and Genetic Algorithms: Proceedings of the International Conference in Portorož, Slovenia[END_REF] suggested a polynomial mutation (PM) operator with a userdefined mutation probability parameter. We use them in our implementation of the mutation operator with a value of 0.20 for the mutation probability. In this operator, a polynomial probability distribution is used to perturb a solution in a parent's vicinity.

The probability distribution in both left and right of a variable value is adjusted so that

• Providing an optimal reconfiguration plan is a natural extension of this work and shall be a key question for future research. Such as how to migrate from the current resource allocation on the cloud computing platform to the new allocation provided with our algorithm.

• We have made use of a genetic algorithm to find an approximate solution taking into account the interests of each player. The disadvantage of genetic algorithms is that they are slow to converge. As a matter of fact, it would not be irrelevant to experiment more with different optimization algorithms. The advantage of genetic algorithms is they can be parallelized to explore the search space using multiple servers.

• We have chosen to use, in our work, vector and matrix representation for the resources and allocation solution. This method of information representation is low-level. A more generic representation at higher levels using Johnson graphs is a track to be taken into account to reduce complexity and improve execution time.

Appendix A Thesis Publications The provider resources may be described in the same way. We must provide a value for each attribute by adding operating cost and usage cost for each hosted virtual machine.

Please write provider resource model like that : CPU ; RAM ; DISK ; COPEX ; USAGE_COST 8 ; 1 6 ;5 0 0 ; 1 . 2 3 0 ; 0 . 8 9

We can detail the information business as profit for each virtual machine along with the downtime cost.

Please write provider resource pricing : XX . XX PRICING ; DOWNTIME_COST 2.00;5.00

Next step is the generation of the pattern. It is saved as a file. The desired number of resources is required. User is prompted to specify path to the save folder. It is possible to enable a verbose mode with boolean variable. Verbose mode provides information on each stage of the optimization process or on each covered solution. Then, we choose the way the model will be generated. Choosing to generate a random pattern, for instance, would go as follows:

File Model Generation process ... Following the previous generation from a random distribution, we get this file:

/ home / tecarot / Simu / Exp1 /; false 10;5 -1 ; 9 ; 2 6 6 ; 5 7 ; 1 0 . 3 5 6 9 3 0 6 1 8 4 6 8 4 7 ;1 0 3 2 . 6 5 5 6 0 9 4 0 8 9 0 8 7 0 ;8 ;6 2 ;5 6 7 ;8 . 7 1 5 3 9 3 8 6 6 4 3 8 9 1 6 ;1 5 3 2 . 2 6 5 5 8 7 3 3 0 7 1 0 8 2 ;2 7 ;3 8 7 ;4 4 5 ;1 6 . 2 9 2 2 9 7 2 1 5 6 4 4 5 8 8 ;2 0 1 . 1 9 7 1 0 9 3 5 0 0 7 2 4 2 4 ;1 ;4 2 4 ;9 6 9 ;1 9 . 7 8 2 5 2 6 0 7 4 8 8 7 7 1 3 ;9 6 9 . 6 4 8 1 6 1 7 4 4 2 7 3 With this file containing the pattern of the allocation problem, we can go to optimization process of cloud computing resources.

B.2 Optimization process

To solve the problem of allocating resources within a cloud computing platform, we have implemented a Java 8-based solver. Our solver can be used with different algorithms such as Round Robin (rr), Branch and Bound (bab) or Genetic Algorithm (ga).

$ java -jar AllocAlgo . jar -algo rr -file test . hawks $ java -jar AllocAlgo . jar -algo bab -file test . hawks $ java -jar AllocAlgo . jar -algo ga -file test . hawks

B.3 Showing results

While running allocation optimization algorithms, ten indicators have been collected.

The indicators are as follows:

• Resolution Time The time for the algorithm to obtain a feasible solution.

Appendix C

Résumé en Français

Abstract. Désormais, le Cloud Computing est couramment employé dans le secteur de l'industrie et des services. Ses utilisations sont nombreuses. Nous pouvons citer, en particulier, les services de stockage ou de sauvegarde en ligne qui offrent la possibilité d'avoir accès à ces données, en tout temps et en tout lieu, grâce à une interface distante.

Ces facilités pour les utilisateurs existent, car les plate-formes de Cloud Computing sous-jacentes sont soumises à une optimisation de bout en bout en termes de gestion et de flexibilité.

Les utilisateurs de ces services sont de plus en plus exigeants au niveau de la disponibilité et de la sécurité de leurs données sur les plate-formes. Pour répondre à ces attentes, les fournisseurs de services se tournent vers une automatisation dans le placement des ressources au sein de leur plate-forme. Cette automatisation permettra une plus grande qualité de service grâce à une meilleure flexibilité de leurs infrastructures informatiques.

Nous présentons dans ce mémoire, une nouvelle méthode de placement permettant de prendre en charge les intérêts du fournisseur, mais aussi ceux du consommateur de services. Les verrous scientifiques que nous traitons sont principalement :

• Proposer une définition de modèle généralisant les infrastructures porteuses d'un Cloud.

• Identifier des indicateurs pertinents pour décrire l'état des infrastructures porteuses et définir le processus d'agrégation de l'information permettant d'alimenter le processus de décision.

• Résolution d'un problème d'optimisation NP-difficile permettant une allocation dynamique, efficace et intelligente des ressources clientes au sein d'un Cloud.

C.1.2 Contributions

Nous résumons pour plus de commodité nos contributions et nos réalisations décrites dans ce mémoire en respectant les défis identifiés à l'origine et nos objectifs de recherche définis.

C.1.3 Organisation du mémoire

Les principaux chapitres de ce mémoire se structurent tels que décrits en • en excluant les individus qui ne sont pas en conformité avec les contraintes;

• en fixant les individus défectueux à travers le processus de réparation;

• en préservant les bons individus par le biais d'opérateurs spéciaux;

• en modifiant l'espace de recherche et en guidant l'algorithme (via des hyperplans).