# A Two-Tier Energy-Aware Resource Management for Virtualized Cloud Computing System

Authors: Wei Huang; Zhen Wang; Mianxiong Dong; Zhuzhong Qian
Journal: Scientific Programming
 (2016)

---

## Abstract

The economic costs caused by electric power take the most significant part in total cost of data center; thus energy conservation is an important issue in cloud computing system. One well-known technique to reduce the energy consumption is the consolidation of Virtual Machines (VMs). However, it may lose some performance points on energy saving and the Quality of Service (QoS) for dynamic workloads. Fortunately, Dynamic Frequency and Voltage Scaling (DVFS) is an efficient technique to save energy in dynamic environment. In this paper, combined with the DVFS technology, we propose a cooperative two-tier energy-aware management method including local DVFS control and global VM deployment. The DVFS controller adjusts the frequencies of homogenous processors in each server at run-time based on the practical energy prediction. On the other hand, Global Scheduler assigns VMs onto the designate servers based on the cooperation with the local DVFS controller. The final evaluation results demonstrate the effectiveness of our two-tier method in energy saving.


---

## Body

## 1. Introduction

Cloud computing provides elastic computing resources on a pay-as-you-go basis for most conceivable forms of applications but it also causes huge amounts of electric energy consumption. Almost 0.5% of world’s total power usage is consumed by the servers in data centers [1]. Among them, processors (CPUs) account for the most significant part of power and have the most dynamical power that can be adjusted, while other components can only be completely or partially turned off [2]. Owing to these reasons, reducing energy consumption of processors using the dynamic nature of CPUs’ power has become a hot research topic in cloud computing system.To service more users for more income, service providers prefer to share cluster resources among users. In cloud environments, the virtualization technique is widely adopted to allow users to share the physical resources. Making the working servers for Virtual Machines (VMs) as less as possible and letting the idle servers be in a low-power mode will improve the utilization of resources and reduce energy consumption, which is known as VM consolidation. In each server, by applying Dynamic Voltage and Frequency Scaling (DVFS), which enables dynamic adjustment of execution frequency on demand, more energy can be saved. The dynamic power consumption of CPU is proportional to the frequency and to the square of voltage. Scaling down the execution frequency will reduce the power while it may also reduce the performance and increase the execution time, which may instead cause more energy consumption (energy is equal to the line integral of powerP to time t, E
=
∫
0
t
‍
P
d
t). On the other hand, real-time tasks in the cloud computing system usually have requirements on execution speed; the extension of execution time may violate QoS requirements. Thus, it is nontrivial to reduce energy consumption by scaling the execution frequencies of tasks [3].VM consideration could improve the resource indeed and many previous works [4–6] achieve significant result on energy saving in virtualized cloud system. However, most of them do not take the advantage of DVFS strategy. Some others only apply the DVFS after allocation while not considering the influence of DVFS before allocation. However, if taking impacts of DVFS technique on energy into consideration before allocation, much more energy can be reduced. But it is not trivial to minimize the total energy consumption by VM allocation algorithm and DVFS strategies in this way. Several problems need to be solved: (1) how to define Quality of Service (QoS) requirements; (2) which servers can load arrival VMs with requirements; (3) which server brings minimum energy consumption by DVFS for arrival VMs and ensures QoS requirements.In this paper, we propose a cooperative two-tier energy-aware management by taking the DVFS into consideration, which offload real-time tasks to VMs on clusters and scaling frequencies. On the local tier, we propose a novel way to find the best combinations of frequencies of different CPUs that consume the least energy based on the practical energy prediction. We take both the frequency-power and utilization-power relationship into consideration when forecasting energy consumption. On the global tier, by cooperating with local DVFS controller, the Global Scheduler assigns a VM to its favourite processor in a cluster that brings minimum energy change. The frequency to execute the arrival workload has been decided before allocation instead of after allocation. The framework proposed in this paper takes both the energy consumption and performance into consideration and achieves good tradeoff between energy and consumption. The status of each hosts is controlled by the global master by regular communication, so the master can control the energy consumption and performance. Meanwhile, the computing can be done in parallel in each candidate for allocation to improve the effectiveness of computation. In summary, the main contributions of this paper are as follows:(i)
We propose the multiprocessor power model, which is shown to be close to the real power consumption of a server according to the evaluation of the model. The multiprocessor power model helps us to precisely estimate the energy consumption.
(ii)
We transform the energy minimization problem of frequency scaling to a node searching problem in directed graphs. We also prove that the optimal state which consumes the least energy can be found from an initial state in which all processors’ frequencies are maximum.
(iii)
We provide a novel scheduling algorithm, which can work in parallel and efficiently cooperates with local DVFS controller, for the problem of energy-aware scheduling. The experiments justify the effectiveness of our strategy on energy saving.The rest of this paper is organized as follows. Section2 introduces some related works. Section 3 introduces the framework of our solution and Section 4 introduces the task model and the analysis of the request of a VM. In Section 5, we introduce the energy prediction method and energy minimizing algorithm of local DVFS controller. The global VM allocation algorithm is presented in Section 6. In Section 7, we evaluate our solution through some experiments. Finally, we conclude this paper in Section 8.


## 2. Related Work

Reducing energy consumption has already been a critical issue of data center in recent years. Many works study the energy saving strategies in virtualized environment. Kusic et al. [7] defined a dynamic resource management as a sequential optimization in virtualized environment. The sequential optimization whose objective is maximizing the profit of provider is solved using Limited Lookahead Control (LLC) by minimizing both energy cost and SLA. But the framework captures the behavior of each application by simulation-based learning and the complexity of the model makes the approach not suitable for large scale data center.In [8], the authors have developed dynamic resource provisioning and allocation problem with virtualized technique for energy-efficient cloud computing. They propose self-manage and energy-aware mechanisms to allocate the Virtual Machines (VMs) and migrate VMs according to CPU utilizations and energy consumption. The placing problem of allocation which can be seen as a bin packing problem is solved by Modification Best Fit Decreasing (MBFD). For the migration problem, three policies are proposed to choose VMs to migrate in order to reduce energy consumption.Cardosa et al. [9] have presented a novel approach for power-efficient VM placement for the heterogeneous data centers by leveraging min-max and share features of the VMs based on the DVFS and soft scaling technique. The power consumption and utilization obtained from the running time of a VM are optimized by being set a priori. However, their approach does not strictly support SLAs and the information of applications’ priorities is needed. Cao and Dong [10] propose an energy-aware heuristic framework for VM consolidation which can obtain a better tradeoff between energy saving and performance. A SLA violation decision algorithm is proposed to determine hosts’ status for SLA violation. Based on the hosts’ status, the minimum power and maximum utilization policy for VM migration are used to achieve the energy saving.Reference [11] maximizes the utilization at virtual machine level in the environment of container. The objective of the paper is to dynamically set the sizes of virtual machines in order to improve the utilization of VMs, which saves overall energy consumption. Experiments show that their method can achieve 7.55% of energy consumption compared to scenarios where the virtual machine sizes are fixed. Reference [12] proposes a VM allocation algorithm to reduce energy consumption and SLA violation, which uses the historical record of VMs’ usage.Some other works mainly focus on the DVFS strategy to decrease processors’ power consumption in hosts. Some of them periodically adjust the frequency according to the performance of server. Reference [13] monitors the utilization of processors periodically and the frequency is decreased very carefully when there are observable impacts on execution time of tasks. Hsu and Feng [14] proposed a β-adaption algorithm that periodically evaluates the performance and automatically adapts the frequency and voltage at run-time. Reference [15] also developed the periodic DVFS controller for multicore processor without using any performance model. However, the length of period has a great impact on the performance of algorithms, it should be evaluated very carefully.Scaling the frequency according to the types of workloads is another efficient way to carry out DVFS control. They achieve the goal of energy saving with a little or limited performance loss by decreasing the frequency during the communication, data access, memory access, or idle phases. Lim et al. [16] proposed a run-time scheduler that applies DVFS control during the communication phases which is identified by intercepting the MPI calls. In [17], the authors presented a novel algorithm that utilizes the opportunities in execution of hybrid MPI/OpenMP application to scale the frequency and reduce energy consumption. Tan et al. implement the DVFS scheduling strategy for data intensive application in [18] and achieved the energy saving. Their strategy adaptively sets the suitable frequency according to the percentage of CPU-bound time in the total execution time of workloads and is implemented in source code level.The DVFS is able to reduce the energy consumption, but it is limited on a single server. A lot of work developed the DVFS-based task scheduling among servers because the distribution of workloads influences the overall energy. References [19, 20] propose similar energy-aware strategies that schedule a set of tasks onto physical machine. They adjust supply voltage by utilizing slack time of noncritical jobs. Reference [19] also discussed the tradeoff between energy consumption and scheduling length. Khan and Ahmad [21] studied the problem of task allocation in grid and they utilized the cooperative game theory to minimize the energy consumption and makespan of tasks for DVFS-based clusters. Similar to [21], Mezmaz et al. studied the problem for the dependent precedence-constrained parallel applications [22]. Different to these works, we study the independent real-time services with deadline constraints in multiprocessor system.References [23–27] researched energy-efficient task scheduling for real-time system. Luo and Jha studied the scheduling of periodic tasks in heterogeneous system and gave a power-efficient solution [27]. In [24], authors proposed an energy-aware task partitioning algorithm with polynomial time complexity for DVFS-based heterogeneous system. Awan and Petters proposed an energy-aware partitioning of tasks method which consists of two phases and they use a realistic power model to estimate power consumption [23]. Our task allocating algorithm cooperates with the local DVFS controller to predict the energy consumption in different situations; the influence of frequency scaling to energy consumption is taken into account before allocation for saving more energy.


