Eugen Feller
email: eugen.feller@inria.fr

Cyril Rohr
email: cyril.rohr@inria.fr

David Margery
email: david.margery@inria.fr

Christine Morin
email: christine.morin@inria.fr

Energy Management in IaaS Clouds: A Holistic Approach

Keywords: Cloud Computing, Energy Management, Consolidation, Relocation, Live Migration, Virtualization

Energy efficiency has now become one of the major design constraints for current and future cloud data center operators. One way to conserve energy is to transition idle servers into a lower power-state (e.g. suspend). Therefore, virtual machine (VM) placement and dynamic VM scheduling algorithms are proposed to facilitate the creation of idle times. However, these algorithms are rarely integrated in a holistic approach and experimentally evaluated in a realistic environment.

In this paper we present the energy management algorithms and mechanisms of a novel holistic energy-aware VM management framework for private clouds called Snooze. We conduct an extensive evaluation of the energy and performance implications of our system on 34 power-metered machines of the Grid'5000 experimentation testbed under dynamic web workloads. The results show that the energy saving mechanisms allow Snooze to dynamically scale data center energy consumption proportionally to the load, thus achieving substantial energy savings with only limited impact on application performance.

I. INTRODUCTION

Cloud computing has gained a lot of attention during the last years and cloud providers have reacted by building increasing numbers of energy hungry data centers in order to satisfy the growing customers resource (e.g. storage, computing power) demands. Such data centers do not only impose scalability and autonomy (i.e. self-organization and healing) challenges on their management frameworks, but also raise questions regarding their energy efficiency [START_REF] Morin | Make IT Green: Cloud Computing and its Contribution to Climate Change[END_REF]. For instance, Rackspace which is a well known Infrastructure-as-a-Service (IaaS) provider hosted approximately 78.717 servers and served 161.422 customers in 2011 [START_REF]Hosting reports third quarter[END_REF]. Moreover, in 2010 data centers have consumed approximately 1.1 -1.5% of the world energy [START_REF] Koomey | Growth in data center electricity use 2005 to 2010[END_REF].

One well known technique to conserve energy besides improving the hardware is to virtualize the data centers and transition idle physical servers into a lower power-state (e.g. suspend) during periods of low utilization. Transitioning idle resources into a lower power state is especially beneficial as servers are rarely fully utilized and lack power-proportionality. For example, according to our own measurements conducted on the Grid'5000 [START_REF] Bolze | Grid'5000: A Large Scale And Highly Reconfigurable Experimental Grid Testbed[END_REF] experimental testbed in France, modern servers still consume a huge amount of power (∼ 182W) despite being idle. Consequently, taking energy saving actions during periods of low utilization appears to be attractive and thus is the target of our research. However, as virtual machines (VMs) are typically load balanced across the servers, idle times need to be created first. Therefore, dynamic VM relocation and consolidation can be used in order to migrate VMs away from underutilized servers. It can be done either eventbased (i.e. relocation) upon underload detection or periodically (i.e. consolidation) by utilizing the live migration features of modern hypervisors (e.g. KVM [START_REF] Kivity | kvm: the Linux virtual machine monitor[END_REF], Xen [START_REF] Barham | Xen and the art of virtualization[END_REF]).

Some dynamic VM relocation (e.g. [START_REF] Wood | Blackbox and gray-box strategies for virtual machine migration[END_REF]) and many consolidation algorithms (e.g. [START_REF] Murtazaev | Sercon: Server Consolidation Algorithm using Live Migration of Virtual Machines for Green Computing[END_REF]- [START_REF] Hermenier | Entropy: a consolidation manager for clusters[END_REF]) have been recently proposed with only few of them being validated in a realistic environment (e.g. [START_REF] Wood | Blackbox and gray-box strategies for virtual machine migration[END_REF]) though under static workloads (i.e. the number of VMs in the system stays constant). Moreover, all these works either target relocation or consolidation and mostly consider only two resources (i.e. CPU, memory).

To the best of our knowledge none of the mentioned works: (1) integrate most of the energy management mechanisms within a holistic cloud management framework: VM resource utilization monitoring and estimations, overload and underload anomaly detection, relocation, consolidation, and power management; [START_REF]Hosting reports third quarter[END_REF] experimentally evaluate them under dynamic workloads (i.e. on-demand VM provisioning); (3) consider more than two resource dimensions (e.g. CPU, memory, network Rx, and network Tx).

In our previous work [START_REF] Feller | Snooze: A Scalable and Autonomic Virtual Machine Management Framework for Private Clouds[END_REF] we have proposed a novel scalable and autonomic VM management framework for private clouds called Snooze. In this work, we focus on its energy management algorithms and mechanisms. Our first contribution is a unique holistic solution to perform VM resource utilization monitoring and estimations, detect and react to anomaly situations and finally do dynamic VM relocation and consolidation to power off and on idle servers. Our second contribution is an experimental evaluation of the proposed algorithms and mechanisms in a realistic environment using dynamic web workloads on 34 power-metered nodes of the Grid'5000 experimental testbed.

The results show that Snooze energy management mechanisms allow it to scale the data center energy consumption proportionally to current utilization with only limited impact on application performance, thus achieving substantial energy savings. This work has direct practical application as it can be either applied in a production environment to conserve energy or as a research testbed for testing and experimenting with advanced energy-aware VM scheduling algorithms.

The remainder of this article is organized as follows.

Section II discusses the related work. Section III introduces the energy saving algorithms and mechanisms of Snooze. Section IV presents the evaluation results. Section V closes this article with conclusions and future work.

II. BACKGROUND Energy conservation has been the target of research during the last years and led to many works at all levels (i.e. hardware and software) of the infrastructure. This section focuses on the software level and presents related work on VM relocation and consolidation.

In [START_REF] Beloglazov | Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing[END_REF] multiple energy-aware resource allocation heuristics are introduced. However, only simulation-based results based on simple migration and energy-cost models are presented. Finally, only one resource dimension (i.e. CPU) is considered.

In [START_REF] Goiri | Energy-efficient and multifaceted resource management for profit-driven virtualized data centers[END_REF] the authors propose a multi-objective profit-oriented VM placement algorithm which takes into account performance (i.e. SLA violations), energy efficiency, and virtualization overheads. Similarly to [START_REF] Beloglazov | Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing[END_REF] this work considers CPU only and its evaluation is based on simulations.

In [START_REF] Wood | Blackbox and gray-box strategies for virtual machine migration[END_REF] a framework is introduced which dynamically reconfigures a cluster based on its current utilization. The system detects overload situations and implements a greedy algorithm to resolve them. However, it does not include any energy saving mechanisms such as underload detection, VM consolidation and power management.

In [START_REF] Hermenier | Entropy: a consolidation manager for clusters[END_REF] a consolidation manager based on constraint programming (CP) is presented. It is solely limited to static consolidation (i.e. no resource overcommitment is supported) and neither includes overload/underload anomaly detection, relocation, nor any power saving actions.

In [START_REF] Graubner | Energy-Efficient Management of Virtual Machines in Eucalyptus[END_REF] the Eucalyptus cloud management framework is extended with live migration and consolidation support. The extension neither supports anomaly detection nor event-based VM relocation. Moreover, it remains unclear when and how many migrations are triggered during its evaluation. Finally, it targets static workloads and is tested on three nodes which is far from any real cloud deployment scenario.

Last but not least in [START_REF] Vmware | Distributed Resource Scheduler (DRS)[END_REF] the VMware Distributed Resource Scheduler (DRS) is presented. Similarly, to our system DRS performs dynamic VM placement by observing the current resource utilization. However, neither its system (i.e. architecture and algorithms) nor evaluation (i.e. performance and energy) details are publicly available.

Snoozes goes one step further than previous works by providing a unique experimentally evaluated holistic energy management approach for IaaS clouds.

III. ENERGY MANAGEMENT IN IAAS CLOUDS: A

HOLISTIC APPROACH Snooze is an energy-aware VM management framework for private clouds. Its core energy conservation algorithms and mechanisms are described in this section.

First we introduce the system model and its assumptions. Afterwards, a brief overview of the system architecture and its parameters is given. Finally, the energy management algorithms and mechanisms are presented.

A. System Model and Assumptions

