Cloud computing has rapidly emerged as a successful paradigm for providing IT infrastructure, resources and services on a pay-per-use basis over the past few years. As, the wider adoption of Cloud and virtualization technologies has led to the establishment of large scale data centers that consume excessive energy and have significant carbon footprints, energy efficiency is becoming increasingly important for data centers and Cloud. Today data centers energy consumption represents 3 percent of all global electricity production and is estimated to further rise in the future. This thesis presents new models and algorithms for energy efficient resource allocation in Cloud data centers. The first goal of this work is to propose, develop and evaluate optimization algorithms of resource allocation for traditional Infrastructutre as a Service (IaaS) architectures. The approach is Virtual Machine (VM) based and enables on-demand and dynamic resource scheduling while reducing power consumption of the data center. This initial objective is extended to deal with the new trends in Cloud services through a new model and optimization algorithms of energy efficient resource allocation for hybrid IaaS-PaaS Cloud providers. The solution is generic enough to support different type of virtualization technologies, enables both on-demand and advanced resource provisioning to deal with dynamic resource scheduling and fill the gap between IaaS and PaaS services and create a single continuum of services for Cloud users. Consequently, in the thesis, we first present a survey of the state of the art on energy efficient resource allocation in cloud environments. Next, we propose a bin packing based approach for energy efficient resource allocation for classical IaaS.

We formulate the problem of energy efficient resource allocation as a bin-packing model and propose an exact energy aware algorithm based on integer linear program (ILP) for initial resource allocation. To deal with dynamic resource consolidation, an exact ILP algorithm for dynamic VM reallocation is also proposed. This algorithm is based on VM migration and aims at constantly optimizing energy efficiency at service departures. A heuristic method based on the best-fit algorithm iii has also been adapted to the problem. Finally, we present a graph-coloring based approach for energy efficient resource allocation in the hybrid IaaS-PaaS providers context. This approach relies on a new graph coloring based model that supports both VM and container virtualization and provides on-demand as well as advanced resource reservation. We propose and develop an exact Pre-coloring algorithm for initial/static resource allocation while maximizing energy efficiency. A heuristic Pre-coloring algorithm for initial resource allocation is also proposed to scale with problem size. To adapt reservations over time and improve further energy efficiency, we introduce two heuristic Re-coloring algorithms for dynamic resource reallocation. Our solutions are generic, robust and flexible and the experimental evaluation shows that both proposed approaches lead to significant energy savings while meeting the users' requirements.

List of Figures

Chapter 1 Introduction

Over the past few years, cloud computing has rapidly emerged as a successful paradigm for providing IT infrastructure, resources and services on a pay-per-use basis. The wider adoption of Cloud and virtualization technologies has led to the establishment of large scale data centers that provide cloud services. This evolution induces a tremendous rise of electricity consumption, escalating data center ownership costs and increasing carbon footprints. For these reasons, energy efficiency is becoming increasingly important for data centers and Cloud.

The fact that electricity consumption is set to rise 76% from 2007 to 2030 [START_REF]World energy outlook 2009 fact sheet[END_REF] with data centers contributing an important portion of this increase emphasizes the importance of reducing energy consumption in Clouds. According to the Gartner report [3], the average data center is estimated to consume as much energy as 25000 households, and according to McKinsey report [START_REF] Kaplan | Revolutionizing Data Center Energy Efficiency[END_REF], "The total estimated energy bill for data centers in 2010 is 11.5 billion and energy costs in a typical data center double every five years". Face to this electronic waste and to these huge amount of energy used to power data centers, energy efficient data center solutions have become one of the greatest challenges.

A major cause of energy inefficiency in data centers is the idle power wasted when resources are under used. In addition, this problem of low resources utilization, servers are permanently switched on even if they are not used and still consume up to 70% of their peak power. To address these problems, it is necessary to eliminate the power waste, to improve efficiency and to change the way resources are used. This can be done by designing energy efficient resource allocation solutions at different Cloud levels, which is the focus of this thesis. In addition to these challenges, provided solutions should scale in multiple dimensions and Cloud providers must also deal with the users' requirements which are being more and more complex. Requested services are more sophisticated and complete since users need to deploy their own applications with the topology they choose and with having the control on both infrastructure and programs. This means combining the flexibility of IaaS and the ease of use of PaaS within a single environment. As a result, the classic three layer model is changing and the convergence of IaaS and PaaS is considered as natural evolutionary step in cloud computing. Cloud resource allocation solutions should be flexible enough to adapt to the evolving Cloud landscape and to deal with users requirements. This key dimension of cloud levels is essential for our research and we address it in depth in this thesis.

Another important dimension we consider is the type of the virtualization. In addition to traditional VM based technology, Cloud providers are also adopting new container-based virtualization technologies like LXC and Docker that enable the deployment of applications into containers. Hence, this resource variety aspect should be taken into account when modeling the problem of resource allocation to scale with the Cloud evolution and with new users requirements.

One last important dimension at which we are interested in this work is the resource provisioning plan. Cloud providers could offer two types of resource provisioning: on-demand and advance or long-term reservation. Advance reservation concept has many advantages especially for the co-allocation for resources. It provides simple means for resource planning and reservation in the future and offers an increased expectation that resources can be allocated when demanded. Although advance reservation of resources in cloud is very advantageous, the focus has been mostly on the on-demand plan.

Solving the problem of resource allocation in Cloud while maximizing energy efficiency and adopting the previously cited dimensions, is a very challenging issue.

In this thesis, we address the problem with its multiple facets and levels to provide not only a specific solution, but also a generic and complete approach.

Research Problem and Objectives

Energy efficient Cloud resources allocation consists in identifying and assigning resources to each incoming user request in such a way, that the user requirements are met, that the least possible number of resources is used and that data center energy efficiency is optimized. Even if Cloud resource allocation problem has been studied in the literature, much of the interest was focused on the IaaS layer and the dimensions of virtualization type and of provisioning plan were also not investigated enough. Some heuristic solutions for IaaS were proposed but there is still a lack of optimal algorithms to ensure energy efficient resource allocation. New hybrid Cloud solutions that combine Iaas and PaaS (e.g. openstack Heat) are evolving over time and being more and more attractive since they enable the joint deployment of infrastructure and applications. However, these solutions still lack energy efficient resource (VM or container) scheduling and no attention was paid to solve the problem at this level.

The main focus of this thesis is on the design and development of models and algorithms for energy efficient resource allocation in Cloud data centers. The first goal of this work is to propose, develop and evaluate optimization algorithms of resource allocation for traditional IaaS architectures that are widely used to manage clouds. The approach is VM based and it should enable on-demand and Chapter 1. Introduction 4 dynamic resource scheduling while reducing the power consumption of the data center. This initial objective is naturally extended to deal with the new trends in Cloud. We aim to provide a new model and optimization algorithms of energy efficient resource allocation for IaaS-PaaS cloud providers. The solution should be generic enough to support different type of virtualization technologies, to enable both on-demand and advanced resource provisioning plans, to deal with dynamic resource scheduling and to fill the gap between IaaS and PaaS to create a single continuum of services for cloud users.

Contributions

Based on the objectives defined previously, we outline the main contributions of this thesis:

1. A survey of the state of the art on energy efficient resource allocation in cloud environments.

A bin packing based approach for energy efficient resource allocation:

• We formulate the problem as a bin-packing model. The model is VM based and provides on-demand resource allocation in IaaS Clouds.

• An exact energy aware algorithm based on integer linear program (ILP) for initial resource allocation.

• An exact ILP algorithm for dynamic VM reallocation. It is based on VM migration and aims to optimize constantly the energy efficiency after service departures.

• Combination of both previous exact algorithms in one algorithm that runs each of them when convenient.

• A heuristic method based on best-fit algorithm adapted to the problem.

• Evaluation and performance analysis of the proposed algorithms.

A graph coloring based approach for energy efficient resource allocation:

• New graph coloring based model for energy efficient resource allocation in IaaS-PaaS providers. The model supports both VM and container virtualization and provides on-demand and advanced reservation resource provisioning.

• An exact Pre-coloring algorithm for initial/static resource allocation while maximizing energy efficiency.

• A heuristic Pre-coloring algorithm for initial/static resource allocation is proposed to scale with problem size.

• Two heuristic Re-coloring algorithms for dynamic resource reallocation are proposed to adapt reservations over time and to improve further energy efficiency.

• Evaluation and comparison of the exact and heuristic solutions in terms of energy efficiency, resource usage and convergence time.

Thesis Organization

This thesis is organized into six chapters. Chapter 2 provides an introduction to both Cloud computing and energy efficiency trends. We show how cloud is transforming IT and how sustainability is becoming increasingly important for Cloud data centers.

Chapter 3 describes the problem of resource allocation in Cloud environments.

We provide background and state of the art solutions for energy efficient resource allocation. Then, we discuss the related issues and problems, as well as the challenges.

In Chapter 4, we present a bin-packing based solution for energy efficient resource allocation in IaaS Clouds. We propose exact and heuristic algorithms to perform initial resource allocation and dynamic resource reallocation while minimizing energy consumption and VM migration costs. Simulations are conducted to show the performance of our exact algorithms and to demonstrate their ability to achieve significant energy savings while maintaining feasible convergence times when compared with the heuristic solution.

Chapter 5 introduces a new graph coloring based solution for energy efficient resource allocation in integrated IaaS-PaaS environments. Both on-demand and advanced reservation plans are considered. We present exact and heuristic algorithms for initial resource allocation and dynamic resource reallocation while satisfying users' requirements and maximizing energy efficiency. Experimentations are conducted to assess the efficiency of our solution.

Introduction

Energy efficiency is becoming increasingly important for Cloud data centers. Their growing scale and their wide use have made a great issue of power consumption.

Before beginning to solve the problem, it is important to study it in depth and to identify the reasons behind it. This chapter introduces the concepts of Cloud computing and virtualization that serves as its enabling technology. We further investigate the problem of energy efficiency in Cloud data centers by studying the major causes of energy waste, presenting the different power saving techniques and introducing energy measurement and modeling in Cloud environments. Finally, we highlight the orientation and the focus of this thesis. • On-demand self-service: automated on-demand resource provisioning.

Cloud Computing

• Broad network access: Resources can be accessed remotely over the network.

• Resource pooling: Resources are pooled and dynamically assigned independently from their physical location.

• Rapid elasticity: Capability can scale to cope with demand peaks.

• Measured Service: Resource usage is metered to enable the pay-per-use model.

An important aspect to consider with the Cloud is the ownership and use of the Cloud infrastructure. Different approaches can be used to deploy Cloud infrastructures:

Private cloud:

Refers to cloud infrastructures owned and managed by a single company, used in a private network and not available for public use.

Community cloud:

Refers to shared cloud infrastructures for specific communities composed by multiple users.

Public cloud:

Refers to high-performance and large infrastructures operated by external companies that provide IT services for many consumers via the Internet.

Hybrid cloud:

As the name already indicates, a hybrid cloud is a combination of both a private and public cloud. Parts of the service run on the company's private cloud, and parts are outsourced to an external public cloud.

Cloud Computing Actors

Cloud computing involves three main actors that have distinct roles and interactions inside the Cloud environment: providers, brokers and users.

Cloud Provider:

The provider possess the Cloud infrastructure on which Cloud services are deployed. This actor is responsible for the management and the control of cloud resources and for handling users' requests.

Cloud user:

A Cloud user is a person or an organization that consumes Cloud services.

Cloud Broker:

The Broker is an intermediate player between Cloud users and provider. It is responsible for the distribution incoming requests between the different providers based on users' requirements. To make a simple analogy, a Cloud broker is like a travel agency that acts as an intermediary between clients and service providers.

Cloud Services Overview

Cloud service models describe how services are made available to users. We distinguish between two different types of models : classic Cloud service models and new hybrid ones.

Classic Cloud service models

Classic Cloud service models can be categorized into three types: Infrastructure as a Service (IaaS), Platform as a Service (PaaS) and Software as a Service (SaaS). IaaS is the most straightforward model for delivering cloud services. It refers to the provisioning and the delivery of basic resources such as virtual machines, physical servers, network and storage. Instead of investing in their own infrastructure, companies are able to rent resources and use them on demand rather than having their resources locally. With IaaS, users have direct access to the lowest level in the stack and are able to build their application environments from scratch. An example of a popular IaaS Cloud is Amazon EC2 [5].

Platform as a Service (PaaS):

PaaS is on a more sophisticated and higher level service compared to IaaS. It provides application development environments and software platforms to develop, deploy, and manage Cloud applications while not worrying about the technology and hiding the low-level details from the user. The most popular cloud platforms are Microsoft Azure Services[6] and Google App Engine [START_REF]Google app engine[END_REF].

Software as a Service (SaaS):

SaaS is the highest level of the Cloud service model. In this scenario, complete applications are provided to users through the internet. SaaS providers manage infrastructure and have complete control of the application softwares. Users just access their applications as if they were hosted locally and don't need to know anything about the Cloud or even be aware about the technologies details. SaaS examples are social media plateforms, mails and project management systems and the most popular SaaS applications are Google Documents[8] and Google Apps [START_REF]Google apps[END_REF].

New hybrid service models

As Cloud is maturing and as users are requesting more flexibility and more control since they need to deploy their applications with the topology they choose and with having the control on both infrastructure and programs, the classic three layer 451 Research [START_REF]Is paas becoming just a feature of iaas?, 451 research group[END_REF], a leading global analyst and data company focused on the business of enterprise IT innovation, states that: " Although it is maturing in technology and market, PaaS is getting squeezed between consolidation with IaaS and heavy use of SaaS. PaaS will most likely survive as a category, but not necessarily as we know it today".

Virtualization and Cloud Computing

Virtualization technology is the main enabler of Cloud computing. It is based on physical resources abstraction in a way that several virtual resources are multiplexed on a physical one. Virtualization is used to provide isolation, flexibility, higher resource utilization, easy resource management as well as resource elasticity and to enable heterogeneous services to co-exist on the same physical hardware. In this thesis, we focus on server virtualization which is the most common resource abstraction technique in Cloud computing. This kind of virtualization allows multiple isolated virtual servers to run on a single one and can be implemented in different ways. Implementation approaches cover full virtualization, para-virtualization and OS-level virtualization. Both full virtualization and paravirtualization use a hypervisor to share the underlying hardware but differ on how the host operating system and the guest operating systems are modified to support virtualization and also on how they interact with each others. In contrast to full virtualization and para-virtualization, operating system level virtualization does not use a hypervisor at all. In this approach, all the virtual servers run the same host OS that performs all the functions of a fully virtualized hypervisor. Hence, based on the approach through which the virtualization is achieved, server virtualization can be classified into two main categories: hypervisor based virtualization and OS or container based virtualization. This classification is further detailed in the next section.

Server virtualization categories

There are two common ways to virtualize resources in Cloud computing: via hosted virtualization using a hypervisor or via container-based virtualization.

Hypervisor based virtualization:

Hypervisor based virtualization is the traditional way of doing virtualization in the Cloud. This technology is based on a layer of software, called hypervisor, which manages the physical server resources. Examples of hypervisors are KVM [START_REF] Kvm | [END_REF],

VMWare [17], Microsoft Hyper-V [START_REF]Microsoft hyper-v[END_REF], Xen into virtualized servers [START_REF] Srikantaiah | Energy aware consolidation for cloud computing[END_REF] and also offers live migration feature [START_REF] Franco Travostino | Seamless live migration of virtual machines over the man/wan[END_REF] to move VMs to other servers without shutting them down.