## 3. Overview

Our framework can accept and analyze the arrival workloads and package them by Virtual Machines (VMs) and allocate them to the suitable server to reduce energy consumption. We first describe the architecture of our solution in Figure1 and subsequently introduce the real-time analysis in this section [3]. In our solution, theGlobal Scheduler assigns a task to a VM to execute it and guarantees its QoS requirement. This VM will be allocated to a host which can offload it without causing any violation of QoS requirement and brings minimum energy consumption. Our objective is to find the allocation method for VMs and frequencies scaling method for tasks to reduce the energy consumption.Figure 1
System architecture of our solution to the energy-aware resource management.Definition 1 (host model).
Leth
o
s
t
j
=
(
U
j
,
F
j
) be denoted as resources ofjth host, where U
j and F
j are vectors that record the utilizations and frequencies of each processor.TheTask Analyzer in Dispatcher receives and analyzes the information of incoming task and sends it to other components when necessary. TheHost Monitor is an assistant component which connects to each server and gathers the basic information of servers. TheLocal Monitor monitors the resources of a server and sends the basic information toHost Monitor when necessary. The basic information of servers is recorded in theHost Model (Definition 1). We mainly focus on the resource of processor, so we only record the states of processors in theHost Model. The main work mechanism of our solution to schedule a new task request t
a
s
k
n is described as follows:(1)
Whent
a
s
k
n comes, theTask Analyzer analyzes the basic information of t
a
s
k
n and sends it to theHost Monitor andGlobal Scheduler (Section 6).
(2)
When theHost Monitor receives the information of t
a
s
k
n, it selects a set of candidates who can load t
a
s
k
n according to the basic information of servers and sends the set to theGlobal Scheduler. In the large datacenter, the number of candidates can be carefully selected to improve the effectiveness of allocation.
(3)
When theGlobal Scheduler receives the candidates and the basic information of t
a
s
k
n, it sends the task information to the servers who are in the candidate set.
(4)
When a candidate receives the task information, thelocal DVFS controller (Section 5) will run to estimate the minimum energy change if t
a
s
k
n is allocated to one of its VM according to the monitored information. Then the controller returns the result to theGlobal Scheduler.
(5)
When theGlobal Scheduler receives responses from all the candidates, it allocates t
a
s
k
n to the best server using our allocation algorithm. There may be some network error in communications like packet error or loss or high network delay. We can set some threshold for theGlobal Scheduler, for example, time threshold for response time or retry times. When response time or retry times of a candidate are larger than the thresholds, theGlobal Scheduler can discard this candidate.This is the simple architecture for energy-aware task scheduling and some project implemented details or optimizations are not discussed in this paper. We mainly focus on the energy-aware scheduling for tasks and provide a solution to this problem. Some problems like single point of failure and network error are also important for the distributed cloud system. We consider that these problems have the maturing solutions in today’s cloud system and these aspects may not be a problem to our solution.


## 4. Task Model

The request of service in the cloud computing system usually has deadline constraints which is the major aspect of Service Level Agreements (SLAs). We explore energy saving method for the cluster that accepts request for tasks. We define thetask model (Definition 2) to describe the request for a task. The task model records some important information that users provide. s
i and d
i describe the requirements of tasks and e
i and u
i describe the execution characters of tasks.Definition 2 (task model).
Lett
a
s
k
i = (
s
i
,
d
i
,
e
i
,
u
i
) describeith task, where s
i
,
d
i
,
e
i
,
u
i represent the start time, relative deadline, predicted execution time, and the average utilization, respectively.For the isolation, scalability, and stability of system, tasks are usually run in the VMs independently in the cloud computing system. We can regard each task as a VM, so the allocation of the tasks is equivalent to the allocation of VMs in some degree. In our model, we assign a task to a VM to run and the VM will be allocated to appropriate host. When a task finishes, the VM loading this task will be shut off or turned into sleep. The living time for a VM to run a task is equal to the execution time of this task. Therefore, the living time for the VM should not exceed the deadline of the tasks. LetV
M
i represent the virtual machine load t
a
s
k
i.We designed theTask Analyzer to accept and analyze the incoming request of tasks. It sends the basic information of tasks to other components after preprocessing. The living time of a task (i.e., VM) usually includes computing time and CPU idle time. The CPU idle time may consist of communication, memory, or disk access. The real-time analysis we designed is to distinguish the computing time and CPU idle time. The average utilization of a VM can reflect the computation and CPU idle time in some degree. Let T
c
(
f
) and T
i represent computing time at frequency f and idle time of a VM, respectively. We estimate the computing time T
c
(
f
m
a
x
)
=
e
i
·
u
i and idle time T
i
=
e
i
·
(
1
-
u
i
) forith task. TheTask Analyzer calculates T
c
(
f
m
a
x
) and T
i and sends these information to other modules.The computing time has a tight relation to the CPU frequency which shows a linear extension to the reduction in frequency [28, 29], while the idle time of a task will barely change due to frequency scaling. Therefore, the living time of the VM ofith task frequency f can be expressed as(1)
T
i
f
=
T
c
f
m
a
x
f
m
a
x
f
+
T
i
.When thelocal DVFS controller predicts the energy consumption in different frequency, the living time of VMs can be calculated by (1) according to the task information provided by Task Analyzer. Although the running time can be predicted under different frequency, the energy prediction and DVFS controller are not a easy task. We will introduce details of our method to solve them in next sections.


## 5. Local DVFS Controller

TheDVFS Controller plays an important role in our framework and it has two main functions. On the one hand, it predicts the energy consumption of a multiprocessor server according to the processors’ utilizations, frequencies, and the living time of VMs. On the other hand, based on the energy prediction, it runs thek-Phase energy Prediction (kPP) algorithm to find the best frequencies combinations that bring minimum energy consumption.


### 5.1. Energy Prediction for Multiprocessor Servers

The electric energy consumption is the integral of the active power with respect to time. Therefore, the power prediction of server is crucial. Previous works like [30–34] provided serval methods to estimate the power of a server. However, they only focused on the frequency-power or utilization-power relationship and the detailed power prediction for multiprocessor platform is also ignored. In this paper, we provide a practical power prediction for multiprocessor servers based on the frequency-power and utilization-power relationship. We utilize the fact that the homogenous processors will consume the same power when they are under the same condition to predict the power consumption.The power consumption of a server consists of two parts: static and dynamic power consumption. The static parts include the power consumption of main board, hard disk, fan, and so forth. CPU accounts for the largest part of dynamic power. According to the previous studies, the dynamic power consumption of CPU is proportional to the frequency and to the square of voltage [34], which can be express as(2)
P
d
y
n
a
m
i
c
≃
A
×
C
×
V
2
×
f
,where A is the percentage of active gates, C is total capacitance, V is supply voltage, and f is the operating frequency. According to [31], the voltage has a linear relationship to frequency, so the dynamic power of a processor can be reduced as a function of frequency: P
d
y
n
a
m
i
c
=
α
×
f
3, where α is a proportional coefficient. Processors also have static power when they are active. Let P
s represent the static power of a server and P
C
P
U
s represent the static power of processor. The power of a host in which all homogenous processors work in the same frequency f with full utilization can be expressed as follows:(3)
P
f
=
P
s
+
N
c
P
C
P
U
s
+
α
f
3
,where N
c is the number of CPUs. We want to eliminate the static power of processors, which is not easy to measure. For a given host, we can easily measure its maximum power which is P
m
a
x
=
P
s
+
N
c
(
P
C
P
U
s
+
α
f
m
a
x
3
). Therefore, we can estimate the power consumption of a host in which all processors work in the same frequency f:(4)
P
f
=
P
m
a
x
-
α
N
c
f
m
a
x
3
-
f
3
.The power consumption is also related to utilizations. Figure2(a) shows the power consumption with only one processor running and Figure 2(b) shows the power of two processors that work in same utilization and frequency. As we can see, the power with different utilization under same frequency is different. The power and the utilization present a linear relationship which is with one voice to [30, 32, 33]. Therefore, the power consumption of one homogenous CPU with frequency f and utilization u can be denoted as(5)
P
C
P
U
u
,
f
=
1
N
c
P
m
a
x
-
P
s
-
α
N
c
f
m
a
x
3
-
f
3
u
.Finally, the power of prediction of a homogenous multiprocessor server can be expressed as(6)
P
h
o
s
t
=
P
s
+
∑
c
=
1
N
c
P
C
P
U
c
=
P
s
+
1
N
c
∑
c
=
1
N
c
P
m
a
x
-
P
s
-
α
N
c
f
m
a
x
3
-
F
j
,
c
3
U
j
,
c
.We can view the power ofjth host as a function of utilizations and frequencies, which is presented as P
h
o
s
t
(
F
j
,
U
j
), where U
j and F
j are defined inHost Model.Figure 2
Real power consumption of Dell R710 whose configurations are introduced in Table1 and the legend represents the different utilizations.
(a)
Only one processor is busy
(b)
Two processors are busyTable 1
Details of servers.
Name
Dell PowerEdge R710
Dell PowerEdge R720
CPUs
Two Intel Xeon processorsE5645 @2.4 GHz
Two Intel Xeon processorsE5-2620 @2.1 GHz
Frequency steps (GHz)
1.60, 1.73, 1.86, 2.00, 2.13, 2.26, 2.39, 2.40
1.20, 1.30, 1.40, 1.50, 1.60, 1.70, 1.80, 1.90, 2.00, 2.10
Memory
24 G 1333 Mhz DDR3
64 G ECC DDR3
Disk
Two 10 k SAS, 250 GB
One 10 k SAS, 300 GB
Operation system
CentOS 6.5
CentOS 6.5Definition 3 (Frequency Scaling Unit).
A time interval[
t
1
,
t
2
) is a Frequency Scaling Unit (FSU) if (1) ∀
t
∈
[
t
1
,
t
2
), N
T
(
t
)
=
N
T
(
t
1
) and (2) N
T
(
·
) changes at t
1 and t
2, where N
T
(
t
) represents the number of VMs at time t in a server.The energy consumption depends on both the execution time and the power. We define the concept ofFrequency Scaling Unit (FSU, Definition 3) to estimate the living time of VMs. The FSU represents a period of time that the number of VMs does not change. Once the number of VMs changes, that is, a VM coming or leaving, it enters the next FSU. An example of FSU is shown in Figure 3, which includes four FSUs. Assuming a VM is stopped at time t
2 and next VM is ended at time t
3, then T
=
t
3
-
t
2 is an FSU. If a VM is allocated to the server at t
1 and the VM finished at t
2, T
=
t
2
-
t
1 is said to thefirst FSU from current time. It is obvious that the number of VMs in the host is equal to the number of FSUs if all VMs finish at the different time, and we suppose that VMs are ended at the different time in a host in the rest of this paper.Figure 3
An example of FSU.If we set consistent frequencies for all processors in an FSU, the power state in this FSU is relatively stable because the workloads in this FSU are fixed. We know the length of this FSU, so the energy consumption in an FSU can be predicted conveniently and precisely by the following equation:E
=
P
×
T, where P and T represent power and time, respectively. Based on the definition of FSU, power function, and related notations in Notations, the energy consumption ofjth host to finish all the VMs can be predicted as follows:(7)
E
j
=
∑
k
=
1
N
j
,
p
P
j
,
k
U
j
,
k
,
F
j
,
k
T
j
,
k
,where the power of host P
j
,
k can be calculated by (6) in different situations. The length of FSU can also be estimated under different frequencies by (1).