We assume a homogeneous data center whose nodes are interconnected with a high-speed LAN connection such as Gigabit Ethernet or Infiniband. They are managed by a hypervisor such as KVM [START_REF] Kivity | kvm: the Linux virtual machine monitor[END_REF] or Xen [START_REF] Barham | Xen and the art of virtualization[END_REF] which supports VM live migration. Power management mechanisms (e.g. suspend, shutdown) are assumed to be enabled on the nodes. VMs are seen as black-boxes. We assume no restriction about applications: both compute and web applications are supported.

B. System Architecture

The architecture of the Snooze framework is shown in A hierarchical layer allows to scale the system and is composed of fault-tolerant components: Group Managers (GMs) and a Group Leader (GL).

LC -GM communication

Inter-GM communication GM -GL communication

Client layer

Each GM manages a subset of LCs and is in charge of the following tasks: [START_REF] Morin | Make IT Green: Cloud Computing and its Contribution to Climate Change[END_REF] LCs enforce VM and host management commands coming from the GM. Moreover, they monitor VMs, detect overload/underload anomaly situations and report them to the assigned GM.

There exists one GL which oversees the GMs, keeps aggregated GM resource summary information, assigns LCs to GMs, and dispatches VM submission requests to the GMs. The resource summary information holds the total active, passive, and used capacity of a GM. Active capacity represents the capacity of powered on LCs, while passive capacity captures resources available on LCs in power saving state. Finally, used capacity represents the aggregated LC utilization.

A client layer provides the user interface. It is implemented by a predefined number of replicated Entry Points (EPs).

C. System Parameters

Let LCs denote the set of LCs and VMs the set of VMs, with n = |LCs| and m = |V M s| representing the amounts of LCs and VMs, respectively.

Available resources (i.e. CPU, memory, network Rx, and network Tx) are defined by the set R with d = |R| (d = 4). CPU utilization is measured in percentage of the total LC capacity. For example, if a LC has four physical cores (PCORES) and a given VM requires two virtual cores (VCORES), the maximum CPU requirement of a VM would be 50%. Memory is measured in Kilobytes and network utilization in Bytes/sec.

VMs are represented by requested and used capacity vectors (RC v resp. UC v ). RC v := {RC v,k } 1≤k≤d reflects the static VM resource requirements in which each component defines the requested capacity for resource k ∈ R. They are used during the initial VM submission to place VMs on LCs. On the other hand, used capacity vectors UC v := {U C v,k } 1≤k≤d become available as the result of monitoring. Each component of the vector represents the estimated VM utilization for resource k over the last measurement period T (e.g. one day).

LCs are assigned with a predefined static homogeneous capacity vector C l := {C l,k } 1≤k≤d . In addition, their current utilization c l is computed by summing up the VM used capacity vectors:

c l := ∀v∈LC l UC v .
We introduce M l := {M ID l,k } 1≤k≤d as the LC resource capping vector which puts an upper bound on the maximum aimed LC utilization for each resource k with 0 ≤ M ID l,k ≤ 1. In other words we keep a limited amount of available resources to compensate for overprovisioning. This is required in order to mitigate performance problems during periods of high resource contention.

LC l is considered to have enough capacity for

V M v if either c l + RC v ≤ C l ⋄ M l holds during submission or c l + UC v ≤ C l ⋄ M l
during VM relocation or consolidation. ⋄ denotes elementwise vector multiplication.

Introducing resource upper bounds leads to situations where VMs can not be hosted on LCs despite enough resources being available. For example when M ID l,CP U = 0.8 and only two PCORES exist, VM requiring all of them can not be placed (i.e. 2 VCORE / 2 PCORE ≤ 0.8 does not hold).

Therefore, we define the notion of packing density (PD) which is a vector of values between 0 and 1 for each resource k. It can be seen as the trust given to the user's requested VM resource requirements and allows VMs to be hosted on LCs despite existing MID capping's. When PD is enabled, Snooze computes the requested VM resource requirements as follows:

RC v := RC v ⋄ PD.
In order to detect anomaly situations we define a 0 ≤ M IN k ≤ 1 and 0 ≤ M AX k ≤ 1 threshold for each resource k. If the estimated resource utilization for k falls below M IN k the LC is considered as underloaded, otherwise if it goes above M AX k LC is flagged as overloaded (see the following paragraphs).

LCs and VMs need to be sorted by many scheduling algorithms. Sorting vectors requires them to be first normalized to scalar values. Different sort norms such as L1, Euclid or Max exist. In this work the L1 norm is used.

D. Resource Monitoring and Anomaly Detection

Monitoring is mandatory to take proper scheduling decisions and is performed at all layers of the system. At the physical layer VMs are monitored and resource utilization information is periodically transferred to the GM by each LC. It is used by the GM in the process of VM resource utilization estimation and scheduling.

At the hierarchical layer, each GM periodically sends aggregated resource summary information to the GL. This information includes the used and total capacity of the GM with the former being computed based on the estimated VM resource utilization of the LCs and is used to guide VM dispatching decisions.

Overload and underload anomaly detection is performed locally by each LC based on aggregated VM monitoring values. This allows the system to avoid many false-positive anomaly alerts. Particularly, for each VM a system administrator predefined amount of monitoring data entries is first collected. After the LC has received all VM monitoring data batches, it performs the total LC resource utilization estimation by averaging the VM resource utilizations and summing up the resulting values. Finally, a threshold crossing detection (TCD) is applied on each dimension of the estimated host resource utilization vector based on the defined M IN k and M AX k thresholds to detect anomaly situations. LCs are marked as overloaded (resp. underloaded) in the data sent to GM if at least one of the dimensions crosses the thresholds.

E. Resource Utilization Estimations

Resource utilization estimations are essential for most of the system components. For example, they are required in the context of anomaly detection and VM scheduling (i.e. placement, relocation, and consolidation).

GM performs LC resource utilization estimations in order to generate its aggregated resource summary information. TCD decisions are based on estimated VM resource utilizations. Finally, in the context of VM scheduling, VM resource utilizations are estimated in order to: (1) Compute the total LC resource utilization; (2) Sort LCs and VMs.

Snooze provides abstractions which allow to easily plug in different estimators for each resource. For example VM CPU utilization can be estimated by simply considering the average of the n most recent monitoring values. Alternatively, more advanced prediction algorithms (e.g. based on Autoregressive-Moving-Average (ARMA)) can be used. In this work the former approach is taken.

F. Energy-Aware VM Scheduling

Scheduling decisions are taken at two levels: GL and GM. At the GL level, VM to GM dispatching is done based on the GM resource summary information. For example, VMs could be dispatched across the GMs in a capacity-aware round-robin or first-fit fashion. In this work round-robin is used. Thereby, GL favors GMs with enough active capacity and considers passive capacity only when not enough active one is available.

Note that summary information is not sufficient to take exact dispatching decisions. For instance, when a client submits a VM requesting 2GB of memory and a GM reports 4GB available it does not necessary mean that the VM can be finally placed on this GM as its available memory could be distributed among multiple LCs (e.g. 4 LCs with each 1GB of RAM). Consequently, a list of candidate GMs is provided by the dispatching policies. Based on this list, a linear search is performed by issuing VM placement requests to the GMs.

At the GM level, the actual VM scheduling decisions are taken. Therefore, four types of scheduling policies exist: placement, overload relocation, underload relocation, and finally consolidation. Placement policies (e.g. round-robin or firstfit) are triggered event-based to place incoming VMs on LCs. Similarly, relocation policies are called when overload (resp. underload) events arrive from LCs and aims at moving VMs away from heavily (resp. lightly loaded) nodes. For example, in case of overload situation VMs must be relocated to a more lightly loaded node in order to mitigate performance degradation. Contrary, in case of underload, for energy saving reasons it is beneficial to move VMs to moderately loaded LCs in order to create enough idle-time to transition the underutilized LCs into a lower power state (e.g. suspend).

Complementary to the event-based placement and relocation policies, consolidation policies can be specified which will be called periodically according to the system administrator specified interval to further optimize the VM placement of moderately loaded nodes. For example, a VM consolidation policy can be enabled to weekly optimize the VM placement by packing VMs on as few nodes as possible.

G. VM Relocation

The Snooze VM overload relocation policy is shown in Algorithm 1. It takes as input the overloaded LC along with its associated VMs and a list of LCs managed by the GM. The algorithm outputs a Migration Plan (MP) which specifies the new VM locations.