Container based virtualization:

Container based virtualization is a lightweight alternative to the hypervisors [START_REF] Soltesz | Container-based operating system virtualization: a scalable, highperformance alternative to hypervisors[END_REF] [START_REF] Xavier | Performance evaluation of containerbased virtualization for high performance computing environments[END_REF].

It is an operating system level technology that allows running multiple isolated virtual environments on the same host. Containers are based on shared operating systems and unlike traditional VMs, they don't run different OSes but use a single operating system (the host's OS). Figure 2.4 shows the difference between the two kinds of virtualization. Some examples of container based solutions are: Docker [START_REF] Docker | [END_REF], Linux containers (LXC) [START_REF]Linux containers[END_REF], Solaris Containers [START_REF]Solaris containers[END_REF], Virtuozzo Containers [START_REF]Virtuozzo containers[END_REF] and OpenVZ [START_REF] Openvz | [END_REF].

It's more appropriate to use hypervisor based virtualization when more security and flexibly are required and when heterogeneous operating systems are needed [START_REF]Virtualization and Containerization of Application Infrastructure: A Comparison[END_REF]. Container based virtualization is convenient when performance is required.

It provides better manageability with a near-native performance and gives a much higher consolidation ratio and most efficient resource usage as it supports large number of instances on a single host. In addition to being lightweight, this solution provides portability, transport, and process-level isolation across hosts.

Although being different, hypervisor and container based virtualization are not exclusive but complementary and increasingly used together. As container based virtualization is commonly used for building lightweight PaaS environments and Chapter 2. Cloud Computing and Energy Efficiency 15 hypervisors are used for IaaS Cloud services, using both solutions enables the deployment of complex services that combine both applications and underlying infrastructures over hybrid IaaS/PaaS cloud providers. Some solutions like Proxmox [START_REF]Proxmox[END_REF] offer both technologies on the same physical server.

Energy Efficiency in Cloud Data Centers

Potential power consuming units in cloud datacenters

To improve energy efficiency in the Cloud, it is important to study the power flow in typical data centers and to understand how power is distributed. In fact, more than half of the electrical power is feeding the IT loads (see Figure 2.5).

According to the EPA's Report to Congress on Server and Data Center Energy [START_REF]Report to congress on server and data center energy efficiency, environmental protection agency[END_REF], servers consume 80% of the total IT load and 40% of total data center power consumption. The rest of power is consumed by other devices like transformers, distribution wiring, air conditioners, pumps, and lighting. The power consumption of cooling equipments is important but it is proportional to the IT power consumption. Technologies like free cooling that are used by big companies (e.g. Google, Facebook, ebay...), are interesting for reducing the power consumption of cooling. These approaches lower the air temperature in data centers by using naturally cool air or water instead of mechanical refrigeration. As a result, the electrical power needed for cooling has enormously decreased. Savings can even reach 100% in case of zero refrigeration which is possible in many climates.

Major causes of energy waste

As explained in the last section, servers are the main power consumers in Cloud data centers. The key reasons for this huge consumption are the following:

Low server utilization:

As data centers are growing in size, the number of servers is continuously increasing. Most data center servers are underused. According to the Natural Resources Defense Council (NRDC) report [START_REF]Natural resources defense council[END_REF][33], average server utilization remained static between 12% and 18% from 2006 and 2012, while servers draw between 60% and 90% of peak power.

Consolidating virtual servers on a smaller number of hosts allows running the same applications with much lower power consumption. By increasing server utilization, the number of required servers and overall energy use will be greatly reduced.

Idle power waste:

Data center servers sit idly and are not processing useful work about 85-95% of the time [START_REF]Scaling up energy efficiency a cross the data center industry: evaluating key drivers and barriers[END_REF]. An idle server consumes about 70% of its peak power even if it is not used [START_REF] Naone | Conjuring clouds[END_REF]. This waste of idle power is considered as a major cause of energy inefficiency. Hence, idle servers in data centers could be turned off to reduce energy consumption.

Lack of a standardized metric of server energy efficiency:

To insure energy efficiency optimizations, it is important to use energy efficiency metric for servers to sort them according to their energy efficiency and to enable scheduling algorithms to make decisions and to select the best resources to maximize energy efficiency. Even though some metrics focusing on IT efficiency have appeared in recent years [START_REF]The Green Grid Data Center Compute Efficiency Metric[END_REF], they do not provide a simple benchmark that can drive the optimization of energy efficiency [START_REF]Scaling up energy efficiency a cross the data center industry: evaluating key drivers and barriers[END_REF].

Energy efficient solutions are still not widely adopted:

As stated in the NRDC report [START_REF]Scaling up energy efficiency a cross the data center industry: evaluating key drivers and barriers[END_REF], many big Cloud farms do a great job on energy efficiency, but represent less than 5% of the global data centers' energy use. The other 95% small, medium, corporate and multi-tenant operations are much less efficient on average. Hence, energy efficiency best practices should be more adopted and used especially for small and medium sized data centers that are typically very inefficient and consume about half of the amount of power consumed by all the data centers.

Power measurement and modeling in Cloud

Before dealing with power and energy measurement and modeling, it is important to understand power and energy relationship and to present their units of measure.

Power consumption indicates the rate at which a machine can perform its work and can be found by multiplying voltage and current while electrical energy is the amount of power used over a period of time. The standard metric unit of power is the watt (W) and the energy unit is watt-hour (Wh). Power and energy can be defined as shown in 2.1 and 2.2, where P is power consumption, I is current, V is voltage, E is energy and T is a time interval:

P = IV (2.
1)

E = P T (2.2)
To quantify power and energy consumption in Cloud, we distinguish between measurement techniques and power and energy estimation models. The first one directly measures actual power consumption via instant monitoring tools.

Power metering models estimate the power consumption of servers and VMs using hardware-provided or OS-provided metrics.

Power measurement techniques

Power direct measurement in Cloud can be achieved in data centers that embed monitoring capabilities and probes such as smart power distribution units (PDUs).

This section introduces several measurement methods to obtain information about the power consumption of servers and VMs.

Power measurement for servers:

The obvious way to get accurate information about energy consumption of servers is to directly measure it. However, this requires extra hardware to be installed in the hosts, need to add intelligent monitoring capabilities in the data center and to deal with huge amounts of data. Green Open Cloud (GOC) [START_REF] Orgerie | When Clouds become Green: the Green Open Cloud Architecture[END_REF] is an example of energy monitoring and measurement framework that relies on energy sensors (wattmeters) to monitor the electricity consumed by Cloud resources. It collects statistics of the power usage in real-time and embeds electrical sensors that provide dynamic measurements of energy consumption and an energy-data collector.

Power measurement for VMs:

Even if power consumption of servers can be measured in real time, power consumption of VMs cannot be measured by any sensor and cannot be connected to a hardware measurement device. Some effort was done in [START_REF] Orgerie | When Clouds become Green: the Green Open Cloud Architecture[END_REF] to measure VM power consumption. The virtual machine power consumption is computed by retrieving the idle power from the power consumption of the server when it hosts the VM, which is impractical and not very accurate. Alternative solutions based on extending a power monitoring adaptor between the server driver modules and the hypervisor are proposed in [START_REF] Stoess | Energy management for hypervisor-based virtual machines[END_REF] and [START_REF] Cherkasova | Measuring cpu overhead for i/o processing in the xen virtual machine monitor[END_REF]. However, this solutions measure the total power consumed by the virtualization layer and don't provide per VM power usage.

Power and energy estimation models

As most servers in modern data center are not equipped with power measurement devices and as VM power cannot be measured by sensors, models that estimate the power and energy consumption as well as VM migration power cost are being more and more attractive for power metering. This section presents a general overview of power estimation models and tools in Cloud and introduces data center energy efficiency metrics.

Power and energy modeling for servers:

Power consumption models for servers have been extensively studied in the literature [START_REF] Rivoire | A comparison of high-level full-system power models[END_REF] and vary from complex to simple.

As the CPU of a server consumes the most important amount of power and as the relationship between power and CPU utilization is linear, CPU based linear models represent a lightweight and a simple way to estimate servers' power usage [START_REF] Preeti Ranjan Panda | Power-Efficient System Design[END_REF]. In [START_REF] Lim | MDCSim: A multi-tier data center simulation, platform[END_REF], [START_REF] Fan | Power provisioning for a warehouse-sized computer[END_REF], [START_REF] Pedram | Power and performance modeling in a virtualized server system[END_REF] and [START_REF] Dargie | A stochastic model for estimating the power consumption of a processor[END_REF] simple utilization based power models for servers are proposed. They assume that CPU is the only factor in their power models and present an approximation for total power against CPU utilization (U) as shown in 2.6 and 2.3:

P = P idle + U * (P P eak -P idle ) (2.
3) P is total power consumption, P P eak is peak power consumption, P idle is idle power consumption, and U is CPU utilization (a fraction between 0 and 1). More complex power models enter into further details and present deeper analysis of power consumption. More parameters like network access rate, hard disk access rate and memory access rate are considered and implicated. Examples of these models are presented in [START_REF] Basmadjian | A methodology to predict the power consumption of servers in data centres[END_REF], [START_REF] Kansal | Virtual machine power metering and provisioning[END_REF], [START_REF] Economou | Full-system power analysis and modeling for server environments[END_REF] and [START_REF] Heath | Energy conservation in heterogeneous server clusters[END_REF].

Chapter 2. Cloud Computing and Energy Efficiency 20

Power modeling for VMs:

Virtual machines power estimating is important to better organize and schedule them in a way that minimizes the data center energy consumption.

Like the estimation models used for servers, CPU utilization could also be used to calculate the power consumption of the CPU by a VM [49] [50].

Models relying on information such as the resource utilization (CPU and memory) or/and on information provided by performance monitoring counters (PMC) known also as hardware performance counters (HPC) have been proposed in [START_REF] Gaurav Dhiman | A system for online power prediction in virtualized environments using gaussian mixture models[END_REF],

[52], [START_REF] Peng | A low-cost power measuring technique for virtual machine in cloud environments[END_REF] and [START_REF] Krishnan | Vm power metering: Feasibility and challenges[END_REF]. Based on the idea of combining PMC and CPU utilization, authors in [START_REF] Kansal | Virtual machine power metering and provisioning[END_REF] present a VM power metering approach and a software of VM power estimation called Joulemeter. This latter has the ability to accurately infer the power consumption without adding any additional hardware or software instrumentation.

Power modeling for VM migration:

Virtual machine live migration consists in moving VM between physical hosts without service interruption. This mechanism allows VM consolidation to achieve better energy efficiency however it brings also additional power consumption and its cost in terms of energy is not negligible [START_REF] Strunk | Does live migration of virtual machines cost energy[END_REF].

Energy cost of migration have not been almost considered when migrating VMs.

Key points for efficient VM consolidation are how to estimate the energy consumption of each VM migration and how to take migration decisions [START_REF] Voorsluys | Cost of virtual machine live migration in clouds: A performance evaluation[END_REF].

Some studies have been performed in [START_REF] Rybina | Investigation into the energy cost of live migration of virtual machines[END_REF], [START_REF] Strunk | Does live migration of virtual machines cost energy[END_REF], [START_REF] Hu | A quantitative study of virtual machine live migration[END_REF], [START_REF] Liu | Performance and energy modeling for live migration of virtual machines[END_REF] and [START_REF] Huang | Power consumption of virtual machine live migration in clouds[END_REF] to investigate the energy cost of VM migration and to model it. The energy overhead of live migration depends essentially on the amount of memory used by the VM and on the available network bandwidth. It increases with an increasing VM size and decreases with an increasing network bandwidth that influences it the most.

Author in [START_REF] Strunk | A lightweight model for estimating energy cost of live migration of virtual machines[END_REF] proposed a lightweight mathematical model to estimate the energy cost of VM live migration. The model is derived through linear regression and the relationship between the energy cost of migration, the network bandwidth and the VM size is expressed in Eq. 2.4 where s represents VMs size, b represents the network bandwidth and A, B and C represent constant values.

E mig = A + B * s + C * b (2.4)
Energy efficiency metrics:

In addition to power models, improving energy efficiency in Cloud data centers requires metrics that reflect data centers and servers' efficiency and provide the necessary information for high level management and scheduling decisions.

Some metrics of energy efficiency have been proposed for data centers. The Green Grid [START_REF] The | The Green Grid Data Center Power Efficiency Metrics: PUE and DCiE[END_REF] These two metrics measures only the proportion of power used by IT equipment and can be used to compare data center efficiency. Energy efficiency metrics for servers that could be used to sort them according to their efficiency and to enable scheduling algorithms to make decisions have not been widely investigated.

Performance per Watt (PPW) has became a popular metric as it can be used to measure and rank the energy efficiency of servers. It can be defined as the rate of transactions or computations that can be delivered by a computer for every watt of power consumed. Formally the PPW is defined by Intel [START_REF]Intel's cloud computing 2015 vision[END_REF] as : " The term performance-per-watt is a measure of the energy efficiency of a computer architecture or a computer hardware. It can be represented as the rate of transactions or computations or a certain performance score that can be delivered by a computer for every watt of power consumed ". This metric provides scores and rank servers no matter their size or structure. The higher the performance per watt, the more energy efficient the server is.

Power saving policies in Cloud

The main power saving strategies in Cloud data centers are dynamic frequency voltage scaling (DVFS), servers powering down and VM consolidation.

Dynamic frequency and voltage scaling (DVFS):

Dynamic voltage frequency scaling (DVFS) is a power management tool that aims to reduce the power consumption of servers when the load is low [START_REF] Pillai | Real-time dynamic voltage scaling for low-power embedded operating systems[END_REF]. DVFS, also known as CPU throttling, scales dynamically the voltage and frequency of the CPU at run-time. For example, Linux kernel allows for DVFS that can be activated in different policies: Performance, PowerSave, User-Space,Conservative, and OnDemand. Each policy has a governor that decides whether the frequency must be updated or not [START_REF] Guerout | Energy-aware simulation with dvfs[END_REF].

As this method decreases the number of instructions the processor executes in running a program, the program took a longer time and the performance reduce [START_REF] Beloglazov | A taxonomy and survey of energy-efficient data centers and cloud computing systems[END_REF]. DVFS is also too dependent on hardware and is not controllable according to the changing needs, its resulting power savings are low compared to other methods.

Even if DVFS aims at reducing power consumption, it just acts at server level. As a completely idle server still consumes up to 70% of power, DVFS power savings remain narrow. These reasons have led to the appearance of other data center level solutions that consolidate workloads onto fewer servers and switch off or put in lower power mode the idle hosts.

Powering down:

Important reduction in energy consumption can be achieved by powering down or switching off servers when they are not in use. As many servers in the data center are idle most of the time, they could be powered down or put into sleep mode in the periods of time when they are not used and then powered up if needed.

This dynamic capacity provisioning or dynamic shutdown problem is challenging as it requires careful planning to select servers to power down and as different factor must be considered. On/Off approaches have been proposed in [START_REF] Zhang | Dynamic energy-aware capacity provisioning for cloud computing environments[END_REF], [START_REF] Chen | Energy-aware server provisioning and load dispatching for connection-intensive internet services[END_REF],

[69], [START_REF] Kusic | Power and performance management of virtualized computing environments via lookahead control[END_REF] and [START_REF] Orgerie | ERIDIS: Energy-efficient Reservation Infrastructure for large-scale DIstributed Systems[END_REF] to dynamically turn on and off data center servers and thus minimizing the energy use. Although its complexity, this technique is efficient and can achieve significant reduction in power consumption.