### 5.2. kPP Algorithm for Energy Minimization

According to the analysis of energy prediction, if we set consistent frequencies in an FSU, then we can predict the energy consumption in an FSU conveniently. If we set FSUs with different frequencies, the living time of VMs and power state of server will be different, which brings different energy consumption. There is an optimal solution that consumes minimum energy when all VMs end in this server. We want to find the frequencies combinations for all FSUs that bring minimum energy on the promise of ensuring the requirements of VMs. Based on the energy prediction, the energy minimization problem of frequency scaling in homogenous multiprocessor platforms can be formalized as follows:(8)
m
i
n
F
j
,
k
∈
F
j
∑
k
=
1
N
j
,
p
P
j
,
k
U
j
,
k
,
F
j
,
k
T
j
,
k
s
.
t
.
∀
j
∈
H
,
V
M
i
∈
J
j
,
s
i
+
∑
m
=
1
N
p
i
t
j
,
m
i
<
d
i
.For clearly describing the problem, we define(
F
j
,
1
,
F
j
,
2
,
…
,
F
j
,
J
j
) as astate of possible frequencies combinations for FSU 1 to J
j using the notations in Notations. If there is only one frequencies combination that is different between two states, we say they are neighbors. For example, if there are two states s
1
:
(
F
j
,
1
,
F
j
,
2
,
…
,
F
j
,
J
j
) and s
2
:
(
F
j
,
1
,
F
j
,
2
,
…
,
F
j
,
J
j
′
) and the frequencies combinations of FSU |
J
j
| in s
1 and s
2 are different while others are the same, then s
1 and s
2 are neighbors. In addition, we define E
(
s
) as the cost function of total energy consumption of s according to (7) if we scale the frequencies like s in each FSU. Let a node present a state and an edge (
u
,
v
) between two nodes presents neighborhood between u and v. The minimization problem is to find the “optimal” node that brings minimum energy without any violation of SLAs from the initial node in the graph.Lemma 4.
Let the initial node represent the state in which all processors’ frequencies are highest in all FSUs. If the initial state ensures SLAs for all VMs, there is a path from initial node to the optimal node with minimum energy consumption without any violation of SLAs.Proof.
Lets
m
=
(
F
j
,
1
,
F
j
,
2
,
…
,
F
j
,
|
J
j
|
) represent the optimal state with minimum energy consumption without any violation of SLAs. If all processors’ frequencies are highest in all FSU of s
m, the initial state is the optimal state. Otherwise, we select the FSU r in which the frequencies are not highest for all CPUs. If we scale the frequencies to highest in r, the new state s
n will also ensure the SLAs for all VMs because processors are working at higher frequencies which leads to shorter execution time. s
n is one of the neighbors of the optimal state, which means that s
n can also move to s
m. Repeating the process above, we can find a path from s
m to initial state s
i, which represents that there is a path from s
i to s
m.


#### 5.2.1.k-Phase Energy Prediction (kPP) Algorithm

By energy prediction ofk FSUs, the best frequencies combinations can be found moving from the initial state according to Lemma 4. There are F
j possible frequencies combinations in each FSU, so there may be F
j
J
j possible states of all FSU with different energy consumption. Let F
L
j represent the frequency levels ofjth host; we have F
j
=
F
L
j
C
j. We want to find the optimal solution with minimum energy consumption in these F
j
J
j possible states while still ensuring SLAs. However, the searching space may be F
L
j
C
j
J
j which is too huge if there are many VMs. Therefore, we provide two heuristic algorithms to search the “optimal” solutions which are based on simulated annealing (SA) [35] and variable depth search (VDS) [36], respectively.(
1) Simulated Annealing Based Heuristic Algorithm. By comparing energy consumption of a random neighbor, we can find a better state that brings less energy. If we repeat the process many times, we may find the optimal state. Let s
0 represent the initial state in Lemma 4. In fact, since the simulated annealing (SA) algorithm has been proved to converge to the optimum with probability 1, it can be expected that our algorithm will output nice results by enough iterations. If we know the frequency steps and tasks’ information, the living time of VMs is determined. Therefore, we can estimate the total energy of the situation of state s
0 (line 3) using the energy cost function E
(
·
). The algorithm runs t
m
a
x iterations to find the state where less energy is consumed compared to the initial state. In each iteration, the algorithm randomly selects an FSU r to change the frequencies of processors and generates a new state s
t. This step takes O
(
1
) time. If the random neighbor s
t violates SLAs for any one of VMs, the state is discarded and our algorithm enters into the next iteration. This step takes O
(
N
j
,
p
) time, where N
j
,
p is the number of tasks. Otherwise, if predicted energy e
t is less than e, s
t is selected as compared state for next iteration due to less energy consumption. The energy prediction takes O
(
N
j
,
p
·
N
c
) time according to (7), where N
c is the number of processors. Besides, the algorithm also changes the state from s to s
t with the probability e
x
p
(
-
(
e
t
-
e
)
/
p
T
) suggested by Metropolis et al. [37] to give the possible to find optimal solution. The details of the simulated annealing based kPP algorithm are presented in Algorithm 1. Obviously, the time complexity of SA-based kPP algorithm is O
(
N
j
,
p
·
N
c
·
t
m
a
x
).Algorithm 1:SA based kPP algorithm.
Input:
The state ofh
o
s
t
j;
Output:
The possible states;
(1)   J
j
=
h
o
s
t
j
.
g
e
t
V
M
(
)
,
F
j
=
h
o
s
t
j
.
g
e
t
F
r
e
q
S
p
a
c
e
(
)
(2)   set s
0 be the state that the frequency is max for each CPU in all FSU
(3)   s
=
s
0
,
e
=
e
m
a
x
=
E
(
s
0
)
,
t
=
0
,
k
=
J
j
(4)   while
t
<
t
m
a
x or s doesn’t change in l rounds do
(5)    s
t
=
s,  r
=
r
a
n
d
o
m
(
k
)
(6)    F
j
,
r
=
r
a
n
d
o
m
(
F
j
-
s
.
g
e
t
(
r
)
) /∗Select a neighbor∗/
(7)    s
t
.
s
e
t
(
r
,
F
j
,
r
) /∗Change frequencies combination of FSU r to F
j
,
r
∗/
(8)    for
i
=
1 to k
do
(9)     if
V
M
i violates SLAs according to s
t
then
(10)    go to (17)
(11)   end if
(12)  end for
(13)  e
t
=
E
(
s
t
)
(14)  if
e
t
≤
e
m
a
x or r
a
n
d
o
m
(
)
<
exp
⁡
(
-
e
t
-
e
t
/
p
T
)
then
(15)   s
=
s
t
,
e
=
e
t /∗Change states∗/
(16)  end if
(17)  t
=
t
+
1
(18)end while
(19) return
s(
2) Variable Depth Search Based Heuristic Algorithm.The VDS-based kPP algorithm selects the state that brings minimum energy in a subset of neighbors and compares it to the current state. If the selected state consumes less energy on the promise of ensuring the SLAs of VMs, we will change the state to it. The initialized state of VDS-based algorithm is the same as the initialization of SA-based algorithm. The algorithm selects a subset of neighbors whose frequencies combination of FSU r are different (lines 5-6). The frequencies combination of FSU r with minimum energy will be selected (line 7) and generates a new state. The energy prediction takes O
(
N
j
,
p
·
N
c
) time, so the selection of state with minimum energy takes O
(
X
·
N
j
,
p
·
N
c
) time, where X is the size of subset. The algorithm checks the violations of SLAs of new state (lines 9–13). The process repeats for t
m
a
x times or until the state s does not change in l iterations. Therefore, the time complexity of this algorithm is O
(
X
·
N
j
,
p
·
N
c
·
t
m
a
x
). The effectiveness of the variable depth search is proved in [36]. The details of VDS-based kPP algorithm are shown in Algorithm 2.Algorithm 2:VDS-based kPP algorithm.
Input:
The state ofh
o
s
t
j;
Output:
The possible states;
(1)   J
j
=
h
o
s
t
j
.
g
e
t
V
M
(
)
,
F
j
=
h
o
s
t
j
.
g
e
t
F
r
e
q
S
p
a
c
e
(
)
(2)   set s
0 be the state that the frequency is max for each CPU in all FSU
(3)   s
=
s
0
,
t
=
0
,
k
=
J
j
(4)   while
t
<
t
m
a
x or s doesn’t change in l rounds do
(5)    s
t
=
s,  r
=
r
a
n
d
o
m
(
k
)
(6)    randomly select a subset X
⊆
F
j
(7)    x
=
argmin
⁡
(
E
(
s
t
.
s
e
t
(
r
,
x
)
)
), for all x
∈
X /∗Select the state form subset with minimum energy consumption∗/
(8)    s
t
.
s
e
t
(
r
,
x
) /∗Change frequencies combination of FSU r to x
∗/
(9)    for
i
=
1 to k
do
(10)   if
V
M
i violates SLAs according to s
t
then
(11)    go to (15)
(12)   end if
(13)  end for
(14)  s
=
s
t /∗Change states∗/
(15)  t
=
t
+
1
(16) end while
(17) return
sThelocal DVFS controller runs the kPP algorithm when theGlobal Scheduler asks it to predict the minimum energy consumption and return it toGlobal Scheduler. This is one of the opportunities to run kPP algorithm. When the workload changes, the power state will change. In addition, the execution time of VMs may have some errors which may lead to the error of energy prediction. Therefore, we apply the frequencies scaling when a VM finishes and scale the frequency for first FSU, which means that the algorithm only scales the CPUs’ frequencies just for the first FSU while predicting the frequencies combinations fork FSUs. As the example shown in Figure 3, if the V
M
4 comes at the time t
1 and is allocated to the host, this host applies the kPP algorithm at that time and sets the CPUs’ frequencies like FSU 1 of the result. When V
M
1 finishes at the t
2, the kPP algorithm also runs to obtain the “optimal” state s and scales frequencies according to the result. Due to the specialities of kPP algorithm at running time, the iteration should be completed in a short time so that the local stage can scale the frequencies in time.


