Benjamin Camus
email: benjamin.camus@inria.fr

Fanny Dufossé
email: fanny.dufosse@inria.fr

Anne-Cécile Orgerie
email: anne-cecile.orgerie@irisa.fr

The SAGITTA approach for optimizing solar energy consumption in distributed clouds with stochastic modeling

Keywords: Data centers, distributed clouds, energy efficiency, renewable energy, scheduling, on/off techniques

Facing the urgent need to decrease data centers' energy consumption, Cloud providers resort to on-site renewable energy production. Solar energy can thus be used to power data centers. Yet this energy production is intrinsically fluctuating over time and depending on the geographical location. In this paper, we propose a stochastic modeling for optimizing solar energy consumption in distributed clouds. Our approach, named SAGITTA (Stochastic Approach for Green consumption In disTributed daTA centers), is shown to produce a virtual machine scheduling close to the optimal algorithm in terms of energy savings and to outperform classical round-robin approaches over varying Cloud workloads and real solar energy generation traces.

Introduction

The rapid increase of demand for Internet services leads Cloud providers to build more and more data centers for hosting these services. The data centers that constitute the Cloud infrastructures are usually geographically distributed for security reasons or to offer lower latency for their clients. This infrastructure increase comes with a dramatic growth of the power consumption globally drawn by data centers. As an example, in 2014, data centers in the U.S. consumed an estimated 70 billion kWh, representing about 1.8% of total U.S. electricity consumption [START_REF] Shehabi | United States Data Center Energy Usage Report[END_REF].

To reduce this impact, Cloud providers resort to renewable energy sources which are either on-site or off-site [START_REF] Tripathi | Optimizing Green Energy, Cost, and Availability in Distributed Data Centers[END_REF]. Such energy sources are mostly intermittent by nature (wind, sun, etc.) with high variations, and periods of time without any production (during night for instance for photovoltaic panels). Energy storage devices can help to overcome this issue. But, they constitute a costly investment and they intrinsically lose part of the energy stored [START_REF] Wang | Energy storage in datacenters: What, where, and how much?[END_REF]. Thus, without storage, renewable energy has to be consumed upon production or it is wasted. In this context, optimizing renewable energy consumption requires to know local availability for the distributed cloud infrastructure, in order to adequately allocate computing resources to incoming user requests. The goal is to geographically distribute the workload among the data centers so that, it fits at best the on-site renewable energy production that is variable and not known.

Here, we consider the problem of scheduling workload across multiple data centers for minimizing renewable energy loss. To solve this issue, we propose SAGITTA: a Stochastic Approach for Green consumption In disTributed daTA centers. SAGITTA uses a stochastic approach for estimating renewable energy production, and greedy heuristics for allocating resources to the incoming user requests and switching off unused servers. While SAGITTA was first introduced in [START_REF] Camus | A stochastic approach for optimizing green energy consumption in distributed clouds[END_REF], the original SAGITTA algorithm did not take into account the switching on and off energy costs. Here these costs are integrated in SAGITTA's algorithm and all the simulations have been redone. This chapter extends the first SAGITTA study [START_REF] Camus | A stochastic approach for optimizing green energy consumption in distributed clouds[END_REF] with the following contributions:

modification of SAGITTA's original version to take into account the switching on and off energy costs; proof of local optimality of SAGITTA; proposition of an optimal algorithm based on dynamic programming to solve the problem; simulation results exploring the influence of green energy forecast and green energy production on SAGITTA and study of its scalability; performance comparison between SAGITTA and the optimal algorithm; study on the exactness of our green power production forecast.

Our simulation-based results show the efficiency of SAGITTA compared to classical allocation approaches. Indeed, compared to the optimal solution, SAGITTA consumes 5.2% more energy overall, while a classical round-robin solution consumes 12.9% more energy overall than optimum.

The remainder of the paper is structured as follows. Related work is presented in Section 2. A formal definition of the problem is given in Section 3. Section 4 details the SAGITTA approach. Section 5 exhibits an optimal algorithm for the considered problem. A simulation-based evaluation is conducted, simulation conditions are described in Section 6 and results are provided in Section 7. Future work is discussed in Section 8.

Related work

Cloud infrastructures consist in geographically distributed data centers which are linked through communication networks [START_REF] Wang | Scientific Cloud Computing: Early Definition and Experience[END_REF]. With the emergence of the Future Internet and the dawning of new IT models such as cloud computing, the usage of data centers, and consequently their power consumption, increases dramatically.

As an example, for 2010, Google used 900,000 servers which consumed 1.9 billion kWh of electricity [START_REF] Koomey | Growth in Data Center Electricity Use 2005 to 2010[END_REF]. Other major Cloud companies present similar figures and similar issues [START_REF] Katz | Tech Titans Building Boom[END_REF].

Virtualization technology and its ability to pool resources through transparent sharing should have minimized worldwide data center consumption. But, the energy consumption of state-of-the-art servers grows inexorably as they embed more and more powerful cores and advanced features and technologies. Consequently, the global data center consumption keeps increasing rapidly [START_REF] Shehabi | United States Data Center Energy Usage Report[END_REF]. This situation raises major environmental, economic and social concerns.

The first way to save energy at a data center level consists in locating it close to where the electricity is generated, hence minimizing transmission losses. For example, Western North Carolina, USA, attracts data centers with its low electricity prices due to abundant capacity of coal and nuclear power following the departure of the region's textile and furniture manufacturing [START_REF]How dirty is your data?[END_REF]. This region has three super-size data centers from Google, Apple and Facebook with respective power demands of 60 to 100 MW, 100 MW and 40 MW [START_REF]How dirty is your data?[END_REF].

Other companies opt for greener sources of energy. For example, Quincy (Washington, USA) supplies electricity to data facilities from Yahoo, Microsoft, Dell and Amazon with its low-cost hydro-electrics left behind following the shutting down of the region's aluminum industry [START_REF]How dirty is your data?[END_REF]. Several renewable energy sources like wind power, solar energy, hydro-power, bio-energy, geothermal power and marine power can be considered to power up super-sized facilities.

