Yanwei Zhang
email: yzhang82@eecs.utk.edu

Yefu Wang
email: xwang@ece.osu.edu

Xiaorui Wang

GreenWare: Greening Cloud-Scale Data Centers to Maximize the Use of Renewable Energy

To reduce the negative environmental implications (e.g., CO2 emission and global warming) caused by the rapidly increasing energy consumption, many Internet service operators have started taking various initiatives to operate their cloud-scale data centers with renewable energy. Unfortunately, due to the intermittent nature of renewable energy sources such as wind turbines and solar panels, currently renewable energy is often more expensive than brown energy that is produced with conventional fossil-based fuel. As a result, utilizing renewable energy may impose a considerable pressure on the sometimes stringent operation budgets of Internet service operators. Therefore, two key questions faced by many cloud-service operators are 1) how to dynamically distribute service requests among data centers in different geographical locations, based on the local weather conditions, to maximize the use of renewable energy, and 2) how to do that within their allowed operation budgets. In this paper, we propose GreenWare, a novel middleware system that conducts dynamic request dispatching to maximize the percentage of renewable energy used to power a network of distributed data centers, subject to the desired cost budget of the Internet service operator. Our solution first explicitly models the intermittent generation of renewable energy, e.g., wind power and solar power, with respect to varying weather conditions in the geographical location of each data center. We then formulate the core objective of GreenWare as a constrained optimization problem and propose an efficient request dispatching algorithm based on linear-fractional programming (LFP). We evaluate GreenWare with realworld weather, electricity price, and workload traces. Our experimental results show that GreenWare can significantly increase the use of renewable energy in cloud-scale data centers without violating the desired cost budget, despite the intermittent supplies of renewable energy in different locations and time-varying electricity prices and workloads.

Introduction

Recent years have seen the rapid growth of large and geographically distributed data centers deployed by Internet service operators to support various services such as cloud computing. As an effort to deal with the increasingly severe global energy crisis, reducing the high energy consumption of those cloud-scale data centers has become a serious challenge. For example, some cloud-service data centers are termed as mega data centers, because they host hundreds of thousands of servers and can draw tens to hundreds of megawatts of power at peak [START_REF] Greenberg | The cost of a cloud: research problems in data center networks[END_REF]. It has also been reported that in a conservative estimation, Google hosts more than 500,000 servers in its data centers distributed in different locations and consumes at least 6.3 × 10 5 MWh in total annually [START_REF] Qureshi | Cutting the electric bill for internet-scale systems[END_REF]. Therefore, minimizing the energy consumption of cloud-scale data centers has recently received a lot of research attention (e.g., [START_REF] Elnozahy | Energy-efficient server clusters[END_REF][START_REF] Chase | Managing energy and server resources in hosting centers[END_REF][START_REF] Le | Managing the cost, energy consumption, and carbon footprint of internet services[END_REF][START_REF] Ahmad | Joint optimization of idle and cooling power in data centers while maintaining response time[END_REF][START_REF] Verma | Server workload analysis for power minimization using consolidation[END_REF][START_REF] Chen | Energy-aware server provisioning and load dispatching for connection-intensive internet services[END_REF]).

In addition to high electricity bills, the enormous energy consumption of cloud-scale data centers can also lead to negative environmental implications (e.g., CO 2 emission and global warming), due to their large carbon footprints. The reason is that most of the produced electricity around the world comes from carbon-intensive approaches, e.g., coal burning [START_REF] Le | Managing the cost, energy consumption, and carbon footprint of internet services[END_REF]. Such energy produced with conventional fossil-based fuel is commonly referred to as brown energy. Therefore, to mitigate the negative environmental implications caused by the rapidly increasing energy consumption, many Internet service operators have started taking various initiatives to operate their cloud-scale data centers with renewable (or green) energy. In contrast to brown energy, green (or clean) energy is normally generated from renewable energy sources, such as wind turbines and solar panels, and is thus more environmentally friendly. For example, major Internet service operators, e.g., Google, Microsoft, and Yahoo!, have all started to increasingly power some of their data centers using renewable energy, and so reduce their dependence on brown energy [START_REF] Pistoia | Battery Operated Devices and Systems: From Portable Electronics to Industrial Products[END_REF][START_REF]Green House Data: Greening the data center[END_REF][START_REF] Thibodeau | Wind power data center project planned in urban area[END_REF]. Therefore, since data centers in different geographical locations may have different availabilities of renewable energy depending on the local weather conditions, it is important for cloudservice operators to dynamically distribute service requests among different data centers to maximize the use of renewable energy.

Unfortunately, due to the intermittent nature of renewable energy sources such as wind and sunlight, currently renewable energy can be often more expensive to produce than brown energy [START_REF]Dominion Virginia Power[END_REF][START_REF]Solar Power at Data Center Scale[END_REF]. While some data centers are trying to build their own wind farms or solar photovoltaic (PV) power plants, due to concerns such as expensive facility investments and management, many Internet service operators choose to work with professional renewable energy producers and utilize the green energy integrated into the power grid. For example, Google has recently purchased 20 years' worth of wind energy from an Iowa wind farm, which will be sufficient to power several of its data centers in Oklahoma [START_REF]Google Buys 20 Years' Worth of Wind Energy To Power Data centers[END_REF]. Google also invested $100 million in the Shepherds Flat Wind Farm in Oregon to generate 845 megawatts of green power, which will be sold directly to Southern California Edison's power grid. As a result of its higher production costs, renewable energy coming from the grid can be more expensive than brown energy. For example, the industrial electricity price for solar energy can be 16.14 cents per KWh in a sunny climate and 35.51 cents per KWh in a cloudy climate [START_REF]Solar Electricity Prices[END_REF]. In contrast, the wholesale brown energy price can be around 6 cents per KWh [START_REF] Qureshi | Cutting the electric bill for internet-scale systems[END_REF]. The Los Angeles Department of Water and Power also estimates that the extra cost for green energy is at least 3 cents per KWh [5]. Therefore, utilizing renewable energy may impose a considerable pressure on the sometimes stringent operation budgets of Internet service operators, as the electricity cost of operating data centers has become a significant portion, e.g., 20% or more of the monthly costs of those enterprises [START_REF] Greenberg | The cost of a cloud: research problems in data center networks[END_REF]. Hence, a key dilemma faced by many service operators is how to exploit renewable energy to the maximum degree that is allowed by their monthly operating budgets.