## 5.1. Energy Prediction for Multiprocessor Servers

The electric energy consumption is the integral of the active power with respect to time. Therefore, the power prediction of server is crucial. Previous works like [30–34] provided serval methods to estimate the power of a server. However, they only focused on the frequency-power or utilization-power relationship and the detailed power prediction for multiprocessor platform is also ignored. In this paper, we provide a practical power prediction for multiprocessor servers based on the frequency-power and utilization-power relationship. We utilize the fact that the homogenous processors will consume the same power when they are under the same condition to predict the power consumption.The power consumption of a server consists of two parts: static and dynamic power consumption. The static parts include the power consumption of main board, hard disk, fan, and so forth. CPU accounts for the largest part of dynamic power. According to the previous studies, the dynamic power consumption of CPU is proportional to the frequency and to the square of voltage [34], which can be express as(2)
P
d
y
n
a
m
i
c
≃
A
×
C
×
V
2
×
f
,where A is the percentage of active gates, C is total capacitance, V is supply voltage, and f is the operating frequency. According to [31], the voltage has a linear relationship to frequency, so the dynamic power of a processor can be reduced as a function of frequency: P
d
y
n
a
m
i
c
=
α
×
f
3, where α is a proportional coefficient. Processors also have static power when they are active. Let P
s represent the static power of a server and P
C
P
U
s represent the static power of processor. The power of a host in which all homogenous processors work in the same frequency f with full utilization can be expressed as follows:(3)
P
f
=
P
s
+
N
c
P
C
P
U
s
+
α
f
3
,where N
c is the number of CPUs. We want to eliminate the static power of processors, which is not easy to measure. For a given host, we can easily measure its maximum power which is P
m
a
x
=
P
s
+
N
c
(
P
C
P
U
s
+
α
f
m
a
x
3
). Therefore, we can estimate the power consumption of a host in which all processors work in the same frequency f:(4)
P
f
=
P
m
a
x
-
α
N
c
f
m
a
x
3
-
f
3
.The power consumption is also related to utilizations. Figure2(a) shows the power consumption with only one processor running and Figure 2(b) shows the power of two processors that work in same utilization and frequency. As we can see, the power with different utilization under same frequency is different. The power and the utilization present a linear relationship which is with one voice to [30, 32, 33]. Therefore, the power consumption of one homogenous CPU with frequency f and utilization u can be denoted as(5)
P
C
P
U
u
,
f
=
1
N
c
P
m
a
x
-
P
s
-
α
N
c
f
m
a
x
3
-
f
3
u
.Finally, the power of prediction of a homogenous multiprocessor server can be expressed as(6)
P
h
o
s
t
=
P
s
+
∑
c
=
1
N
c
P
C
P
U
c
=
P
s
+
1
N
c
∑
c
=
1
N
c
P
m
a
x
-
P
s
-
α
N
c
f
m
a
x
3
-
F
j
,
c
3
U
j
,
c
.We can view the power ofjth host as a function of utilizations and frequencies, which is presented as P
h
o
s
t
(
F
j
,
U
j
), where U
j and F
j are defined inHost Model.Figure 2
Real power consumption of Dell R710 whose configurations are introduced in Table1 and the legend represents the different utilizations.
(a)
Only one processor is busy
(b)
Two processors are busyTable 1
Details of servers.
Name
Dell PowerEdge R710
Dell PowerEdge R720
CPUs
Two Intel Xeon processorsE5645 @2.4 GHz
Two Intel Xeon processorsE5-2620 @2.1 GHz
Frequency steps (GHz)
1.60, 1.73, 1.86, 2.00, 2.13, 2.26, 2.39, 2.40
1.20, 1.30, 1.40, 1.50, 1.60, 1.70, 1.80, 1.90, 2.00, 2.10
Memory
24 G 1333 Mhz DDR3
64 G ECC DDR3
Disk
Two 10 k SAS, 250 GB
One 10 k SAS, 300 GB
Operation system
CentOS 6.5
CentOS 6.5Definition 3 (Frequency Scaling Unit).
A time interval[
t
1
,
t
2
) is a Frequency Scaling Unit (FSU) if (1) ∀
t
∈
[
t
1
,
t
2
), N
T
(
t
)
=
N
T
(
t
1
) and (2) N
T
(
·
) changes at t
1 and t
2, where N
T
(
t
) represents the number of VMs at time t in a server.The energy consumption depends on both the execution time and the power. We define the concept ofFrequency Scaling Unit (FSU, Definition 3) to estimate the living time of VMs. The FSU represents a period of time that the number of VMs does not change. Once the number of VMs changes, that is, a VM coming or leaving, it enters the next FSU. An example of FSU is shown in Figure 3, which includes four FSUs. Assuming a VM is stopped at time t
2 and next VM is ended at time t
3, then T
=
t
3
-
t
2 is an FSU. If a VM is allocated to the server at t
1 and the VM finished at t
2, T
=
t
2
-
t
1 is said to thefirst FSU from current time. It is obvious that the number of VMs in the host is equal to the number of FSUs if all VMs finish at the different time, and we suppose that VMs are ended at the different time in a host in the rest of this paper.Figure 3
An example of FSU.If we set consistent frequencies for all processors in an FSU, the power state in this FSU is relatively stable because the workloads in this FSU are fixed. We know the length of this FSU, so the energy consumption in an FSU can be predicted conveniently and precisely by the following equation:E
=
P
×
T, where P and T represent power and time, respectively. Based on the definition of FSU, power function, and related notations in Notations, the energy consumption ofjth host to finish all the VMs can be predicted as follows:(7)
E
j
=
∑
k
=
1
N
j
,
p
P
j
,
k
U
j
,
k
,
F
j
,
k
T
j
,
k
,where the power of host P
j
,
k can be calculated by (6) in different situations. The length of FSU can also be estimated under different frequencies by (1).


## 5.2. kPP Algorithm for Energy Minimization

According to the analysis of energy prediction, if we set consistent frequencies in an FSU, then we can predict the energy consumption in an FSU conveniently. If we set FSUs with different frequencies, the living time of VMs and power state of server will be different, which brings different energy consumption. There is an optimal solution that consumes minimum energy when all VMs end in this server. We want to find the frequencies combinations for all FSUs that bring minimum energy on the promise of ensuring the requirements of VMs. Based on the energy prediction, the energy minimization problem of frequency scaling in homogenous multiprocessor platforms can be formalized as follows:(8)
m
i
n
F
j
,
k
∈
F
j
∑
k
=
1
N
j
,
p
P
j
,
k
U
j
,
k
,
F
j
,
k
T
j
,
k
s
.
t
.
∀
j
∈
H
,
V
M
i
∈
J
j
,
s
i
+
∑
m
=
1
N
p
i
t
j
,
m
i
<
d
i
.For clearly describing the problem, we define(
F
j
,
1
,
F
j
,
2
,
…
,
F
j
,
J
j
) as astate of possible frequencies combinations for FSU 1 to J
j using the notations in Notations. If there is only one frequencies combination that is different between two states, we say they are neighbors. For example, if there are two states s
1
:
(
F
j
,
1
,
F
j
,
2
,
…
,
F
j
,
J
j
) and s
2
:
(
F
j
,
1
,
F
j
,
2
,
…
,
F
j
,
J
j
′
) and the frequencies combinations of FSU |
J
j
| in s
1 and s
2 are different while others are the same, then s
1 and s
2 are neighbors. In addition, we define E
(
s
) as the cost function of total energy consumption of s according to (7) if we scale the frequencies like s in each FSU. Let a node present a state and an edge (
u
,
v
) between two nodes presents neighborhood between u and v. The minimization problem is to find the “optimal” node that brings minimum energy without any violation of SLAs from the initial node in the graph.Lemma 4.
Let the initial node represent the state in which all processors’ frequencies are highest in all FSUs. If the initial state ensures SLAs for all VMs, there is a path from initial node to the optimal node with minimum energy consumption without any violation of SLAs.Proof.
Lets
m
=
(
F
j
,
1
,
F
j
,
2
,
…
,
F
j
,
|
J
j
|
) represent the optimal state with minimum energy consumption without any violation of SLAs. If all processors’ frequencies are highest in all FSU of s
m, the initial state is the optimal state. Otherwise, we select the FSU r in which the frequencies are not highest for all CPUs. If we scale the frequencies to highest in r, the new state s
n will also ensure the SLAs for all VMs because processors are working at higher frequencies which leads to shorter execution time. s
n is one of the neighbors of the optimal state, which means that s
n can also move to s
m. Repeating the process above, we can find a path from s
m to initial state s
i, which represents that there is a path from s
i to s
m.