In spite of these approaches, numerous data facilities have already been built and cannot be moved. Cloud infrastructures, on the other hand, can still take advantage of multiple locations to use green sources of energy with approaches such as follow-the-sun and follow-the-wind [START_REF] Figuerola | Converged Optical Network Infrastructures in Support of Future Internet and Grid Services Using IaaS to Reduce GHG Emissions[END_REF]. As sun and wind provide renewable sources of energy whose capacity fluctuates over time, the rationale is to place computing jobs on resources using renewable energy, and migrate jobs as renewable energy becomes available on resources in other locations. However, the migration cost, in terms of both energy and performance, may be prohibitive [START_REF] Callau-Zori | An experiment-driven energy consumption model for virtual machine management systems[END_REF].

Within the data center itself, a range of technologies can be utilized to make cloud computing infrastructures more energy efficient, including better cooling technologies, temperature-aware scheduling [START_REF] Fan | Power provisioning for a warehouse-sized computer[END_REF], Dynamic Voltage and Frequency Scaling (DVFS) [START_REF] Snowdon | Power Management and Dynamic Voltage Scaling: Myths and Facts[END_REF], and resource virtualization [START_REF] Talaber | Using Virtualization to Improve Data Center Efficiency[END_REF]. The use of Virtual Machines [START_REF] Barham | Xen and the Art of Virtualization[END_REF] brings several benefits including environment and performance isolation; improved resource utilization by enabling workload consolidation; and resource provisioning on demand. Nevertheless, such technologies should be analyzed and used carefully for actually improving the energy-efficiency of computing infrastructures [START_REF] Miyoshi | Critical power slope: understanding the runtime effects of frequency scaling[END_REF].

One of the most efficient techniques for saving energy in not fully utilized data centers consists in shutting down unused resources as switched off resources consumes less power than idle ones [START_REF] Orgerie | A Survey on Techniques for Improving the Energy Efficiency of Large-Scale Distributed Systems[END_REF]. The number of switched off resources can be increased by consolidation techniques [START_REF] Orgerie | A Survey on Techniques for Improving the Energy Efficiency of Large-Scale Distributed Systems[END_REF]. However, switching on and off resources consumes time and energy and these costs need to be taken into account in order to effectively ensure energy savings [START_REF] Rais | Impact of Shutdown Techniques for Energy-Efficient Cloud Data Centers[END_REF].

Concerning green energy integration, Ren et al. have proposed an online scheduling algorithm which optimizes the energy cost and fairness among different data centers subject to queuing delay constraints [START_REF] Ren | Provably-Efficient Job Scheduling for Energy and Fairness in Geographically Distributed Data Centers[END_REF]. While their work is based on a distributed Cloud model similar to ours, they aim at minimizing the cost of the consumed electricity, instead of the wasted renewable energy in our case. Tripathi et al. have presented a mixed integer linear programming formulation for capacity planning while minimizing the total cost of ownership [START_REF] Tripathi | Optimizing Green Energy, Cost, and Availability in Distributed Data Centers[END_REF]. Their model schedules demand considering the availability of green energy and its price variation to lower the total cost of ownership. Finally, a literature review of renewable energy integration in data centers can be found in [START_REF] Deng | Harnessing renewable energy in cloud datacenters: opportunities and challenges[END_REF].

Problem

First, the Cloud model and assumptions are described in Section 3.1 similarly to [START_REF] Camus | A stochastic approach for optimizing green energy consumption in distributed clouds[END_REF]. Then, Section 3.2 proposes the problem formulation.

Cloud model

We consider a distributed Cloud infrastructure comprising several data centers geographically distributed and powered by the regular electrical grid on one side and on-site photovoltaic panels (PV) on the other side. The user management of the Cloud is assumed to be centralized. This Cloud model is shown on Figure 1.

Incoming users requests can arrive at any time. Each request requires to be computed by a virtual machine (VM) located on any of the data centers. Each data center hosts a given amount of homogeneous servers.

Problem formulation

We consider a system of M data centers spread over a large area. A data center DC i is characterized by its number S i of servers. Servers are considered homogeneous over the different data centers, in term of computing capabilities and energy consumption.

As for the application model, we consider identical VMs submitted at unpredictable rate. The VMs are supposed to be executable in less than one time slot. We can thus describe both computing and memory requirement of VMs by the number C of VMs that a server can complete in a single time slot. We consider that a server consumes at full capacity a power of P s .

The main difference with previous paper [START_REF] Camus | A stochastic approach for optimizing green energy consumption in distributed clouds[END_REF] concern the energy consumption model. In [START_REF] Camus | A stochastic approach for optimizing green energy consumption in distributed clouds[END_REF], the model only considered the processing cost, that is the consumption of servers during the processing time. The switching ON/OFF costs were only used to evaluate the performance of resulting algorithms. In this paper, we take into account the switching ON/OFF costs in the basis model. More precisely, we consider that the switches are done at beginning of the time slots, and that the switching time is negligible compared to the time slot duration. For example, the duration to turn on will not impact the number of VM executed in the remaining time. We compute in this paper the energy at the scale of the time slots, and we do not evaluate if the energy is used mostly at beginning or at the end on a time slot. Therefore, in our model, the energy consumption, likewise the energy production, is smoothed on the time slot.

Consequently, the energy consumption of DC i has three possible component. The first part is the power consumption of each server, and is proportional to the number of servers ON at current time slot t on DC i , U i (t). The second part is the costs of switching on servers, proportional to the number of servers turned on U + i (t) = max(0, U i (t) -U i (t -1)) and the last on the cost of shutting down servers, proportional to U - i (t) = max(0, U i (t -1) -U i (t)). The total power consumed by the system is thus