The overload relocation policy first estimates the LC utilization, computes the maximum allowed LC utilization, and the overloaded capacity delta (i.e. difference between estimated and maximum allowed LC utilization). Afterwards it gets the VMs assigned to the overloaded LC, sorts them in increasing order based on estimated utilization and computes a list of candidate VMs to be migrated. The routine to compute the migration candidates first attempts to find the most loaded VM among the assigned ones whose estimated utilization equals or is above the overloaded capacity delta. This way a single migration will suffice to move the LC out of overload state. Otherwise, if no such VM exists, it starts adding VMs to the list of migration candidates starting from the least loaded one until the sum of the estimated resource utilizations equals or is above the overload capacity delta. Finally the destination LCs are sorted in increasing order based on estimated utilization and migration candidates are assigned to them starting from the first one if enough capacity is available. Moreover, the new VM to LC mappings are added to the MP. The underload relocation policy is depicted in Algorithm 2. It takes as input the underloaded LC and its associated VMs along with the list of LCs managed by the GM. It first retrieves the VMs from the underloaded LC and sorts them in decreasing order based on the estimated utilization. Similarly, LCs are sorted in decreasing order based on the estimated utilization. Then, VMs are assigned to LCs with enough spare capacity and added to the MP. The algorithms follows an allor-nothing approach in which either all or none of the VMs are migrated. Migrating a subset of VMs does not contribute to the energy saving objective (i.e. create idle times) and thus is avoided. In order to avoid a ping-pong effect in which VMs are migrated back and forth between LCs, LCs are transitioned into a lower power state (e.g. suspend) once all VMs have been migrated thus they can not be considered as destination LCs during subsequent underload events.

H. VM Consolidation

VM consolidation is a variant of the multi-dimensional binpacking problem which is known to be NP-hard [START_REF] Csirik | On the multidimensional vector bin packing[END_REF]. Our system is not limited to any particular consolidation algorithm. However, because of the NP-hard nature of the problem and the need to compute solutions in a reasonable amount of time Add (v, LC f it ) mapping to the migration plan 13: end for 14: return Migration plan MP it currently implements a simple yet efficient two-objective (i.e. minimizes the number of LCs and migrations) polynomial time greedy consolidation algorithm. Particularly, a modified version of the Sercon [START_REF] Murtazaev | Sercon: Server Consolidation Algorithm using Live Migration of Virtual Machines for Green Computing[END_REF] algorithm is integrated which differs in its termination criteria and the number of VMs which are removed in case not all VMs could be migrated from a LC. Sercon follows an all-or-nothing approach and attempts to move VMs from the least loaded LC to a non-empty LC with enough spare capacity. Either all VMs can be migrated from a host or none of them will be. Migrating only a subset of VMs does not yield to less number of LCs and thus is avoided.

The pseudocode of the modified algorithm is shown in Algorithm 3. It takes as input the LCs including their associated VMs. LCs are first sorted in decreasing order based on their estimated utilization. Afterwards, VMs from the least loaded LC are sorted in decreasing order, placed on the LCs starting from the most loaded one and added to the migration plan. If all VMs could be placed the algorithm increments the number of released nodes and continues with the next LC. Otherwise, all placed VMs are removed from the LC and MP and the procedure is repeated with the next loaded LC. The algorithm terminates when it has reached the most loaded LC and outputs the MP, number of used nodes, and number of released nodes.

I. Migration Plan Enforcement

VM relocation and consolidation algorithms output a migration plan (MP) which specifies new mapping of VMs to

LCs required to transition the system from its current state to the new optimized one. Migration plan is enforced only if it yields to less LCs. Enforcing the migration plan computed by the relocation and consolidation algorithms of our framework is straightforward as it only involves moving VMs from their current location to the given one. Note that, unlike other works (e.g. [START_REF] Hermenier | Entropy: a consolidation manager for clusters[END_REF]) our algorithms do not introduce any sequential dependencies or cycles. Particularly, VMs are migrated to an

LC if and only if enough capacity is available on it without requiring other VMs to be moved away first.

Migrations can happen either sequentially or in parallel. In the former case only one VM is moved from the source to the destination LC at a time, while the latter allows multiple VMs to be migrated concurrently. Given that modern hypervisors Algorithm 3 VM Consolidation (e.g. KVM) support parallel migrations there is no reason not to do so given that enough network capacity is available. This is exactly what our system does.

Still, there exists a caveat here related to the pre-copy live migration termination criteria of the underlying hypervisor. For example, in KVM live migration can last forever (i.e. make no progress) if the number of pages that got dirty is larger than the number of pages that got transferred to the destination LC during the last transfer period.

In order to detect and resolve such situations Snooze spawns a watchdog for each migration. Watchdog enforces convergence after a system administrator predefined convergence timeout given the migration is still pending. Therefore it suspends the VM thus preventing further page modifications. The hypervisor is then able to finish the migration and restart the VM on the destination LC.

J. Power Management

In order to conserve energy, idle nodes need to be transitioned into a lower power state (e.g. suspend) after the migration plan enforcement. Therefore, Snooze integrates a power management module, which can be enabled by the system administrator to periodically observe the LC utilization and trigger power-saving state transitions (e.g. from active to suspend) once they become idle (i.e. do not host any VMs).

Particularly, power management works as follows. Snooze can be configured to keep a number of reserved LCs always on in order to stay reactive during periods of low utilization. Other LCs are automatically transitioned into a lower power state after a predefined idle time threshold has been reached (e.g. 180 sec) and marked as passive. Passive resources are woken up by the GMs either upon new VM submission or overload situation when not enough active capacity is available to accommodate the VMs. Therefore a wakeup threshold exists which specifies the amount of time a GM will wait until the LCs are considered active before starting another placement attempt on those LCs.

The following power saving actions can be enabled if hardware support is available: shutdown, suspend to ram, disk, or both. Thereby, different shutdown and suspend drivers can be easily plugged in to support any power management tools. For example, shutdown can be implemented using IPMItool or by simply calling the Linux native shutdown command.

Finally to enable LC power on, wakeup drivers can be specified. Currently, two wakeup mechanisms are supported in Snooze: IPMI and Wake-On-Lan (WOL).

IV. EVALUATION

A. System Setup

Snooze was deployed on 34 power metered HP ProLiant DL165 G7 nodes of the Grid'5000 experimental testbed in Rennes (France) with one EP, one GL, one GM and 31 LCs. All nodes are equipped with two AMD Opteron 6164 HE CPUs each having 12 cores (in total 744 compute cores), 48 GB of RAM, and a Gigabit Ethernet connection. They are powered by six APC AP7921 power distribution units (PDUs). Power consumption measurements and the benchmarking software execution are done from two additional Sun Fire X2270 nodes in order to avoid influencing the measurement results.

The node operating system is Debian with a 2.6.32-5-amd64 kernel. All tests were run in a homogeneous environment with qemu-kvm 0.14.1 and libvirt 0.9.6-2 installed on the machines. Each VM is using a QCOW2 disk image with the corresponding backing image hosted on a Network File System (NFS). Incremental storage copy is enabled during live migration. Debian is installed on the backing image. The NFS server is running on the EP with its directory being exported to all LCs. VMs are configured with 6 VCORES, 4GB RAM and 100 MBit/sec network connection. Note that libvirt currently does not provide any means to specify the network capacity requirements. Therefore, Snooze wraps around the libvirt template and adds the necessary network capacity (i.e. Rx and Tx) fields.

Tables I, II, III, and IV show the system settings used in the experiments.

B. Experiment Setup

Our study is focused on evaluating the energy and performance benefits of the Snooze energy-saving mechanisms for dynamic web workloads. To make the study realistic, the experiment is set up in a way that reflects a real-world web application deployment: An extensible pool of VMs, each hosting a copy of a backend web application running on a HTTP server, while a load-balancer accepts requests coming from an HTTP load injector client (see Figure 2). Both the load-balancer and load injector are running on the Sun Fire X2270 nodes. The backend application consists of a single HTTP endpoint, which triggers a call to the stress tool [START_REF]Stress tool[END_REF] upon each request received. Each stress test loads all VM cores during one second and uses 512 MB of RAM.

Register

The load-balancer tool used is HAProxy v1.4.8, which is a state-of-the-art load-balancer used in large-scale deployments [START_REF]HAProxy -The Reliable, High Performance TCP/HTTP Load Balancer[END_REF]. HAProxy is configured in HTTP mode, four concurrent connections maximum per backend, round-robin algorithm, and a large server timeout to avoid failed requests.