In this paper, we propose GreenWare, a novel middleware system that conducts dynamic request dispatching to maximize the percentage of renewable energy used to power a network of distributed data centers, subject to the desired cost budgets of Internet service operators. We first model the intermittent generation of renewable energy, i.e., wind power and solar power, with respect to the varying weather conditions in the geographical location of each data center. For example, the available wind power generated from wind turbines is modeled based on the ambient wind speed [START_REF] Patel | Power systems: Design, Analysis, and Operation[END_REF][START_REF]WindPower Program[END_REF], while the available solar power from solar plants is estimated by modeling the maximum power point on irradiance (i.e., solar energy per unit area of the solar panel's face) and temperature [START_REF] Li | Solarcore: Solar energy driven multi-core architecture power management[END_REF][START_REF] Sera | PV panel model based on datasheet values[END_REF]. Based on the models, we formulate the core objective of GreenWare as a constrained optimization problem, in which the constraints capture the Quality of Service (QoS, e.g., response time) requirements from customers, the intermittent availabilities of renewable energy in different locations, the peak power limit of each data center, and the monthly cost budget of the Internet service operator. We then transfer the optimization problem into a linear-fractional programming (LFP) formulation for an efficient request dispatching solution with a polynomial time average complexity.

Specifically, this paper makes the following major contributions:

-We propose a novel GreenWare middleware system in operating geographically distributed cloud-scale data centers. GreenWare dynamically dispatches incoming service requests among different data centers, based on the timevarying electricity prices and availabilities of renewable energy in their geographical locations, to maximize the use of renewable energy, while enforcing the monthly budget determined by the Internet service operator. -We explicitly model renewable energy generation, i.e., wind turbines and solar panels, with respect to the varying weather conditions in the geographical location of each data center. As a result, our solution can effectively handle the intermittent supplies of renewable energy. -We formulate the core objective of GreenWare as a constrained optimization problem and propose an efficient request dispatching solution based on LFP. -We evaluate GreenWare with real-world weather, electricity price, and workload traces. Our experimental results show that GreenWare can significantly reduce the dependence of cloud-scale data centers on fossil-fuel-based energy without violating the desired cost budget, despite the intermittent supplies of renewable energy and time-varying electricity prices and workloads.

The rest of the paper is organized as follows. Section 2 introduces the overall architecture of the proposed GreenWare middleware system. Section 3 presents the modeling and formulations of GreenWare. Section 4 discusses the simulation strategy. Section 5 evaluates GreenWare with real-world traces. Section 6 reviews the related work and Section 7 concludes the paper.

GreenWare Architecture

In this section, we provide a high-level description of the proposed GreenWare system. GreenWare dynamically conducts request dispatching among data centers in order to maximize the percentage of renewable energy used to power a network of distributed data centers, based on the time-varying electricity prices and availabilities of renewable energy in their geographical locations. In the meantime, GreenWare guarantees the desired QoS for customers and effectively maintains the electricity bill within a cost budget determined by the Internet service operators.

In this work, we assume that a network of distributed data centers share a common cost budget, which can be determined by the Internet service operator periodically in each budgeting period (e.g., a month). A local optimizer is assumed to be present in each single data center in the network to dynamically adjust the number of active servers to minimize the power consumption of the data center, while maintaining a desired level of QoS based on a QoS model detailed in Section 3.2. We also assume that the short-term weather conditions (e.g., in one hour) and the configurations of wind turbines and solar panels of each data center are available. As shown in Figure 1, GreenWare is a centralized system that manages a data center network for maximizing the use of renewable energy within the cost budget. While such a centralized architecture is commonly used in the management of data center networks [START_REF] Le | Managing the cost, energy consumption, and carbon footprint of internet services[END_REF][START_REF] Rao | Minimizing electricity cost: optimization of distributed internet data centers in a multi-electricity-market environment[END_REF][START_REF] Qureshi | Cutting the electric bill for internet-scale systems[END_REF], GreenWare can be extended to work in a hierarchical way, which is our future work. Similar to [START_REF] Ahmad | Joint optimization of idle and cooling power in data centers while maintaining response time[END_REF][START_REF] Liu | Greening geograhpical load balancing[END_REF][START_REF] Zhang | Capping the electricity cost of cloud-scale data centers with impacts on power markets[END_REF], we use one month as the budgeting period and one hour as the period for GreenWare to be invoked and conduct the request dispatching operation. In every invocation period, GreenWare performs three steps: First, Green-Ware computes the hourly budget based on the monthly cost budget from the service operator and the electricity cost already consumed in the previous invocation periods, as well as the observations of the workload's historical behaviors in the same hours in the past (e.g., last two weeks) as discussed in Section 4.3. Second, based on the time-varying electricity prices and availability of renewable energy at each data center, with respect to the varying weather conditions in their geographical location (e.g., irradiance, temperature, and wind speed), GreenWare runs the optimization algorithm in Section 3 to compute the desired request dispatching (e.g., the fraction of workload allocated to each data center) such that (1) the overall percentage of renewable energy used to power a network of distributed data centers is maximized within budget constraints; (2) the total electricity cost is below the budget of the current hour; and (3) the application-level QoS (e.g., desired response time) for customers is guaranteed. Third, GreenWare redirects the incoming requests among data centers based on the determined request dispatching in Step (2), using the dynamic request routing mechanism already deployed in cloud-scale data center networks. Note that dynamic request routing has already been implemented by many Internet service operators to map requests to servers, for the purposes of customer QoS guarantees and fault-tolerance [START_REF] Qureshi | Cutting the electric bill for internet-scale systems[END_REF].

Design Methodology of GreenWare

In this section, we first present the problem formulation of the optimization objective of GreenWare. We then introduce the adopted performance and server power models, as well as the wind power model and solar power model. Finally, we discuss our request dispatching solution. Note that we focus mainly on wind power and solar power in this work because there exists meteorological data [START_REF]Measurement and Instrumentation data center[END_REF] for us to simulate their intermittent availabilities in distributed data centers. GreenWare can be applied to other types of renewable energy, such as hydro-electric and geothermal, if their corresponding meteorological data is also available.

Problem Formulation

We first introduce the following notation. N data centers are operated in a cloud-scale data-center network. The i th data center consumes pW i kilowatts of wind energy, pS i kilowatts of solar energy and pB i kilowatts of brown energy, respectively. The total power consumption p i (i.e., p i = pW i + pS i + pB i ) of the i th data center should not exceed the peak power limit P s i of the data center. The intermittent availabilities of the renewable energy in the local power market of the i th data center are denoted as P W i and P S i . In particular, P W i and P S i are the estimated wind power output from the wind farm and the maximum solar power output from the solar plant, respectively. The corresponding wind farm and solar plant are assumed to be the renewable energy sources for the local power market of the i th data center. P rW i , P rW i and P rB i are the current electricity prices of the three types of energy from the power market of the i th data center, respectively. The whole system has an incoming workload of λ requests per hour. Our algorithm allocates the i th data center with a workload of λ i requests per hour to maximize the percentage of renewable energy used, depending on the wind and solar power models based on local weather conditions (presented in Sections 3.3 and 3.4), within the allocated cost budget Cs. The average response time of the i th data center is R i and the corresponding response time set point is Rs i .

Given a workload of λ requests per hour, the optimization goal is to dynamically choose a request dispatching strategy such that the i th data center is assigned λ i requests to maximally use renewable energy to power the data center network within the cost budget. Specifically, in order to maximize the overall renewable energy usage of all the N data centers, x i percentage of wind power and y i percentage of solar power out of the total power consumption p i by the i th data center will have to be determined. Then, z i percentage of the total power consumption is supplemented in the form of brown energy. It is clear that z i = 1 -x i -y i . In summary, the optimization problem can be expressed as follows. Problem 1:

M aximize : N i=1 (pW i + pS i ) N i=1 (pW i + pS i + pB i ) (1) subject to N i=1 λ i = λ (2)
λ i ≥ 0 (3)
R i ≤ Rs i (4) 0 ≤ pW i ≤ P W i (5) 0 ≤ pS i ≤ P S i (6) 0 ≤ pW i + pS i + pB i ≤ P s i (7) N i=1 (P rW i • pW i + P rS i • pS i + P rB i • pB i ) ≤ Cs (8)
Specifically, pW i , pS i , pB i , P W i , and P S i (in KW) will be numerically the same as energy (in KWh) since the invocation period used in this work is assumed to be one hour. In order to solve the optimization Problem 1, it is important to model the variables pW i , pS i and pB i as functions of λ i , x i and y i . It is clear that

pW i = x i • p i ; pS i = y i • p i ; pB i = z i • p i (9)
where

x i + y i + z i = 1.
Thus, in the following we first model the power consumption p i and the average response time R i with the request distribution rate λ i for the i th data center. We then model the availabilities of wind power and solar power, i.e., P W i and P S i , respectively, based on the weather condition of the i th data center, e.g., irradiance, temperature, and wind velocity. We discuss an efficient solution design for Problem 1 in Section 3.5.

Response Time and Power Models

Queueing theory is widely used to model the performance of a web server [START_REF] Ahmad | Joint optimization of idle and cooling power in data centers while maintaining response time[END_REF][START_REF] Bolch | Queueing Networks and Markov Chains[END_REF]. In this paper, we use the M/M/n queueing model in queueing theory [START_REF] Rao | Minimizing electricity cost: optimization of distributed internet data centers in a multi-electricity-market environment[END_REF] to model the response time for a data center. The average response time of the requests to a web server consists of two portions: (1) the average waiting time that the requests spend in a queue waiting to be serviced and (2) the service time, i.e., 1 µ , given the service rate µ of the data center. Specifically, the average waiting time for a data center with n active servers can be expressed as

1 n•µ-λ • P Q
, where P Q represents the probability that the incoming requests need to wait in a queue to be serviced. Furthermore, we assume that all the active servers will likely keep busy, i.e., running at close to 100% utilization, because a local optimizer running in each data center minimizes the number of active servers. Hence, without loss of generality, P Q is assumed to be 1, since all the active servers are assumed to be running at close to 100% utilization. The same assumption is used in existing solutions on electricity cost minimization for data centers [START_REF] Rao | Minimizing electricity cost: optimization of distributed internet data centers in a multi-electricity-market environment[END_REF]. Therefore, we have

R i = 1 µ i + 1 n i • µ i -λ i ( 10
)
where n i is the number of active servers and µ i is the average service rate of a single server, i.e., the number of requests the server is able to process in a unit time, in the i th data center .

As discussed in Section 2, we assume that a local optimizer runs in every data center and dynamically adjusts the number of active servers to provide a desired level of QoS (e.g., response time) with the least number of servers. As a result, given a request rate of λ i and a desired response time Rs i of the i th data center, the number of desired active servers n i can be derived from equation [START_REF]NYISO[END_REF]. Thus, we have p i = n i • sp i , where sp i is the average power consumption of a single server in the i th data center. Although the power consumption of a server is usually a function of the utilization of the server, we assume that sp i is constant because when the local optimizer minimizes the number of active servers, all the servers remaining active will likely run close to a 100% utilization. Thus, the utilization will be approximately the same. It is then clear that a linear server power model based on the incoming work rate λ i for the i th data center can be derived, i.e., p i = f (λ i ), where f (λ i ) is a linear function.

Wind Power Model

The number of wind turbine installations is rapidly growing worldwide. It is expected that the US can get 20% of its electricity from wind energy by the year 2030 [START_REF] Hohl | Wind Power for Data Centers[END_REF][START_REF] Petru | Modeling of wind turbines for power system studies[END_REF]. It has been shown that wind power generated by wind turbines in a wind farm can be modeled as a function of the actual wind speed [START_REF] Patel | Power systems: Design, Analysis, and Operation[END_REF][START_REF]WindPower Program[END_REF]. For example, the wind power output p wind by a single wind turbine, with respect to a wind speed of v, can be approximated as follows

p wind =    0 v < v in , v > v out p r • v-vin vr -vin v in < v < v r p r v r < v < v out
where v r , p r are the rated speed and power of the wind turbine and v in , v out are cut-in and cut-out wind speeds. Specifically, the cut-in speed is the wind speed at which the turbine first starts to rotate and generate power, e.g., a typical value between 3 and 4 meters per second; while the cut-out speed is employed by the braking system to bring the rotor to a standstill to eliminate the risk of damaging the turbine rotor due to the continuously rising wind speed, e.g., a cut-out speed of usually around 25 meters per second.

In the case of a large-scale wind power generation farm, e.g., one consisting of a large number m w of wind-turbines, the overall wind power output is estimated as the sum of the power output values sampled at different turbines for simplicity [START_REF] Kariniotakis | Wind power forecasting using advanced neural networks models[END_REF] P W = mw k=1 p k wind where p k wind is the power output from the k th wind turbine with respect to the wind speed v, with t05e assumption that the wind turbines have the same wind speed in the same wind farm.

Solar Power Model

The worldwide photovoltaic (PV) power capacity installation grows in a nearly exponential way, despite their relatively high cost [START_REF] Sera | PV panel model based on datasheet values[END_REF]. In this work, we model the solar power generated by solar plants with respect to the varying weather conditions, such as irradiance and temperature, based on a single diode equation [START_REF] Sera | PV panel model based on datasheet values[END_REF][START_REF] Paukshto | Invariance of single diode equation and its application[END_REF]. In particular, the single diode equation has been widely used to simulate the available electrical power generated from a single PV panel. Specifically, the resulting current-voltage characteristic of a PV panel is

i = I ph -I o • (e v+i•Rs ns •V th -1) - v + i • R s R sh ( 11
)
where I ph is the photo-generated current while I o is the dark saturation current with respect to the ambient weather pattern. Moreover, the single-diode model takes into account both the series and parallel (shunt) resistance of the PV panel, referred to as R s and R sh , respectively. V th is the junction thermal voltage, i.e., V th = k • T /q, where k is Boltzmann's constant, q is the charge of the electron and T is the ambient temperature. n s is the number of the solar cells in the PV panel connected in series, e.g., n s = 72 in BP-MSX 120 panels [START_REF]BP MSX 120 solar module[END_REF].

To show the solar power output from PV panels with respect to the varying weather conditions (e.g., irradiance and temperature), equation [START_REF]Solar Power at Data Center Scale[END_REF] can then be transformed as equation [START_REF]Google Buys 20 Years' Worth of Wind Energy To Power Data centers[END_REF] by including these two key factors, i.e., irradiance and temperature [START_REF] Sera | PV panel model based on datasheet values[END_REF]. In particular, it has been demonstrated that the dark saturation current of I o just varies with the ambient temperature T , independent on the irradiance condition G [START_REF] Sera | PV panel model based on datasheet values[END_REF][START_REF] Castaner | Modelling Photovoltaic Systems Using PSpice[END_REF]. Furthermore, for a high-quality solar cell, it typically has a low series resistance R s but a high parallel resistance R sh . As a result, the solar model in this work only takes into considerations the series resistance (i.e., R sh = ∞), which is consistent with the prior study [START_REF] Li | Solarcore: Solar energy driven multi-core architecture power management[END_REF]. We thus have the fact that I ph can be approximated by I sc for simplicity, where I sc is the short-circuit current. In particular, I sc is directly proportional to the irradiance as well as the ambient temperature. Thus, we have

i(G, T ) = I sc (G, T ) -I o (T ) • e v(G,T )+i(G,T )•Rs ns •V th (12)
where In particular, the solar power produced by a PV panel with respect to the varying weather conditions, based on the current-voltage characteristic shown as equation ( 11) is the product of the output voltage and current. Namely, p solar = v(G, T )•i(G, T ). It has been demonstrated that the power output p solar generated by a PV panel shows a unique maximum value under uniform irradiation and temperature [START_REF] Li | Solarcore: Solar energy driven multi-core architecture power management[END_REF][START_REF] Sera | PV panel model based on datasheet values[END_REF]. In order to achieve the maximum efficiency of solar plants, some researchers have already put efforts in extracting the maximum power point from solar plants [START_REF] Ding | A new method to determine the optimum load of a real solar cell using the lambert w-function[END_REF][START_REF] Kothari | Determination of optimum load for a solar cell[END_REF]. We thus estimate the solar power output by a PV panel as the maximal power value which can be extracted from the PV panel (referred to as mpp). Specifically, mpp is achieved with respect to an optimal load r mp and the corresponding current i mp [START_REF] Ding | A new method to determine the optimum load of a real solar cell using the lambert w-function[END_REF], where

I sc (G, T ) = G G0 •I sc •(1 + ki 100 •(T -T 0 )) and I o (T ) = I sc •(1 + ki 100 •(T -T 0 ))• e - Voc+kv •(T -T 0 ) ns•V th . G
r mp = R s + ns•V th Isc(G,T )+Io(T )-imp . Thus, mpp = i 2 mp • r mp .
The Lambert W -function method is then used to calculate the maximum power point mpp of the PV panel with respect to the varying weather conditions. We assume that there are m s PV panels installed in a large-scale solar plant. Thus, the overall solar power output by the solar plant is estimated as

P S = ms k=1 mpp k
where mpp k is the maximum power point from the k th PV panel with respect to the irradiance G and temperature T .

Problem Solution

Based on the analysis above, the optimization Problem 1 is a non-linear programming problem with both a non-linear objective function and non-linear constraints, with respect to decision variables of λ i , x i and y i . However, for a service operator, it is important to design an efficient solution in order to dynamically make decisions to green the data centers with acceptable runtime overheads. We thus transfer the non-linear optimization Problem 1 into a well-studied linearfractional programming formulation as in the form of Problem 2, which can be further transferred into a standard linear programming problem. Specifically, note that for the equations (9) with respect to pW i , pS i and pB i as discussed in Section 3.1, we can alternatively assume that among the λ i requests serviced by the i th data center, λ W i , λ S i and λ B i requests are serviced with wind energy, solar energy and brown energy, respectively. Thus, we can limit the decision variables for the optimization Problem 1 in (1 -8) to only workload-related variables of λ W i , λ S i and λ B i , instead of both workload-related variables (i.e., λ i ) and percentage variables (i.e., x i and y i ).

Since

λ i = λ W i + λ S i + λ B i , Problem 1 in (1 -8
) can be further transferred as follows. Problem 2:

M aximize : N i=1 f (λ W i + λ S i ) N i=1 f (λ W i + λ S i + λ B i ) (13)
subject to

N i=1 (λ W i + λ S i + λ B i ) = λ (14)
λ W i ≥ 0 ( 15
)
λ S i ≥ 0 (16)
λ B i ≥ 0 (17)
R i ≤ Rs i (18) 0 ≤ f (λ W i ) ≤ P W i (19) 0 ≤ f (λ S i ) ≤ P S i (20) 0 ≤ f (λ W i + λ S i + λ B i ) ≤ P s i (21) N i=1 (P rW i • f (λ W i ) + P rS i • f (λ S i ) + P rB i • f (λ B i )) ≤ Cs (22)
Specifically, f (λ W i ), f (λ S i ) and f (λ B i ) represent the amount of wind energy, solar energy and brown energy consumed in the i th data center, respectively. It is clear that f (λ W i ), f (λ S i ) and f (λ B i ) are linear functions as discussed in Section 3.2. Problem 2 is thus a specific case of linear-fractional programming problem with a fractional objective function and linear constraints. In order to solve the LFP-based optimization Problem 2, we leverage a standard technique discussed in [START_REF] Hillier | Introduction to Operations Research[END_REF] to transfer the problem in (13 -22) to a linear programming problem. The detailed transformation is not shown due to space limitations, but the steps can be found in [START_REF] Hillier | Introduction to Operations Research[END_REF]. In our system, we implement the proposed GreenWare middleware system based on the linprog solver in Matlab. In particular, linprog uses an simplex method, which has been proven to have a low complexity in practice [START_REF]The Running Time of the Simplex Method[END_REF].

Simulation Setup

We aim to use realistic parameters in our experimental setup. We design a simulator and use real-world weather data, Web request traces, as well as electricity price data from utility companies to evaluate the proposed GreenWare system. As discussed, GreenWare dynamically conducts request dispatching to maximize the percentage of renewable energy used to power a network of distributed data centers within the cost budget determined by the Internet service operator. These evaluations primarily target web server-based applications, which provide the request-response type of web services. Specifically, the setup simulates an Internet-scale data center network such as Google's data centers within the US.

Datacenter Parameters

In our evaluation, we simulate a large system composed of four geographically distributed data centers for an Internet service operator (e.g., Google). Accordingly, four different locations are assumed in the simulator, i.e., San Luis Valley in Colorado, Los Angeles in California, Oak Ridge in Tennessee and Lanai in Hawaii, which are the locations whose meteorological data are available in [START_REF]Measurement and Instrumentation data center[END_REF].

The power consumption profile of each server in the same location is assumed to be approximately the same, which is usually true when homogeneous servers and configurations are used in each data center [START_REF] Rao | Minimizing electricity cost: optimization of distributed internet data centers in a multi-electricity-market environment[END_REF][START_REF] Lin | Dynamic right-sizing for power-proportional data centers[END_REF]. Specifically, similar to a related study [START_REF] Li | Towards optimal electric demand management for internet data centers[END_REF], the server configuration in each location is respectively assumed to be as follows: Data Center 1 (2.0 GHz AMD Athlon processor), Data Center 2 (1.2 GHz Intel Pentium 4630 processor), Data Center 3 (2.9 GHz Intel Pentium D950 processor), and Data Center 4 (2.7 GHz AMD Athlon processor). Their power consumption is assumed to be 88.88, 34.10, 149.19, and 141.28 Watts and their processing capacity coefficients are estimated as 500, 300, 725, and 675 requests per second, respectively.

Renewable Energy Availability

To emulate the intermittent availabilities of renewable energy in the locations of different data centers, i.e., wind power and solar power, we use meteorological data from the Measurement and Instrumentation Data Center (MIDC) [START_REF]Measurement and Instrumentation data center[END_REF] of the National Renewable Energy Laboratory. A variety of meteorological data, including irradiances, temperature, and wind speed, is covered in those records from the MIDC. Moreover, prior studies have shown that the data from the MIDC is sufficiently accurate [START_REF] Li | Solarcore: Solar energy driven multi-core architecture power management[END_REF]. In particular, we use meteorological data from the four stations, e.g., Sun Spot One, Loyola Marymount University Rotating Shadowband Radiometer, Oak Ridge National Laboratory and La Ola Lanai, since they have consistent time periods with available meteorological data, beginning from June 1st, 2010 to June 30th, 2010. We further assume that there are 200 turbines installed in each wind farm and 10,000 solar panels installed in each solar plant to provide renewable energy to the local power utilities of the 4 data centers. In particular, BP-MSX 120 panels produced by British Petroleum are assumed to be used in the solar plants [START_REF]BP MSX 120 solar module[END_REF].

Specifically, based on the power models discussed in Sections 3.3 and 3.4, as well as the varying weather conditions obtained from MIDC, the available renewable energy of all the 4 data centers throughout the entire simulated month is demonstrated in Figures 2 and3. In particular, Figure 2 depicts the overall available wind energy of all the 4 data centers, while Figure 3 shows the overall available solar energy. As shown in these two figures, the available renewable energy shows a diurnal pattern. This is due to the fact that the local weather conditions have a nearly diurnal pattern.

Real-World Workload Traces

To build our workloads in the simulator, we use a trace of Internet traffic from Wikipedia.org [START_REF] Urdaneta | Wikipedia workload analysis for decentralized hosting[END_REF]. In particular, we use this tracefile with 2-month long data, which contains 10% of user requests that arrived at Wikipedia between October 1st, 2007 and November 30th, 2007. Figure 4 shows the hourly behavior of user requests in October and November, 2007. As illustrated in the figure, the users' behavior shows a very clear weekly pattern in visiting the Wikipedia website. Specifically, we take the 1-month long Wikipedia trace of November as the incoming workload in the simulator while using the October trace data to work as the historical observations of the workload to predict hourly cost budgets.

To do so, we maintain a history of the request arrival rate seen during each hour of the week over the past several weeks. We then calculate every averaged hourly workload weight of the whole week over the past several weeks as the hourly budget weight in the coming week. Based on experiments, we find that for this Wikipedia trace, a 2-week long history trace data can provide a reasonable prediction on hourly cost budgets. Note that more sophisticated prediction methods, such as [START_REF] Urgaonkar | Dynamic provisioning of multi-tier internet applications[END_REF], can also be integrated into our system. To make our evaluation more general, we also stress test GreenWare with another workload trace from the 1998 World Cup game, which includes the request data of 33 servers from 4 geographical locations. In particular, it records the incoming requests to all the servers with a granularity of 1 second from April 30th to July 26th, 1998.

Electricity Price Traces

To simulate the electricity price for the brown energy, we use the price trace from New York Independent System Operator (NYISO) [START_REF]NYISO[END_REF], since they have complete and accurate price data records. Specifically, we use the Day-Ahead price data from November 1st, 2007 to November 30th, 2007, which is consistent with the dates of the Wikipedia traces. We apply the price data from the four zones, including Capital, Central, Dunwoodie and Genesee to the 4 data centers in our simulation.

On the other hand, regarding the electricity price of renewable energy, it is usually true that renewable energy has a higher electricity price compared to brown energy [START_REF]Dominion Virginia Power[END_REF]5], due to the intermittent nature of renewable energy sources such as wind and sunlight, as well as expensive facility investments and management. For example, renewable energy costs an additional 1.5 cents per KWh compared to the regular energy in the power market of Virginia [START_REF]Dominion Virginia Power[END_REF]. Furthermore, solar energy is typically much more expensive than wind energy, due to the relatively high capital expenses [START_REF]Energy modality comparison based on projected[END_REF][START_REF]Solar Power at Data Center Scale[END_REF]. Thus, to be more practical, in our simulation we assume that the wind electricity price is 1.5 cents higher per KWh than brown energy [START_REF]Dominion Virginia Power[END_REF]; while solar energy is 18.0 cents higher per KWh [START_REF]Energy modality comparison based on projected[END_REF].