M i=1 P s × U i (t) + P ON × U + i (t) + P OF F × U - i (t).
This power requirement is to be compared with the green power produced at each data center. We model the green power available at time slot t in data center DC i as a random variable G i (t) that follows a truncated normal distribution of mean Eg i (t) and standard deviation p i (t), with lower limit 0. Thus, the brown power consumed at time slot t in DC i is equal to

max(0, P s × U i (t) + P ON × U + i (t) + P OF F × U - i (t) -G i (t)
). Our problem consists in allocating VMs to data centers, in order to minimize the consumption of brown energy. VMs are allocated by time slots. Then, our objective is to turn ON the adequate number of servers on the best locations for this criteria. We denote N (t) the number of waiting VMs at time slot t. We thus need to have enough servers ON for all waiting VMs at time slot t:

M i=1 U i (t) ≥ N (t)/C
. All these notations are summarized in Table 1. Random variable of the green power produced at time slot t Egi(t) Expected green power generation at data center i during time slot t (input) pi(t)

Standard deviation of green power generation on data center i (input) w

Workload portion (number of VM): 0 < w ≤ N (t) (input) Eci(P, t) Expected brown consumption of data center i with power P at time slot t

SAGITTA

In this section, we present our approach named SAGITTA: a Stochastic Approach for Green consumption In disTributed daTA centers. The details for computing the expected green and brown consumption are provided in Section 4.1. SAGITTA's algorithms are presented in Section 4.2 and its local optimality is demonstrated in Section 4.3.

Expected green and brown consumption

We now evaluate the expected brown power consumption of data center DC i at time t, consuming power P , Ec i (P, t). We first evaluate the density function of the random variable of the green power generation of DC i at time t G i (t).

Let X be a random variable following a normal distribution of parameters Eg i (t) and p i (t), density function

φ(t) = 1 p i (t) √ 2π e -1 2 t-Eg i (t) p i (t)
and distributive function

Φ(t) = 1 2 1 + erf t -Eg i (t) p i (t) √ 2 .
Then, for x > 0,

P (G i (t) < x) = P (X < x|X > 0) = P (0 < X < x) P (X > 0)
and the density function of G i (t) equals φ i (t) = φ(t) P (X>0) . Let B i (t) be the random variable of the brown consumption of DC i at time slot t. Then, as shown in [START_REF] Camus | A stochastic approach for optimizing green energy consumption in distributed clouds[END_REF], we have:

Ec i (P, t) = (P -Eg i (t)) Φ(P ) -Φ(0) 1 -Φ(0) -p i (t) 2 φ(0) -φ(P ) 1 -Φ(0) , with φ(x) = 1 pi(t) √ 2π e -1 2 x-Eg i (t) p i (t) 2 and Φ(x) = 1 2 1 + erf x-Egi(t) pi(t) √ 2 .
In the following, if the considered time slot is clear, we simply note Ec i (P ) for the expected brown power consumption.

Algorithms description

Our SAGITTA approach uses several algorithms to take decisions and allocate VMs to physical servers. These algorithms are designed to determine at any time slot on which data center to turn ON and OFF servers. At each time slot, our constraint is to turn ON the minimum number of servers that allows for executing all requested VMs, that is N (t)/C .

Algorithm 1: General algorithm if 1≤i≤M Ui(t) < N (t) C then Switch on decision; (Algorithm 2) else if 1≤i≤M Ui(t) > N (t) C then Switch off decision; (Algorithm 3) end if Transfer decision; (Algorithm 4) for 1 ≤ i ≤ M do
Let Ui(t) servers on and fill them, switch off the rest; end for

The general algorithm (Algorithm 1) is designed as follows. It first determines if the number of servers available is under or over the requested number. If there is not enough servers ON, Algorithm 2 determines the location of servers to switch on. If some servers are unnecessary, Algorithm 3 determines where servers should be shut down. These decisions are done regarding the expected green energy production in the different data centers. More precisely, Algorithm 2 compares the expected extra cost in brown energy consumption c i induced by an additional server ON on any data centers, and selects the data center with minimum expected extra cost. The variable U i (t) is then incremented, but the servers are only switched on at end of Algorithm 1, when all decisions are taken on any data centers. The same way, Algorithm 3 selects one by one the servers to switch OFF to maximize the expected gain.

Algorithm 2: Switch on decision Finally, Algorithm 4 evaluates if the brown power consumption could be reduced by transferring the available processing power from one data center to another. More precisely, the algorithm determines some location where a fixed number of servers is turned off, and a new location where the same number of servers is turned on. One server is selected for switch OFF on the data center of maximum gain and another one to switch ON on the data center of minimum cost, if the gain on the first data center exceed the cost on the second one. The costs and gain are computing with respects to previous preallocation. For example, the cost of turning a server on is not the same if Algorithm 3 has decided to turn off a server at previous step, that is if U i (t) < U i (t -1) or not. If no such decision was taken, the cost c i is the same as in Algorithm 2, c i = Ec i (P i + P ON + P s ) -Ec i (P i ), that includes the cost to turn on and the cost of processing. In the other case, turning on a server correspond to cancel a decision to turn off a server, that is c i = Ec i (P i -P OF F + P s ) -Ec i (P i ). The same holds for gain g i to turn off a server.

for 1 ≤ i ≤ M do Pi = Ui(t -1) × Ps Ui(t) = Ui(t -1) if Ui(t) < Si then Compute ci = Eci(Pi + PON + Ps) -Eci(Pi); else ci = +∞; end if end for while 1≤i≤M Ui(t) < N (t) C do Find j such that cj = min

Algorithm 3: Switch off decision

for 1 ≤ i ≤ M do Pi = Ui(t -1) × Ps if Ui(t) > 0 then Compute gi = Eci(Pi) -Eci(Pi + POF F -Ps); else gi = -1; end if end for while 1≤i≤M Ui(t) > N (t) C do Find j such that gj = max 1≤i≤M gi; Uj(t) --; Pj+ = POF F -Ps Recompute gj; end while
After running Algorithm 4, general Algorithm 1 applies all these decisions. The selected number of servers are turned ON and OFF and all VMs are allocated to available servers.