Finally, the load injector tool is the well-known Apache benchmark tool [START_REF]ab -Apache HTTP server benchmarking tool[END_REF]. It is configured to simulate 20 concurrent users sending a total number of 15000 requests. According to our experiments these parameters provide the best trade-off between the experiment execution time and the effectiveness of illustrating the framework features.

The initial deployment configuration of the backend VMs is done using the Bfire tool [START_REF]Bfire -A powerful DSL to launch experiments on BonFIRE[END_REF], which provides a domainspecific language (DSL) for declaratively describing the provisioning and configuration of VMs on a cloud provider. Bfire also allows the monitoring of any metric and provides a way to describe elasticity rules, which can trigger up-or down-scaling of a pool of VMs when a key performance indicator (KPI) is below or over a specific threshold. This tool is currently developed by INRIA within the BonFIRE project [START_REF]BonFIRE -Testbeds for Internet of Services Experimentation[END_REF]. A thin wrapper was developed to make Snooze Bfire-compatible (i.e. interact with the Snooze RESTful API to provision VMs).

The experiment lifecycle is as follows: our Bfire DSL is fed into the Bfire engine, which initially provisions one backend VM on one of the physical nodes. At boot time, the backend VM will automatically register with the load-balancer so that it knows that this backend VM is alive. Once this initial deployment configuration is ready, the Bfire engine will start the Apache benchmark against the load-balancer. During the whole duration of the experiment, Bfire will also monitor in a background thread the time requests spent waiting in queue at the load-balancer level (i.e. before being served by a backend application). Over time, this KPI will vary according to the number of backend VMs being available to serve the requests. In our experiment, if the average value of the last 3 acquisitions of that metric is over 600ms (an acceptable time for a client to wait for a request), then a scale-up event will be generated, which will increase the backend pool by four new VMs at once. If the KPI is below the threshold, then nothing happens. This elasticity rule is monitored every 15 seconds, and all newly created VMs must be up and running before it is monitored again (to avoid bursting). Meanwhile, an additional background process is registering the power consumption values coming from the PDUs to which the physical nodes are attached. At the end of the experiment, we show the performance (i.e. response time) of the application, the power consumption of the nodes, the number of VMs and live migrations. Moreover, we visualize all the events (i.e. Bfire, relocation, consolidation, power management) which were triggered in our system during the experiments.

Two scenarios are evaluated: [START_REF] Morin | Make IT Green: Cloud Computing and its Contribution to Climate Change[END_REF] No energy savings, to serve as a baseline; (2) Energy savings enabled (i.e. underload relocation, consolidation and power management). In both scenarios overload detection is enabled.

C. Elastic VM Provisioner Events

The elastic VM provisioner (i.e. Bfire) events (i.e. READY, SCALING, SCALED) without and with energy savings enabled (red resp. green colored) are shown in Figure 3. The experiment starts by provisioning one backend VM which results in the provisioner to become READY. When it becomes ready we start the actual benchmark which soon saturates the VM capacity. Bfire reacts by SCALING up the number of VMs to four. It takes approximately five minutes to provision the VMs. This is reflected in the subsequent SCALED event which signals the VM provisioning success. The same process happens until the end of the benchmark execution. In total four SCALING (resp. SCALED) are triggered which result in 17 VMs to be provisioned by the end of the Apache benchmark. Note that the experiment with energy savings enabled lasts a bit more (1.2% of time) than without energy savings because of the need to power on nodes and lightly increased response time (see the following paragraphs).

D. Apache Benchmark Performance

The Apache benchmark results (i.e. response time for each request) are depicted in Figure 4. As it can be observed, response time increases with the number of requests in both cases (i.e. without and with energy savings). However, more interestingly is the fact that response time is not significantly impacted when energy savings are enabled. Particularly, in both scenarios a response time peek exists at the beginning of the experiment. Indeed, one backend VM is quickly saturated. However, when times passes only minor performance degradation can be observed.

The main reason for the minor performance degradation lies in the fact that once energy savings are enabled, servers are powered down, thus increasing the time requests remain in the HAProxy queue until they can be served by one of the backends. Moreover, Bfire dynamically increases the number of VMs with growing load. Increasing the number of VMs involves scheduling, powering on LCs as well as a software provisioning phase in which tools are installed on the scheduled VMs in order to register with HAProxy. This requires time and thus impacts application performance (i.e. requests are queued). Performance could be further improved by taking proactive scaling up decisions. Finally, underload relocation and consolidation are performed which involve VM migration which contributes to the performance degradation.

E. System Power Consumption and Events

The system power consumption without and with energy savings is depicted in Figure 5.

Without energy savings our experimental data center first consumes approximately 5.7 kW of idle power. With the start of the benchmark the load increases to 6.1 kW and falls back with the end of the evaluation. Note that our experiments did not fully stress all the 744 compute cores which would have resulted in even higher power consumption (∼ 7.1 kW) but would also have made harder to conduct the experiment due to the increased execution time. Snooze overcommits nodes by allowing them to host more VMs than physical capacity allows it. This leads to overloaded situations requiring VMs to be live migrated. In this context we distinguish between two types of events: overload relocation (OR) and migration plan enforced (MPE). The former is triggered in case of overload situation and results in a migration plan which needs to be enforced. MPE events signal the end of the enforcement procedure. Figure 6 shows the event profile including the number of migrations. As it can be observed the first two OR events trigger five migrations. This is due to the fact that the First-Fit placement is performed upon initial VM submission. This leads to an overload situation on the LCs which needs to be resolved. However, as time progresses the number of migrations decreases as VMs are placed on more lightly loaded LCs. With energy savings enabled, when the experiment starts the system is idle, and thus the nodes have been powered down by Snooze, reducing the power consumption to approximately one kW (see Figure 5).

When the benchmark is started the system reacts by taking actions required to provision just as many nodes as needed to host the VMs. This results in the power consumption following the system utilization (i.e. increasing number of VMs). Note that the power consumption never drops to the initial value (i.e. one kW) as VMs are kept in the system in order to illustrate the framework mechanisms. Consequently, once idle they still consume additional power. In a production environment VMs would be shutdown by the customers thus resulting in additional power savings.

Particularly, the following actions presented in Figure 7 are performed: (1) detect LC underload and overload; (2) trigger underload and overload relocation (UR resp. OR) algorithms; (3) enforce migration plans (MPE); (4) perform periodic consolidation (C); (5) take power saving actions such as power up and down (PUP resp. PDOWN) depending on the current load conditions. In order to get an insight in the system behaviour we have captured all these events. During the benchmark execution the first OR event appears as the system becomes overloaded. The overload situation is resolved by powering up one LC and migrating five VMs. Then consolidation is started which migrates two VMs. The system continues to react to OR/UR events and adapt the data center size according to the current load (i.e. PUP and PDOWN events follow) until the end of the benchmark. Note that the number of migrations decreases with the benchmark execution time as the HAProxy load decreases with increasing number of backend VMs thus resulting in less OR events. Towards the end of the benchmark UR happens and results in a series of PDOWN events. Finally, consolidation is started and improves the VM placement by migrating one VM. This shows that relocation and consolidation are complementary.

Putting all the results together, data center energy consumption measured during the benchmark execution without and with power management enabled amounted to 3.19 kWh (34 nodes), respectively 1.05 kWh (up to 11 nodes), resulting in 67% of energy being conserved. We estimated that for the same workload with a smaller data center size of 17 nodes, the energy gains would have been approximately 34%.

V. CONCLUSIONS AND FUTURE WORK

This paper has presented and evaluated the energy management mechanisms of a unique holistic energy-aware VM management framework called Snooze. Snooze has a direct practical application: it can be either utilized in order to efficiently manage production data centers or serve as a testbed for advanced energy-aware VM scheduling algorithms.

To the best of our knowledge this is the first cloud management system which integrates and experimentally evaluates most of the required mechanisms to dynamically reconfigure virtualized environments and conserve energy within a holistic framework. Particularly, Snooze ships with integrated VM monitoring and live migration support. Moreover, it implements a resource (i.e. CPU, memory and network) utilization estimation engine, detects overload and underload situations and finally performs event-based VM relocation and periodic consolidation. Snooze is the first system implementing the Sercon consolidation algorithm which was previously only evaluated by simulation. Finally, once energy savings are enabled, idle servers are automatically transitioned into a lower power state (e.g. suspend) and woken up on demand.