Evaluation Results

In this section, we first introduce two baselines. We then compare the proposed GreenWare middleware system against the baselines.

Baselines

In our work, we use two baselines in our experiments, a cost minimization only policy and a green energy usage maximization only policy, referred to as Min-Cost and Max-Green, respectively. (1) Min-Cost. Similar to GreenWare, Min-Cost also tries to minimize the electricity cost by distributing requests among geographically distributed data centers to leverage the varying electricity prices in different locations. However, different from GreenWare, Min-Cost is unaware of renewable energy and thus prefers brown energy in cost minimization. Min-Cost is similar to the state-of-the-art work [START_REF] Rao | Minimizing electricity cost: optimization of distributed internet data centers in a multi-electricity-market environment[END_REF] in minimizing the electricity bill in operating data center networks. (2) Max-Green. Similar to GreenWare, Max-Green tries to maximize the use of renewable energy by distributing more requests to data centers where more renewable energy is available. However, Max-Green does so regardless of the cost budget and thus may lead to a high operation cost for the Internet service operators and sometimes even budget violations. This scheme is similar to the state-of-the-art work [START_REF] Stewart | Some joules are more precious than others: Managing renewable energy in the datacenter[END_REF] in powering data centers with renewable energy.

Impacts of the Monthly Cost Budget