Energy aware consolidation:

A key technique of power saving in Cloud data centers is workload consolidation onto a smaller number of servers. This approach aims to reduce the high consumption of energy by selecting the most energy efficient servers [START_REF] Srikantaiah | Energy aware consolidation for cloud computing[END_REF].

Dynamic Optimization and further workload consolidation into an even fewer number of server can be performed thanks to VM live migration. It is an essential mechanism that dynamically moves virtual machines to different hosts without rebooting the operating system inside the VM.

Energy aware consolidation problem for Cloud has been significantly studied in the literature. A detailed overview will be provided in the next chapter to present the related works in the area.

Research orientation and focus

This thesis deals with the problem of energy efficient resource allocation in Cloud data centers. We aim at reducing the power consumption of data centers by reducing the power consumption of servers. We focus essentially on energy aware consolidation techniques and optimization models that minimize the number of active servers in order to increase the energy efficiency of Cloud data centers. To quantify power consumption and energy efficiency we rely on power and energy estimation models as well as energy efficiency metrics.

Both classic Cloud service models and new hybrid models are considered and targeted. We aim to bring energy efficiency to the commonly used and widespread

IaaS providers and to support also the new trend of hybrid IaaS/PaaS Cloud providers. On-demand and advanced reservation plans are also important aspects that we consider when allocating resources to users.

Conclusions

This chapter introduced the concepts of Cloud computing and virtualization and investigated the problem of energy efficiency in Cloud. We presented the major causes of energy waste in Cloud data centers, presented the energy measurement and modeling methodologies and described the power saving techniques in Cloud data centers. This chapter has also concluded with a discussion of the orientation and focus of this thesis.

The next chapter explores in more details the problem of resource allocation or scheduling in Cloud. We provide background and state of the art solutions for energy efficient resource allocation. Then, we discuss the related issues and problems, as well as the challenges. Different important dimensions will be considered in our literature study. These dimensions cover the type of the resource provisioning plan, the Cloud service model and also the static or dynamic aspects of the solutions.

On-demand resource allocation vs advanced resource reservation

Cloud providers could offer different kinds of provisioning plans. The most two important ones are on-demand and reservation plans. The on-demand plan allows users to access resources at the time when they need. In Reservation plan the resources could be reserved earlier and the resource availability is ensured in future.

On-demand resource allocation:

Most of the Cloud providers rely on simple policies like on-demand (immediate) to allocate resources. These solutions allocate the resources if available, otherwise the requests are not accepted.

In [START_REF] Srikantaiah | Energy aware consolidation for cloud computing[END_REF], [START_REF] Beloglazov | Energy efficient resource management in virtualized cloud data centers[END_REF], [START_REF] Murtazaev | Sercon : Server consolidation algorithm using live migration of virtual machines for green computing[END_REF] and [START_REF] Li | Enacloud: An energy-saving application live placement approach for cloud computing environments[END_REF], authors proposed energy-aware heuristic algorithms and policies in order to save energy by minimizing the number of running servers. The key idea is to consolidate applications or tasks on a minimum number of servers to switch off machines in surplus. Another study is presented in [START_REF] Chimakurthi | Power efficient resource allocation for clouds using ant colony framework[END_REF] where the authors presented a nature-inspired VM consolidation algorithm influenced by Ant Colony Optimization. This algorithm aims also at reducing the number of used physical machines and thus saves energy.

All the above work discusses how to reduce energy consumption of cloud data centers using on-demand and immediate algorithms for energy efficient resource allocation. These algorithms are derived for homogeneous data centers that embed monitoring capabilities and probes (e.g smart power distribution units (PDUs)) or that embed power consumption estimation tools. Or most of today's data centers are considered mega data centers (composed of heterogeneous servers [START_REF] Koomey | Estimating total power consumption by servers in the u.s. ad the world[END_REF]) and still lack energy monitoring capabilities. More details on on-demand Cloud resources

Advanced resource reservation:

Advance resource reservation provides simple means for resource planning in the future and offers an increased expectation that resources can be allocated when demanded. Although advance reservation of resources in Cloud is very advantageous, most of the Cloud providers use simple resource allocation policies like on-demand and best effort that did not incorporate the dimension of time and support future planning of resource provisioning.

Haizea scheduler [START_REF] Haizea | [END_REF] is an open source resource lease manager. It supports four kinds of resource allocation policies: immediate, best-effort, advance reservation (AR) and deadline sensitive. AR lease is requested by users when they need to use infrastructure for fixed start and end time of lease. Resource reservation is achieved by a mapping function that uses a slot table which has two dimensions: the physical nodes and the duration. This mapping function takes a set of requested resources and maps them to physical servers based on the availability in the slot table in a specified time interval. Haizea uses also a greedy algorithm to determine how VMs are mapped to servers. This latter sorts servers from lower to higher loaded. Then, it traverses the list of nodes and tries to map as many lease nodes into each server before moving on to the next. The existing scheduling algorithms in Haizea are simple, greedy and do not address energy efficiency [START_REF] Sotomayor | Combining batch execution and leasing using virtual machines[END_REF].

Advance resource reservation algorithms for IaaS infrastructure as a Service are proposed in [START_REF] Nathani | Policy based resource allocation in iaas cloud[END_REF] and [START_REF] Loganathan | Differentiated policy based job scheduling with queue model and advanced reservation technique in a private cloud environment[END_REF]. These are queuing models based algorithms that check whether enough resources are available or not for the requested duration. They only aim at resource reservation and disregard energy efficiency requirements.

Static vs dynamic Cloud resources allocation

Energy efficient algorithms for initial Cloud resources allocation:

Currently, resource allocation mechanisms used in Cloud data centres include load balancing, round robin and greedy algorithms. The existing scheduling algorithms used by OpenNebula [81], Eucalyptus [START_REF]Eucalyptus[END_REF] and OpenStack [START_REF]Openstack[END_REF] Cloud managers are greedy or simple round robin based and do not address energy efficiency.

Authors in [START_REF] Van Do | Comparison of allocation schemes for virtual machines in energy-aware server farms[END_REF] propose a simple energy-aware policy incorporating allocation schemes of virtual servers to achieve the aim of green computing. The considered allocation schemes are round robin, first fit, etc. This work saves energy by setting servers to the lower power consumption state when they do not host VMs.

The proposed policy governs servers to a low-energy consuming state when they are idle and manages them into the operating state of full functionality when they are used.

The works in [START_REF] Mazzucco | Maximizing cloud providers' revenues via energy aware allocation policies[END_REF], [START_REF] Van Do | A performance model for maintenance tasks in an environment of virtualized servers[END_REF], [START_REF] Mitrani | Service center trade-offs between customer impatience and power consumption[END_REF], [START_REF] Mitrani | Managing performance and power consumption in a server farm[END_REF] and [START_REF] Van Do | Comparison of scheduling schemes for ondemand iaas requests[END_REF] try to save energy by proposing policies for dynamically powering servers on and off. These policies are based on queuing models and heuristic-based methods are presented. An approach based on Dynamic Voltage Frequency Scaling (DVFS) is proposed in [START_REF] Gregor Von Laszewski | Poweraware scheduling of virtual machines in dvfs-enabled clusters[END_REF]. This proposed work focus on scheduling virtual machines to reduce power consumption via the technique of DVFS.

The energy efficient algorithms proposed in [START_REF] Beloglazov | Energy efficient resource management in virtualized cloud data centers[END_REF] and [START_REF] Dang | Energy efficient resource allocation strategy for cloud data centres[END_REF] go further by adopting consolidation policies that strives to use a minimal number of servers to accommodate all requested VMs. Both works have proposed heuristics for the bin packing problem as algorithms for VMs consolidation.

Authors in [START_REF] Srikantaiah | Energy aware consolidation for cloud computing[END_REF] consolidate applications or tasks on reduced number of physical machines to switch off machines in surplus. They propose a heuristic for multidimensional bin packing and show that using less physical hosts can save energy consumption. Authors in [START_REF] Song | Multitiered on-demand resource scheduling for vm-based data center[END_REF] present also a multi-tiered resource scheduling scheme that provides on-demand capacities to the hosted services via resources

Energy efficient algorithms for VMs migration:

In [START_REF] Verma | pmapper: Power and migration cost aware application placement in virtualized systems[END_REF], the authors present a power-aware server consolidation framework, called pMapper that continuously optimize the VM placement to minimize power consumption. It relies on greedy heuristics for bin packing problem and it introduces the cost of VM migration but without providing information about its calculation.

Another similar framework called Entropy is proposed in [START_REF] Hermenier | Entropy: A consolidation manager for clusters[END_REF]. It is a resource manager for homogeneous clusters that performs dynamic consolidation based on constraint programming and it takes migration overhead into account.

Reference [START_REF] Beloglazov | Energy efficient resource management in virtualized cloud data centers[END_REF] addresses policies for dynamic VMs reallocation using VMs migration according to CPU performance requirements. Their most effective policy, a double threshold policy, is based on the idea of setting upper and lower utilization thresholds for hosts and keeping the total utilization of the CPU of all the VMs between these thresholds. If the CPU utilization of a host exceeds the upper threshold, some VMs are migrated and if it falls below the lower threshold, all the hosted VMs should be migrated.

Authors in [START_REF] Tiago C Ferreto | Server consolidation with migration control for virtualized data centers[END_REF] treat the problem of consolidating VMs in a server by migrating VMs with steady and stable capacity needs. They proposed an exact formulation based on a linear program described by a too small number of valid inequalities.

Indeed, this description does not allow solving, in reasonable time and in an optimal way, problems involving allocation of a large number of items (or VMs) to many bins (or Servers). In order to scale and find solutions for large sizes, the authors resorted to a heuristic using a static and a dynamic consolidation of VMs to reduce energy consumption of the hosting nodes or servers.

In [START_REF] Murtazaev | Sercon : Server consolidation algorithm using live migration of virtual machines for green computing[END_REF], authors presented a server consolidation (Sercon) algorithm which consists of minimizing the number of used nodes in a data center and minimizing the number of migrations at the same time. They compared their algorithm with the heuristic FFD (First-Fit Decreasing) [START_REF] Edward G Coffman | Approximate Solutions to Bin Packing Problems[END_REF] that solves the Bin-Packing problem and have shown the efficiency of Sercon to consolidate VMs and minimize migrations.

However, Sercon is a heuristic that can not always reach or find the optimal solution.

Chapter 3. Background & Related Work on Energy Efficient Cloud Resources Allocation 31

In [START_REF] Li | Enacloud: An energy-saving application live placement approach for cloud computing environments[END_REF], authors presented an approach EnaCloud for dynamic live placement taking into account energy efficiency in a cloud platform. They proposed an energyaware heuristic algorithm in order to save energy by minimizing the number of running servers. Another study relying on dynamic resource allocation is presented in [START_REF] Chimakurthi | Power efficient resource allocation for clouds using ant colony framework[END_REF]. The authors presented a nature-inspired VM consolidation algorithm inspired from an Ant Colony Optimization. This algorithm aims at reducing the number of used physical machines and thus saves energy.

Authors in [START_REF] Lin | Energy-efficient virtual machine provision algorithms for cloud systems[END_REF] propose two heuristic algorithms for energy-aware virtual machine scheduling and consolidation. These algorithms are respectively based on a dynamic round-robin approach (DRR) and on an hybrid one which combines DRR and First-Fit. Another VM consolidation method for power saving in data centers that relies on the bin packing First-Fit heuristic is proposed in [START_REF] Takeda | A rank-based vm consolidation method for power saving in datacenters[END_REF]. This method migrates VMs on the basis of server ranks where the rank represents server selection priority and is uniquely assigned to each server.

IaaS vs hybrid IaaS/PaaS Cloud providers

Scheduling and energy efficiency have been discussed and investigated in IaaS

Clouds. Almost all of the related works presented in the two last sections are dedicated for the IaaS level.

As the well known PaaS solutions for service orchestration like Windows Azure [6],

Google App Engine [START_REF]Google app engine[END_REF], and Heroku [START_REF]Cloud application platform[END_REF] are not open source and provide a blackbox solution for the public Cloud, some open-source projects like CloudFoundry [START_REF]Cloudfoundry[END_REF] and OpenShift [100] that provide private PaaS are becoming more and more popular. These PaaS systems can be built on IaaS and conduct to construct PaaS on IaaS.

In fact, new hybrid Cloud solutions that combine Iaas and PaaS like OpenStack Heat [START_REF]Openstack[END_REF] are evolving over time and being more and more attractive since they enable the joint deployment of infrastructure and applications. Thanks to this hybrid IaaS-PaaS solutions, users can deploy their own applications with the topology they choose and with having the control on both infrastructure and programs.

Like classical PaaS solutions, the new hybrid IaaS-PaaS solutions are using LXC containers [START_REF]Linux containers[END_REF] and Docker [START_REF] Docker | [END_REF]

Scope and positioning of the thesis

Table 3.1 presents a summary of the comparison between relevant related works.

We compare the various research efforts in terms of provisioning plan, Cloud service level, virtualization category, dynamicity and power saving methods.

Proposed solutions of initial Cloud resource allocation [START_REF] Beloglazov | Energy efficient resource management in virtualized cloud data centers[END_REF], [START_REF] Dang | Energy efficient resource allocation strategy for cloud data centres[END_REF] and of VM migration at IaaS level [START_REF] Verma | pmapper: Power and migration cost aware application placement in virtualized systems[END_REF], [START_REF] Takeda | A rank-based vm consolidation method for power saving in datacenters[END_REF], [START_REF] Lin | Energy-efficient virtual machine provision algorithms for cloud systems[END_REF], [START_REF] Chimakurthi | Power efficient resource allocation for clouds using ant colony framework[END_REF], [START_REF] Li | Enacloud: An energy-saving application live placement approach for cloud computing environments[END_REF], [START_REF] Murtazaev | Sercon : Server consolidation algorithm using live migration of virtual machines for green computing[END_REF], [START_REF] Tiago C Ferreto | Server consolidation with migration control for virtualized data centers[END_REF], [START_REF] Beloglazov | Energy efficient resource management in virtualized cloud data centers[END_REF], [START_REF] Hermenier | Entropy: A consolidation manager for clusters[END_REF] are heuristic based and can not reach or find the optimal solution. Another important aspect which was not always considered when moving VMs is the energy cost of migration. This cost should be taken into account before making decisions as migration brings additional power consumption and its cost in terms of energy is not negligible [START_REF] Strunk | Does live migration of virtual machines cost energy[END_REF].

Chapter Most of the proposed solutions are based on policies for the on-demand plan to allocate resources. Advance resource reservation has received less attention and existing solutions [START_REF] Nathani | Policy based resource allocation in iaas cloud[END_REF], [START_REF] Loganathan | Differentiated policy based job scheduling with queue model and advanced reservation technique in a private cloud environment[END_REF], [START_REF] Sotomayor | Combining batch execution and leasing using virtual machines[END_REF], [START_REF] Haizea | [END_REF] are based on simple heuristics and do not consider energy efficiency. However, this concept has many advantages especially for the co-allocation for resources. Advance reservation provides simple means for resource planning and reservation in the future and offers an increased expectation that resources can be allocated when demanded. This thesis investigates the problem of energy efficient Cloud resources allocation.