### 5.2.1.k-Phase Energy Prediction (kPP) Algorithm

By energy prediction ofk FSUs, the best frequencies combinations can be found moving from the initial state according to Lemma 4. There are F
j possible frequencies combinations in each FSU, so there may be F
j
J
j possible states of all FSU with different energy consumption. Let F
L
j represent the frequency levels ofjth host; we have F
j
=
F
L
j
C
j. We want to find the optimal solution with minimum energy consumption in these F
j
J
j possible states while still ensuring SLAs. However, the searching space may be F
L
j
C
j
J
j which is too huge if there are many VMs. Therefore, we provide two heuristic algorithms to search the “optimal” solutions which are based on simulated annealing (SA) [35] and variable depth search (VDS) [36], respectively.(
1) Simulated Annealing Based Heuristic Algorithm. By comparing energy consumption of a random neighbor, we can find a better state that brings less energy. If we repeat the process many times, we may find the optimal state. Let s
0 represent the initial state in Lemma 4. In fact, since the simulated annealing (SA) algorithm has been proved to converge to the optimum with probability 1, it can be expected that our algorithm will output nice results by enough iterations. If we know the frequency steps and tasks’ information, the living time of VMs is determined. Therefore, we can estimate the total energy of the situation of state s
0 (line 3) using the energy cost function E
(
·
). The algorithm runs t
m
a
x iterations to find the state where less energy is consumed compared to the initial state. In each iteration, the algorithm randomly selects an FSU r to change the frequencies of processors and generates a new state s
t. This step takes O
(
1
) time. If the random neighbor s
t violates SLAs for any one of VMs, the state is discarded and our algorithm enters into the next iteration. This step takes O
(
N
j
,
p
) time, where N
j
,
p is the number of tasks. Otherwise, if predicted energy e
t is less than e, s
t is selected as compared state for next iteration due to less energy consumption. The energy prediction takes O
(
N
j
,
p
·
N
c
) time according to (7), where N
c is the number of processors. Besides, the algorithm also changes the state from s to s
t with the probability e
x
p
(
-
(
e
t
-
e
)
/
p
T
) suggested by Metropolis et al. [37] to give the possible to find optimal solution. The details of the simulated annealing based kPP algorithm are presented in Algorithm 1. Obviously, the time complexity of SA-based kPP algorithm is O
(
N
j
,
p
·
N
c
·
t
m
a
x
).Algorithm 1:SA based kPP algorithm.
Input:
The state ofh
o
s
t
j;
Output:
The possible states;
(1)   J
j
=
h
o
s
t
j
.
g
e
t
V
M
(
)
,
F
j
=
h
o
s
t
j
.
g
e
t
F
r
e
q
S
p
a
c
e
(
)
(2)   set s
0 be the state that the frequency is max for each CPU in all FSU
(3)   s
=
s
0
,
e
=
e
m
a
x
=
E
(
s
0
)
,
t
=
0
,
k
=
J
j
(4)   while
t
<
t
m
a
x or s doesn’t change in l rounds do
(5)    s
t
=
s,  r
=
r
a
n
d
o
m
(
k
)
(6)    F
j
,
r
=
r
a
n
d
o
m
(
F
j
-
s
.
g
e
t
(
r
)
) /∗Select a neighbor∗/
(7)    s
t
.
s
e
t
(
r
,
F
j
,
r
) /∗Change frequencies combination of FSU r to F
j
,
r
∗/
(8)    for
i
=
1 to k
do
(9)     if
V
M
i violates SLAs according to s
t
then
(10)    go to (17)
(11)   end if
(12)  end for
(13)  e
t
=
E
(
s
t
)
(14)  if
e
t
≤
e
m
a
x or r
a
n
d
o
m
(
)
<
exp
⁡
(
-
e
t
-
e
t
/
p
T
)
then
(15)   s
=
s
t
,
e
=
e
t /∗Change states∗/
(16)  end if
(17)  t
=
t
+
1
(18)end while
(19) return
s(
2) Variable Depth Search Based Heuristic Algorithm.The VDS-based kPP algorithm selects the state that brings minimum energy in a subset of neighbors and compares it to the current state. If the selected state consumes less energy on the promise of ensuring the SLAs of VMs, we will change the state to it. The initialized state of VDS-based algorithm is the same as the initialization of SA-based algorithm. The algorithm selects a subset of neighbors whose frequencies combination of FSU r are different (lines 5-6). The frequencies combination of FSU r with minimum energy will be selected (line 7) and generates a new state. The energy prediction takes O
(
N
j
,
p
·
N
c
) time, so the selection of state with minimum energy takes O
(
X
·
N
j
,
p
·
N
c
) time, where X is the size of subset. The algorithm checks the violations of SLAs of new state (lines 9–13). The process repeats for t
m
a
x times or until the state s does not change in l iterations. Therefore, the time complexity of this algorithm is O
(
X
·
N
j
,
p
·
N
c
·
t
m
a
x
). The effectiveness of the variable depth search is proved in [36]. The details of VDS-based kPP algorithm are shown in Algorithm 2.Algorithm 2:VDS-based kPP algorithm.
Input:
The state ofh
o
s
t
j;
Output:
The possible states;
(1)   J
j
=
h
o
s
t
j
.
g
e
t
V
M
(
)
,
F
j
=
h
o
s
t
j
.
g
e
t
F
r
e
q
S
p
a
c
e
(
)
(2)   set s
0 be the state that the frequency is max for each CPU in all FSU
(3)   s
=
s
0
,
t
=
0
,
k
=
J
j
(4)   while
t
<
t
m
a
x or s doesn’t change in l rounds do
(5)    s
t
=
s,  r
=
r
a
n
d
o
m
(
k
)
(6)    randomly select a subset X
⊆
F
j
(7)    x
=
argmin
⁡
(
E
(
s
t
.
s
e
t
(
r
,
x
)
)
), for all x
∈
X /∗Select the state form subset with minimum energy consumption∗/
(8)    s
t
.
s
e
t
(
r
,
x
) /∗Change frequencies combination of FSU r to x
∗/
(9)    for
i
=
1 to k
do
(10)   if
V
M
i violates SLAs according to s
t
then
(11)    go to (15)
(12)   end if
(13)  end for
(14)  s
=
s
t /∗Change states∗/
(15)  t
=
t
+
1
(16) end while
(17) return
sThelocal DVFS controller runs the kPP algorithm when theGlobal Scheduler asks it to predict the minimum energy consumption and return it toGlobal Scheduler. This is one of the opportunities to run kPP algorithm. When the workload changes, the power state will change. In addition, the execution time of VMs may have some errors which may lead to the error of energy prediction. Therefore, we apply the frequencies scaling when a VM finishes and scale the frequency for first FSU, which means that the algorithm only scales the CPUs’ frequencies just for the first FSU while predicting the frequencies combinations fork FSUs. As the example shown in Figure 3, if the V
M
4 comes at the time t
1 and is allocated to the host, this host applies the kPP algorithm at that time and sets the CPUs’ frequencies like FSU 1 of the result. When V
M
1 finishes at the t
2, the kPP algorithm also runs to obtain the “optimal” state s and scales frequencies according to the result. Due to the specialities of kPP algorithm at running time, the iteration should be completed in a short time so that the local stage can scale the frequencies in time.


## 5.2.1.k-Phase Energy Prediction (kPP) Algorithm