The Snooze energy management mechanisms have been extensively evaluated using a realistic dynamic web deployment scenario on 34 power-metered nodes of the Grid'5000 experimental testbed. Our results have shown that the system is able to dynamically scale the data center energy consumption proportionally to its utilization thus allowing it to conserve substantial power amounts with only limited impact on application performance. In our experiments we have shown that with a realistic workload up to 67% of energy could be conserved. Obviously the achievable energy savings highly depend on the workload and the data center size.

In the future we intend to extend our work to scientific and data analysis applications and evaluate different power management actions (e.g. suspend to ram, disk, both). Moreover we plan to integrate our previously proposed nature-inspired VM consolidation algorithm [START_REF] Feller | Energy-Aware Ant Colony Based Workload Placement in Clouds[END_REF] and compare its scalability with the existing greedy algorithm as well as alternative consolidation approaches (e.g. based on linear programming). In addition we plan to apply machine learning techniques in order to predict VM resource utilization peaks and trigger pro-active relocation and consolidation actions. Finally, power management features will be added to the group leader in order to support power cycling of idle group managers.

Snooze is available as open-source software under the GPL v2 license at http://snooze.inria.fr.

Fig- ure 1 .

 1 It is partitioned into three layers: physical, hierarchical, and client.

Fig. 1 .

 1 Fig. 1. System architecture

Algorithm 1

 1 VM Overload Relocation 1: Input: Overloaded LC with the associated VMs and resource utilization vectors UC, list of destination LCs 2: Output: Migration Plan M P 3: c ← Estimate LC utilization 4: m ← Compute max allowed LC utilization 5: o ← Compute the amount of overloaded capacity (c, m) 6: V M ssource ← Get VMs from LC 7: Sort V Msource in increasing order 8: V M candidates ← computeMigrationCandidates(V M ssource, o) 9: Sort destination LCs in increasing order 10: for all v ∈ V M candidates do 11: LC f it ← Find LC with enough capacity to host v (v, LCs) 12:if LC f it = ∅ then , LC f it ) mapping to the migration plan 16: end for 17: return Migration plan M P

Algorithm 2 7 :

 27 VM Underload Relocation 1: Input: Underloaded LC with the associated VMs and resource utilization vectors UC, list of destination LCs 2: Output: Migration Plan MP 3: V M candidates ← Get VMs from underloaded LC 4: Sort V M candidates in decreasing order 5: Sort LCs in decreasing order 6: for all v ∈ V M candidates do LC f it ← Find LC with enough capacity to host v 8:if LC f it = ∅ then

Fig. 2 .

 2 Fig. 2. Experiment setup

Fig. 3 .

 3 Fig. 3. Elastic VM provisioner events

Fig. 4 .

 4 Fig. 4. Apache benchmark performance

Fig. 5 .

 5 Fig. 5. Power consumption

Fig. 6 .

 6 Fig. 6. Snooze system events without energy savings

Fig. 7 .

 7 Fig. 7. Snooze system events with energy savings enabled

1 :

 1 Input: List of LCs with their associated VMs and resource utilization vectors UC 2: Output: Migration Plan M P , nUsedNodes, nReleasedNodes 3: MP ← ∅

	4: nUsedNodes ← 0 5: nReleasedNodes ← 0 6: localControllerIndex ← |LCs| -1
	7: while true do
	8:	if localControllerIndex = 0 then
	9:	break;
	10:	end if
	11:	Sort LCs in decreasing order
	12: 13: 14: 15:	LC least ← Get the least loaded LC (localControllerIndex) V M s least ← Get VMs from LC least if V M s least = ∅ then localControllerIndex ← localControllerIndex -1
	16:	continue;
	17:	end if
	18: 19: 20:	Sort V M s least in decreasing order nPlacedVMs ← 0 for all v ∈ V M s least do
	21:	Find suitable LC to host v
	22:	if LC = ∅ then
	23:	continue;
	24:	end if
	25: 26: 27:	LC least ← LC least ∪ {v} MP ← MP ∪{v} nPlacedVMs ← nPlacedVMs + 1
	28:	end for
	29: 30:	if nPlacedVMs = |V M s least | then nReleasedNodes ← nReleasedNodes + 1
	31:	else
	32: 33:	LC least ← LC least \ V M s least MP ← MP \V M s least
	34:	end if
	35:	localControllerIndex ← localControllerIndex -1
	36: end while
	37: nUsedNodes ← |LCs| -nReleasedNodes
	38: return Migration plan M P , nUsedNodes, nReleasedNodes

VI. ACKNOWLEDGMENTS

We would like to thank Oleg Sternberg (IBM Haifa Research Lab), Piyush Harsh (INRIA), Roberto G. Cascella (INRIA), Yvon Jégou (INRIA), and Louis Rilling (ELSYS Design) for all the great discussions and feedbacks. This research is funded by the French Agence Nationale de la Recherche (ANR) project EcoGrappe under the contract number ANR-08-SEGI-008-02. Experiments presented in this paper were carried out using the Grid'5000 experimental testbed, being developed under the INRIA ALADDIN development action with support from CNRS, RENATER and several Universities as well as other funding bodies (see https://www.grid5000.fr).


Safa Cherigui

Christine Guillemot

Dominique Thoreau

Philippe Guillotel

Patrick Perez

HYBRID TEMPLATE AND BLOCK MATCHING ALGORITHM FOR IMAGE INTRA PREDICTION

Keywords: Texture prediction, intra coding, template matching, block matching, H.264

Template matching has been shown to outperform the H.264 prediction modes for Intra video coding thanks to better spatial prediction and no additional ancillary data to transmit. The method indeed works well when the template and the block to be predicted are highly correlated, e.g., in homogenous image areas, however, it obviously fails in areas with non homogeneous textures. This paper explores the idea of using a block-matching intra prediction algorithm which, thanks to a Rate-Distorsion (RD) based decision mechanism, will naturally be used in image areas when template matching (TM) fails. This new method offers a significant coding gain compared to H.264 Intra prediction modes and the template matching based prediction. Indeed, the TM-based algorithm and the proposed hybrid algorithm lead, with the Bjontergaard measure, to rate gains of up to respectively 38.02% and 48.38% at low bitrates when compared with H.264 Intra only.

INTRODUCTION

This paper addresses the problem of Intra prediction which is a key component of image and video compression algorithms. Given observations, or known samples in a spatial neighborhood which may be affected by quantization noise, the goal is to estimate unknown samples of the block to be predicted. For example, in H.264/AVC, there are three intra-frame prediction types called Intra-4x4, Intra-8x8 and Intra-16x16 respectively [START_REF] Wiegand | Overview of the H.264/AVC video coding standard[END_REF]. For each intra prediction mode, a block is predicted from prior encoded samples of spatially neighboring blocks. In addition to the so-called "DC" mode which consists in predicting the entire block from the mean of neighboring pixels, eight directional prediction modes have been specified. The prediction is done by simply "propagating" the pixel values along the specified direction. This approach is particularly suitable in presence of contours, when the directional mode chosen corresponds to the orientation of the contour. However, it fails in more complex textured areas. Besides, in H.264/AVC, intra prediction is used to eliminate the correlation between current block and adjacent pixels, but for some video sequences, the current block has a great similarity with blocks from other parts of the picture.

Several new intra prediction methods have been proposed to exploit redundancy within an image. Firstly, a block based intra prediction method has been introduced in [START_REF] Yu | New intra prediction using intra macroblock motion compensation[END_REF], which integrates motion estimation and motion compensation techniques classically used in inter-frame. In this approach, the reconstructed part of the image is taken as a reference frame, and the prediction is the block that best matches the current block. Note that the derived matching vectors are required to be coded because they are needed at the decoder for reconstruction of the prediction. An alternative spatial prediction algorithm based on template matching has been described in [START_REF] Tan | Intra prediction by template matching[END_REF]. A so-called template is formed by previously encoded pixels in the close neighborhood of the block to be predicted. The best match between the template of the block to be predicted and candidate texture patches with the same shape, within a causal search window, gives the predictor for the current block to be coded. This approach has later been improved in [START_REF] Tan | Intra prediction by averaged template matching predictors[END_REF] by averaging multiple template matching predictors, including larger and directional templates, resulting in up to 15% rate saving when compared to H.264/AVC Intraprediction. However, a best match of the template does not necessarily lead to a good predictor for the unknown block to be predicted, especially in non homogenous texture areas of the image or when there are discontinuities between the template and the block to be predicted. Blocks located in image areas having such characteristics will be better predicted if we can do a direct match with the block to be predicted. But this is feasible only at an extra rate cost which will represent the coding of the vector of correspondence between the two matching blocks. This is a block matching algorithm as used classically for motion estimation, but this time run spatially by defining a search window in the causal part of the current frame. In order to avoid the strong impact of the matching vector cost on the rate-distortion performance of the complete compression algorithm, this mode has to be used only for blocks where TM fails. A decision based on an RD cost function including the rate of the matching vector Fig. 1. Prediction problem statement and notations: X k denotes the known pixels (or template), X u is the current block to be predicted, and SW is the window within which the best predictor will be searched for. and the prediction residue is thus proposed. More precisely, two H.264 intra prediction modes (the least statistically used modes among the 9 available ones) are replaced by the TM and BM based intra predictions. The TM prediction algorithm and the proposed hybrid TM/BM predictions algorithm can thus be compared with the H.264 intra prediction modes.