In this experiment, we evaluate the proposed GreenWare middleware with respect to different monthly cost budgets.

Figures 5 and6 depict how GreenWare works with the Wikipedia workload under a monthly cost budget of $340K. In particular, these two figures show that with a sufficient monthly cost budget (e.g., as shown in Figure 5, the allocated hourly budget is sufficient throughout the entire month), brown energy is used only in the invocation periods with insufficiently available renewable energy. That is, as indicated in Figure 6, only when the available renewable energy supply is less than the actual renewable energy demand (i.e., a difference lower than 0), the corresponding renewable energy usage does not reach 100%, e.g., the hours of 2, 5, 6, 7 and etc. Note that there are some invocation periods which have a zero usage of renewable energy, e.g., the hours of 1, 3, 4 and etc. This is because that there is no available renewable energy at all due to the weather conditions in those invocation periods. In addition, Figure 5 demonstrates that the hourly allocated cost budget within one week shows a growing trend. This is due to the fact that we carry over the unused allocated cost budget from previous invocation periods to the remaining invocation periods in the same week. Hourly Cost ($) (log scale)

Time (hour)

Hourly Budget GreenWare

Time (hour)

Renewable Energy Usage Difference b/w Renewable Energy Supply and Renewable Energy Demand Fig. 6. Hourly renewable energy usage by GreenWare with a sufficient monthly cost budget of $340K, with respect to Nov. 2007 Wikipedia trace.