By energy prediction ofk FSUs, the best frequencies combinations can be found moving from the initial state according to Lemma 4. There are F
j possible frequencies combinations in each FSU, so there may be F
j
J
j possible states of all FSU with different energy consumption. Let F
L
j represent the frequency levels ofjth host; we have F
j
=
F
L
j
C
j. We want to find the optimal solution with minimum energy consumption in these F
j
J
j possible states while still ensuring SLAs. However, the searching space may be F
L
j
C
j
J
j which is too huge if there are many VMs. Therefore, we provide two heuristic algorithms to search the “optimal” solutions which are based on simulated annealing (SA) [35] and variable depth search (VDS) [36], respectively.(
1) Simulated Annealing Based Heuristic Algorithm. By comparing energy consumption of a random neighbor, we can find a better state that brings less energy. If we repeat the process many times, we may find the optimal state. Let s
0 represent the initial state in Lemma 4. In fact, since the simulated annealing (SA) algorithm has been proved to converge to the optimum with probability 1, it can be expected that our algorithm will output nice results by enough iterations. If we know the frequency steps and tasks’ information, the living time of VMs is determined. Therefore, we can estimate the total energy of the situation of state s
0 (line 3) using the energy cost function E
(
·
). The algorithm runs t
m
a
x iterations to find the state where less energy is consumed compared to the initial state. In each iteration, the algorithm randomly selects an FSU r to change the frequencies of processors and generates a new state s
t. This step takes O
(
1
) time. If the random neighbor s
t violates SLAs for any one of VMs, the state is discarded and our algorithm enters into the next iteration. This step takes O
(
N
j
,
p
) time, where N
j
,
p is the number of tasks. Otherwise, if predicted energy e
t is less than e, s
t is selected as compared state for next iteration due to less energy consumption. The energy prediction takes O
(
N
j
,
p
·
N
c
) time according to (7), where N
c is the number of processors. Besides, the algorithm also changes the state from s to s
t with the probability e
x
p
(
-
(
e
t
-
e
)
/
p
T
) suggested by Metropolis et al. [37] to give the possible to find optimal solution. The details of the simulated annealing based kPP algorithm are presented in Algorithm 1. Obviously, the time complexity of SA-based kPP algorithm is O
(
N
j
,
p
·
N
c
·
t
m
a
x
).Algorithm 1:SA based kPP algorithm.
Input:
The state ofh
o
s
t
j;
Output:
The possible states;
(1)   J
j
=
h
o
s
t
j
.
g
e
t
V
M
(
)
,
F
j
=
h
o
s
t
j
.
g
e
t
F
r
e
q
S
p
a
c
e
(
)
(2)   set s
0 be the state that the frequency is max for each CPU in all FSU
(3)   s
=
s
0
,
e
=
e
m
a
x
=
E
(
s
0
)
,
t
=
0
,
k
=
J
j
(4)   while
t
<
t
m
a
x or s doesn’t change in l rounds do
(5)    s
t
=
s,  r
=
r
a
n
d
o
m
(
k
)
(6)    F
j
,
r
=
r
a
n
d
o
m
(
F
j
-
s
.
g
e
t
(
r
)
) /∗Select a neighbor∗/
(7)    s
t
.
s
e
t
(
r
,
F
j
,
r
) /∗Change frequencies combination of FSU r to F
j
,
r
∗/
(8)    for
i
=
1 to k
do
(9)     if
V
M
i violates SLAs according to s
t
then
(10)    go to (17)
(11)   end if
(12)  end for
(13)  e
t
=
E
(
s
t
)
(14)  if
e
t
≤
e
m
a
x or r
a
n
d
o
m
(
)
<
exp
⁡
(
-
e
t
-
e
t
/
p
T
)
then
(15)   s
=
s
t
,
e
=
e
t /∗Change states∗/
(16)  end if
(17)  t
=
t
+
1
(18)end while
(19) return
s(
2) Variable Depth Search Based Heuristic Algorithm.The VDS-based kPP algorithm selects the state that brings minimum energy in a subset of neighbors and compares it to the current state. If the selected state consumes less energy on the promise of ensuring the SLAs of VMs, we will change the state to it. The initialized state of VDS-based algorithm is the same as the initialization of SA-based algorithm. The algorithm selects a subset of neighbors whose frequencies combination of FSU r are different (lines 5-6). The frequencies combination of FSU r with minimum energy will be selected (line 7) and generates a new state. The energy prediction takes O
(
N
j
,
p
·
N
c
) time, so the selection of state with minimum energy takes O
(
X
·
N
j
,
p
·
N
c
) time, where X is the size of subset. The algorithm checks the violations of SLAs of new state (lines 9–13). The process repeats for t
m
a
x times or until the state s does not change in l iterations. Therefore, the time complexity of this algorithm is O
(
X
·
N
j
,
p
·
N
c
·
t
m
a
x
). The effectiveness of the variable depth search is proved in [36]. The details of VDS-based kPP algorithm are shown in Algorithm 2.Algorithm 2:VDS-based kPP algorithm.
Input:
The state ofh
o
s
t
j;
Output:
The possible states;
(1)   J
j
=
h
o
s
t
j
.
g
e
t
V
M
(
)
,
F
j
=
h
o
s
t
j
.
g
e
t
F
r
e
q
S
p
a
c
e
(
)
(2)   set s
0 be the state that the frequency is max for each CPU in all FSU
(3)   s
=
s
0
,
t
=
0
,
k
=
J
j
(4)   while
t
<
t
m
a
x or s doesn’t change in l rounds do
(5)    s
t
=
s,  r
=
r
a
n
d
o
m
(
k
)
(6)    randomly select a subset X
⊆
F
j
(7)    x
=
argmin
⁡
(
E
(
s
t
.
s
e
t
(
r
,
x
)
)
), for all x
∈
X /∗Select the state form subset with minimum energy consumption∗/
(8)    s
t
.
s
e
t
(
r
,
x
) /∗Change frequencies combination of FSU r to x
∗/
(9)    for
i
=
1 to k
do
(10)   if
V
M
i violates SLAs according to s
t
then
(11)    go to (15)
(12)   end if
(13)  end for
(14)  s
=
s
t /∗Change states∗/
(15)  t
=
t
+
1
(16) end while
(17) return
sThelocal DVFS controller runs the kPP algorithm when theGlobal Scheduler asks it to predict the minimum energy consumption and return it toGlobal Scheduler. This is one of the opportunities to run kPP algorithm. When the workload changes, the power state will change. In addition, the execution time of VMs may have some errors which may lead to the error of energy prediction. Therefore, we apply the frequencies scaling when a VM finishes and scale the frequency for first FSU, which means that the algorithm only scales the CPUs’ frequencies just for the first FSU while predicting the frequencies combinations fork FSUs. As the example shown in Figure 3, if the V
M
4 comes at the time t
1 and is allocated to the host, this host applies the kPP algorithm at that time and sets the CPUs’ frequencies like FSU 1 of the result. When V
M
1 finishes at the t
2, the kPP algorithm also runs to obtain the “optimal” state s and scales frequencies according to the result. Due to the specialities of kPP algorithm at running time, the iteration should be completed in a short time so that the local stage can scale the frequencies in time.


## 6. Global Scheduler

Different allocations of a new VM may affect the overall energy consumption, because the new VM executed on different servers will bring different energy consumption. We want to find the appropriate scheduling to minimize the energy consumption to finish all the VMs. We can obtain the different energy consumption with different allocation if we ask each host to predict the minimum energy consumption. Using the results of different allocations, we can select a better allocating scheme to reduce the energy consumption. Our goal is to minimize the overall energy cost of the whole cluster for finishing all VMs including the new VMV
M
n. To solve the energy minimization problem of VM scheduling, we first formalize the problem. Let decision parameter a
j
,
c
i be 1 if theith VM is allocated tocth CPU ofjth host, otherwise 0. The energy-efficient VM allocation problem can be expressed as(9)
m
i
n
∑
j
∈
H
m
i
n
F
j
,
k
∈
F
j
∑
k
=
1
N
j
,
p
P
j
,
k
U
j
,
k
,
F
j
,
k
T
j
,
k
s
.
t
.
∑
j
∈
H
,
c
∈
C
j
a
j
,
c
n
≤
1
;
J
j
=
J
j
∪
V
M
n
,
if
a
j
,
c
n
=
1
;
∀
j
∈
H
,
V
M
i
∈
J
j
,
s
i
+
∑
m
=
1
N
p
i
t
j
,
m
i
<
d
i
;
∀
k
∈
N
j
,
p
,
j
∈
H
,
∑
c
∈
C
j
U
j
,
k
c
<
U
T
j
.The energy minimization problem of VM scheduling is to find the server which brings minimum energy of whole cluster ifV
M
n is allocated to it. The minimum energy consumption of each server can be predicted by kPP algorithm, represented by E
M
I
N
j forjth host. If an incoming VM is allocated tojth host, the value of E
M
I
N
j changes while the minimum energy consumption of other hosts does not change. When V
M
n is allocated to theyth host, the energy consumption becomes E
M
I
N
y
′
+
∑
j
∈
H
-
{
y
}
‍
E
M
I
N
j, where E
M
I
N
y
′ is the minimum energy cost if V
M
n is allocated toyth host. We have(10)
E
m
i
n
=
E
M
I
N
y
′
+
∑
j
∈
H
-
y
E
M
I
N
j
=
Δ
E
M
I
N
y
+
E
M
I
N
y
+
∑
j
∈
H
-
y
E
M
I
N
j
=
Δ
E
M
I
N
y
+
∑
j
∈
H
E
M
I
N
j
.So we can select the host that brings minimum energy change Δ
E
M
I
N
y to run the incoming VM. We call the scheduling algorithmMinimum energy Change(MC), shown in Algorithm 3. TheGlobal Scheduler sends the information of a VM after analyzing to a subset of host (line 1) and each host returns the predicted minimum energy change on it. Therefore, we can run the energy-efficient algorithm in parallel to obtain the minimum energy consumption for each host when a VM arrives. After thelocal DVFS controller predicts the minimum energy change, it also records the best processor to hold this VM. When this VM is really allocated to it, the VM will be scheduled onto this best processor. Once deciding the host, the selected host will start a VM to run the VM working under the selected frequencies. It is obvious that the time complexity is O
(
H
+
L
+
T
), where L and T represent the time complexity of local predicting algorithm and communication time, respectively.Algorithm 3:Minimum energy change allocation.
Input:
A new VMV
M
n;
Output:
Designate host and processor for loadingV
M
n;
(1) Host Monitor selects a subset of active hosts that can load the VM
(2) notify the information of V
M
n to all candidates
(3) each host estimates the minimum energy change Δ
E
M
I
N
j if VM is allocated to processor c of h
o
s
t
j
(4) h
o
s
t
j
=
a
r
g
m
i
n
j
∈
H
(
Δ
E
M
I
N
j
)
(5) return
h
o
s
t
jThe number of candidate hosts will affect the total cost of a cluster, we evaluate the influence of kPP strategy on the total energy cost. Assume the total VM number isN
t; the size of subset for candidate hosts is N
h and the average run-time of local DVFS algorithm is 0.5 seconds. Let the mean power consumed by a VM be P
¯ Watt and the average length of VMs be t
¯ seconds. The kPP algorithm runs when the MC algorithm asks candidate hosts to estimate energy consumption; the energy consumption of kPP algorithm in this part is N
h
·
P
¯
·
N
t
·
0.5. The kPP algorithm also runs when a VM is allocated and finished, so the energy for this part is 2
·
N
t
·
P
¯
·
0.5, and the total energy produced by all VMs is N
t
·
P
¯
·
t
¯. Therefore, theenergy consumption ratio (ECR) of kPP algorithm compared to the total energy cost is(11)
E
C
R
=
0.5
·
N
h
+
1
t
¯
.In a large scale data center, the mean VM length can be acquired according to the historical data, and we can carefully select the size of candidate host estimating the energy change of offloading a new VM to increase the energy consumption of kPP algorithm as less as possible.