The rest of the paper is organized as follows. Section 2 formulates the image prediction problem and reviews the main background approaches. Section 3 describes the proposed hybrid template and block matching intra predictions algorithm. Section 4 gives performance illustrations in the context of prediction and compression.

IMAGE PREDICTION: BACKGROUND APPROACHES

Let X be a texture patch which comprises a known part X k (of a given shape) formed by the pixels located in a causal neighborhood of the current block, called the template, and of an unknown part X u formed by the current block to be predicted (see Fig. 1). This section briefly reviews the most popular approaches to predict X u knowing the previously encoded and decoded samples of X k .

H.264 prediction modes

The H.264/AVC standard defines three types of intra prediction modes depending on the block size: the Intra-4x4, Intra-8x8 and Intra-16x16 [START_REF] Wiegand | Overview of the H.264/AVC video coding standard[END_REF]. For Intra prediction of 16x16 blocks, four intra prediction modes can be used while for Intra prediction of 4x4 and 8x8 blocks, nine modes have been defined as shown in Fig. 2. Here, we consider the three types of blocks which are then predicted from prior encoded pixels from spatially neighboring blocks. In addition to the so-called "DC" mode which consists in predicting the entire 4x4 or 8x8 block from the mean of neighboring pixels, eight directional prediction modes are specified [START_REF]Draft ITU-T Rec. and Final Draft Int. Standard of Joint Video Spec[END_REF]. The prediction is done by simply propagating (or interpolating) the pixel values along the specified direction.

Fig. 2. A 4x4 block with its boundary pixels and its eight directional intra prediction modes.

Template Matching (TM)

The TM algorithm searches, within a given search window SW located in the causal part of the image, the "best matching" patch in the sense of minimizing the Euclidean distance between the vector formed by the known samples X k of the neighborhood of the block to be predicted (of n 2 pixels size) and the co-located pixels in the candidate patches taken from SW . In Fig. 1, the known region X k is formed by the pixel values of 3 neighboring blocks, hence, the corresponding X k vector is of size N = 3n 2 pixels. Note, however, that different forms of templates X k can be considered [START_REF] Turkan | Image prediction: Template matching vs. Sparse approximation[END_REF]. The pixels in the candidate patch which are co-located to those of the block to be predicted are then used as predictors.

Block Matching (BM)

The block matching algorithm has been initially used for motion compensation in video compression. However, this approach has also been explored for intra coding [START_REF] Yu | New intra prediction using intra macroblock motion compensation[END_REF]. This block based intra prediction method performs similarly as motion estimation and compensation in inter-frame predictive coding, but here the reference block used in the prediction is searched in the causal part of the current image. Indeed, this algorithm searches, in a given search window SW in the reconstructed image, the best matching block by minimizing the Euclidian distance between the vector formed by the unknown samples X u of the block to be predicted and the candidate blocks taken from SW . Note that the unknown region X u is of size n 2 pixels.

HYBRID TM/BM PREDICTIONS ALGORITHM

The proposed intra prediction method consists in using the best of the TM and BM algorithms. The BM spatial prediction is used when the TM spatial prediction fails. Using both TM and BM intra prediction modes enables to take advantage of both methods. Indeed, the template matching approach works well when the unknown block to be predicted and its template are correlated to the ones matched by template. Besides, TM does not require sending additional matching vectors but the same template matching process has to be carried out on the decoder side increasing the complexity. By contrast, block matching based prediction method can better decorrelate the block to be predicted with the reconstructed image region and does not require to perform any estimation motion on the decoder side but the matching vectors have to be sent to the decoder. Therefore, the hybrid TM/BM method can first reduce the computational complexity at the decoder compared to TM only and also reduce the impact of matching vectors rate cost compared to BM only.

We have introduced TM and BM-based intra prediction modes in the H.264 codec (KTA reference software [7]) by replacing two existing modes of the H.264 algorithm as depicted in Fig. 3. Here, the two intra prediction modes, which are replaced by TM and BM modes, correspond to the least statistically used modes in H.264 Intra only. This facilitates the implementation by keeping the same syntax and allows saving signaling bits. Here, the proposed hybrid TM/BM approach is applied to Intra-4x4 and Intra-8x8 and the matching vectors are limited to full-pel accuracy. The selection of the best coding mode for a given block is conducted according to a minimization of Lagrangian criterion, also called Rate-Distortion Optimization (RDO) criterion:

min (D + λ × R) (1)
where D represents the distortion between the original block and the reconstructed block by using the Sum of Square Errors (SSE) distance metric, λ represents a trade-off coefficient between the distortion and the bits needed for coding the block. The parameter λ is selected as in the KTA reference software (λ = 0.65×2 QP/3 ), with QP corresponding to the quantization parameter. For intra coding mode based on BM, the rate cost R is calculated according to the following formula:

R = R mode + R res + R vector ( 2
)
where R mode , R res and R vector represent the bits needed for coding respectively the block coding mode, the residue and the matching vector. R mode and R res are encoded with the KTA entropy coding scheme (CABAC). The matching vectors are coded using a fixed length code (FLC) which varies nevertheless according to the size of the causal search window SW . For intra coding mode based on TM, the equation ( 2) is also used with R vector = 0. 1 and2, where coding efficiencies were compared using the Bjontegaard metric [START_REF] Bjontegaard | Calculation of average psnr differences between rd curves[END_REF].

Here, we considered a search window of size of 64x128 pixels and matching vectors at full-pel accuracy. Compared to H.264 Intra only, average BD-rate gains obtained with the TM-based compression method are of 17.56% at low bitrates and 13.64% at high bitrates whereas the ones obtained with the hybrid TM/BM based compression method are of 24.78% at low bitrates and 16.74% at high bitrates.

The first set of pictures (from Barbara to City2) is partially composed of pseudo-regular textures that fit well with the different algorithms tested. The pictures Zone1 (Fresnel image) and Pan0 qcif (nearly regular texture) can be considered as atypical. The Matrix, composed of sequences of random numbers, is a test image (taken from the Matrix movie) that highlights the virtues of two algorithms. Indeed, the TM does not allow a reliable prediction of a given number knowing only its neighborhood. However, this approach works well in texture synthesis because it is based only on visual aspects instead of a PSNR measure. In contrast, the BM allows the good prediction of a number, if the same number is present in the causal search window. We obtained also interesting results with conventional images like Foreman (CIF) and Spincalendar (HD), especially at low bitrates.

From all test sequences, we can notice that the use of both TM and BM predictions enables to get better coding efficiency compared to H.264 Intra for various contents in all resolutions. However, the proposed hybrid TM/BM method offers variable coding performances due to the type of content in the pictures. In fact, on the one hand, we can see that the coding gains are less important for the sequences Barbara and Foreman compared to H.264 Intra only since H.264 intra prediction modes are quite well suited. On the other hand, we can observe that the coding gains are significant for the pictures such as Zone1 and City2 that present local stationary properties. Indeed, a bit rate saving up to 41.78% and 48.38% respectively is achieved at low-bitrates compared to H.264 Intra only.

Experimental results show also that the proposed method outperforms the TM-based approach and the BM-based approach. This was explained by the fact that the two approaches are quite complementary. From the simulation results, we can point out that BM provides a better prediction in local variations of the signal than TM as we can see with the pictures Barbara and Snook (cf. Table 1).

Fig. 4 illustrates the use of TM and BM prediction modes for Intra-8x8 only. We can notice that the picture Barbara presents pseudo-periodic structures which are locally vari- ables due to spatial deformations of the fabric. It is the reason why the TM mode is less selected than BM mode. The picture City2 shows that TM and BM methods complement each other since this image presents locally homogeneous textures while at the same time having a slight perspective effect.