We then study GreenWare under a series of different monthly cost budgets. As shown in Figure 7, with the increase of the monthly cost budget, the monthly average percentage of renewable energy usage keeps rising and then stays stable. This is due to the fact that fewer invocation periods are allocated with an insufficient cost budget in the case with a higher monthly cost budget. Therefore, more renewable energy can be used to power the data center networks. For example, with a monthly cost budget of $100K, there are 202 invocation periods which have sufficient renewable energy supply but with an insufficient allocated cost budget; while as low as only 42 invocation periods are allocated with an insufficient cost budget in the case with a $160K monthly cost budget. As a result, a higher monthly average percentage of 58.17% of renewable energy usage is achieved with the monthly cost budget of $160K, compared to a percentage of 45.95% with the monthly budget $100K. Thus, when all the invocation periods have a sufficient budget due to a sufficient monthly cost budget, e.g., $320K and $340K, the monthly average renewable energy usage stays stable. This set of experiments demonstrates that GreenWare can significantly increase the use of renewable energy in powering the data center network, subject to the desired cost budget.

Comparison with Baselines

In this experiment, we compare GreenWare with the two baselines: Min-Cost and Max-Green. Figure 8 depicts the cost and brown energy consumption of GreenWare, Max-Green and Min-Cost, with respect to a given monthly budget, e.g., $100K, for the Wikipeida workload. The results are normalized against Min-Cost, which actually indicates the case of only using brown energy in powering data center networks. Figure 8 shows that although Max-Green (i.e., maximizing the use of green energy regardless of cost budget) can decrease brown energy consumption by 58% compared to Min-Cost by utilizing as much renewable energy as possible. However, due to its unawareness of cost budget, Max-Green results in a 109% cost increase and exceeds the monthly cost budget by 29%. On the other hand, GreenWare can achieve an as-much-as-42% decrease in brown energy consumption at only a 52% cost increase, compared to Min-Cost. More importantly, GreenWare successfully controls the electricity bill to stay within the cost budget for the Internet service operator.