SAGITTA local optimality

We demonstrate in this section, that Algorithms 2, 3 and 4 are locally optimal. More precisely, at time slot t, with respect to the normal laws (N (Eg i , p i ) 2 )) 1≤i≤M , these algorithms select the best servers to turn on or off, to minimize the expect brown power consumption. We first consider Algorithm 2. Theorem 1. Algorithm 2 is locally optimal with respect (N (Eg i , p i ) 2 )) 1≤i≤M .

Proof. We are studying the execution of SAGITTA during one unique time slot, so we do not precise t in this proof. For sake of simplicity, we denote in this proof c i (P ) = Ec i (P + P ON + P s ) -Ec i (P ). We compare Algorithm 2 to any selection of servers to turn on. We do not compare to a configuration where some servers are turned on and others turned off.

We first prove that the function c i (P ) is increasing, and then that this property induces the local optimality of Algorithm 2.

Ec i (P ) = P × Φ(P ) -Φ(0) 1 -Φ(0) - P 0 xφ(x)dx 1 -Φ(0)
Algorithm 4: Transfer decision = Φ(P )-Φ(0) 1-Φ(0) + P × φ(P ) 1-Φ(0) -P φ(P )

for 1 ≤ i ≤ M do if Ui(t) > Ui(t -1) then gi = Eci(Pi) -Eci(Pi -Ps -PON ); else gi = Eci(Pi) -Eci(Pi + POF F -Ps); end if if Ui(t) < Ui(t -1) then ci = Eci(Pi -POF F + Ps) -Eci(Pi); else ci = Eci(Pi + PON + Ps) -Eci(Pi); end if end for while max 1≤i≤M gi > min 1≤j≤M cj do Find k such that g k = max
1-Φ(0) = Φ(P )-Φ(0) 1-Φ(0) Then, d dP c i (P ) = Φ(P + P ON + P s ) -Φ(P ) 1 -Φ(0) .
The function Φ is strictly increasing, as it is the cumulative distributive function of law N (Eg i , p i ) 2 ). Then, the derivative of function c i (U ) is strictly positive, and c i (U ) is strictly increasing. Intuitively, the more servers are turned on on a data center, the higher is the ratio of brown power consumption of this data center.For sake of simplicity, we denote P i (U ), the power consumption corresponding to U servers on on data center DC i . Function P i is clearly strictly increasing.

We demonstrate now that the local optimality of Algorithm 2 can be deduced from this property. We consider here the location of servers to turn on, and not the possible transfers. Let (U opt i ) 1≤i≤M be the optimal choice for total brown power production, and (U alg i ) 1≤i≤M the decision of Algorithm 2. First denote that by hypothesis, we have 1≤i≤M U opt i = 1≤i≤M U alg i . Suppose that for some i and j, U opt i > U alg i and U opt j < U alg j . Consider the step of Algorithm 2 at which the last server was decided to be turned on on DC j . Let U i be the number of servers this algorithm had decided to turn on on DC i at this step. By definition of Algorithm 2, c j (P j (U

alg j -1)) ≤ c i (P i (U i )). As proven earlier, c i (P i (U i )) ≤ c i (P i (U alg i )) ≤ c i (P i (U opt i -1)). As (U opt i ) 1≤i≤M is optimal, then c i (P i (U i )) = c i (P i (U alg i )) = c i (P i (U opt i - 1
)) and as c i and P i are strictly increasing,

U alg i = U opt i -1. Thus, c j (P j (U alg j -1)) = c i (P i (U opt i - 1
)) and so, the decision to turn on a last server on DC i or DC j does not impact the expected brown power consumption.

As this property holds for all possible differences between (U opt i ) 1≤i≤M and (U alg i ) 1≤i≤M , we can conclude that both selections have the same expected brown power consumption and that (U alg i ) 1≤i≤M is optimal.

Theorem 2. Algorithm 3 is locally optimal with respect (N (Eg i , p i ) 2 )) 1≤i≤M .

Proof. This demonstration is very similar to the previous one, so we use similar intermediate results. Let g i (P ) = Ec i (P )-Ec i (P +P OF F -P s ). Then, d dP g i (P ) =

Φ(P )-Φ(P +P OF F -Ps) 1-Φ(0)
, g i (P ) is strictly increasing. Now, let (U opt i ) 1≤i≤M be the optimal choice for total brown power production, and (U alg i ) 1≤i≤M the decision of Algorithm 3. Suppose that for some i and j, U opt i > U alg i and U opt j < U alg j . As in previous proof, we denote P i (U ) the power consumption on data center DC i corresponding to U servers on.

Consider the step of Algorithm 3 at which the last server was decided to be turned off on DC i . Let U j be the number of servers the algorithm had decided to turn on on DC j at this step. By definition of Algorithm 3, g j (P j (U alg j + 1)) ≥ g i (P i (U i )). We have g i (P i (U i )) ≥ g i (P i (U alg i )) ≥ g i (P i (U opt i + 1)). By optimality, we obtain g i (P i (U i )) = g i (P i (U alg i )) = g i (P i (U opt i + 1)). As g i (P i (P )) is strictly increasing, U alg i = U opt i + 1 and the decision to turn off a last server on DC i or DC j does not impact the expected brown power consumption.

As in the previous proof, we obtain that (U alg i ) 1≤i≤M is optimal.

Theorem 3. Algorithm 4 is locally optimal with respect (N (Eg i , p i ) 2 )) 1≤i≤M .

Proof. Let (U opt i ) 1≤i≤M be the optimal choice for total brown power production, and (U alg i ) 1≤i≤M the decision of Algorithm 4. Suppose that for some i and j, U opt i > U alg i and U opt j < U alg j . As previously, P i (U ) is the power consumption on data center DC i for U servers on.