## 7. Experimental Evaluation

### 7.1. Evaluating Power Prediction

The energy prediction of server depends on the accuracy of power prediction under different utilizations and frequencies. We have evaluated the multiprocessor power prediction method by comparing the real power consumption to the estimation of power model in different status for a specific host. The real experimental environment is shown in Figure4. The details of server R710 used in our paper are shown in Table 1. We explore the real power consumption R710 and use the first seven steps when we evaluate the power model because the last frequency is very close to the frequency 2.39 GHz. The power consumption of the host when both processors are fully utilized at frequency level 2.39 GHz is 192 Watt and the static power when the system is not idle is 110 Watt. The proportional coefficient α
=
2.33135 is obtained and calibrated by offline experiments.Figure 4
Real system architecture.For evaluating the multiprocessor power prediction, we randomly select some frequencies and utilizations of two processors and use power model to estimate the power consumption. At the same time, we measure the real power consumption of R710 server with the same frequencies and utilizations of processors and results are shown in Table2. We use the Aitek AWE 2101 power analyzer to measure power. Table 2 shows that the estimated power is very close to the real power consumption of the server with the same utilizations and frequencies of different processors.Table 2
Power comparison.
Frequencies (GHz)
Utilizations
Power (Watt)
Error
C
P
U
1
C
P
U
2
C
P
U
1
C
P
U
2
Estimation
Real
1.60
2.00
61%
87%
145.33
147.01
−1.14%
1.73
2.13
95%
84%
156.45
157.81
−0.86%
1.86
1.73
19%
14%
117.50
117.03
+0.40%
2.00
1.60
59%
9%
127.96
128.32
−0.28%
2.13
2.13
61%
84%
155.67
155.68
+0.00%
2.13
1.86
58%
57%
141.94
142.68
−0.52%
2.26
2.00
58%
30%
139.10
137.89
+0.87%
2.26
2.39
98%
81%
178.21
181.69
+1.91%
2.39
1.60
92%
18%
150.87
149.79
+0.72%
2.39
2.13
12%
59%
133.48
133.15
+0.25%


### 7.2. Convergence Speed

In this subsection, we compare the convergence speeds of the two algorithms and present them in Tables3 and 4. The reported run-times and iteration times are for running the two algorithms of a synthetic 2-processor and 4-processor with 7 frequency levels machine where 12 and 24 VMs are executed in parallel. The RT and EC in Tables 3 and 4 represent running time and energy consumption, respectively. We can draw three obvious conclusions: (1) the SA-based algorithm iterates significantly faster than the VDS-based algorithm which means that more iterations can be executed during the same period; (2) the VDS-based algorithm outperforms the SA-based algorithm while it leads to the same iteration times if the host is equipped with serval processors; (3) when the processor number and frequency levels are relatively small, both the two algorithms converge rapidly and obtain the close results. And the VDS-based algorithm perform better than SA-based algorithm when the number of processors is small. This conclusion suggests that the service provider may prefer the SA-based algorithm if they persist in finding the best frequency configurations.Table 3
Run-time versus SA iterations.
SA iterations
⁢2 CPUs with 12 VMs
⁢4 CPUs with 24 VMs
RT (ms)
EC (J)
RT (ms)
EC (J)
0
0
2466027
0
3210277
10
1
2397905
1
3195957
100
3
2385065
7
3117021
1000
20
2323755
50
3004518
10000
170
2301687
486
2952581
100000
1676
2293194
4895
2923625
1000000
16645
2289410
46070
2851156Table 4
Run-time versus VDS iterations.
VDS iterations
⁢2 CPUs with 12 VMs
⁢4 CPUs with 24 VMs
RT (ms)
EC (J)
RT (ms)
EC (J)
0
0
2466027
0
3210277
10
5
2379716
12
3080983
100
38
2302226
118
2926700
1000
361
2293796
1145
2859979
10000
3519
2289368
11682
2855693
100000
35245
2289438
115659
2843434
1000000
349465
2289410
1140554
2848026Notice that, in this experiment, we use a very extreme set-up where a 4-processor host is enforced to run as much as 24 VMs at the same time, which means a processor must be responsible for 6 VMs on average. In fact, in the real datacenters, it can be expected that the average VM number on a single processor is far less than 6. Thus our algorithm can run efficiently enough to serve for our online VM scheduling algorithm and obtain an accepted result within 1 second which is close to results of more iterations.


### 7.3. Experiments in Real Environment

Our real experimental environment has three servers and a controller on a virtual machine. The power is measured by Aitek Power Analyzer AWE2101. Each R720 server whose details are shown in Table1 runs the kPP algorithm to predict energy and control processors’ speed. We combine the kPP algorithm with the random (Ran) and first-fit (FF) VM scheduling. Therandom scheme allocates the coming task to the processor randomly from the subset of processors which can offload the new task without causing any violations of QoS requirements. Thefirst-fit scheme gives each processor an index and allocates the coming task to the processor with smallest index who can offload the new task without causing any violations of QoS requirements. Meanwhile, the proposed global assignment (MC) is also combined with the default DVFS controller Ondemand [38] (DEF) in Linux. The two-tier energy-aware resource management proposed in this paper is represented byMC-kPP. We compare these six strategies to evaluate the performance of our solution on energy savings. For each VM, its execution time is generated uniformly at random between aminimum andmaximum living time represented by E
T
m
i
n and E
T
m
a
x, respectively. The deadline of a VM is set from 1 to 1.5 times longer to its execution time randomly. Moreover, their utilizations requirements follow the normal distribution with μ
=
0.75 and σ
=
1. In addition, the arriving times of VMs follow a Poisson distribution with different average rates.In these experiments, the iteration times are 10000 for SA-based kPP and 1000 for VDS-based kPP and the number of neighbors in VDS-based kPP algorithm is 20. The results of SA-based and VDS-based algorithms are very close, so we show the results of VDS-based kPP algorithm in Figure5 whose legend represents different numbers of VMs. Meanwhile, the size of candidates in MC algorithm is equal to the number of servers. As we can see in Figure 5, the energy savings of our solution can reach from 8% to 17% in the real environment with 3 servers.Figure 5
Energy consumption of real system. The legend in (a) and (b) means that the number of VMs needs to be allocated.
(a)
E
T
m
i
n
=
600
,
E
T
m
a
x
=
3600
(b)
E
T
m
i
n
=
600
,
E
T
m
a
x
=
7200


### 7.4. Simulation Results

Due to the inaccessibility of a large scale datacenter, we conduct the simulations to evaluate MC-kPP solution in a larger cluster. We model Dell R710 servers to service the dynamically arriving VMs. Meanwhile, the attributes of generated VMs are the same as the attributes introduced in Section7.3.As we can see in Figure6(a), the local kPP algorithm can reduce energy consumption of a specific server compared to Ondemand strategy. In addition, the influences of global scheduling algorithm are greater than the influences of local DVFS controller on energy savings when different scheduling algorithms are applied. The lengths of VMs in Figure 6(b) are generated uniformly and randomly between 600 and 7200 seconds. The legend in Figure 6(b) represents the arriving ratio of VMs in one minute. The results show an increasing tendency of the energy saving ratio with the increments of VM numbers and the best result can reach about 28%. In Figure 6(c), we investigate the influence of lengths of VMs; VMs are generated in different lengths which are shown in the legend. As shown in Figure 6(c), MC-kPP can also save more energy when the VMs become more. At the same time, MC-kPP performs better when the average execution time of VMs becomes longer, because the influence of local kPP algorithm itself becomes smaller and the effectiveness of frequencies scaling becomes more obvious. In addition, the size of subset in MC algorithm is also investigated in Figure 6(d); the energy consumption of kPP algorithm in local machine is below 0.5% of total energy consumption when the average execution time is long. With the increment of subset size, the performance of MC-kPP is improved because a better server can be found in a larger scale. We also evaluate the effectiveness of MC-kPP in different scales of data centers ranging from 50 to 5000 servers with different features of arriving VMs. According to the results of Figure 7, the MC-kPP outperforms other strategies in different scales of datacenters, which can reach about 25% energy savings. With the increasement of host numbers and VM numbers, MC-kPP performs stably in different scenarios.Figure 6
Performance evaluation on different aspects. The legend in (a) represents the “server numbers-total VM number.” The legend in (b) represents the “VM request number arriving in a minute.” The legend in (c) and (d) represents the “(minimum living time, maximum living time).”
(a)
Energy saving
(b)
Arriving ratios
(c)
VM lengths
(d)
Influence of subset sizeFigure 7
Energy consumption of different scale of datacenters with different number of VMs.
(a)
50 hosts
(b)
1000 hosts
(c)
3000 hosts
(d)
5000 hosts