To demonstrate the effectiveness of GreenWare with different workloads, we also stress test GreenWare using the 1998 World Cup trace. Specifically, we use the request trace in June as the incoming workload in the simulation, and the May trace as historical data to predict the hourly cost budget. To simulate the workload of cloud-service data centers, we proportionally increase the request numbers. Figure 9 shows the experiment results on the comparison between GreenWare and the two baselines. As demonstrated in the figure, Max-Green achieves a 42% decrease in brown energy consumption compared to Min-Cost. However, the electricity bill exceeds the given monthly cost budget (e.g., $100K) by 31%. On the other hand, GreenWare obtains an as-much-as-21% decrease in brown energy consumption while successfully controlling the electricity bill to stay within the monthly cost budget.

Impacts of Pricing Policies of Renewable Energy

In this experiment, we show that the proposed GreenWare middleware always prefers the type of renewable energy that has a lower electricity price. Thus, an efficient cost minimization is guaranteed. Since in our work we just consider two types of the most popular renewable energy, i.e., wind energy and solar energy, we assume two different pricing policies: (1) wind energy has a lower electricity price, as discussed in Section 4.4; and (2) solar energy has a lower price than wind energy. Note that the current practice is that wind energy is typically less expensive than solar energy. However, in order to stress test GreenWare, we assume a lower price for solar energy in (2). Figures 10 and11 demonstrate how the usage of different types of renewable energy varies with different pricing policies as discussed above. Intuitively, the more expensive renewable energy is taken into use only when the less expensive type of renewable energy is used up. As shown in Figure 10, with the first pricing policy (i.e., wind energy price is lower), solar energy is used to power data centers only after all the supplied wind energy has been used up, as indicated in the second data center (DC#2). Similarly, with the second pricing policy, wind energy is used to power data centers only after all the available less expensive solar energy is consumed, as in all the data centers in Figure 11. Note that in Figure 10, Data Centers 1, 3 and 4 begin to use the more expensive solar energy though there is still some wind energy left. This is because that there are some invocation periods when the available wind energy is too much to serve the incoming workload. As a result, some wind energy is left unused and the unused wind energy cannot be used in the following invocation periods due to the intermittent feature of the renewable energy.

Related Work

Greening data centers is becoming an increasingly important topic in operating cloud-scale data center networks for Internet service operators, due to (1) data centers having become major energy consumers [START_REF]Report to congress on server and data center energy efficiency[END_REF] and (2) the global energy crisis and environmental concerns (e.g., global warming) [START_REF] Li | Solarcore: Solar energy driven multi-core architecture power management[END_REF]. To our best knowledge, our study is the first one that proposes to maximally use the renewable energy supplied by the local power utilities for Internet service operators, while being aware of the time-varying electricity price and enforcing a desired cost budget. Compared with the state of the art, the considerations of various realistic constraints make GreenWare more practical. We now discuss the related work.

Energy conservation in data centers. Many recent research projects have tried to minimize the energy consumption of data centers. For example, Chen et al. [START_REF] Chen | Energy-aware server provisioning and load dispatching for connection-intensive internet services[END_REF] and Chase et al. [START_REF] Chase | Managing energy and server resources in hosting centers[END_REF] reduce the energy consumption of connection servers hosting long-lived TCP-connection services and web servers providing request-response type of services, respectively. Heo et al. [START_REF] Heo | Integrating adaptive components: An emerging challenge in performance-adaptive systems and a server farm case-study[END_REF] have developed an adaptation graph analysis mechanism to solve the conflicts between interacting adaptive components, e.g., On/Off and dynamic voltage scaling policies in server farms, to minimize energy consumption. Elnozahy et al. [START_REF] Elnozahy | Energy-efficient server clusters[END_REF] investigate various combinations of dynamic voltage scaling and node on/off policies to reduce the energy consumption in server farms. Other strategies on reducing energy consumption of servers are also proposed (e.g., [START_REF] Horvath | Dynamic voltage scaling in multitier web servers with end-to-end delay control[END_REF][START_REF] Verma | Server workload analysis for power minimization using consolidation[END_REF]).

Our work differs from these efforts in several ways: (1) none of them try to use renewable energy to power data center networks; and (2) none of them put efforts on managing the electricity cost for the Internet service operators.

Managing electricity cost in data centers. A few recent projects have proposed to minimize the electricity bills of data center networks. For example, Qureshi et al. [START_REF] Qureshi | Cutting the electric bill for internet-scale systems[END_REF] try to lower the electricity bill by utilizing the varying electricity prices in different locations of distributed data centers. Rao et al. [START_REF] Rao | Minimizing electricity cost: optimization of distributed internet data centers in a multi-electricity-market environment[END_REF] consider a multi-electricity-market environment to reduce the electricity bill. In a recent study, Zhang et al. [START_REF] Zhang | Capping the electricity cost of cloud-scale data centers with impacts on power markets[END_REF] propose an electricity bill capping algorithm to minimize the electricity cost within the cost budget for data center networks. Lin et al. [START_REF] Lin | Dynamic right-sizing for power-proportional data centers[END_REF] have tried to minimize the energy cost together with delay cost by rightly sizing data centers. Our work differs significantly from these efforts in that none of them try to maximize the use of renewable energy in powering data center networks for the Internet service operators.

Utilizing renewable energy in data centers. This is a relatively new topic with only few initial studies. Le et al. [START_REF] Le | Managing the cost, energy consumption, and carbon footprint of internet services[END_REF][START_REF] Le | Cost-and energy-aware load distribution across data centers[END_REF] propose to cap the consumption of brown energy while maintaining service level agreements (SLAs). Liu et al. [START_REF] Liu | Greening geograhpical load balancing[END_REF] investigate how renewable energy can be used to lower the electricity price of brown energy in a specific power market, i.e., where the brown energy is dynamically priced in proportion to the total brown energy consumption. Brown et al. [START_REF] Brown | Rerack: Power simulation for data centers with renewable energy generation[END_REF] propose a simulation infrastructure to model a data center using renewable energy sources. In contrast to those studies, GreenWare aims to solve a related but different problem, i.e., maximizing the use of renewable energy subject to the cost budget of the Internet service operators. Steward et al. [START_REF] Stewart | Some joules are more precious than others: Managing renewable energy in the datacenter[END_REF] also try to maximize the use of renewable energy in data centers. However, their study assumes that Internet service operators have their own wind farms or solar plants. In contrast, GreenWare considers a different case where the service operators buy renewable energy from the power grid, which is a more common case for many data centers because of concerns such as expensive facility investments and management. In addition, their study does not consider the extra cost of renewable energy and may lead to budget violations as shown in the comparisons between GreenWare and Max-Green in Section 5.3. Li et al. [START_REF] Li | Characterizing and analyzing renewable energy driven data centers[END_REF] propose a load power tuning scheme for managing intermittent renewable power in a single data center without considering the costs. In contrast, we focus on distributing requests among data centers in different locations.

Conclusion

Two key questions faced by many cloud-service operators are 1) how to dynamically distribute service requests among data centers in different geographical locations, based on the local weather conditions, to maximize the use of renewable energy, and 2) how to do so within their allowed operation budgets. In this paper, we have presented GreenWare, a novel middleware system that conducts dynamic request dispatching to maximize the percentage of renewable energy used to power a network of distributed data centers, subject to the desired cost budget of the Internet service operators. Our solution first explicitly models the intermittent generation of renewable energy, e.g., wind power and solar power, with respect to varying weather conditions in the geographical location of each data center. We then formulate the core objective of GreenWare as a constrained optimization problem and propose an efficient request dispatching algorithm based on linear-fractional programming (LFP). We evaluate GreenWare with real-world weather, electricity price, and workload traces. Our experimental results show that GreenWare can significantly increase the use of renewable energy in cloud-scale data centers without violating the desired cost budget, despite the intermittent supplies of renewable energy in different locations and time-varying electricity prices and workloads.