By definition of Algorithm 4, c i (P i (U alg i )) ≥ g j (P j (U alg j )). Moreover, we know

g i (P i (U opt i )) = c i (P i (U opt i - 1
)) ≥ c i (P i (U alg i )) and g j (P j (U opt j + 1)) ≤ g j (P j (U alg j )). Thus, g i (P i (U opt i )) ≥ c j (P j (U opt j )), U opt i -1 = U alg i and U opt j + 1 = U alg j . The decision to turn on a last server on DC i and DC j does not impact the expected brown power consumption.

By induction, we obtain that (U alg i ) 1≤i≤M is optimal.

We have proven that our algorithms are locally optimal, it means that there are optimal only regarding the current time slot. It is clear that the only point in the model that impacts this locality is the switching ON/OFF costs. Without these costs, the power consumption on current time slot does not depend on previous time slot. Thus, we obtain the following theorems. Theorem 4. Algorithm 2 is optimal without switching ON/OFF costs, with respect (N (Eg i , p i ) 2 )) 1≤i≤M . Theorem 5. Algorithm 3 is optimal without switching ON/OFF costs, with respect (N (Eg i , p i ) 2 )) 1≤i≤M . Theorem 6. Algorithm 4 is optimal without switching ON/OFF costs, with respect (N (Eg i , p i ) 2 )) 1≤i≤M .

5 Computing the optimal

Simulation overview

The whole cloud implementation model is described in Figure 2. We simulate data centers using the DCSim (Data Center Simulator) discrete-event M&S tool [START_REF] Tighe | DCSim: A data centre simulation tool for evaluating dynamic virtualized resource management[END_REF]. This simulator provides the power consumption of each data center as a function of time.

We implement our algorithm in an ad-hoc way using the Java language into a simulated cloud controller. This simulator receives as inputs the green power production for each data center as well as the cloud workload (i.e. the number of VMs to deploy on the cloud for each time slot). Based on these inputs and on SAGITTA's algorithms, the controller generates for each server the VM allocation and the instructions which are directly sent to the simulated data center manager.

Note that we do not explicitly model the brown power production as we assume it to be infinite (at the scale of the cloud). We also ignore the telecommunication network as we assume it to have negligible impact on the system functioning (we assume network to be oversized for our scenario), and an almost constant power consumption over time if no energy-saving technique is applied [START_REF] Orgerie | A Survey on Techniques for Improving the Energy Efficiency of Large-Scale Distributed Systems[END_REF]. Finally, we do not take into account here the energy consumed by the data centers' cooling systems.

In order to perform the simulations, we connect all these heterogeneous models using the MECSYCO (Multi-agent Environment for Complex-SYstem-COsimulation) M&S platform [START_REF] Camus | Hybrid Co-simulation of FMUs using DEV&DESS in MECSYCO[END_REF][START_REF] Camus | MECSYCO: a Multi-agent DEVS Wrapping Platform for the Co-simulation of Complex Systems[END_REF] which is based on the DEVS (Discrete-EVent System specification) formalism [START_REF] Zeigler | Theory of Modeling and Simulation: Integrating Discrete Event and Continuous Complex Dynamic Systems[END_REF]. We have defined a DEVS interface for DC-Sim, and implemented it in MECSYCO.

Data center simulation

Our cloud consists in five homogeneous data centers composed of five clusters. Each of these clusters contains 80 homogeneous nodes, so overall, the cloud comprises a total of 400 servers. The characteristics of each server are based on the Taurus servers of the French experimental testbed Grid'5000 4 . These Taurus servers are equipped with 2 Intel Xeon E5-2630 CPU with 6 cores each, 32GB memory, 598GB storage and a 10 Gigabit Ethernet interface. In order to determine the power consumption of each node, we implement the power model of [START_REF] Li | Opportunistic Scheduling in Clouds Partially Powered by Green Energy[END_REF], which is based on real measurements made on Taurus nodes. These measurements notably state that a Taurus server consumes 8W when powered OFF, 97W when idle, and 220W at 100% CPU load (i.e. P s = 220W for our algorithm).

Within this cloud, we deploy homogeneous VMs that are equivalent to the Amazon EC2 "large" flavor5 -i.e. each VM requires 4 CPU cores, 8GB memory and 80GB storage. Hence, three VMs can be simultaneously running on one node. For the sake of simplicity, we assume that, when deployed, a VM always works at full capacity. In the same way, we neglect the delays for the VM to start/stop. All the VMs are automatically deleted at the end of each time slot. A time slot lasts five minutes in our simulations.

Green power production

In order to feed the controller during the simulation, we use real recordings of green power production and real workload traces. We get the former from the Photovolta project6 of the University of Nantes. These recordings correspond to the power produced by a single Sanyo HIP-240-HDE4 photovoltaic panel updated every five minutes over one week. In order to have heterogeneous trajectories between data centers (and thus to represent solar irradiance differences between sites spread across a country), we select recordings starting at different dates, namely: 4th of September 2016, 2nd of February 2014, 8th of June 2014, 22nd of June 2015 and 21st of December 2014. We consider here that 30 photovoltaic panels (for a surface of 165.6m 2 ) are installed at each data center. Then we scale these photovoltaic signals accordingly.

Workload input

We use the normalized ClarkNet HTTP trace of [START_REF] Tighe | DCSim: A data centre simulation tool for evaluating dynamic virtualized resource management[END_REF] for our cloud workload, shown in Figure 3. This workload trace spans over one week. We scale this workload to 98% of the cloud total capacity (i.e. the maximal workload peak represents 98% of the total computing capacity of the cloud). The trace peaks are synchronized with the photovoltaic signal ones to have proper day-night cycles in our simulation.

Algorithm implementation