## 7.1. Evaluating Power Prediction

The energy prediction of server depends on the accuracy of power prediction under different utilizations and frequencies. We have evaluated the multiprocessor power prediction method by comparing the real power consumption to the estimation of power model in different status for a specific host. The real experimental environment is shown in Figure4. The details of server R710 used in our paper are shown in Table 1. We explore the real power consumption R710 and use the first seven steps when we evaluate the power model because the last frequency is very close to the frequency 2.39 GHz. The power consumption of the host when both processors are fully utilized at frequency level 2.39 GHz is 192 Watt and the static power when the system is not idle is 110 Watt. The proportional coefficient α
=
2.33135 is obtained and calibrated by offline experiments.Figure 4
Real system architecture.For evaluating the multiprocessor power prediction, we randomly select some frequencies and utilizations of two processors and use power model to estimate the power consumption. At the same time, we measure the real power consumption of R710 server with the same frequencies and utilizations of processors and results are shown in Table2. We use the Aitek AWE 2101 power analyzer to measure power. Table 2 shows that the estimated power is very close to the real power consumption of the server with the same utilizations and frequencies of different processors.Table 2
Power comparison.
Frequencies (GHz)
Utilizations
Power (Watt)
Error
C
P
U
1
C
P
U
2
C
P
U
1
C
P
U
2
Estimation
Real
1.60
2.00
61%
87%
145.33
147.01
−1.14%
1.73
2.13
95%
84%
156.45
157.81
−0.86%
1.86
1.73
19%
14%
117.50
117.03
+0.40%
2.00
1.60
59%
9%
127.96
128.32
−0.28%
2.13
2.13
61%
84%
155.67
155.68
+0.00%
2.13
1.86
58%
57%
141.94
142.68
−0.52%
2.26
2.00
58%
30%
139.10
137.89
+0.87%
2.26
2.39
98%
81%
178.21
181.69
+1.91%
2.39
1.60
92%
18%
150.87
149.79
+0.72%
2.39
2.13
12%
59%
133.48
133.15
+0.25%


## 7.2. Convergence Speed

In this subsection, we compare the convergence speeds of the two algorithms and present them in Tables3 and 4. The reported run-times and iteration times are for running the two algorithms of a synthetic 2-processor and 4-processor with 7 frequency levels machine where 12 and 24 VMs are executed in parallel. The RT and EC in Tables 3 and 4 represent running time and energy consumption, respectively. We can draw three obvious conclusions: (1) the SA-based algorithm iterates significantly faster than the VDS-based algorithm which means that more iterations can be executed during the same period; (2) the VDS-based algorithm outperforms the SA-based algorithm while it leads to the same iteration times if the host is equipped with serval processors; (3) when the processor number and frequency levels are relatively small, both the two algorithms converge rapidly and obtain the close results. And the VDS-based algorithm perform better than SA-based algorithm when the number of processors is small. This conclusion suggests that the service provider may prefer the SA-based algorithm if they persist in finding the best frequency configurations.Table 3
Run-time versus SA iterations.
SA iterations
⁢2 CPUs with 12 VMs
⁢4 CPUs with 24 VMs
RT (ms)
EC (J)
RT (ms)
EC (J)
0
0
2466027
0
3210277
10
1
2397905
1
3195957
100
3
2385065
7
3117021
1000
20
2323755
50
3004518
10000
170
2301687
486
2952581
100000
1676
2293194
4895
2923625
1000000
16645
2289410
46070
2851156Table 4
Run-time versus VDS iterations.
VDS iterations
⁢2 CPUs with 12 VMs
⁢4 CPUs with 24 VMs
RT (ms)
EC (J)
RT (ms)
EC (J)
0
0
2466027
0
3210277
10
5
2379716
12
3080983
100
38
2302226
118
2926700
1000
361
2293796
1145
2859979
10000
3519
2289368
11682
2855693
100000
35245
2289438
115659
2843434
1000000
349465
2289410
1140554
2848026Notice that, in this experiment, we use a very extreme set-up where a 4-processor host is enforced to run as much as 24 VMs at the same time, which means a processor must be responsible for 6 VMs on average. In fact, in the real datacenters, it can be expected that the average VM number on a single processor is far less than 6. Thus our algorithm can run efficiently enough to serve for our online VM scheduling algorithm and obtain an accepted result within 1 second which is close to results of more iterations.


## 7.3. Experiments in Real Environment

Our real experimental environment has three servers and a controller on a virtual machine. The power is measured by Aitek Power Analyzer AWE2101. Each R720 server whose details are shown in Table1 runs the kPP algorithm to predict energy and control processors’ speed. We combine the kPP algorithm with the random (Ran) and first-fit (FF) VM scheduling. Therandom scheme allocates the coming task to the processor randomly from the subset of processors which can offload the new task without causing any violations of QoS requirements. Thefirst-fit scheme gives each processor an index and allocates the coming task to the processor with smallest index who can offload the new task without causing any violations of QoS requirements. Meanwhile, the proposed global assignment (MC) is also combined with the default DVFS controller Ondemand [38] (DEF) in Linux. The two-tier energy-aware resource management proposed in this paper is represented byMC-kPP. We compare these six strategies to evaluate the performance of our solution on energy savings. For each VM, its execution time is generated uniformly at random between aminimum andmaximum living time represented by E
T
m
i
n and E
T
m
a
x, respectively. The deadline of a VM is set from 1 to 1.5 times longer to its execution time randomly. Moreover, their utilizations requirements follow the normal distribution with μ
=
0.75 and σ
=
1. In addition, the arriving times of VMs follow a Poisson distribution with different average rates.In these experiments, the iteration times are 10000 for SA-based kPP and 1000 for VDS-based kPP and the number of neighbors in VDS-based kPP algorithm is 20. The results of SA-based and VDS-based algorithms are very close, so we show the results of VDS-based kPP algorithm in Figure5 whose legend represents different numbers of VMs. Meanwhile, the size of candidates in MC algorithm is equal to the number of servers. As we can see in Figure 5, the energy savings of our solution can reach from 8% to 17% in the real environment with 3 servers.Figure 5
Energy consumption of real system. The legend in (a) and (b) means that the number of VMs needs to be allocated.
(a)
E
T
m
i
n
=
600
,
E
T
m
a
x
=
3600
(b)
E
T
m
i
n
=
600
,
E
T
m
a
x
=
7200


## 7.4. Simulation Results

Due to the inaccessibility of a large scale datacenter, we conduct the simulations to evaluate MC-kPP solution in a larger cluster. We model Dell R710 servers to service the dynamically arriving VMs. Meanwhile, the attributes of generated VMs are the same as the attributes introduced in Section7.3.As we can see in Figure6(a), the local kPP algorithm can reduce energy consumption of a specific server compared to Ondemand strategy. In addition, the influences of global scheduling algorithm are greater than the influences of local DVFS controller on energy savings when different scheduling algorithms are applied. The lengths of VMs in Figure 6(b) are generated uniformly and randomly between 600 and 7200 seconds. The legend in Figure 6(b) represents the arriving ratio of VMs in one minute. The results show an increasing tendency of the energy saving ratio with the increments of VM numbers and the best result can reach about 28%. In Figure 6(c), we investigate the influence of lengths of VMs; VMs are generated in different lengths which are shown in the legend. As shown in Figure 6(c), MC-kPP can also save more energy when the VMs become more. At the same time, MC-kPP performs better when the average execution time of VMs becomes longer, because the influence of local kPP algorithm itself becomes smaller and the effectiveness of frequencies scaling becomes more obvious. In addition, the size of subset in MC algorithm is also investigated in Figure 6(d); the energy consumption of kPP algorithm in local machine is below 0.5% of total energy consumption when the average execution time is long. With the increment of subset size, the performance of MC-kPP is improved because a better server can be found in a larger scale. We also evaluate the effectiveness of MC-kPP in different scales of data centers ranging from 50 to 5000 servers with different features of arriving VMs. According to the results of Figure 7, the MC-kPP outperforms other strategies in different scales of datacenters, which can reach about 25% energy savings. With the increasement of host numbers and VM numbers, MC-kPP performs stably in different scenarios.Figure 6
Performance evaluation on different aspects. The legend in (a) represents the “server numbers-total VM number.” The legend in (b) represents the “VM request number arriving in a minute.” The legend in (c) and (d) represents the “(minimum living time, maximum living time).”
(a)
Energy saving
(b)
Arriving ratios
(c)
VM lengths
(d)
Influence of subset sizeFigure 7
Energy consumption of different scale of datacenters with different number of VMs.
(a)
50 hosts
(b)
1000 hosts
(c)
3000 hosts
(d)
5000 hosts


## 8. Conclusions

In this paper, we propose a cooperative two-tier energy-efficient strategy to manage the VM allocations and adapt frequencies scaling for saving energy. A frequency scaling algorithm is proposed based on the practical power and energy prediction. The Global Scheduler collaborates with local DVFS controller to assign VMs and save overall energy. In addition, two heuristic algorithms are provided for searching the optimal solutions which predict minimum energy consumption. The time complexities of both the algorithms are acceptable with satisfactory results according to the experiments. Finally, the real experiment results justify the effectiveness of MC-kPP.



---

*Source: 4386362-2016-10-03.xml*