Note that at the encoder, the BM algorithm can be performed jointly with the TM algorithm. However, at the decoder, the computational complexity depends only on the occurence of TM mode.

CONCLUSION

In this paper, a hybrid template and block matching algorithm for intra coding has been introduced. This new approach of prediction offers interesting results compared to respectively H.264 Intra only and TM mode included in H.264 Intra. Moreover, the hybrid TM/BM method enables to reduce the computational complexity at the decoder compared to TM only because the BM mode does not need to perform a best matching search at the decoder. Future work will consider more efficient methods using a vector predictor to code the BM vectors such as a median predictor. Besides, so far, TM and BM have been performed only at full-pel accuracy, which enables us to avoid sub-pel interpolations on the fly. However, the sub-pel accuracy could be also investigated knowing that the sub-pel accuracy will increase the BM vectors cost.

Fig. 3 .

 3 Fig. 3. Synoptic of hybrid TM/BM intra prediction modes selection for 4x4 or 8x8 blocks.

  4. PERFORMANCE ILLUSTRATION Three coding schemes: the TM-based algorithm, the BMbased algorithm and the proposed hybrid TM/BM based algorithm have been assessed comparatively to H.264 Intra prediction modes. Several test sequences of different resolutions were tested and shown in Tables

Fig. 4 .

 4 Fig. 4. Illustration of modes used in 8x8 prediction: TM (in blue) and BM (in red) (QP=31).

Table 2 .

 2 Rate-Distortion gains (with the Bjontergaard measure) with respect to H.264 Intra prediction modes at high bit rates (computed at 4 rate points: QP=26,31,36,41).


G Hassen

P De Buhan

E Bourgeois

DESIGN OF PILED-RAFT FOUNDATIONS BY MEANS OF A MULTI-PHASE MODEL ACCOUNTING FOR SOIL-PILE INTERACTIONS

The settlement behavior of a pile-raft foundation is analyzed with the help of a multiphase model aimed at describing the overall behavior of the reinforced ground. According to this model, the group of piles is treated as a homogenized continuous medium in interaction with the soil along the pile length, as well as at their lower tips. These two kinds of interaction, which play a decisive role in the way the piles are actually working as strengthening elements, are described by specific constitutive laws which can be directly introduced in the general governing equations of the multiphase model. Thus improved, the multiphase model can then be incorporated in a finite element code developed in the context of an elastoplastic behavior of the soil, provided that the constitutive parameters of the interaction laws have been previously identified. This identification procedure is performed through numerical simulations of the simple problem of a single pile, loaded at its top. The global response of vertically loaded piled-raft foundations, expressed in the form of load settlement curves, is finally presented, clearly highlighting the decisive influence of the mobilized pile shaft friction and tip resistance on the foundation settlement reduction.

INTRODUCTION

The setup of rational and reliable design methods for piled-raft foundations still remains a major computational challenge. Indeed, referring for instance to a finite element simulation of this kind of geotechnical structures, a fully three-dimensional analysis is required, with a locally refined mesh discretization in order to capture with sufficient accuracy the complex interactions prevailing between the piles, the surrounding soil and the raft. This leads to the elaboration of a complex and sophisticated computational tool, the use of which remains limited to rather simple configurations, such as purely vertical loading [START_REF] Lee | Three-dimensional analysis of bearing behavior of piled raft on soft clay[END_REF]. Conceived as an improved homogenization procedure, a so-called "multiphase model" has been proposed, which can easily be implemented in a f.e.m.-based numerical code, thus leading to a considerable simplification of the initial design problem and to dramatically reduced computational times [START_REF] Sudret | Multiphase model for inclusion-reinforced geostructures. Application to rock-bolted tunnels and piled raft foundations[END_REF].

The present contribution is focused on extending the range of applicability of the model, in order to account for soil-pile interactions taking place not only along the pile length (mobilized "shaft or skin friction"), as already developed in [START_REF] Bourgeois | Finite element simulations of the behaviour of piled-raft foundations using a multiphase model[END_REF], but also at the lower ends of the piles (mobilized "tip resistance"), both kinds of interactions being captured through specific laws expressed in the formalism of the multiphase model. The analysis is carried out following two successive steps. First, appropriate values for the constitutive stiffness and strength parameters of the above interaction laws are identified from numerical simulations performed on a representative volume of pile-reinforced ground. These parameters are then incorporated in the multiphase model and implemented in a finite element code, allowing to investigate the behavior of pile-reinforced foundations and thus provide insight into the way the foundation settlement is actually reduced by the incorporation of piles.

PRINCIPLE OF THE MULTIPHASE APPROACH

Problem statement

The typical engineering problem to be dealt with is that of a shallow strip footing of width B resting upon a soft clay which has been previously reinforced by a group of piles of length L placed just beneath the raft. The latter is subject to a purely vertical loading characterized by a linear density Q along the raft's axis Oz, as sketched in Figure 1(a). Denoting by ρ the pile's radius and by s the spacing between two adjacent piles assumed to be distributed in the soil mass following a regular square pattern, a key parameter of such a reinforcement scheme is the reinforcement volume fraction defined as:

2 2 s ρ π η = (1)
which is generally small. Our objective is to investigate through numerical simulations the actual settlement reduction provided by the piles.

Outline of the multiphase model

The multiphase approach consists in replacing the composite pile-strengthened zone of height L and width B located beneath the raft, not by one single equivalent medium as in the traditional homogenization approach, but by two superposed interacting continua, called "phases". According to this model, a detailed presentation of which may be found in [START_REF] Sudret | Multiphase model for inclusion-reinforced geostructures. Application to rock-bolted tunnels and piled raft foundations[END_REF], the soil is represented by a matrix phase, while the group of piles is represented by a reinforcement phase. More precisely, two coincident particles are located at any geometrical point of the reinforced zone; each particle is attributed its own kinematics, namely a displacement vector ξ m for the matrix phase particle and ξ r for the reinforcement phase particle.

The matrix phase is a classical continuous medium where the stress at any point is defined by a tensor σ m , whereas the stress in the reinforcement phase occupying the domain V is defined by a uniaxial tensor

x x r e e n ⊗
along the vertical pile orientation, where n r can be interpreted as the axial force in the piles per unit cross sectional area of reinforced soil. The equilibrium equations, expressed for each phase separately, may be written as: where, for the sake of simplicity, the external body forces (gravity) have been omitted. In the above equations, I is a body force volume density, which represents, at the macroscopic scale of the multiphase model, the action of the piles on the soil along their length ("shaft or skin friction"). A second kind of soil-pile interaction should be taken into account, corresponding to the action exerted by the pile lower tips onto the soil. This interaction takes place on the horizontal surface Σ located at a depth L from the surface, as shown in Figure 2, in the form of a surface density pe x , while the matrix phase exerts on the lower boundary surface Σ of the reinforcement phase an opposite surface density -pe x (right hand side of Figure 2). The existence of such an interaction surface density, associated with the "pile tip resistance", implies the following condition on the lower boundary of the reinforcement phase:

p L x n r - = = ) ( ( 3a
)
It generates at the same time in the matrix phase a discontinuity of the vertical stress component across Σ:

p L x L x m xx m xx - = = - = - + ) ( ) ( σ σ (3b)
Besides, it should be noted that the same uniform displacement boundary condition is imposed by the rigid raft on top of both phases (Figure 2):

x r m e x x δ ξ ξ = = = = ) 0 ( ) 0 ( ( 4
)
where δ is the foundation surface settlement.

Constitutive equations of the multiphase model

Assuming that the pile remain elastic, the constitutive equation of the reinforcement simply writes:

r r n αε = (5) where x r x r ∂ ∂ = / ξ ε
is the axial strain of the reinforcement phase, while α is the axial stiffness of the piles per unit transverse area, which can be evaluated as the product of the reinforcement volume fraction by the Young's modulus p E of the pile constituent material:

p E η α = (6)
On the other hand the matrix phase constitutive relations are simply identified with those of the soil, modelled as a linear elastic perfectly plastic, purely cohesive material, with an cohesion C. Furthermore, the above described soil-pile interactions are governed by specific constitutive laws which can be written as follows.

• The first kind of interaction ("shaft friction") is formulated by means of a relationship linking the interaction force volume density I to the relative axial displacement between the reinforcement and the matrix phases, defined as:

m x r x ξ ξ - = ∆ (7)
In the context of an elastic perfectly plastic behavior, such a constitutive law takes the following form: where ∆ p is the plastic component of the relative displacement, while c I and I 0 are coefficients describing the stiffness of the interaction and the threshold value of the interaction force density for which an irreversible relative displacement between the matrix and reinforcement phases occurs. The latter parameter can for instance be related to the maximum skin friction between the piles and the ground [START_REF] Bourgeois | Finite element simulations of the behaviour of piled-raft foundations using a multiphase model[END_REF]. • Similarly, the second type of interaction, associated with the "pile tip resistance", will be expressed by a relation between the interaction force surface density p and the axial reinforcement/matrix relative displacement on Σ(x=L). Adopting an elastoplastic framework, we thus obtain:

     = - = ≤ = + = ≥ ≤ = ∆ ∆ - ∆ = 0 , if 0 0 , if 0 if 0 with ) (
( ) These interaction constitutive laws are strongly reminiscent of load-transfer curves ("t-z" curves) classically introduced for designing the load bearing capacity of individual piles driven in a soil (see among the most recent references: [START_REF] Ashour | Mobilized side and tip resistances of piles in clay[END_REF]. It should be emphasized that an important difference between the above interaction laws and the usual load-transfer curves, is that the relevant kinematic variable associated with the pile-ground interaction forces is the relative displacement (∆) between the matrix and reinforcement phases and not the absolute settlement (z) of the pile.

     = - = ≤ = + = ≥ ≤ = ∆ ∆ - ∆ = 0 , if 0 0 , if 0 if 0 with ) ( ) ( 0

IDENTIFYING THE CONSTITUIVE PARAMETERS OF THE MULTIPHASE MODEL

The key ingredient to the application of the multiphase approach to the simulation of the piled-raft settlement behavior lies in the identification of the different constitutive parameters introduced above.

Matrix and reinforcement phases

The identification of the constitutive stiffness and yield strength parameters of both phases is very straightforward. Owing to the fact that the reinforcement volume fraction introduced in Eq. ( 1) is small, and consequently the soil volume fraction is close to unity, the matrix phase is assigned the same elastoplastic characteristics as the purely cohesive soft clayey soil, namely:

kPa 30 , 3 . 0 , MPa 45 = = = m m m C E ν (10)
As regards the reinforcement phase, assumed to remain elastic as the (concrete) piles, the axial elastic stiffness density is simply calculated from Eqs. ( 1) and ( 6). Thus:

MPa 613 MPa 12500 % 9 . 4 m 2 , m 25 . 0 = → = = → = = α η ρ p E s (11)

Elastic interaction parameters

The determination of the interaction stiffness parameters I c and p c is based upon the same procedure as that used for piled-embankments [START_REF] Hassen | Multiphase constitutive model for the design of piled-embankments: comparison with three-dimensional simulations[END_REF], which can be briefly described as follows. Considering the representative elementary volume of reinforced ground comprising one single pile surrounded by the soil, subject to a laterally constrained compressive loading, as pictured in Figure 4, the numerical simulation of this auxiliary problem (performed by means of a standard finite element code) is compared with the solution derived from the multiphase description of the same problem, which may be expressed analytically in the context of linear elasticity. More precisely, the identification is realized from fitting the numerical and analytical curves giving the variation with depth of the proportion λ of the total loading supported by the reinforcing pile. In the present configuration, the values of the interaction coefficients associated with the best fitting of these curves (Figure 4) are:

MPa.m 5 , MPa.m 40 -1 -2 = = p I c c (12)

Yield strength interaction parameters

The parameters governing the strength of the interaction laws (i.e. 0 I and 0 p ) can also be very simply evaluated on the basis of the numerical solution to the auxiliary problem, the loading being applied up to obtaining a complete plastification of the soil surrounding the pile. Figure 5 displays the corresponding axial load distribution along the pile length, expressed in terms of (compressive) stress n r in the reinforcement phase, which turns out to vary linearly from -204 kPa at the pile head (x=0m) to -32 kPa at the pile tip (x=12m).

Such a result can be interpreted as follows in the framework of the multiphase model, assuming that both interaction forces have reached their yield values:

EXAMPLE OF NUMERICAL SIMULATION

Due to the symmetry with respect to the vertical plane passing through the footing axis, only one half of the piled raft foundation to be analyzed as a plane-strain problem, is represented in Figure 6, with its corresponding finite element mesh of 1,732 triangular elements and 3,542 nodes. The total width of the rigid footing acting on top of the pile-reinforced is equal to 12 m, so that the reinforcement scheme consists in six rows of 12m piles regularly spaced by a distance of 2m. All the other geometrical and geotechnical characteristics adopted in the following simulations are the same as those previously introduced.

It should be pointed out that the refinement of the mesh in the reinforced zone is the same as for a non reinforced, and thus homogeneous, soil. The only significant difference lies in the fact that three degrees of freedom (instead of two in the case of homogeneous soil) are attached to each node, namely the two components of the matrix phase displacement along with the axial relative displacement between phases ∆. The numerically computed load-settlement curves are displayed in Figure 7. The four curves drawn up to the ultimate bearing capacity of the structure (vertical branch of the curves) correspond to the following four different situations.

▫ First, the foundation without any pile (non reinforced case) for which the ultimate bearing capacity is equal to 960 kN/m, that is slightly above the classical value predicted by the Prandtl's failure mechanism ((π+2)CB/2 ≅ 930 kN/m). ▫ The case of the piled-raft foundation, where the condition of perfect bonding (PB) between phases has been assumed, which can be enforced by assigning very high values to the interaction stiffness ( I c , p c ) and strength ( 0 I , 0 p ) parameters. The corresponding ultimate bearing capacity is equal to almost twice that of the un-piled raft: 1700 kN/m. ▫ The two remaining cases considered in the analysis are those where only the "side" interaction law is taken into account (S) and when both "side" and "tip" interactions are accounted for (S&T) The corresponding ultimate bearing capacity is equal to 1350 kN/m in the latter case, 1280 kN/m in the former one.

Figure 8 represents a detailed picture of the load-settlement curves in the vicinity of a working load level of 1200kN/m, which exceeds the ultimate bearing capacity of the non reinforced foundation. Notable differences can be observed for the corresponding settlements evaluated on the basis of the above mentioned hypotheses: 3.3cm for the perfect bonding assumption, 8.1cm and 6cm for the "side interaction only" and "side and tip interaction" assumptions, respectively. This influence is confirmed in Figure 9, showing the corresponding variations of forces along the pile located in the middle of the reinforce zone, expressed in terms of stress distributions n r along the corresponding vertical line in the reinforcement phase. The most striking difference between the three profiles is the value of the reinforcement stress at the tip of the piles (x=12m), which vanishes when no tip interaction is taken into account, takes the maximum value of -127kPa when perfect bonding is assumed and the intermediate value of -31kPa (that is close to -p 0 ) when tip interaction is also considered in the analysis.

CONCLUSION

It has been shown in this contribution how it was possible to incorporate specific soil-pile interaction laws in a multiphase model developed for the numerical simulation of piled-raft foundations. The important role played by such so-called "side and tip" interaction laws on the ultimate bearing capacity of the foundation, as well as on its settlement under working load conditions, has been clearly assessed in the analysis performed above.

Reliable predictions of piled-raft behaviour are therefore strongly dependent on the possibility of identifying appropriate values for the stiffness and yield strength interaction parameters to be introduced in the multiphase numerical calculations. The identification procedure proposed in this contribution, based on the numerical simulation of an auxiliary problem, should be used in a more systematic way, in order to produce closed-formed expressions giving the interaction parameters as functions of geometric (pile diameter and

Fig. 1 .

 1 Fig. 1. Piled raft under vertical loading: (a) initial problem and (b) multiphase description

Fig. 2 .

 2 Fig. 2. Statics of the piled raft foundation modelled as a system made of two mutually interacting phases

Fig. 3 .

 3 Fig. 3. Stress-strain diagrams for (a) the "shaft friction" and (b) "tip resistance" interaction laws

  Fig. 4. Identification of the interaction stiffness parameters

Fig. 5 .

 5 Fig. 5. Axial load distribution along the reinforcement for a fully plastic surrounding soil in the auxiliary problem

Fig. 6 .

 6 Fig. 6. Finite element discretization of the piled-raft foundation

Fig. 8 .Fig. 8 .

 88 Fig. 8. Load-settlement curves of the piled and unpiled-raft foundation under different assumptions