The controller implementing our SAGITTA approach is run at each time slot (i.e. each five minutes). It saves all the data received from the green power sources during the current day. The controller computes at each time slot the standard deviations p i (t) using this history. It computes each expected green power production Eg i (t) by averaging a reference green power production trajectory (the Photovolta project recording of the 20th of August 2013 in our case which is the day with the best yield) scaled according to the last green power production received from i. More precisely, we denote P ref (t) the green power production at corresponding hour the day of reference (see Figure 4). We obtain the following formula:

Eg i (t) = max 0, P V i (t -1) + P ref (t) -P ref (t -1) 2 .
Fig. 4. Expected green power production computation for a time slot from t to t + 1 from [START_REF] Camus | A stochastic approach for optimizing green energy consumption in distributed clouds[END_REF].

Note that we consider with this formula that Eg i (t) is equal to the average between the green power production received at t -1 and the one estimated at t. Thus, we take into account that the green power trajectory changes during the time slot, and not only at its beginning.

In order to minimize the number of ON/OFF cycles for the servers, the controller fills in priority the hosts already ON. Therefore, from a time slot to the next one, the controller keeps trace of the employed servers.

Simulated approaches

We compare SAGITTA performance against two Round-Robin inspired algorithms:

-Round-Robin-VM distributes the VMs fairly between the data centers regardless their green power production. -Round-Robin-DC starts filling with VMs the first data center (in an arbitrary predefined order). If this data center becomes full, the algorithm starts using the next one, and so on.

Like SAGITTA, these two algorithms employ in priority the nodes already ON.

As the performance of Round-Robin-DC strongly depends on the order of the data centers, we test two opposite configurations corresponding to the best and the worst possible contexts. To define these contexts, we sort the photovoltaic traces according to the total amount of green energy they provide. We assign then the traces to the data centers following this order. The best context corresponds to the case where the photovoltaic traces are sorted in a decreasing order. Thus, the first data center (i.e. the one filled in priority) will be supplied by the best photovoltaic power trajectory. The worst context corresponds then to the case where the traces are sorted in an increasing order (i.e. the data center with the worst green power supply will always be filled first).

Results

Based on the simulation framework described in the previous section, several experiments were run to validate our proposed approach. The simulations are performed in order to compare SAGITTA against state-of-the-art approaches (Section 7.1). The influence of the green energy forecast is analyzed (Section 7.2). Various green production scenarios are studied to estimate the impact of green energy location on SAGITTA's performance (Section 7.3). The scalability of SAGITTA is evaluated by increasing the number of data centers (Section 7.4). SAGITTA is compared to the optimal approach (Section 7.5). Finally, we study the exactness of the green power production forecast (Section 7.6).

Energy consumption with SAGITTA vs. round-robin approaches

The second set of simulation integrates the switching ON/OFF costs and estimates their impact on the algorithms' energy consumption to reflect this point. Following the data collected by [START_REF] Rais | Impact of Shutdown Techniques for Energy-Efficient Cloud Data Centers[END_REF] on the Taurus cluster, we add a static energy consumption penalty of 5.28 Wh (consumed in 150 seconds) for each switch-ON command, and 0.56 Wh (consumed in 10 seconds) for each switch-OFF command sent. As shown in Table 2, even when considering these penalties, simulations show that SAGITTA performs better than the other solutions with a difference of at least 10%. Figure 5 shows the power consumption over time of each data center in the simulated cloud using SAGITTA. This figure also shows the number of transfers made by Algorithm 4 -a negative (respectively positive) value meaning that the algorithm switches off (respectively on) hosts. This plot highlights the usefulness of the transfer algorithm. For instance, at time 173,700 s. which corresponds to early morning, DC 2 starts producing green energy slightly earlier than DC 0. SAGITTA takes then advantage of this situation by performing 19 transfers from DC 0 to DC 2. Transfers are highly correlated with discontinuities in the green power production trajectories. Thus, the transfer decision may enable adapting the VM allocation, and consequently the energy consumption, to unforeseen increases and decreases of the green power production. In the absence of transfer, the switch on and off decisions enable adapting the DC workload to their green power production -i.e. the data centers with higher power production are generally more used than the others.

For the sake of simplicity, in the following, we will consider the best case for the Round-Robin-DC algorithm (with data centers ranked by their overall green energy production). All the simulations in the next sections also include the switching ON/OFF costs.

Influence of the green energy forecast

One basis of the SAGITTA approach is the green energy production forecast. The value Eg i (t), namely the expected PV production in DC i at time slot t is computed regarding the electricity production at time slot t -1. This approach permits a simple computation for the value Eg i (t) to parametrize the probability law of green energy production. However, this formula estimates the electricity production regarding only the previous time slot, despite of the high volatility of solar energy. We experiment in this section an evaluation of Eg i (t) on a sliding window of PV production values. We target here the optimal size of the window, and the weight to give to the values of the different time slots of the window.

We propose several solutions to determine Eg i (t) on a sliding window of size s. For the sake of simplicity, we denote g i (t) = P V i (t) -P ref (t), with P ref (t) the daily production at same hour, the day of reference. We then make a weighted average value of values g i (t), with weight p i :

Egi(t) = max   0, P Vi(t -1) + s k=1 (g i (t-k)×p s-k ) s k=1 p k + P ref (t) 2   .
The first variant CST1 uses constant weigths p k = 1 for recent and old values. In the second variant ADD1, the values of p k increase linearly:

p k = k + 1.
Finally, the values of p k are multiplied by 2 at each step in PROD1: p k = 2 k . In these variants, the computation includes values corresponding to the night, when P V i (t) and P ref (t) are both null. This impacts the estimation with useless values. Then, in variants CST2, ADD2 and PROD2, all values g i (t) corresponding to P ref (t) = 0 are removed from the computation. Results of these computations are detailed in Figure 6.

The first unexpected result is the very low values of the optimal size of the sliding window. Regardless of the variant, the best size of the window is always 2, with a slight reduction of the brown energy consumed. The good performance of algorithms PROD1 and PROD2 can be related to the large weight given to the earliest production values in the computation. The weight to early values has indeed a large impact the variants' performance.