We aim at reducing the power consumption of data centers by reducing the power consumption of servers. We focus essentially on energy aware consolidation techniques and optimization models that minimize the number of active servers in order to increase the energy efficiency of Cloud data centers. The proposed algorithms act as an energy consumption aware VM scheduler and can be used to enhance current infrastructure managers and schedulers such as OpenNebula [81] and OpenStack [START_REF]Openstack[END_REF]. The power consumption indicators can be provided by energy consumption estimation tools such as joulemeter [START_REF] Kansal | Virtual machine power metering and provisioning[END_REF]. A dedicated simulator is used to assess performance and crosscheck with the performance results produced by the exact algorithms. Evaluation results show that the exact allocation algorithm combined with migration reduces considerably the number of required servers to serve a given load and can thus minimize power consumption in data centers.

Conclusions

The System Model

The model considers infrastructure providers allocating physical resources instances to host users' and tenants' applications or, equivalently for this work, VMs. The physical resources are seen as servers. It is assumed that applications are packaged into virtual machines to be hosted by the infrastructure providers. The cloud providers save energy and reduce power consumption by packing and consolidating through migration of VMS to maximize the number of idle servers to put to sleep mode. • Cloud IaaS manager (e.g. OpenStack [START_REF]Openstack[END_REF], OpenNebula [81] and Eucalyptus [START_REF]Eucalyptus[END_REF]) control and manage cloud resources and handle clients requests, VM scheduling and fetch and store images in storage spaces.

• Energy estimation module is an intermediate module between the cloud infrastructure manager and the energy-aware scheduler. to run the algorithms are retrieved via the Cloud IaaS manager that is also used to execute the VM deployment and migration actions.

To derive the system model, we consider the size n of client requests in terms of the number of required VMs and the types of desired VM instances (e.g., small, Chapter 4. Bin packing based Approach for Energy Efficient Resource Allocation 38 medium, large). Each V M i is characterized by a lifetime t i and a maximum power consumption p i . Each server or hosting node j, from the data center, has a power consumption limit or power cap noted P j,M ax . This can be fixed by Cloud administrators. We assume that all servers are homogeneous; extending the model to heterogeneous servers is trivial but will increase complexity and will not necessarily provide additional insight.

The approach adopted to achieve energy efficiency in our proposal is to use a bin packing algorithm for optimal placement of user requests and to follow with dynamic consolidation once a sufficient number of departures have occurred. The dynamic consolidation is handled by the migration algorithm which regroups VMs to free as many servers as possible to put them into sleep mode or to shut them down.

Energy Efficient Static Resource Allocation

Exact Allocation Algorithm

The proposed exact VM allocation algorithm is an extended Bin-Packing approach through the inclusion of valid conditions expressed in the form of constraints or inequalities. The objective is to pack items (VMs in our case) into a set of bins (servers or nodes hosting the VMs) characterized by their power consumptions.

In addition to n, the number of requested VMs, we define the number of servers, m, available in the data center. The servers are assumed to have the same power consumption limit: P j,M ax , {j = 1, 2, ..., m}. At run-time, each server j hosting a number of VMs is characterized by its current power consumption: P j,current .

Since the objective is to minimize the energy consumption of the data centers, we define as key decision variable e j for each server j that is set to 1 if server j is selected to host VMs, 0 if it is not selected. In addition, we define the bivalent variable x ij to indicate that V M i has been placed in server j and set x ij to 1; This optimization is subject to a number of linear constraints reflecting the capacity limits of the servers and obvious facts such as a VM can only be assigned to one server or a server can only host VMs according to the amount of remaining resources:

x ij = 0 otherwise
1. Each server has a power limit P j,M ax that cannot be exceeded when serving or hosting VMs and this occurs according to remaining capacity:

n i=1 p i x ij ≤ P j,M ax e j -P j,Current , ∀j = 1, . . . , m (4.2)
2. A cloud provider has to fulfil all requests within a prescribed SLA or quota and each requested VM will be assigned to one and only one server:

m j=1 x ij = 1, ∀i = 1, . . . , n (4.3)
3. For servers verifying the condition P j,M ax > P j,current and P j,current = 0, the total number of used servers is lower bounded by e j = 1, if the server j is used; 0, otherwise. (4.9)

x ij = 1, if the V M i is placed in server j; 0, otherwise. (4.10)
All the variables and constants used in the model are listed for easy reference below:

• n is the size of the request in number of requested VMs.

• m is the number of servers in the data center.

• p i represents the power consumption of V M i .

• x ij is a bivalent variable indicating that V M i is assigned to a server j.

• e j is a variable used to indicate whether the server j is used or not.

• P j,M ax represents the maximum power consumption of server j.

• P j,current represents the current power consumption of server j (P j,current = P j,idle + k p k with VM k hosted by server j).

• P j,idle represents the power consumption of server j when it is idle.

Constraints in server CPU, memory and storage are also added to the model to confine even further the model convex hull:

n i=1 cpu i x ij ≤ CP U j e j (4.11)
where cpu i is the requested CPU by V M i . CP U j is the CPU capacity of server j. where mem i is the requested memory by V M i and M EM j is the memory capacity of server j.

m i=1 sto i x ij ≤ ST O j e j (4.13)
where sto i is the requested storage by V M i and ST O j is the storage capacity of server j.

In this work we assume that these constraints are met and verified and we hence only need to focus on the energy efficiency constraints through (4.2).

Modified Best Fit Heuristic Algorithm

The exact and extended Bin-Packing is compared to a Best-Fit heuristic adaptation of the Best-Fit algorithm [START_REF] Edward G Coffman | Approximate Solutions to Bin Packing Problems[END_REF]. The heuristic proposed to achieve energy efficient VM placement consists of two steps:

1. sorting the requested VMs in decreasing order of power consumption. This builds somehow an ordered stack that is used in the second step for packing VMs in available servers;

2. The sorted VMs are handled starting from the top of the stack and attempting to place the most power consuming VMs in the server with the smallest remaining power consumption budget until a VM down the stack fits in this target server. The process repeats or continues until all VMs in the stack are placed and packed as much as possible in the most occupied servers. This will tend to free servers for sleep mode or switching off.

As this Best-Fit heuristic algorithm tries to approximate the Bin-Packing algorithm, it is selected for comparison with our exact VM allocation proposal. The allocation algorithms are combined with a migration algorithm to minimize overall data center power consumption. In our case, the objective is to benchmark the exact VM allocation and migration algorithms with a heuristic algorithm.

The Best-Fit heuristic was selected since it is known to achieve good suboptimal performance compared with classical Bin-Packing. where y i = 1 is used to indicate that server i is idle and y i = 0 means that at least one VM is active in server i. P i,idle is the power consumed by idle servers, p k is the cost in terms of consumed power when migrating V M k .

Variable z ijk is the bivalent variable expressing migration of V M k from server i to server j. Variable q i is the total number of VMs hosted on server i and that are candidate for migration into destination servers, especially server j in equation (4.14).

The objective function (4.14) is subject to the migration constraints cited earlier.

These conditions are formally expressed through valid inequalities and constraints that have to be respected when minimizing overall energy consumption.

1. When migrating V M k from a server i to a server j (see figure 4.3), the algorithm must prevent backward migrations and can only migrate into one specific destination node. Stated in an equivalent way: if a V M k is migrated from a server i (source) to a server j (destination), it can not be migrated to any other server l (l = j). The proposed inequality (4.15) also ensures that VMs in destination node and VMs migrated to destination nodes are not migrated as we are aiming at filling these nodes instead of emptying them obviously. This is reflected by the inequality :

z ijk + z jlk ≤ 1; (4.15)
2. To strengthen further the previous condition, a valid inequality is added to ensure that when a V M k is migrated from server i to server j (see figure 4.4), migrations to other nodes l (l = j) are prevented or forbidden: 3. A server j is limited by its power consumption limit P j,M ax . The inequality (4.17) allows each server j to host VMs without exceeding its power limit:

m i=1 q i k=1
p k z ijk ≤ (P j,M ax -P j,Current ) (1 -y j ) (4.17)

Where P j,Current is the current power consumption of server j.

If a non

z ijk ∆t k ≥ T 0 , (4.20)
where ∆t k = t k -CurrentT ime, where CurrentT ime represents current or VM migration handling time.

The optimal VM consolidation and migration model and objective function (4.14) can be summarized for convenience with all the valid conditions as:

max M = m i=1 P i,idle y i - m i=1 m j=1 q i k=1 p k z ijk (4.21)
Subject To:

z ijk + z jlk ≤ 1 (4.22)
∀i = 1, . . . , m , ∀j = 1, . . . , m , ∀k = 1, . . . , q i , ∀k = 1, . . . , q j , j = i, and ∀l = 1, . . . , m , l = j, k = k .

z ijk ∆t k ≥ T 0 , (4.27)
z ijk = 1, if the V M k is migrated from a server i to a server j; 0, otherwise. (4.28) Whenever necessary these algorithms may resort to turning new nodes on, when the set of active nodes are full and cannot host the new arriving VM instances (small, medium or large). Both algorithms will attempt serving the requests in the currently active nodes and will of course typically avoid turning any new nodes on.

y i = 1,

Combination of allocation and migration al-

The algorithms are combined with the migration algorithm that is launched if a number of VM jobs terminate since their dedicated resources become available for opportunistic reuse and for more efficient resource allocation and distribution.

These departures are the opportunity for the consolidation algorithm to rearrange allocations by moving VMs into the smallest possible set of nodes. All emptied or freed servers (or nodes) are turned off to minimize energy consumption.

The consolidation is achieved by the exact migration algorithm that moves VMs from selected source nodes to selected destination nodes.

Performance evaluation

Our proposed algorithms are evaluated through a Java language implementation and the linear solver CPLEX [101]. A dedicated simulator is developed to conduct the performance assessments and the comparison. The objective of the numerical evaluation is to quantify the percentage of energy savings or power consumption savings that can be expected when combining the exact allocation algorithm and the consolidation process using our proposed exact migration algorithm. The answers provided by the numerical analysis concern also the scalability and complexity of the proposed algorithms in the size of the data centers and the arrival rate of requests for resources to host VMs which is also synonymous to load on the system. Note, however, that the simulation are conducted for an arrival rate strictly lower than the rate of VM job departures from the system; thus simulations correspond to cases where the likelihood of finding an optimal or a good solution is high.

The assessment scenarios correspond to data centers with 100 servers or nodes for the first five experiments. In the last two experiments 200 servers are considered.

We collect essentially as performance indicators, the percentage of used servers (which automatically provides the energy consumed or saved by the algorithms) and the time required for the algorithms to find their best solutions (optimal for the exact algorithms). All the servers have a power consumption cap P j,M ax set to 200 watts (the peak power of a typical server is around 250 watts [102]). To perform per-VM power estimation we referred to a power estimation model proposed in [START_REF] Bertran | Technical report upc-dac-rr-cap-18 accurate energy accounting for shared virtualized environments using pmc-based power modeling techniques[END_REF]. Three SP ECcpu2006 [104] workloads (454.calculix, 482.sphinx and 435.gromacs) with high, medium and low power consumption were considered. Their associated power consumption is close to 13 watts, 11 watts and 10 watts respectively. The power estimation model proposed in [START_REF] Kansal | Virtual machine power metering and provisioning[END_REF] provided additional insight. The power consumption of other SP ECcpu2006 [104] workloads (471.omnetpp, 470.lbm and 445.gobmk) were evaluated. Estimated power consumptions were found to be between 25 and 28 watts for these elements. Without loss of generality and to ease intuitive verification of the results, we refer to these published consumption to associate to each VM type (small, medium and large) an energy consumption p i respectively equal to 10 watts (low), 20 watts (medium) more servers that could be turned off. The average line for the exact algorithm is around 80% of servers used while the average for the exact algorithm with migration is more in the order of 60%. The next experiments and simulations address the achievable energy savings using different VM requests inter-arrival times (noted by λ -1 ) and lifetimes (represented by µ -1 that also reflects the service rate µ -1 ) in order to assess the performance for variable system loads since the ration λ/µ governs performance. The number of servers has been fixed to 200 hosting nodes for the reported results in Table 5.2. One hundred (100) simulation runs are average for each parameter setting in the table. Table 5.2 reports the energy savings with the migration algorithm compared to the allocation algorithm without migration.

Energy savings depend evidently on the service rate or the lifetime of VMs or the duration of their jobs relative to the load induced by the VM resource requests.

Savings in the simulation can reach as high as 41.89% for inter-arrival times of 25 seconds and job durations of 30 seconds. For less favorable ratios or loads, the savings for the scenarios tested in the evaluation are less significant but remain and longer job durations (of 100sec).