Fig. 1 .

 1 Fig. 1. Proposed GreenWare system for distributed cloud-scale data center networks.

  0 and T 0 are the respective irradiance level and temperature in Standard Test Conditions (STC), i.e., G 0 = 1000W/m 2 and T 0 = 25 o C. I sc , V oc , k v and k i are the given parameters of short-circuit current, open-circuit voltage, temperature coefficients of the short-circuit and the open-circuit in STC from the datasheet of PV panels, respectively.

Fig. 2 .Fig. 3 .

 23 Fig. 2. The trace of available wind energy throughout the entire simulated month.

Fig. 4 .

 4 Fig. 4. Wikipeida workload trace from October 1st, 2007 to November 30th, 2007.

Fig. 5 .

 5 Fig. 5. Hourly electricity cost by GreenWare with a sufficient monthly cost budget of $340K, with respect to Nov. 2007 Wikipedia trace.

Fig. 7 .

 7 Fig. 7. Average percentage of renewable energy usage by GreenWare with a series of different monthly cost budgets.

Fig. 8 .Fig. 9 .

 89 Fig. 8. Comparison between GreenWare and baselines with respect to Nov. 2007 Wikipeida trace.

Acknowledgments

This work was supported, in part, by NSF under CNS-0720663 and CAREER Award CNS-0845390.