Influence of green energy production

Cloud providers need to adequately dimension their on-site photovoltaic panels (PVs). This issue involves a trade-off between the financial cost of installing and operating PVs, and the financial gains they are bringing in terms of green energy produced and thus, electricity that has not to be bought from the regular grid. We perform a set of experiments to determine the influence of green energy production on SAGITTA performance. As shown in Figure 7, the number of PVs varies per data center and the total brown power consumption is recorded over one week. We can see that, as soon as green energy is available, SAGITTA consumes clearly less brown energy than the other approaches.

Figure 7 also shows that up to about 25 photovoltaic panels, the brown energy consumption curves have a steeper slope, leading to higher gains per photovoltaic panels. For more than 25 photovoltaic panels, the energy gains are lower per added panel. When reaching 45 panels, the green energy production exceeds the total energy consumption of the data center (represented by the case with 0 panel). However, this production is concentrated during the day (as shown in Figure 5), whereas the workload, and consequently the energy consumption, spans over the day and the night. Thus, when reaching a number of photovoltaic panels whose production covers most of the Cloud energy consumption during daylight, adding panels can only save the energy consumption peaks at the beginning and the end of the day (when panels produce less energy), and their buying cost can thus exceed the monetary gains they generate.

Scalability of SAGITTA

In order to check if the SAGITTA's energy savings scale up, we simulate the power consumption of distributed clouds with a larger number of data centers. For these different clouds, we progressively increase the number of data centers, and so the number of green power sources (still taken from the Photovolta project), while maintaining the same total number of nodes (and so an unchanged input workload). The total photovoltaic energy production is also kept as steady as possible by progressively decreasing the number of photovoltaic panels per data centers. Yet we decided not to consider fractions of panels, so the number of panels slightly varies between the scenarios to keep whole numbers. The compositions of these clouds are summed up in Table 3.

As shown in Figure 8, the simulation results discloses that SAGITTA scales up: it maintains its energy gains in larger clouds, and always consumes less brown energy than the other approaches. From a computing time point of view, in our simulation environment, it takes 9 seconds to execute SAGITTA over the whole workload trace (representing one week) for the case with 5 data centers, and 28 seconds for the case with 40 data centers. While this computing time is increased by a factor of 3 (when increasing the data center number by a factor of 8), it still remains inconsequential for the scalability of SAGITTA.

Comparison with the optimal

We compare SAGITTA with the optimal solution when considering ON/OFF switches penalties. In order to compute this optimal solution, we implement the algorithm 5 in python. Due to the high level of computing resources required, we parallelize and distribute the first forall loop of the algorithm. For each time slot, we use 30 hosts of the Grid'5000 platform to run in parallel the algorithm. Even with this optimization, we only were able to compute the optimal solution for a cloud composed of 5 data-centers of 20 hosts. The algorithm took about 2 weeks to perform 1 week of simulation.

The results are shown in Tables 4 and5. We can see that:

-SAGITTA is very close to the optimal solution although it requires way lesser computing resources than the optimal algorithm. -SAGITTA still performs better than the other two algorithms. 7.6 Exactness of the green power production forecast

The Table 6 shows the difference between the green power production predicted by SAGITTA and the actual ones. The Root-Mean-Square Deviation (RMSD) and the Normalized RMSD (NRMSD) are given in order to allow comparing SAGITTA with other future green power prediction models. We can see that SAGITTA makes an average error of only 311.3W, which corresponds by comparison to the power consumed by 1.4 working hosts. This is a relatively small error when considering that the green production of each DC ranges from approximately 0W to 25,000W. This demonstrate that the prediction model of SAGITTA is accurate.

Conclusion

In this chapter, we consider the problem of optimizing the green energy consumption of a geographically distributed cloud equipped with on-site photovoltaic panels. We tackle this challenge by distributing the cloud workload (composed of virtual machines) among the different data-centers.

We propose here a new version of the SAGITTA (a Stochastic Approach for Green consumption In disTributed daTA centers) approach which is based on this strategy. SAGITTA relies on a stochastic modeling of the expected green energy production in order to adequately allocate virtual machines to the data centers. The approach also switches off unused servers to save energy. In the new version, SAGITTA now natively takes into account of the energy costs arising from these on/off switches. This extension of SAGITTA is more robust and offers slightly better results.

We have proven in this paper that SAGITTA is locally optimal -i.e. that SAGITTA is optimal regarding the current time slot. In order to evaluate the performance of SAGITTA when considering the on/off switches costs, we also proposed a dynamic programming algorithm for computing the optimal energy consumption of the whole experiment. We conducted a simulation-based evaluation using real workload traces, wattmeter measurements on testbed servers, and real production traces from photovoltaic panels. We compared SAGITTA with two round-robin algorithms which do not consider the green energy production for allocating virtual machines in the cloud. The results show that SAGITTA can allocate virtual machines in a more energy-efficient way than these traditional approaches. Moreover, SAGITTA exhibits good results in term of brown energy consumption with a difference of only 5.2% with the optimal solution computed by our dynamic programming algorithm. The simulations also show that SAGITTA can adapt to different green energy production patterns as it outperforms traditional approaches in all these cases. Finally, we shown that SAGITTA can smoothly scale with the number of data centers belonging to the cloud.

In future work, we plan to extend SAGITTA by integrating the ability to dynamically migrate virtual machines and the energy production from one site to another. We also want to adapt SAGITTA to continuous (i.e. non time-slotted) workloads. Finally we want to integrate in our simulation the impact of network devices on the energy consumption.

Fig. 1 .

 1 Fig. 1. Considered cloud model from [3].

  ) + +; Pj+ = PON + Ps Recompute cj; end while

2 .

 2 Find l such that c l = min 1≤j≤M cj; U k (t) --; U l (t) + +; Recompute g k and P k ; Recompute c l and P l ; Let first evaluate the derivative function of Ec i (P ).

ddP

  Ec i (P ) = Φ(P )-Φ(0

Fig. 2 .

 2 Fig. 2. Bloc diagram view of the cloud model from [3].

Fig. 3 .

 3 Fig.3. The input workload used in the experiments from[START_REF] Camus | A stochastic approach for optimizing green energy consumption in distributed clouds[END_REF].

Fig. 5 .

 5 Fig. 5. Power consumption per data center with SAGITTA and transfer decisions.

Fig. 6 .

 6 Fig.6. Influence of Egi estimation from[START_REF] Camus | A stochastic approach for optimizing green energy consumption in distributed clouds[END_REF].

Fig. 7 .

 7 Fig. 7. Influence of green energy production on brown energy consumption from [3].

Fig. 8 .

 8 Fig. 8. Brown energy consumption of SAGITTA with increasing number of data centers.

Table 1 .

 1 Table of Notations

	Notation	Definition
	Constants
	M	Number of data centers
	DCi	Data center number i
	Si	Number of servers in data center i

C Maximum number of VMs in parallel on a server Ps Maximum power consumption of a server Variables N (t) Number of incoming VMs for time slot t (input) Ui(t) Number of machines ON at current time slot on data center i (output) Gi(t)

Table 2 .

 2 Total cumulative brown energy consumption.

	SAGITTA Round-Robin-VM Round-Robin-DC
	Best 2.77 MWh	3.38 MWh	3.02 MWh
	Worst 2.77 MWh	3.38 MWh	4.4 MWh

Table 3 .

 3 The considered cloud scenarios with increasing number of data centers.

	Number of data centers	5 10 15 20 25 30 35 40
	Total number of nodes	400 400 400 400 400 400 400 400
	Number of PV per data centers 30 14 9 7 6 5 4 3

Table 4 .

 4 Total cumulative energy consumptions over one week when considering ON/OFF penalties.

	optimal SAGITTA Round-Robin-VM Round-Robin-DC
	Best 649,259Wh 666,238Wh	822,204Wh	733,304Wh
	Worst 649,259Wh 666,238Wh	822,204Wh	1,086,626Wh

Table 5 .

 5 Percentage of cumulative energy consumptions over the optimal when considering ON/OFF penalties.

		SAGITTA Round-Robin-VM Round-Robin-DC
	Best	5.2%	26.6%	12.9%
	Worst	5.2%	26.6%	67.4%

Table 6 .

 6 Differences between the green power production predicted by SAGITTA and the actual ones.

		DC1	DC2	DC3	DC4	DC5 Average
	Average	243.22W 332.96W 602.51W 303.71 74.44W 311.37W
	Standard deviation 618.96W 884.74W 1456.11W 863.1W 270.21W 921.97W
	RMSD	665.03W 945.32W 1575.84W 914.97W 280.27W 973.13W
	NRMSD	2.66%	3.72%	6.22%	4.66%	2.14%	3.83%

https://www.grid5000.fr

https://aws.amazon.com/ec2/

http://photovolta2.univ-nantes.fr

We propose in this section an optimal algorithm that allows to compute the minimal power consumption for the whole experiment, knowing the workload trace and the green power production. This algorithm is then employed to evaluate the performance of our algorithms in the simulations. Obviously it cannot be used to allocate VMs, as it is based on complete data knowledge.

This algorithm (Algorithm 5) is a dynamic programming algorithm based on the concept of configurations. We consider as a configuration, a possible state of the platform, described by the number of servers on on each data center. More formally, configuration c at time slot t is defined as c = (k 1 , . . . , k M ), where k i is the number of servers on at time slot t on data center DC i We defined as P (c, t) the minimal power consumption of a schedule for the t first time slots, with k i servers on on DC i for each i at time slot t.

We denote L(t) the set of pairs (c, P (c, t)), for all the possible configurations for time slot t. Notice that the total number of servers on during a time slot is directly related to the workload, thus i k i = N (t)/C . As the complexity of this algorithm directly depends on the size of L(t), this property permits to strongly reduce the execution time of experiments simulating this algorithm.

This algorithm computes recursively the set L(t) for each time slot t, based on L(t -1). More precisely, it first computes the possible configurations, that is the set of tuples c = (k 1 , ..., k M ) such that for all i, k i ≤ S i and i k i = N (t)/C . Then, for each of these tuples, it computes P (c, t) using L(t -1). To that end, it considers each possible configuration c at time slot t -1 and computes the power consumption at time slot t, based on the number of servers to turn on

Acknowledgments

This work has been supported by the Inria exploratory research project COSMIC (Coordinated Optimization of SMart grIds and Clouds).

Algorithm 5: Optimal algorithm L(t): list of values (k1, ..., kM , P ) where ki is the number of servers ON on DCi at current time slot and P the lowest brown power consumed with this final configuration; for 1 ≤ t ≤ tmax do forall j1, j2, • • • , jM such that ∀k, 0 ≤ ji ≤ Si and i ji = Nt/C do P = +∞; forall (k1, ..., kM , Pt-1) ∈ L(t -1) do if Pt-1 ≤ P then and off during this time slot and the power consumption for the servers on. When adding to P (c , t -1), we obtain the minimum power consumption for t time slots with configuration c at time t -1 and c at time t. We can then take the minimum for all (c , P (c , t -1)) ∈ L(t -1) and we obtain P (c, t). L(0) is initialized with one unique tuple in the configuration c, k i = 0 for all i and P (c, 0) = 0, this means all servers off, and no power consumed yet.

Validation framework

We evaluate our algorithm through a modeling and simulation (M&S) process. In the following, we first give an overview of the whole cloud implementation model (Section 6.1). We then detail our implementation of the data centers (Section 6.2), of the green power production (Section 6.3), of the cloud workload (Section 6.4), of the algorithm implementation (Section 6.5), and the different simulations performed (Section 6.6).