X X X X X X X X X X X X µ -1 (s) λ -1 (
In order to complete the analysis, the energy savings that can be achieved by the Best-Fit, the exact allocation and the exact allocation combined with migration are compared for similar scenarios with a restricted set of parameter settings (λ -1 = 10s). All the servers are initially considered OFF, which means that the energy saving is initialized to 100%. Figure 4.12 depicts the evolution of the percentage of energy saved by the three algorithms. The obvious dependence on system load is reflected by the gradual decrease of energy savings for increasing VM lifetimes

Conclusions

In this chapter, we propose a bin packing based approach for energy efficient New hybrid Cloud solutions that combine Iaas and PaaS like OpenStack Heat [START_REF]Openstack[END_REF] are evolving over time and being more and more attractive since they enable the joint deployment of infrastructure and applications. However, most of the interest was on the IaaS Clouds. These solutions still lack energy efficient resource scheduling and no attention was paid to solve the problem at this level.

In IaaS clouds, the focus has been mostly on smart placement and optimal packing for efficient resource utilization including in some cases an energy efficiency criterion [72] [105]. The time dimension has received less attention when, in fact, it is expected that users or consumers will acquire virtual resources from providers We propose a new model based on graph coloring to prevent time conflicts combined with energy consumption minimization and resource utilization maximization criteria to achieve optimal and conflict free allocations. For the purpose we cast the advance resource reservation problem into a graph coloring problem and more specifically make use of graph pre-coloring and re-coloring to handle resource requests and resources releases. Graph coloring is NP-complete and is defined as coloring the vertices of a graph with the minimum number of colors without any two adjacent vertices having the same color. Graph coloring was used in various research areas of computer science such data mining [START_REF] Smith-Miles | Predicting metaheuristic performance on graph coloring problems using data mining[END_REF], image segmentation [START_REF] Gómez | A graph coloring approach for image segmentation[END_REF], register allocation [START_REF] Chaitin | Register allocation & spilling via graph coloring[END_REF], timetabling [START_REF] Neufeld | Graph coloring conditions for the existence of solutions to the timetable problem[END_REF], frequency assignment [START_REF] James | Graph colouring and frequency assignment[END_REF] and aircraft maintenance scheduling [START_REF] Biro | Cross fertilisation of graph theory and aircraft maintenance scheduling[END_REF]. Graph coloring fits well with the problem of advance resource reservation since it can be made to ensure non conflicting resource reservations (when consumers can not use the same resource simultaneously or share the resource in the same time interval). It fits also on-demand resource allocation if the start time is immediate the end time is not fixed.

In our proposed model, improvements in energy efficiency are achieved by privileging reservation of more energy efficient resources in priority. To prioritize the selection of servers we rank them according to their performance per watt PPW, a measure of the energy efficiency of a computer architecture or a computer hardware defined in [112]. The higher the performance per watt, the more energy efficient the computer is. Our model is generic enough to use alternate energy consumption or energy efficiency metrics and will remain relevant if another metric is adopted.

Starting from the graph coloring technic combined with the energy efficiency met- Recoloring (MA-EEGR) that reassign resources after services end. We compare our proposed algorithms with the baseline advance reservation algorithm (AR) used in the Haizea resource manager [START_REF] Haizea | [END_REF] and show that our heuristics achieve significantly better results in terms of energy efficiency and resource utilization.

The System Model

Our proposed model is based on graph coloring [START_REF] West | Introduction to Graph Theory[END_REF] which is defined as follows:

given a graph G = (V, E) and an integer k, a proper k-coloring of a graph G is an assignment of distinct k colors to each vertex such that two adjacent vertices have not the same color. The least k such that G is k-colorable is called the chromatic number and denoted by χ(G). To derive our proposed model, we model virtual resources as colors, we translate VM requests or demands into a graph G and we relate them to graph coloring and the energy efficiency metric.

Resource Modeling: Colors

We consider a cloud data center with m heterogeneous virtualized servers. We assume resources are exposed in the form of virtual resource units (VRUs). A

VRU is an abstraction of resources that is characterized by its computational, memory, and communication capacities and by its availability. VRU could represent a virtual container for hosting one instance of an application or could simply represent a compute unit like ECU Amazon EC2 Compute Unit [5]. Each VRU is modeled as a color c j,id where j corresponds to the server providing this VRU and id specifies the id of the VRU. Colors belonging to the same server j form a Chapter 5. Graph coloring based Approach for Energy Efficient Resource Allocation 59 cluster of colors C j . If at least one color of the color cluster C j is reserved, we consider that C j is used, else it is free.

To each C j , we associate a weight w j which represents PPW (performance per watt) of server j. As already mentioned, we adopt for the servers power efficiency metric which can be defined as the rate of transactions or computations that can be delivered by a computer for every watt of consumed power. This measure is becoming an increasingly important metric for data centers [START_REF] Wang | Review of performance metrics for green data centers: a taxonomy study[END_REF]. Manufacturers of servers such as Intel, AMD and Original Equipment Manufacturer (OEM) favor the performance per watt metric over more straightforward performance metrics.

End User Request Modeling : Request Subgraph

The end user request

R k = {V M 1 , ..., V M n k } expresses a demand of n k VMs. Each
V M i requires a specific amount r i of resource units. V M i is logically divided into r i requested resource units (defined as RRUs). Each RRU will be assigned to a unique VRU (see Figure 5.2 and Figure 5.3). The selected VRU is reserved for the associated V M i for the duration of its specified start to stop interval:

[a i , b i ].
Hence, all RRUs of a specific VM are assigned to the same reservation interval.

Energy efficiency metric

The performance per watt (PPW) is an increasingly used metric to assess the energy efficiency of data centers, supercomputers, servers or hardware [START_REF] Wang | Review of performance metrics for green data centers: a taxonomy study[END_REF]. Intel, AMD and Original Equipment Manufacturer (OEM) use the PPW [112] as the energy efficiency metric to measure and rank the energy efficiency of computers.

It can be defined as the rate of transactions or computations that can be delivered by a computer for every watt of power consumed. A server PPW tends to vary with its resources usage or solicitation. Traditionally, a server PPW is established and measured at full load (e.g. Intel). This is the metric considered in our model.

The PPW metric is used to select in priority the servers that have the highest reported PPW values. Less efficient servers will be less used or solicited and can hence be shutdown or put to sleep mode to save energy. Once graph G is constructed, the next step is to color the graph while maximizing its average power efficiency by privileging the servers with the highest PPW performance when assigning VRUs:

P P W = |V | h=1 w j x h,c j,id |V | h=1 x h,c j,id (5.1)
Less efficient servers will be less used and could be shutdown or put to sleep mode in order to achieve more energy savings.

In addition to finding the chromatic number χ(G), the number of used color clusters (or servers) should be minimized. This will consolidate VRUs assigned to RRUs in a minimum number of servers. To these objectives, we associate a number of valid conditions and constraints to speed up convergence towards a viable solution. The RRUs of the same VM have to be assigned to VRUs (colors) belonging to the same server or color cluster.

The reservation of resources at new requests arrivals can be seen as a pre-coloring extension of the graph coloring problem, a generalization of graph coloring, since at each new request arrival we have a graph where a subset of the vertices already have a color and we have to extend this pre-coloring to the whole graph (see [START_REF] West | Introduction to Graph Theory[END_REF]). To handle the new resource reservation requests, we use the EEGP heuristic based algorithm to pre-color the graph so as to achieve no-conflict scheduling and Chapter 5. Graph coloring based Approach for Energy Efficient Resource Allocation 64 To handle service departures, when VM jobs end and the assigned VRUs are released, we resort to heuristic algorithms, EEGR and MA-EEGR. Service departures are opportunities for reassignments where freed and more power efficient resources will be substituted for less performing ones. The objective is to reduce opportunistically the chromatic number χ(G) further. This corresponds to a partial graph recoloring problem [START_REF] West | Introduction to Graph Theory[END_REF] where some vertices are recolored to maximize P P W . Recoloring consists in our case of migrating a VM from a server to another more power efficient one (see Figure 5.8 and Figure 5.9).

Since the energy efficient VM reservation problem in cloud data centers is known to be NP-hard, an exact (in our case an ILP-based algorithm) will find the optimal solutions in acceptable convergence times only for small graphs or problem sizes.

In order to scale and find solutions in reasonable convergence times, we resort to the EEGP heuristic, that uses the notations and variables listed in Table 5.1. The exact algorithm is useful to check if the performance of the EEGP algorithm is close to optimal in terms of number of used colors and energy efficiency and to assess the performance improvement in convergence time.

Energy Efficient Initial Advanced Resource

Reservation

Exact energy efficient graph precoloring Algorithm

The proposed exact energy efficient graph precoloring algorithm is an extended graph coloring approach with valid conditions expressed in the form of constraints or inequalities. The problem is cast into an ILP whose objective function minimizes the number of used resources (VRUs or colors) and minimizes simultaneously the energy consumption of the data centers (or maximizes the energy efficiency by maximizing P P W ).

We define as key decision variable z c for each color c that is set to 1 if color c is reserved to a RRU, 0 if it is not reserved. In addition, we define the bivalent Chapter 5. Graph coloring based Approach for Energy Efficient Resource Allocation 67

E

The set of all edges in the graph G. E

The set of intra VM edges χ(G)

The chromatic number of a graph (the smallest number of colors needed to color the vertices of G).

G k Subgraph associated to request R k . V k Vertex set of the graph G k . E k Edge set of the graph G k . R k A request having a single id k. n k Number of virtual machines of re- quest R k . V M i A virtual machine which logically di- vided into r i RRUs. r i Number of VRUs requested by V M i . [a i , b i ]
The time during it a V M i is reserved. c j,id A virtual resource unit VRU (or a color), where j is the server to which it belongs and where id is its associated id.

C j

Cluster of colors containing colors that belong to the same server j. w j

The performance per watt (PPW) of the server j. P j,idle

Power consumption of server j when it is idle. x uc = 0 otherwise.

z c A binary variable. z c = 1 if
The objective function to reserve all the demands (or RRUs) to a minimum number of colors while maximizing energy efficiency can be expressed using:

min c∈C z c - m j=1 n u=1 c∈C j w j x uc (5.2)
This optimization is subject to a number of linear constraints and obvious facts such as a color can only be reserved to one RRU or such as RRUs of the same VM are reserved to colors belonging to the same color cluster. These conditions are formally expressed through valid inequalities and constraints that have to be respected when maximizing overall energy efficiency :

1. Each requested resource unit RRU is associated to one and only one VRU.

The proposed equality (5.3) ensures that each vertex of the graph is colored with a unique color :

c∈C x uc = 1, ∀u ∈ V (5.3) 2.
In graph coloring, any two nodes connected by an edge must have different colors. The valid inequality (5.4) ensures that two linked RRUs are reserved to two different VRUs (or colors) :

x uc + x vc ≤ 1, ∀(u, v) ∈ E, c ∈ C (5.4)
3. Another valid inequality ensures that z c is equal to 1 if the color c is assigned to a RRU u :

x uc ≤ z c , ∀u ∈ V, c ∈ C (5.5)
4. The RRUs of the same virtual machine have to be associated to colors of the same color cluster (server): x uc = 1, ∀u ∈ V (5.8)

x uc ≤ c,c ∈C j ,c =c
x uc + x vc ≤ 1, ∀(u, v) ∈ E, c ∈ C (5.9)
x uc ≤ z c , ∀u ∈ V, c ∈ C (5.10)

x uc ≤ c,c ∈C j ,c =c
x vc , ∀(u, v) ∈ E , j = 1, . . . , m (5.11)

z c = 1, if color c is used; 0, otherwise.
(5.12)

x uc = 1, if a RRU u is colored with color c; 0, otherwise.

(5.13)

The notations used by the proposed graph coloring model for the energy efficient resource reservation are listed in Table 5.1 for easy reference.

Energy efficient graph precoloring heuristic (EEGP)

Using the same underlying model illustrated in Figures 5.6 the EEGP heuristic as an alternative that converges much faster to near optimal solutions (found by the exact algorithm).

The proposed EEGP algorithm assigns gradually colors to not yet colored vertices (RRUs). For each set of vertices (RRUs) belonging to the same VM, the algorithm uses the steps specified below to achieve coloring which is equivalent to assigning a VRU to each RRU in the set. The EEGP algorithm uses the following steps to find a solution:

1. Find the color cluster C j with the highest PPW and with free VRUs. The first step of the EEGP algorithm is handled by the function Find-Color-Cluster(C,V M i ) described further in this work.

2. Determine the neighboring RRUs (or graph vertices) directly connected to V M i RRUs. This step in the EEGP algorithm is handled by the function

List-of-Connected-Nodes(V M i ) that constructs the list L V M i of RRUs connected to V M i . In Figure 5.7, L V M 4 = {v2, v3, v4}.
3. Construct the list of colors ∈ C j that are not assigned to V M i neighboring RRUs. This step uses the function List-of-Unused-colors(C j ,L V M i ) to construct the list col j,V M i .

4. Finally, the algorithm can assign to each RRU ∈ V M i a different color from the list col j,V M i .

Algorithm 1 EEGP Algorithm

Input: Graph G and a set of color clusters C Output: Coloring of G (Not colored nodes)

1: for all (Not colored) V M i ∈ V do 2: C j = Find-Color-Cluster(C,V M i ) 3: L V M i = List-of-Connected-Nodes(V M i ) 4: col j,V M i = List-of-Unused-colors(C j ,L V M i ) 5:
for all RRU ∈ V M i do 6:

color(RRU, col j,V M i )

7:

end for 8: end for

The function Find-Color-Cluster(C,V M i ) selects the color cluster C j ∈ C (or server) from which to reserve (partially or totally) VRUs for the V M i RRUs (or vertices). The selected C j , is the color cluster with the highest P P W that satisfies the following two conditions:

free-colors(V M i , C j ) = |C j | -deg(V M i , C j ) 5: if (free-colors(V M i , C j ) ≥ r i ) then 6:
found = true Sort the list of unused color clusters in decreasing order by their highest PPW.

12:

for C j in the list do end for 18: end if 1. C j has enough free colors to assign to the V M i RRUs. To verify this condition, we compute free-colors(V M i , C j ) that gives the number of free colors of C j needed to color the V M i RRUs. Let deg(V M i , C j ) be the number of colors associated to the neighbours of the V M i RRUs within server C j . The free-colors(V M i , C j ) is obtained by subtracting deg(V M i , C j ) from the total number of colors of C j . In the example shown in Figure 5.7, deg(V M 4 , C 2 ) is equal to 3, so, free-colors(V M 4 , C 2 ) is equal to 1 (4 -3). Hence, C 2 does not have enough free resources to assign to the two V M 4 RRUs (namely, v7 and v8). This compels the algorithm to pursue the search by checking the next best P P W server (or color cluster), that is check C 3 . This server has enough free colors because deg(V M 4 , C 3 ) is equal to 0 (no neighbours are using the resources) and free-colors(V M 4 , C 3 ) is equal to 10 (10 -0).

13: free-colors(V M i , C j ) = |C j | -deg(V M i , C j ) 14: if free-colors(V M i , C j ) ≥ r i then
The RRUs, v7 and v8 of V M 4 , are assigned colors 10 and 11 from C 3 . The partial re-coloring heuristic algorithm, EEGR, is triggered at service departures to find more energy efficient solutions by re-coloring some of the graph G vertices. This corresponds to the migration of some of the VMs to another more power efficient server as described:

Using

1. After the departure of a V M i , EEGR builds a list Recol V M i of candidates for re-coloring using the function VMsToRecolor(V M i ). This returns the list of VMs connected to V M i that are associated to color clusters (or servers)

whose P P W is lower than that associated to V M i . Since V M i departs and frees resources from a given server, these resources become candidates for Chapter 5. Graph coloring based Approach for Energy Efficient Resource Allocation 74

hosting VMs following migrations that will improve energy efficiency. Figure 5.8 illustrates these actions. When V M 2 (associated to C 2 ) departs (actually the entire Request R 1 departs), V M 4 that was connected to V M 2 and that is associated to the less energy efficient color cluster C 3 becomes candidate for migration that is achieved through the action: Recol V M 2 = V M 4 or colors/VRUs 6 and 7 of C 2 are assigned to V M 4 nodes v7 and v8 respectively.

2. For each V M j belonging to list Recol V M i , color V M j using EEGP.

Algorithm 2 EEGR Algorithm

1: if (End of V M i associated to C k ) then 2: Recol V M i ← VMsToRecolor (V M i ) 3:
for all V M j ∈ (Recol V M i ) do 4:

EEGP(V M j )

5:

end for 6: end if gained by this mechanism, E j,gain , is lower than the threshold fixed by the administrator, E threshold (see Eq. 5.14). We define E j,gain as the energy saved after emptying a server j. This gain is calculated by retrieving the energy consumed by VM migrations from server j to a server k (E mig,C j /C k ) and the energy consumed to switch on the server j from the idle energy consumption of server j (E j,idle ) during the period of its inactivity (t j,inactive ). For simplicity reasons, we assume powering on or off a server is negligible and E j,OF F/ON is equal to zero. The threshold E threshold is set to the lowest possible value which is zero. The energy consumption of VM migrations E mig,C j /C k is estimated using a lightweight mathematical model proposed in [START_REF] Strunk | A lightweight model for estimating energy cost of live migration of virtual machines[END_REF] (see section 2.3.3.2 for more details). where v is the number of nodes to be recolored and m is the number of hosts or color clusters.

       E j,gain ≥ E threshold E j,gain = E j,idle -(E mig,C j /C k + E j,
Algorithm 3 MA-EEGR Algorithm

1: if (End of V M i associated to C k ) then 2: clusterlist ← list-clusters-to-empty (V M i ) 3: for C j ∈ clusterlist do 4: if (Empty(C j ,C k )) then 5:
if (E j,gain >= E threshold ) then 6:

vmlist ← list-vm-to-migrate (V M i , C j )

7:

for all V M j ∈ vmlist do 8:

L V M j = List-of-Connected-Nodes(V M j ) 9: col k,V M j = List-of-Unused-colors(C k ,L V M j ) 10:
for all RRU ∈ V M j do 11:

color(RRU, col k,V M j )

12:

end for

Evaluation results

Energy Efficient Initial Advanced Resource Reservation

In the experiments below, we assess the performance of the EEGP heuristic in comparison with the proposed exact solution and also with the advance reservation (AR) algorithm from the Haizea scheduler. The AR algorithm is a greedy mapping algorithm based on the idea that free physical hosts are selected in priority. 5.10, that the EEGP heuristic is computationally efficient compared to the exact algorithm. For example, the heuristic algorithm finds solutions within 0.0005 % of optimal in about 10 ms while the exact algorithm requires 31 mn to find the optimal solution. In addition to global graph size G, convergence time depends also on the request subgraph sizes. As The AR algorithm is faster than EEGP for large instances since it does not seek near optimal or optimal solutions. It just needs to find the least loaded servers to host VMs. Looking jointly at Figures 5.11 and 5.12, the EEGP outperforms considerably the AR algorithm in terms of average PPW and uses much fewer servers (a few versus tens of servers or physical hosts). Figure 5.12 shows that the EEGP algorithm is four times better than the AR algorithm in energy efficiency.

Chapter 5. Graph coloring based Approach for Energy Efficient Resource Allocation 79

In Figure 5.13, the EEGP heuristic performance is identical to that of the exact algorithm in terms of energy efficiency. Both algorithms provide the same average performance per watt when reserving VRUs and have the same behaviour since they select the most energy-efficient resources. The EEGP heuristic consumes a little bit more VRUs (or colors) than the exact solution as depicted in Figure 5.14. The chromatic number (number of used colors) is slightly higher when the heuristic algorithm is used. The EEGP heuristic uses nevertheless as many servers as the exact solution to achieve the resource reservation as depicted in Figure 5.15. The AR algorithm selecting the less loaded servers consumes more servers (a factor of 10). The effectiveness of EEGP heuristic is highlighted by the very small (0.0014%) relative gap with the exact solution.

The EEGP heuristic overall performance is quite good in terms of energy, resource usage and is as remarkable in terms of convergence time that is found close to the simple and basic AR algorithm. In the experiments below, we assess firstly the performance of the EEGP heuristic in comparison with the proposed EEGP+EEGR algorithm that combines the initial reservation process (EEGP) with the dynamic adaptation process(EEGR).

Recall that EEGR algorithm aims at adapting dynamically the resources placement at service departures using the technique of resources recoloring. Secondly, we assess the impact of the migration cost on the recoloring algorithms. We compare the gain, in term of energy, obtained when comparing the Energy Efficient Graph Recoloring and the Migration Aware Energy Efficient Graph Recoloring algorithms.

Chapter 5. Graph coloring based Approach for Energy Efficient Resource Allocation 83

The performance evaluation is conducted for low and high load conditions and for sustained arrivals of resource reservation requests as well as discontinuous requests to highlight when the use of EEGR is relevant.

(1) Algorithms' behaviour when demand is high and continuous: As expected, the EEGP is more than five times better than AR in terms of average energy efficiency. For this high load conditions, EEGP and EEGR, achieve slightly better results (on average) than EEGP alone (two per cent). EEGR finds no opportunities to improve the overall energy efficiency through migration since resources are always used. No resources can be freed for long enough to be exploited for improvements. (2) Algorithms' behaviour when request arrivals is low:

Figure 5.17 shows the average performance per watt of the data center at low load for the three algorithms. In this simulation, the size of data center m is set to 1000.

Chapter 5. Graph coloring based Approach for Energy Efficient Resource Allocation 84

The load is generated in a an Interrupted Poisson Process arrival pattern. EEGP is more than twice better than AR in terms of average performance per Watt.

Results achieved by EEGP and EEGR both running together are roughly three times better than AR and nearly twenty-five percent better than EEGP. The quiet periods, in the requests arrivals, allow the EEGR algorithm to improve energy efficiency through migration of active VMs into less power consuming servers. The use of EEGR is only useful when there are enough and long enough quiet periods in user demand. (3) Resource utilization:

Conclusions and Discussion

Energy efficiency is becoming increasingly important for Cloud data centers. Their growing scale and their wide use have made a great issue of power consumption.

The overall goal of this work is to design and develop models and algorithms for energy efficient resource allocation while considering different dimensions of the problem. These key dimensions are the resource provisioning plan, the dynamicity of the solution, the type of the virtualization and the Cloud service model.

Solving the problem of resource allocation in Cloud while maximizing energy efficiency and adopting the previously cited dimensions, is a very challenging issue.

In this thesis, we address the problem with its multiple facets and levels to provide not only a specific solution, but also a generic and complete approach. The major contributions which have been made by this thesis are summarized as follows:

• Chapter 2 introduces the concepts Cloud computing and of virtualization that serves as its enabling technology. We further investigate the problem of energy efficiency in Cloud data centers by studying the major causes of energy waste, presenting the different power saving techniques and introducing energy measurement and modeling in Cloud environments.

•

Future Research Directions

Some issues related to the energy efficient resource allocation problem in Cloud environments have not been addressed in this thesis, these limitations will be addressed as future work. The potential future directions of this research include the following:

• Admission control mechanisms that use different strategies are important to decide which user requests to accept. In fact, advanced reservation technique enables users to get guaranteed services in private Clouds where the capacity is limited since advanced reservation requests have strict starting and ending time and resources must be available at the specified time. If the system is extensively flooded with advance reservation requests, this will lead to starvation of on-demand requests. We aim to integrate an admission control mechanism with our solution to improve the optimality our of resource scheduling. This mechanism will be based on a negotiation process to propose alternative time slots if advance reservation requests are not accepted.

• Load prediction techniques play important role to predict the overall load in the system. As future work, we will enhance our solutions with prediction algorithms to further improve the stability and performance of our proposed resource allocation algorithms.

• Most research on resources scheduling in Cloud environments focus on computational resources. Scheduling network and storage with computational resources is not well investigated. In addition, the network connection between Cloud data centers is a important aspect to consider when scheduling Chapter 6. Conclusions and Future Research Directions 93 resources in geographically distributed Cloud environments. Future work must be done to extend our proposed work in order to deal with the above mentioned aspects.

• An important goal of this thesis is to integrate our proposed solutions for energy efficient resource allocation with OpenStack. We aim to provide the missing scheduling policies and to bring energy efficiency to this Cloud environment. We are actively progressing in the achievement of this goal and different manuals and documents were developed and published.

Thesis Publications

International Journal

• C.

A.3 Initial network creation

After creating the image, the next step is to create the virtual network infrastructure to which the instance will connect.

Create an external network:

viii 5 .

 5 11 Convergence Time . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.12 Average Performance Per Watt . . . . . . . . . . . . . . . . . . . . 5.13 Average Performance Per Watt . . . . . . . . . . . . . . . . . . . . 5.14 Chromatic Number . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.15 Number of used servers . . . . . . . . . . . . . . . . . . . . . . . . . 5.16 Average Performance Per Watt( high load conditions ) . . . . . . . 5.17 Average Performance Per Watt ( low load conditions ) . . . . . . . 5.18 Number of used servers . . . . . . . . . . . . . . . . . . . . . . . . . 5.19 Migration percentage comparison between MA-EEGR and EEGR . 5.20 Comparison between MA-EEGR and EEGR in terms of number of server shutdown . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.21 Comparison between MA-EEGR and EEGR in terms of migration cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.22 Recoloring using EEGR algorithm . . . . . . . . . . . . . . . . . . . 5.23 Recoloring using MA-EEGR alorithm . . . . . . . . . . . . . . . . . A.1 VM instance creation in Openstack-nova IaaS providers . . . . . . . B.1 Container based virtualization vs hypervisor based virtualization . . B.2 Components interaction to create a stack . . . . . . . . . . . . . . B.3 Horizon dashboard interface after stack creation . . . . . . . . . . . B.4 Containers creation . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 Chapter 1 .

 11 Introduction 2

Figure 1 . 1 :

 11 Figure 1.1: Resource Allocation in Cloud Computing

Chapter 1 .

 1 Introduction 6 Chapter 6 draws conclusions, summarizes our major contributions and discusses perspectives, challenges and future work directions.

2. 2 . 1

 21 What is Cloud Computing? Cloud computing has become one of the fastest growing paradigms in computer science. It is a model for providing IT resources as a service in a cost efficient Chapter 2. Cloud Computing and Energy Efficiency 8 and pay-per-use way. By adopting Cloud services, companies and simple users are enabled to externalize their hardware resources, services, applications and their IT functions.

Figure 2 . 1 :

 21 Figure 2.1: Cloud Computing

Figure 2 . 2 :

 22 Figure 2.2: Classic Cloud service models

  concept has often been a subject of speculation and discussion. The consolidation of IaaS and PaaS is one of the key predictions for this year. Lines between Cloud services are blurring which results in the combination of IaaS and PaaS and to the appearance of new hybrid Cloud providers that enable users to create a single continuum of services. Leading companies like Amazon[5], Microsoft[10] and Google[11] are concurrently going to blend IaaS and PaaS and don't want users to think strictly about IaaS or PaaS when they require Cloud services. An example of this trend of new combined Chapter 2. Cloud Computing and Energy Efficiency 12 Cloud services is Kubernetes[12]. It is a newly released Google solution that solves both IaaS and PaaS. Openstack [13] IaaS provider is also gaining PaaS features and providing combined IaaS-PaaS services by orchestrating Docker [14] containers via Openstack Heat. Details about this mechanism are given in Appendix B.

Figure 2 .

 2 Figure 2.3: Server Virtualization

  [19] and Virtual Box[20]. Guests are called virtual machines VMs and they run different operating systems such as Windows and Linux on top of the same physical host. Even if this type of virtualization introduces an additional software layer, it enables resource consolidation

Figure 2 . 4 :

 24 Figure 2.4: Container based virtualization vs hypervisor based virtualization

Figure 2 . 5 :

 25 Figure 2.5: Typical power draw in a data center Source: Cisco white paper [1]

Figure 2 . 6 :

 26 Figure 2.6: Server power model based on CPU utilization.A linear model serves as a good approximation[START_REF]Power Management in the Cisco Unified Computing System: An Integrated Approach[END_REF].

26 3. 2

 262 As mentioned earlier in the report, the main objective of this thesis is the design and development of models and algorithms for energy efficient resource allocation in Cloud data centers while considering different dimensions of the problem. These key dimensions are the resource provisioning plan, the dynamicity of the solution, the type of the virtualization and the Cloud service model. To provide efficient solutions, to address the issue from different angles and to handle the constraints of the problem at different levels, existing state of the art methods and models need to be studied and discussed. This chapter presents the current state of the art and work of the areas related to this thesis. We describe in more details the problem of energy efficient resource allocation in Cloud data centers then we provide an overview on the state of the art of energy efficient Cloud resource allocation at different dimensions and levels. The chapter also presents the research objectives and the thesis positioning in relation to existing research. Chapter 3. Background & Related Work on Energy Efficient Cloud Resources Allocation Energy Efficient Resource Allocation in Cloud Resource allocation or scheduling is one of the most important tasks in cloud computing. It consists in identifying and assigning resources to each incoming user request in such a way that the user requirements are met and specific goals of the cloud provider are satisfied. These goals could be optimizing energy consumption or cost optimizing, etc. Based on the resource information like resource usage and monitoring, the requests information and the Cloud provider goal, the resource allocator or scheduler finds out resource allocation solutions, see Figure 3.1. Schedulers could just ensure the initial and static resource allocation after request arrival or ensure both static and dynamic resource allocation to manage resources in a continuous way and to further optimize and readjust the old requests.

Figure 3 . 1 :

 31 Figure 3.1: Resource Allocation in Cloud Computing

Chapter 3 .

 3 Background & Related Work on Energy Efficient Cloud Resources Allocation 28 allocation algorithms are given in the next section where the solutions are classified into static and dynamic.

  Two different types of resource allocation are static and dynamic allocation. Static resource allocation is performed initially when requests arrive. Dynamic resource allocation is used to manage resources in a continuous way and to further optimize and readjust the old requests. The dynamic resource allocation or consolidation Chapter 3. Background & Related Work on Energy Efficient Cloud Resources Allocation 29 is handled by VM live migration and aims to minimize the number of used or activated servers.

4 .

 4 This chapter described the main research efforts in the area of energy efficient Cloud resource allocation. We mainly focus on the reservation plan dimension to classify the related work. Dimensions of type of the virtualization type and the Cloud service model are also considered in the discussion. This chapter presented also the thesis position in relation to existing work.The main direction of this thesis is the design and development of models and algorithms for resource allocation in Cloud data centers while increasing energy efficiency. The next chapters describe in detail our contributions for this research direction.Cloud data centers are electricity guzzlers especially if resources are permanently switched on even if they are not used. An idle server consumes about 70% of its peak power[START_REF] Naone | Conjuring clouds[END_REF]. This waste of idle power is considered as a major cause of energy inefficiency. An important way to bring energy efficiency to Cloud environments is to introduce energy aware scheduling and placement algorithms and enhanced resource management. This work is a contribution to the reduction of such excessive energy consumption using energy aware allocation and migration algorithms to have a maximum number of idle servers to put into sleep mode. Intel's Cloud Computing 2015 Vision[START_REF]Intel's cloud computing 2015 vision[END_REF] stresses also the need for such dynamic resource scheduling approaches to improve power efficiency of data centers by shutting down and putting to sleep idles servers. This work proposes an exact energy aware allocation algorithm using the formulation of the Bin-Packing problem. The aim of this algorithm is to reduce the number of used servers or equivalently maximize the number of idle servers to put in sleep mode. To take into account workloads and service times a linear integer programming algorithm is used to optimize constantly the number of Chapter Bin packing based Approach for Energy Efficient Resource Allocation 36 used servers after service departures. This migration algorithm is combined with the exact allocation algorithm to reduce overall energy consumption in the data centers.

Figure 4 .

 4 Figure 4.1 depicts the system model composed of the proposed energy efficient allocation and migration algorithms (contributing to scheduling), an energy consumption estimator and a cloud manager (handling infrastructure resource instantiation and management). Each module is briefly described to set the stage for the analytical modeling of the energy efficient resource allocation problem in clouds.

Figure 4 . 1 :

 41 Figure 4.1: The system model

Chapter 4 .

 4 . The objective function to place all the demands (or VMs) in a minimum number of servers can be expressed using: min Z = Bin packing based Approach for Energy Efficient Resource Allocation 39

4 )pChapter 4 .

 44 The exact and extended Bin-Packing VM allocation model can be summarized by lumping the objective function with all the constraints and conditions into the following set of equations: i x ij ≤ P j,M ax e j -P j,Current , ∀j = 1, . . . , m (4.6)m j=1 x ij = 1, ∀i = 1, . . . , n(4.7) Bin packing based Approach for Energy Efficient Resource Allocation 40

Chapter 4 .

 4 m i=1 mem i x ij ≤ M EM j e j (4.12) Bin packing based Approach for Energy Efficient Resource Allocation 41

Chapter 4 .Chapter 4 .

 44 Bin packing based Approach for Energy Efficient Resource Allocation 42 4.4 Energy Efficient Dynamic Resource Allocation (Re-allocation) 4.4.1 Exact Migration AlgorithmThe placed and running VMs in the servers will gradually leave the system as their related jobs end. These departures are the opportunity to re-optimize the placement by migrating VMs always in the system for consolidation in a minimum number of fully packed severs. A migration algorithm based on an integer linear program (ILP) is presented to achieve the consolidation. This ILP algorithm consists in introducing a number of valid inequalities to reduce the span of the convex hull of the migration problem.The mathematical model for the VM consolidation via migration relies on a linear integer programming formulation. The objective for the algorithm is to migrate VMs from nodes selected as source nodes (those the algorithm aims at emptying so they can be turned off) to other selected destination nodes (those the algorithm aims at filling so they serve a maximum number of VMs within their capacity limits).Ideally, the algorithm should minimize the number of active nodes, maximize the overall number of VMs handled by the active nodes and hence maximize the number of unused, empty or idle nodes. The algorithm should also minimize the power consumption caused by migrations. If the power consumption or cost of VM migration is uniform or homogeneous across hosting nodes or servers, the objective reduces to minimizing the number of migrations.The migration concerns the set of non idle servers m , m < m, whose power consumptions are lower than P j,M ax with j in m . Despite the slight reduction in size m < m, the problem remains NP-hard. Hence, we resort to an exact algorithm based on linear integer programming to address optimal migration for practical problem sizes or number of instances.The objective function for the optimal VM migration and consolidation can be expressed as the maximization of the number of idle servers in the infrastructure: max M = m i=1 P i,idle y i -Bin packing based Approach for Energy Efficient Resource Allocation 43

Figure 4 . 2 :

 42 Figure 4.2: Example of VMs' migration

Chapter 4 .

 4 Bin packing based Approach for Energy Efficient Resource Allocation 44

Figure 4 .

 4 Figure 4.3: A server candidate to a migration should not migrate its own VMs

Figure 4 . 4 :

 44 Figure 4.4: A V M k can not be migrated to many servers at the same time

m j=1,j =i z ijk ≤ 1 ( 4 . 23 )Chapter 4 .pz

 14234 ∀i = 1, . . . , m , ∀j = 1, . . . , m , ∀k = 1, . . . , q i , ∀l = 1, . . . , m , l = j. Bin packing based Approach for Energy Efficient Resource Allocation 46 k z ijk ≤ (P j,M ax -P j,Current ) (1 -y j ) (4.24) ∀j = 1, . . . , m, j = i ijk = q i y i , ∀i = 1, . . . , m , j = i (

Figure 4 .Chapter 4 .

 44 Figure 4.5 summarizes how the allocation and migration algorithms are combined to achieve minimal energy consumption in infrastructure nodes and hence data centers. Both the exact Bin-Packing extension and the Best-Fit heuristic are used to ensure optimal and suboptimal placement respectively.

Figure 4 . 5 :

 45 Figure 4.5: Combination of the migration algorithm with the two allocation algorithms

Chapter 4 .

 4 Bin packing based Approach for Energy Efficient Resource Allocation 49 and 30 watts (high) to stay in line with published values. The requests for resources to serve VMs have a constant arrival rate. The requested VM instance types are discrete uniform in [1, 3] (1 for small, 2 for medium and 3 for large instances). The VM sizes are arbitrarily drawn as uniform in [1, 3] and classified according to their type. We retained only the random drawings that fulfill the VM characteristics in size and type.

Figure 4 . 6 :

 46 Figure 4.6: Comparison between the exact and heuristic allocation algorithms

Figure 4 .

 4 Figure 4.6 depicts results of a comparison between the adapted Best-Fit heuristic and our exact extended Bin-Packing allocation algorithms. The simulations correspond to 100 servers and resource requests in number of VMs in the [1, 200] range. The lifetime of the VMs are uniform in [30s, 180s]. That is VM jobs last at least 30s and will terminate in less than 180s. The exact allocation algorithm as expected outperforms the Best-Fit heuristic for the 1000s time interval simulated and reported in Figure 4.6. The Best-Fit heuristic uses more often all available nodes or servers (100% ordinate value in Figure 4.6) while the exact algorithm manages to use fewer nodes with 10 to 50% more unused servers that Best-Fit.

Figure 4 . 4 .

 44 Figure 4.7 extends the analysis for the exact and extended Bin-Packing allocation algorithm by comparing its performance with and without consolidation. When the exact algorithm is combined with the migration algorithm (that uses migration to empty some nodes) it can significantly provide additional power savings or

Figure 4 . 7 :

 47 Figure 4.7: Performance comparison of the exact allocation algorithm with and without migration

Figure 4 .

 4 Figure 4.8 pursues the analysis for the exact bin-Packing VM allocation algorithm by reporting performance as a function of data center sizes and VM requestsinduced load. The time before convergence to the optimal placement is reported as a function of data center size (from 100 to 1000 nodes or servers) for request sizes ranging from 50 to 500 VMs. Clearly, because the problem is NP-Hard, the convergence time of the exact algorithm grows exponentially for requests exceeding 300 VMs; especially for number of servers beyond 400. The time needed to find the optimal solutions remains acceptable and reasonable, within 10 s, for data center sizes below 500 receiving requests less than 400 VMs. The time needed for convergence grows unacceptably high outside of this operating range for the simulated scenarios (tens of seconds to few minutes). This motivated the use of the Best-Fit algorithm to find solutions faster even if they are bound to be suboptimal as reported in Figure4.6.

Figure 4 . 8 :

 48 Figure 4.8: Execution time of the Exact Allocation Algorithm

Figure 4 . 9 :Chapter 4 .

 494 Figure 4.9: Execution time of the exact migration algorithm (m = 5)

Figure 4 .

 4 Figure 4.10: Execution time of the exact migration algorithm (m = 10)

Chapter 4 .

 4 Bin packing based Approach for Energy Efficient Resource Allocation 53

Figure 4 .

 4 Figure 4.11: Execution time of the exact migration algorithm (m = 20)

Chapter 4 .

 4 Bin packing based Approach for Energy Efficient Resource Allocation 54

Figure 4 .

 4 Figure 4.12: Energy savings

4 .

 4 resource allocation for classical IaaS clouds. We formulate the problem of energy efficient resource allocation as a bin-packing model. This model is VM based and provides on-demand resource allocation. We propose an exact energy aware algorithm based on integer linear program (ILP) for initial resource allocation. To deal with dynamic resource consolidation, an exact ILP algorithm for dynamic VM reallocation was also proposed. It is based on VM migration and aims to optimize constantly the energy efficiency after service departures. A heuristic method based on best-fit algorithm was also adapted to the problem. Experimental results show benefits of combining the allocation and migration algorithms and Chapter Bin packing based Approach for Energy Efficient Resource Allocation 55 demonstrate their ability to achieve significant energy savings while maintaining feasible runtimes when compared with the best fit heuristic. The next chapter introduces a graph coloring-based approach to deal with the new trends in Cloud.

  for a specified time interval to take advantage of the cloud flexibility and cost reduction benefits. Energy efficient advance resource reservation (or scheduling) combined with optimal placement has not been as thoroughly investigated. The starting and ending time of user requested cloud services have to be taken into account and combined with energy consumption minimization criteria in order to avoid resource reservation conflicts and collisions for concurrent or overlapping requests. Chapter 5. Graph coloring based Approach for Energy Efficient Resource Allocation 57This is the focus of our work where we take into account advance resource reservation and time conflicts while simultaneously aiming at improved energy efficiency and resource utilization for providers. We aim to provide a generic model and optimization algorithms of energy efficient resource allocation that could be applied by IaaS-PaaS cloud providers. Another goal is to dynamically optimize placement while avoiding conflicts when allocating resources to users by preventing the assignment of resources to concurrent requests.

Figure 5 . 1 :

 51 Figure 5.1: Request Subgraph Construction

Figure 5 . 2 : 61 Figure 5 . 3 :Figure 5 . 4 :

 52615354 Figure 5.2: Graph coloring based model

Figure 5 . 5 :

 55 Figure 5.5: Model building in case of a LAMP application deployement

Chapter 5 . 63 5. 2 . 4

 56324 Graph coloring based Approach for Energy Efficient Resource Allocation Graph coloring for Energy Efficient Resource Reservation Conflicts between all requested resources are derived from an undirected global dynamic graph G. G = (V, E) is dynamically constructed over time and updated after request arrivals and departures. Vertex set V represents RRUs belonging to all requested VMs and E represents the set of all edges in the graph. In case of a new request arrival (request R k ), new nodes and edges will appear on the graph. Thus, the global graph (G = G ∪ G k ) will represent a conjunction of G and G k . In case of a request reservation end, G k will be retrieved and deleted from the global graph G. This is depicted in the first step of Figure 5.6 and 5.8 illustrating how graph G is updated at request arrivals and service departures.

Figure 5 . 6 : 65 Figure 5 . 7 :

 566557 Figure 5.6: Graph Coloring (first request)

Figure 5 . 8 :

 58 Figure 5.8: Energy Efficient Graph Recoloring

x

  vc , ∀(u, v) ∈ E , j = 1, . . . , m (5.6) Chapter 5. Graph coloring based Approach for Energy Efficient Resource Allocation 70The exact and extended graph precoloring model can be summarized by lumping the objective function with all the constraints and conditions into the following set of equations:

  and 5.7, to derive the exact ILP-based algorithm (through a graph pre-coloring extension), we propose Chapter 5. Graph coloring based Approach for Energy Efficient Resource Allocation 71

Chapter 5 . 2 :

 52 Graph coloring based Approach for Energy Efficient Resource Allocation 72 function: Find-Color-Cluster (C,V M i ) : Input: A V M i and a set of color clusters C Output: A color cluster C j to color V M i RRUs 1: boolean found = false Sort the list of used color clusters in decreasing order by their highest PPW. 3: for C j in the list do 4:

  C j ensures that the minimum number of colors (VRUs) are used to color the graph G. For example, if C j and C k have the same power weight Chapter 5. Graph coloring based Approach for Energy Efficient Resource Allocation 73 (or P P W ) and C j is used but C k is not, C j is chosen because some of its colors are already used in the graph. To color a subgraph G k , the worst complexity of the algorithm is |V k | * m, where V k is the number of nodes of G k and m is the number of hosts or color clusters. The cost of updating the global graph G by adding or deleting subgraphs depends on the data structure used to represent this graph. We adopt the most commonly used data structure for representing graphs which is the adjacency list representation implemented with linked lists of adjacent nodes because of its simplicity and dynamic aspects. This structure stores the adjacency list of each node as a linked list in a space of O(|V | + |E|), supports optimal and dynamic insertions or deletions of nodes and fast scanning of edges. Inserting or deleting edges and nodes takes O(1) when using adjacency list. To add subgraph G k to the global graph G, nodes V k and intra VM and inter VM edges E k should be inserted. The links that indicate overlapping reservation time intervals (inter VM edges) are determined after consulting the head nodes list which is sorted according to reservation time. Hence, the worst complexity of adding a subgraph G k to G is O(|V | + |V k | + |E k |). 5.4 Energy Efficient Advanced Dynamic Resource Reservation 5.4.1 Energy Efficient Graph Recoloring Heuristic (EEGR)

Figure 5 . 9 : 75 5. 4 . 2

 597542 Figure 5.9: Reservation over time

  shown in Figure 5.10, convergence time for the exact algorithm is 13 min for (|V | = 112, |V k | = 43) and 4.4 s for (|V | = 117, |V k | = 5). The EEGP heuristic can achieve near optimal performance with significantly reduced computation time (see Figure 5.11) not exceeding 12 s for graph sizes of 3000 (|V | = 3000).

Figure 5 . 80 Figure 5 . 12 :

 580512 Figure 5.10: Convergence Time

Figure 5 . 14 :

 514 Figure 5.14: Chromatic Number

Figure 5 .

 5 Figure 5.16 shows the average performance per watt of the data center when applying AR, EEGP and EEGP+EEGR algorithms. In this experiment, the size of data center m is set to 1000. Request arrivals follow a poisson process with rate of 10 requests per second. The average performance per Watt of the data center improves significantly when the EEGP and EEGP+EEGR algorithms are used.

Figure 5 . 16 :

 516 Figure 5.16: Average Performance Per Watt( high load conditions )

Figure 5 .

 5 Figure 5.17: Average Performance Per Watt ( low load conditions )

Figure 5 . 18 ,

 518 Figure5.18, depicts the evolution of the number of used servers by the proposed heuristics and AR to assess their performance as a function of load. To reveal the relative performance of the algorithms, we use a specific scenario where we increase gradually the system load (through additional arrivals) until event 50 (see abcissa) and then uniformly decrease this load at constant rate from event 50 to 300 through service departures. The results show that for high load both EEGP and EEGP combined with EEGR use the same number of servers (curves up to event 50 when load reaches its maximum in the simulated scenario) while AR uses many more. Our heuristic algorithms use only 135 servers (at event 50 or

Figure 5 . 18 :Figure 5 . 19 :Figure 5 . 20 :Figure 5 . 21 : 88 Figure 5 . 22 :

 51851952052188522 Figure 5.18: Number of used servers

  Chapter 3 presents a survey of the state of the art on energy efficient resource allocation in cloud environments. We describe in more details the problem of energy efficient resource allocation in Cloud data centers then we provide an overview on the state of the art of energy efficient Cloud resource allocation at different dimensions and levels. Our goal in this survey has been to get a deeper understanding of the problem, to position the thesis in relation to existing research and to identify the key challenges and issues. • In chapter 4, we propose a bin packing based Approach for Energy Efficient Resource Allocation for Classical IaaS clouds. We formulate the problem of energy efficient resource allocation as a bin-packing model. This model is VM based and provides on-demand resource allocation. We propose an exact energy aware algorithm based on integer linear program (ILP) for initial resource allocation. To deal with dynamic resource consolidation, an exact ILP algorithm for dynamic VM reallocation was also proposed. It is based on VM migration and aims to optimize constantly the energy efficiency after service departures. A heuristic method based on best-fit algorithm was also adapted to the problem. Experimental results show benefits of combining the allocation and migration algorithms and demonstrate their ability to achieve significant energy savings while maintaining feasible runtimes when compared with the best fit heuristic. • Chapter 5 presents a graph-coloring based approach for energy efficient resource allocation in hybrid IaaS-PaaS providers. This approach relies on a new graph coloring based model that supports both VM and container virtualization and provides on-demand and advanced reservation resource provisioning. We propose and develop an exact Pre-coloring algorithm for initial/static resource allocation while maximizing energy efficiency. A heuristic Pre-coloring algorithm for initial/static resource allocation was also proposed to scale with problem size. To adapt reservations over time and to improve further energy efficiency, we introduce two heuristic Re-coloring algorithms for dynamic resource reallocation. Evaluation and comparison of the exact Chapter 6. Conclusions and Future Research Directions 92 and heuristic solutions in terms of energy efficiency, resource usage and convergence time are conducted to demonstrate the efficiency of our proposed algorithms. Our heuristic Pre-coloring algorithm for initial resource allocation is shown to perform very close to optimal, to scale well with problem size and to achieve fast convergence times. Both heuristic Re-coloring algorithms that dynamically adapt the resource allocations at service departures gain significantly energy efficiency and exhibit fast convergence.

# 4 #

 4 Create the external network : neutron net -create ext -net --shared --router : external = True # Create the subnet for the external network : neutron subnet -create ext -net --name ext -subnet \ --allocation -pool start =192.168.100.101 , end = 1 92. 1 6 8 . 1 0 0 . 2 0 0 \ --disable -dhcp --gateway 192.168.100.1 1 9 2 . 1 6 8 . 1 0 0 . 0 / 2 Create an internal (tenant) network: source creds # Create the internal network : neutron net -create int -net # Create the subnet for the internal network : neutron subnet -create int -net --name int -subnet \ --dns -nameserver 8.8.8.8 --gateway 172.16.1.1 172.16.1.0/24 Create a router on the internal network and attach it to the external network: Attach the router to the internal subnet : neutron router -interface -add router1 int -subnet # Attach the router to the external network by setting it as the gateway : neutron router -gateway -set router1 ext -net

  Background & Related Work on Energy Efficient Cloud Resources Allocation 30 levels. Allocation or placement is also static as opposed to dynamic placement according to workload where migration is applied to reallocate resources.

flowing among VMs. A global resource flowing algorithm was introduced to optimize resource allocation among applications. Both approaches are achieved at the task level and hence fit better the Platform or Software as a Service (PaaS, SaaS) Chapter 3.

  Background & Related Work on Energy Efficient Cloud Resources Allocation 32 energy efficient resource (VM or container) scheduling and no attention was paid to solve the problem at this level.OpenStack Heat is an openstack service that handles the orchestration of complex deployments on top of OpenStack clouds. Orchestration basically manages the infrastructure but it supports also the software configuration management. Heat provides users the ability to define their applications in terms of simple templates.

	This component has also enabled OpenStack to provide a combined IaaS-PaaS
	service. Orchestrating Docker containers in OpenStack via Heat provides orches-
	tration of composite cloud applications and accelerates application delivery by
	making it easy to package them along with their dependencies (this mechanism is

that are radically changing the way applications are built, shipped, deployed, and instantiated. However, these solutions still lack Chapter 3. described in details in Appendix B). Even if this approach based on Docker integration into OpenStack is very advantageous and provides users with complete services and with more control, OpenStack Heat is still based on static assignment and requires VM and container scheduling. The energy efficiency was also completely disregarded.

A new container as a service solution called Kubernetes

[12]

was released by Google to manage containerized applications across multiple hosts and to provide basic mechanisms for deployment of applications. Kubernetes's scheduler is currently very simple and relies on a first-come-first-served (FCFS) algorithm. No attention was paid to energy efficiency in this solution.

  3. Background & Related Work on Energy Efficient Cloud Resources Allocation 33 As the comparison table shows, hybrid IaaS/PaaS solutions still lack energy efficient policies that schedule both VMs and containers to provide users with complete services. Cloud resource assignment is static or simple and no attention was paid to energy efficiency.

Table 3 . 1 :

 31 Related work comparison

			Provisioning	Service	Virtualization	Static vs	Power
			Plan		model	Category	Dynamic	Saving
	[84],	[85],	On-demand	IaaS	Hypervisor	Static	Powering
	[86],	[87],				based		down
	[88]
	[72], [90]		On-demand	IaaS	Hypervisor	Static	Consolidation
						based
	[21], [91]		On-demand	PaaS	Hypervisor	Static	Consolidation
						based
	[77], [78]		On-demand	IaaS	Hypervisor	Static	No	power
			and	ad-		based		saving
			vanced
			reservation
	[79], [80]		advanced		IaaS	Hypervisor	Static	No	power
			reservation		based		saving
	[92],	[97],	On-demand	IaaS	Hypervisor	Dynamic	Dynamic
	[96],	[75],				based		Consolida-
	[74],	[73],						tion
	[94],	[72],
	[93]
	[12],		On-demand	IaaS/PaaS	Hypervisor	Static	No	power
	[13]+[14]					and	con-	saving
						tainer based

  To quantify power Chapter 3. Background & Related Work on Energy Efficient Cloud Resources Allocation 34 consumption and energy efficiency we rely on power and energy estimation models as well as energy efficiency metrics. The first objective of our work is to propose, develop and evaluate optimization algorithms of resource allocation for traditional IaaS architectures that are widely used to manage clouds. The approach is VM based and it should enable ondemand and dynamic resource scheduling while reducing the power consumption of the data center. We propose algorithms that are based on exact formulations of the consolidation problem and of the VM migrations to optimally consolidate VMs in servers while minimizing the energy cost of migrations.

This initial objective is naturally extended to deal with the new trends in Cloud.

We aim to provide a new model and optimization algorithms of energy efficient resource allocation for IaaS-PaaS Cloud providers. The solution should be generic enough to support different type of virtualization technologies, to enable both ondemand and advanced resource provisioning plans, to deal with dynamic resource scheduling and to fill the gap between IaaS and PaaS in order to create a single continuum of services for Cloud users.

  Bin packing based Approach for Energy Efficient Resource Allocation 45

	m	q i
			z ijk = q i y i , ∀i = 1, . . . , m , j = i	(4.18)
	j=1	k=1
	5. Another valid inequality is the upper bound in the total number of empty
	servers:
		m i=1	y i ≤ m -	m j=1 P j,Current P j,M ax	(4.19)
	6. Another important aspect is to avoid migration of VMs whose lifetime or
	leftover lifetime t k is shorter than the time needed to make migration deci-
	sions T 0 :

-idle server i is a source of VM migration, then it should migrate all of its hosted VMs in order to be put to sleep mode or shut down once completely emptied: Chapter 4.

  The end result is the Chapter 4. Bin packing based Approach for Energy Efficient Resource Allocation 48 activation and use of the smallest set of nodes in the data centers.

Table 4 .

 4

1: Table of percentage of gained energy when migration is used

  Graph coloring based Approach for Energy Efficient Resource Allocation 58 deal with on-demand resource allocation if the start time is immediate the end time is not fixed.

	For initial resource reservation (after request arrival), we provide an integer linear
	programming formulation which generalizes the graph coloring problem. Then, we
	derive an Energy Efficient Graph Pre-coloring EEGP heuristic algorithm to deal
	with larger graph instances and to slow computation times. To adapt reservations
	when resources are released, we propose two heuristic algorithms called Energy
	Efficient Graph Recoloring (EEGR) and Migration Aware Energy Efficient Graph

ric, this work propose a new generic graph coloring model of energy efficient advance resource reservation in IaaS-PaaS cloud data centers. The proposed model provides users with access to a set of resources for a specified time while minimizing resource usage and maximizing data centers' energy efficiency. It could also Chapter 5.

Table 5

 5

		.1: Notations
	Symbol Meaning
	V RU	Virtual resource unit : a color.
	RRU	Abstract representation of VRU at
		request level : a graph vertex.
	G	Global graph of requests.
	V	Vertex set of G. It represents the
		RRUs belonging to all requested
		VMs.

  Graph coloring based Approach for Energy Efficient Resource Allocation 69 variable x uc to indicate that RRU u has been reserved to color c and set x uc to 1;

	Chapter 5.
		color c
		is used and 0 otherwise.
	x uc	A binary variable. x uc = 1 if RRU u
		is reserved to color c and 0 otherwise.
	y j	A binary variable. y j = 1 if at least
		one color belonging to C j is used and
		0 otherwise.
	n	Total number of nodes in the graph
		G.
	m	Number of virtualized servers of the
		data center.

  OF F/ON ) E j,idle = P j,idle * t j,inactive These selected color clusters have colors associated to VMs connected to V M i and whose PPW is lower than the color cluster associated to V M i . For example, in Figure5.8, V M 2 associated to C 2 departs. Color cluster C 3 is associated to V M 4 that was connected to V M 2 . As C 3 is less energy efficient than C 2 , C 3 is added to the list of candidate color cluster to be freed (clusterlist = C 3 ).Chapter 5. Graph coloring based Approach for Energy Efficient Resource Allocation 76For each color cluster C j in the list (clusterlist), we check first if color cluster C k have enough free colors to recolor vertices assigned to colors from C j and connected to V M i (if Empty(C j ,C k ) = true). Then, we check if migration decision will provide power gain (line 5). Once these two conditions are satisfied, the next step is to build the list of VMs to recolor with colors from C k . This list, vmlist, is returned by the function list-vm-to-migrate(V M i , C j ) and contains VMs connected to V M i and in the same time associated to C j . The last step is to recolor each V M j in vmlist following the same steps as our EEGP algorithm, but without applying the function Find-Color-Cluster (lines 8-11). The selected color cluster from which to reserve (partially or totally) colors (VRUs) for V M j vertices (RRUs) is fixed to C k . The worst complexity of this algorithm is O(v * m),

	(5.14)
	Algorithm 3 describes the proposed MA-EEGR algorithm. Once a virtual machine
	V M i (associated to C k ) ends, we build a list of color clusters candidate to be freed
	(line 2).

  To simulate an heterogeneous data center, we refer to SPECpower ssj2008 benchmark [104] which provides an evaluation of servers Chapter 5. Graph coloring based Approach for Energy Efficient Resource Allocation 77 based on the performance per watt metric. We generate an infrastructure composed of thousands of heterogeneous servers chosen randomly from the benchmarking results. For simplicity reasons, we assume that resource units are equivalent to User requests arrive following a poisson process with rate of 10 requests per second. To remove the possibility of very short and very long living VMs, the lifetime of a VM or the interval during which a V M i is reserved (b i -a i ) is uniformly distributed between 200s and 1800s. The number of VMs per request is uniformly distributed between 1 and 10. The number of RRUs per

	13: 14: 15: 16: 17: end if end if end for end if end for 5.5 Performance evaluation 5.5.1 Evaluation Settings 11 ECU ). Thus, information on performance per watt w j and on the number of colors (VRU) |C j | of each server j are directly retrieved the SPECpower ssj2008 benchmark. Users' Requests. VM is uniformly distributed between 1 and 20 ( e.g EC2 instance types, namely small, large, xlarge, high-cpu-medium and high-cpu-xlarge have respectively 1, 4, Heterogeneous data center. ECUs [5] (e.g an Intel Xeon X5550 has 13 ECU and an Intel Xeon E5430 has about 8, 5 and 20 EC2 compute units (ECUs)).

  The assessment scenarios correspond to a data center with 1000 servers and thousands of virtual resource units VRUs (or colors) for the experiments leading to the results of Figures 5.12 and 5.13 and correspond to data centers with 100 servers and with 1175 VRUs for the rest of the evaluated scenarios. The efficiency of our heuristic EEGP algorithm is shown in Table5.2. We evaluate the gap between the achieved objective functions values by the exact algorithm and the EEGP heuristic solution. Table5.2 reports this gap in % between the EEGP heuristic and the exact solutions for small and medium global graph G sizes. This

	Chapter 5. Graph coloring based Approach for Energy Efficient Resource
	Allocation				78
	gap = (heuristic solution-optimal solution) optimal solution	× 100
	Table 5.2: Gap between EEGP and Exact solutions
	Graph size	Objective function Z	Gap
		EEGP	Exact
	4	-9794.28	-9794.28	0
	32	-78371.24	-78370.24 0.0012
	69	-165171.61 -165170.61 0.0006
	112	-267828.16 -267824.16 0.0014
	117	-279474.33 -279470.33 0.0014
	162	-380412.61 -380410.61 0.0005
	208	-466824.37 -466817.37 0.0014
	232	-507047.02 -507042.02 0.0009
	262	-575017.54 -575012.54 0.0008
	299	-654000.31 -653995.30 0.0007
	335	-716852.47 -716844.47 0.0011
	365	-769421.88 -769415.88 0.0007
	399	-823698.82 -823688.82 0.0012
	416	-854652.27 -854641.27 0.0012
	437	-889098.53 -889089.53 0.0010
		Average gap		0.0010
	Table 5.2 indicates that the EEGP achieved objective function values are only
	0.001 % from the optimal. We next examine the computation time of the pro-
	posed algorithms. It can be seen, in Figure
	gap is computed using:

Table 5 .

 5 3 depicts the convergence time of the EEGP algorithm running in a server with 24GB of RAM and a pair of 2.53GHz Intel Xeon E5540 quad-core processors.

	In this experiment, the size of the data center m was fixed to 10000 servers. The
	time required for EEGP to converge to a solution was evaluated for requests of
	size 30 RRUs per VM and for colored graph, G, sizes of 1000, 2000, 3000, 4000 and
	5000. Results show that EEGP solves the problem for large graphs in reasonable

time ; not exceeding a minute for the largest graph size of 5000. Chapter 5. Graph coloring based Approach for Energy Efficient Resource Allocation 82 Figure 5.15: Number of used servers

Table 5.3: convergence Time of EEGP (m=10000)

  Ghribi and D. Zeghlache, "Graph Coloring for Energy Efficient Advance Resource Reservation in Green Clouds," Submitted to to the International Journal of Cloud Computing (IJCC), 2014. C. Ghribi, M. Hadji and D. Zeghlache, "Energy Efficient VM Scheduling for Cloud Data Centers: Exact Allocation and Migration Algorithms," Cloud and Grid Computing (CCGrid), 2013 13th IEEE/ACM International Symposium on Cluster , pp. 671-678, doi:10.1109/CCGrid.2013.89. • C. Ghribi and D. Zeghlache, "Exact and Heuristic Graph-Coloring for Energy Efficient Advance Cloud Resource Reservation," Cloud Computing (CLOUD), 2014, CLOUD '14 Proceedings of the 2014 IEEE International Conference on Cloud Computing, pp. 112-119, doi:10.1109/CLOUD.2014.25. -container -format bare --disk -format qcow2 \ --location http :// cdn . download . cirros -cloud . net /0.3.2/ cirros -0.3.2 -x86_64 -disk . img

	List Images:
	glance image -list
	International Conferences
	• Posters
	• C. Ghribi, M. Hadji and D. Zeghlache, "Dynamic Virtual Machine schedul-
	ing for Energy Efficient Cloud data centers," The Institut Mines-Télécom
	symposium, "Energy Tomorrow", 2013, http://www.mines-telecom.fr/
	wpcontent/uploads/2014/04/201305_Posters_efficacite_energetique.
	pdf.

-

Appendix A VM instance creation in

Openstack-nova IaaS providers A.1 OpenStack Nova

OpenStack Nova is the OpenStack compute project. It is a compute controller that pools computing resources like CPU, memory, etc... Nova provides API's to control on-demand scheduling of compute instances like virtual machines on multiple virtualization technologies, bare metal, or container technologies. Nova uses images to launch instances or VMs. In this chapter, we will provide a description of the steps followed to create an instance with Nova.

A.2 Image creation

Create a simple credential file: Check the status of your instance:

Create a floating IP address on the external network to enable the instance to access to the internet and also to make it reachable from external networks: Here is a snapshot of the Horizon dashboard interface after instance launching: A docker container is also portable, it hosts the application and its dependencies and it is able to be deployed or relocated on any Linux server. The Docker element that manages containers and deploys applications on them is called Docker Engine.

The second component of Docker is Docker Hub. It's the Docker's repository of application that allow users to share their applications with their team members and they can ship and run it anywhere

B.3 OpenStack and Docker

Openstack can be easily enhanced by docker plugins.

B.4 Deploy Docker containers with OpenStack Heat

In this section, we will show how to install the Docker plugin, how to write a template and how to deploy it with Heat.

B.4.1 Install the Docker Plugin

To get the Docker plugin, download the Heat folder available on GitHub:

B.4.2 Create the Heat template

Before editing the template, let's discuss about the content and the resources we will define.

103

In this example, we want to dockerize and deploy a lamp application. So, we will create a docker container running apache with php and another one running mysql database.

We define an OS::Heat::SoftwareConfig resource that describes the configuration and an OS::Heat::SoftwareDeployment resource to deploy configs on OS::Nova::Server (the Virtual machine or the Docker server). We associate a floating IP to the Docker server to be able to connect to Internet ( using OS::Nova::FloatingIP and OS::Nova::FloatingIPAssociation resources). Then, we create two docker containers of type DockerInc::Docker::Container on the Docker host.

Note: here we provide a simple template, many other interseting parameters ( port bindings, name, links...) can enhance the template and enable more sophisticated use of Docker. These parameters are not supported by the current Docker plugin. We will provide more complex templates with the next plugin version.

Create template in the docker-stack.yml file with the following content: To create a fedora based image, we followed the steps bellow: Here is a snapshot of the Horizon dashboard interface after stack launching:

To check that the containers are created: