# FP-ABC: Fast and Parallel ABC Based Energy-Efficiency Live VM Allocation Policy in Data Centers

Authors: Jianhua Jiang; Yunzhao Feng; Milan Parmar; Keqin Li
Journal: Scientific Programming
 (2016)

---

## Abstract

Virtual machine (VM) technology is one of the energy-efficiency approaches to save energy with acceptable quality of service (QoS). In our previous studies, Artificial Bee Colony (ABC) based VM allocation policy can make a good tradeoff between performance and energy consumption. However, there are two problems in state-of-the-art ABC based approaches: (1) how to find global optimized solutions efficiently; (2) how to minimize the decision time of VM allocation. To solve these two problems, the idea of simulated annealing is adopted to get a better global optimum, and the idea of gradient descent is applied to accelerate the speed of finding solution space in Δ
t. Compared with state-of-the-art ABC based policies, the experimental results show that the proposed algorithm efficiently reduces energy consumption and SLA violation.


---

## Body

## 1. Introduction

At present, a large number of data centers have been put into practice to support internet-based services. Many applications, such as E-commerce and scientific computing, require large-scale data-intensive computing. As data centers and their applications continue increasing, how to realize energy-efficiency computing has become a particular challenge.There are several properties of data centers making the problem of energy-efficiency computing difficult to be solved. First, workload of a data center is a priori unknown to energy-efficiency policy and will likely be variable over both time and space. As a result, a static energy-efficiency policy is insufficient. Second, customers wish their jobs can be finished in time with an acceptable price. Third, lots of computing and storage nodes are occupied in finishing their jobs in time with high energy consumption and low utilization. Therefore, finding a tradeoff between energy consumption and performance in data centers is an important issue.Many practices have been applied to achieve energy-efficiency, such as Dynamic Voltage and Frequency Scaling (DVFS) [1] and virtual machine technique [2]. Virtual machine technique can improve the utilization rate of resources, which are computing and storage nodes. For example, low-load nodes will be slept to save energy when their VMs have been migrated to other nodes with workload balance principles.VM allocation policies with workload balance are considered as one of the important energy-efficiency solutions in data centers. In CloudSim [3] simulator, the classical policies have been proposed, such as Random Selection (RS), Minimum Migration Time (MMT), and Median Absolute Deviation (MAD), to make VM allocation decisions. Zhao et al. [4] applied PSO algorithm to VM allocation policy, and they have achieved significantly on the measurement of energy-efficiency and QoS. In our previous works, Artificial Bee Colony (ABC) [5] is adopted to achieve energy-efficiency [6]. However, ABC based VM allocation policies have disadvantages of finding global solutions in time.To solve these problems, the idea of simulated annealing is adopted to find the global solution as much as possible in this paper. Based on the principle of simulated annealing, following bees have probability to jump out of local optimum to find global optimum in other solution space. Even more, the idea of gradient descent is applied to accelerate the speed of finding solution inΔ
t with QoS. Considering these two ideas, an ABC based energy-efficiency live VM allocation policy with simulated annealing and gradient descent is proposed in this paper.The main contributions of the paper are summarized as follows:(i)
The idea of gradient descent is used to solve the problem that is how to satisfy the requirement of accelerating the speed of finding local optimum solution in a data center.
(ii)
The idea of simulated annealing is adopted to getm approximate global optimums with searching in turn per Δ
t duration.
(iii)
After finding global optimums in time, the frequency of VM migrations is reduced greatly to achieve a fairly high energy-efficiency level.The rest of this paper is organized as follows. Related work is depicted in Section2. The proposed VM allocation policy is given in Section 3. Simulated experiments are done in Section 4. Discussion and analysis are given in Section 5. Section 6 concludes the paper.


## 2. Related Work

The virtual machine allocation (VM allocation) is a process that is finding the target host for the live migrant VM. Traditionally, VM allocation policy is designed to achieve high performance. Currently, energy consumption is considered as another important influencing factor to evaluate the reasonability of VM allocation policy. Therefore, performance and energy consumption are two major influencing factors to construct energy-efficiency evaluation model.Fan et al. [7] found a strong correlation between single server and CPU utilization rate; that is, there is a direct linear correlation between CPU utilization rate and the server’s energy consumption. The higher the CPU utilization rate is, the more the energy consumption is. This is represented by a host energy evaluation model:(1)
P
t
o
t
a
l
=
P
i
d
l
e
+
P
b
u
s
y
-
P
i
d
l
e
μ
c
p
u
,where P
t
o
t
a
l represents the total energy consumption of a host, P
i
d
l
e represents the energy consumption of an idle host, P
b
u
s
y represents the energy consumption of a high load host, and μ
c
p
u indicates the CPU utilization rate of a host. But it cannot measure the nonlinear CPU utilization rate.Boglazov [8] proposed another empirical nonlinear model to evaluate the energy consumption of a host:(2)
P
t
o
t
a
l
=
P
i
d
l
e
+
P
b
u
s
y
-
P
i
d
l
e
2
μ
c
p
u
-
μ
c
p
u
γ
,where γ represents calibration parameters for minimizing the squared error, which is obtained by experiments.For the cost of energy consumption from data centers, researchers have found a variety of efficient policies to reduce the cost of energy and keep a relatively high QoS level.Deng et al. [9] proposed the concept of green data centers, which means low energy consumption, low cost, and low levels of environment pollution. Fiandrino et al. [10] proposed the model of energy consumption for VM migration, which can reduce the cost of energy consumption of data centers to achieve workload balance. However, they did not discuss the problem of finding global optimum and unsuitable VM migration. Nakada and Hirofuchi [11] optimized the number of physical hosts and reduced the frequency of virtual machine migrations. They made Service Level Agreement (SLA) as an important influencing factor to measure the optimal results and also placed VM migration as a multiobjective optimization issue.Nishant et al. [12] utilized the ant colony algorithm to solve the problem of VM migration. Each ant only updates its local data, which leads to the low rate of convergence. Jeyarani et al. [13] presented SAPSO to realize dynamic VM scheduling in data centers. SAPSO promptly detects and efficiently tracks the changing optimum that represents target servers for VM placement. However, the idea did not take future workload into account. From the perspective of long operation, the policy may incur additional costs.Previously, our research focuses on making use of ABC algorithm to solve the problem of VM allocation, but it is insufficient on the speed of convergence for findingm local optimums in data centers. When dealing with the same volume of jobs, the higher the energy-efficiency level of target host is, the less it costs. As we all know, the energy-efficiency level will be decreased rapidly when the workload of a target host is larger than a certain critical value. Therefore, it is important to achieve a fairly high energy-efficiency level in data centers by making an effective live VM allocation policy. In our previous researches, ABC based energy-efficiency live VM allocation policy has been proposed. However, there are still two problems which need to be solved in Section 1.


## 3. ABC Based Live VM Allocation Policy with Simulated Annealing and Gradient Descent

Workload balance in data centers can save energy by migrating VMs to target hosts, and the key is to assign VM to the optimal target host [14]. To achieve the goal of saving energy in data centers, we introduce an ABC algorithm to seek the best target hosts. However, Bi and Wang [15] found that an ABC algorithm is easy to fall into local optimum. To solve this problem, simulated annealing makes the scouts jump out of local optimal solution space and then optimize the optimal solution within multiple iterations. The following paper will elaborate it from two aspects, one is the energy evaluation model of data centers, and the other is an enhanced energy-efficiency live VM allocation policy.


### 3.1. Data Center Energy Evaluation Model

In the live VM allocation process, we want to assess the cost that the VM needs to be migrated to the target host. We useP
d
i
f
f, which represents difference in the energy consumption, to evaluate virtual machine migration process cost:(3)
P
a
f
t
e
r
=
P
i
d
l
e
+
P
b
u
s
y
-
P
i
d
l
e
2
μ
c
p
u
_
a
f
t
e
r
-
μ
c
p
u
_
a
f
t
e
r
γ
P
n
o
w
=
P
i
d
l
e
+
P
b
u
s
y
-
P
i
d
l
e
2
μ
c
p
u
_
n
o
w
-
μ
c
p
u
_
n
o
w
γ
P
d
i
f
f
=
2
P
b
u
s
y
-
P
i
d
l
e
μ
c
p
u
_
a
f
t
e
r
-
μ
c
p
u
_
n
o
w
+
P
b
u
s
y
-
P
i
d
l
e
μ
c
p
u
_
n
o
w
γ
-
μ
c
p
u
_
a
f
t
e
r
γ
,where P
a
f
t
e
r corresponds to the energy consumption of a target host after receiving VM and P
n
o
w means the current energy consumption of the target host.On the basis of the energy evaluation model, the metric of fitness is defined as in(4)
F
σ
,
ω
=
tan
⁡
θ
=
E
σ
-
E
ω
x
σ
-
x
ω
2
+
y
σ
-
y
ω
2
,where E corresponds to the energy consumption and σ and ω mean two different physical hosts.


### 3.2. Formal Problem

We formalized the problem as migratingn virtual machines to m hosts. Its solution is represented as n-dimensional vector, where each element represents a target host. We can describe the problem as to find a virtual machine allocation policy; we define it as A, which is to satisfy the demand to maximize computing performance while minimizing energy consumption. To solve this problem, we define an array of S
=
{
H
,
V
M
,
E
,
A
}. H represents m physical hosts; H
(
m
,
t
)
=
{
H
1
,
H
2
,
H
3
,
…
,
H
m
}, where t means the VM migration time and VM represents n VMs. V
M
(
n
,
t
,
Δ
t
)
=
{
V
M
1
,
V
M
2
,
…
,
V
M
n
} is expressed as n VM migration demand in Δ
t. E
(
m
,
t
)
=
{
E
1
,
E
2
,
E
3
,
…
,
E
m
} represents the total energy consumption of m hosts. The purpose of the algorithm is to find the host location for maximum performance and minimize energy consumption. There are multiple locations to meet the demand, so we define as (6), i
∈
{
1,2
,
3
,
…
,
n
}, j
∈
{
1,2
,
3
,
…
,
m
}, r
∈
{
1,2
,
3
,
…
,
s
}, φ represents a different location selected that is migrating VM to number j host, and it has the following relationship:(5)
φ
=
1
if  VM  has  been  allocated  to
H
j
and
r
c
r
V
M
≤
a
c
r
H
j
0
if  VM  has  been  allocated  to
H
j
and
r
c
r
V
M
≥
a
c
r
H
j
I
n
v
a
l
i
d
if  VM  has  not  been  allocated  to
H
j
,
(6)
Z
s
=
∑
i
=
1
n
∑
j
=
1
m
φ
,
(7)
Δ
E
=
δ
k
r
-
δ
k
-
1
r
,
(8)
δ
E
=
∑
k
=
1
m
δ
k
r
-
δ
k
-
1
r
,where r
c
r
V
M represents the smallest computing nodes of VMs and a
c
r
H
j marks the available computing resources of jth host. There are o positions for max φ that can be selected in S placement policy. It can be expressed as P
S
=
{
m
,
V
M
,
o
,
t
}.The second parameter is based on energy consumption;A
=
{
m
,
V
M
,
r
,
t
+
t
k
}, where r corresponds to any placement of o and k represents the host number. The position o, when selecting the host number k, is represented as A
=
{
m
,
V
M
,
r
,
t
+
t
k
}. Their energy is represented as δ
k
γ, and it means, according to r, the total energy consumption that is migrating VMs to the host. Hence migrating VM energy consumption can be expressed as (7). In order to achieve better energy-efficiency, energy-efficiency VM migration can be represented as (8). In other words, in order to minimize energy consumption, we must minimize the value of δ
E.


### 3.3. Expressed Solutions

In order to achieve an ABC based energy-efficiency algorithm, representation of the solution becomes a priority. Solutions expressed represent the correspondence between the optimal bee and problem spaces found by ABC based algorithm. In this paper, there arenVMs to be migrated to m target hosts, so this is an n-dimensional vector problem. Each dimension is an integer from 0 to m
-
1. Position vector is represented as g
B
e
s
t
i
=
{
g
B
i
1
,
g
B
i
2
,
…
,
g
B
i
D
}. v
i
j shows a nectar of the ith (The ith solution vector) position of the jth (jth VMs to be migrated) dimension. Velocity vector is represented as v
i
=
{
v
i
1
,
v
i
2
,
…
,
v
i
j
,
…
,
v
i
D
}; v
i
j shows j-dimensional speed of the ith nectar source. p
B
e
s
t
i
=
{
p
B
i
1
,
p
B
i
2
,
…
,
p
B
i
D
} shows that the current optimal location is found, and best position vector is represented as g
B
e
s
t
i
=
{
g
B
i
1
,
g
B
i
2
,
…
,
g
B
i
D
}, which is regarded as the current best target location in the population.


### 3.4. The Main Idea of ABC Based Energy-Efficiency Live VM Allocation Policy

An ABC based live VM allocation policy has been considered as a better energy-efficiency policy. According to [15], it can reduce 25%~30% energy cost with acceptable SLA violation. However, in big data time, the ABC based energy-efficiency live VM allocation policy will face huge amount of data-intensive jobs and need to get the best VM allocation decision in time.To solve these problems, we have improved the ABC algorithm in two ways. First, the traditional speed of ABC based algorithm uses fitness function to find local optima which need to be optimized. Therefore, the idea of gradient descent is applied to getting the local optima rapidly. Second, the traditional ABC based algorithm maybe falls into the local optima in a time window ofΔ
t. Therefore, simulated annealing is applied to finding the global optima.


### 3.5. Improved Artificial Bees Live VM Allocation Policy

As illustrated in Figure1, the FP-ABC VM allocation policy can be described as shown in Algorithm 1.Algorithm 1
Input: the candidate target host queue CTHQ = h
1
,
h
2
,
…
,
h
n
Output: BestTargetHost
Pseudo-code as follows:
(1) CTHQ = h
1
,
h
2
,
…
,
h
n are marked unexplored; Set the SimMigTaskQueue;
(2) Set the maximum temperature (T_max), T = T_max and T_min;
(3) Initialize CandidateTargetHostQueue;
(4) Set NeighborHostQueue to be Null, and set BestTargetHost also to be Null;
(5) Set the number of following bees as K;
(6) Set the initial time point t, // set the number of n VM migration requests;
(7) While (T  ≥  T_min)
(8)      Select an undetected host randomly, and send scouts in candidate target host queue;
(9)      do
(10)  Parbegin
(12)        Calculates the host power // Sent K following bees near the scouts randomly
(13)        Use of gradient descent, calculation and evaluation function
J
E
=
1
2
∑
i
=
1
m
E
x
i
,
y
i
2
(14)    If (J
(
E
)
=
0)
(1
5)        Output the host number of current nearby following bee // find current local optima
(1
6)    else
(1
7)        in accordance with the rules of
min
⁡
f
x
i
+
α
∂
∂
x
i
E
x
i
,
y
j, min
⁡
f
y
j
+
α
∂
∂
x
i
E
x
i
,
y
j
to apply the program of the gradient descent
(18)          x
i
+
1
=
x
i
-
α
∂
∂
x
i
E
x
i
,
y
j,  y
j
+
1
=
y
j
-
α
∂
∂
y
j
E
x
i
,
y
j
(19)    Endif
(2
0)        use
E
x
i
-
α
∂
∂
x
i
E
=
min
α
>
0
⁡
E
x
i
-
α
∂
∂
x
i
E  to update α
k;
(2
1)    ParEnd
(2
2)    T
k
=
T
0
/
k
m // Make use of simulated annealing.
(2
3) Update fitness value,
F
i
,
j
=
tan
⁡
θ
=
E
σ
-
E
ω
(
x
i
-
x
j
)
2
+
(
y
i
-
y
j
)
2;
(2
4) While (F
i
,
j
=
0)
(2
5)  Following bees have returned, update current best target host;
(2
6)  Update unexplored candidate target host group;
(27)  Update the nearby hosts, candidate host queue and Top-N current best target host queue
(28)  Recording time t;
(29) Endwhile
(30) Δ
E
=
E
-
E
0 // Out of the current local optimal solution based on the Metropolis criterion
(31) If(exp
⁡
(
-
Δ
E
/
T
)
>
r
a
n
d
o
m
(
0,1
)
)
(3
2)  Return to Line
(
7
)
(3
3) else
(34)  Output BestTargetHost
(3
5) Endwhile
(3
6) Output similar target hostsFigure 1
Flowchart of FP-ABC VM allocation policy.


## 3.1. Data Center Energy Evaluation Model

In the live VM allocation process, we want to assess the cost that the VM needs to be migrated to the target host. We useP
d
i
f
f, which represents difference in the energy consumption, to evaluate virtual machine migration process cost:(3)
P
a
f
t
e
r
=
P
i
d
l
e
+
P
b
u
s
y
-
P
i
d
l
e
2
μ
c
p
u
_
a
f
t
e
r
-
μ
c
p
u
_
a
f
t
e
r
γ
P
n
o
w
=
P
i
d
l
e
+
P
b
u
s
y
-
P
i
d
l
e
2
μ
c
p
u
_
n
o
w
-
μ
c
p
u
_
n
o
w
γ
P
d
i
f
f
=
2
P
b
u
s
y
-
P
i
d
l
e
μ
c
p
u
_
a
f
t
e
r
-
μ
c
p
u
_
n
o
w
+
P
b
u
s
y
-
P
i
d
l
e
μ
c
p
u
_
n
o
w
γ
-
μ
c
p
u
_
a
f
t
e
r
γ
,where P
a
f
t
e
r corresponds to the energy consumption of a target host after receiving VM and P
n
o
w means the current energy consumption of the target host.On the basis of the energy evaluation model, the metric of fitness is defined as in(4)
F
σ
,
ω
=
tan
⁡
θ
=
E
σ
-
E
ω
x
σ
-
x
ω
2
+
y
σ
-
y
ω
2
,where E corresponds to the energy consumption and σ and ω mean two different physical hosts.


## 3.2. Formal Problem

We formalized the problem as migratingn virtual machines to m hosts. Its solution is represented as n-dimensional vector, where each element represents a target host. We can describe the problem as to find a virtual machine allocation policy; we define it as A, which is to satisfy the demand to maximize computing performance while minimizing energy consumption. To solve this problem, we define an array of S
=
{
H
,
V
M
,
E
,
A
}. H represents m physical hosts; H
(
m
,
t
)
=
{
H
1
,
H
2
,
H
3
,
…
,
H
m
}, where t means the VM migration time and VM represents n VMs. V
M
(
n
,
t
,
Δ
t
)
=
{
V
M
1
,
V
M
2
,
…
,
V
M
n
} is expressed as n VM migration demand in Δ
t. E
(
m
,
t
)
=
{
E
1
,
E
2
,
E
3
,
…
,
E
m
} represents the total energy consumption of m hosts. The purpose of the algorithm is to find the host location for maximum performance and minimize energy consumption. There are multiple locations to meet the demand, so we define as (6), i
∈
{
1,2
,
3
,
…
,
n
}, j
∈
{
1,2
,
3
,
…
,
m
}, r
∈
{
1,2
,
3
,
…
,
s
}, φ represents a different location selected that is migrating VM to number j host, and it has the following relationship:(5)
φ
=
1
if  VM  has  been  allocated  to
H
j
and
r
c
r
V
M
≤
a
c
r
H
j
0
if  VM  has  been  allocated  to
H
j
and
r
c
r
V
M
≥
a
c
r
H
j
I
n
v
a
l
i
d
if  VM  has  not  been  allocated  to
H
j
,
(6)
Z
s
=
∑
i
=
1
n
∑
j
=
1
m
φ
,
(7)
Δ
E
=
δ
k
r
-
δ
k
-
1
r
,
(8)
δ
E
=
∑
k
=
1
m
δ
k
r
-
δ
k
-
1
r
,where r
c
r
V
M represents the smallest computing nodes of VMs and a
c
r
H
j marks the available computing resources of jth host. There are o positions for max φ that can be selected in S placement policy. It can be expressed as P
S
=
{
m
,
V
M
,
o
,
t
}.The second parameter is based on energy consumption;A
=
{
m
,
V
M
,
r
,
t
+
t
k
}, where r corresponds to any placement of o and k represents the host number. The position o, when selecting the host number k, is represented as A
=
{
m
,
V
M
,
r
,
t
+
t
k
}. Their energy is represented as δ
k
γ, and it means, according to r, the total energy consumption that is migrating VMs to the host. Hence migrating VM energy consumption can be expressed as (7). In order to achieve better energy-efficiency, energy-efficiency VM migration can be represented as (8). In other words, in order to minimize energy consumption, we must minimize the value of δ
E.


## 3.3. Expressed Solutions

In order to achieve an ABC based energy-efficiency algorithm, representation of the solution becomes a priority. Solutions expressed represent the correspondence between the optimal bee and problem spaces found by ABC based algorithm. In this paper, there arenVMs to be migrated to m target hosts, so this is an n-dimensional vector problem. Each dimension is an integer from 0 to m
-
1. Position vector is represented as g
B
e
s
t
i
=
{
g
B
i
1
,
g
B
i
2
,
…
,
g
B
i
D
}. v
i
j shows a nectar of the ith (The ith solution vector) position of the jth (jth VMs to be migrated) dimension. Velocity vector is represented as v
i
=
{
v
i
1
,
v
i
2
,
…
,
v
i
j
,
…
,
v
i
D
}; v
i
j shows j-dimensional speed of the ith nectar source. p
B
e
s
t
i
=
{
p
B
i
1
,
p
B
i
2
,
…
,
p
B
i
D
} shows that the current optimal location is found, and best position vector is represented as g
B
e
s
t
i
=
{
g
B
i
1
,
g
B
i
2
,
…
,
g
B
i
D
}, which is regarded as the current best target location in the population.


## 3.4. The Main Idea of ABC Based Energy-Efficiency Live VM Allocation Policy

An ABC based live VM allocation policy has been considered as a better energy-efficiency policy. According to [15], it can reduce 25%~30% energy cost with acceptable SLA violation. However, in big data time, the ABC based energy-efficiency live VM allocation policy will face huge amount of data-intensive jobs and need to get the best VM allocation decision in time.To solve these problems, we have improved the ABC algorithm in two ways. First, the traditional speed of ABC based algorithm uses fitness function to find local optima which need to be optimized. Therefore, the idea of gradient descent is applied to getting the local optima rapidly. Second, the traditional ABC based algorithm maybe falls into the local optima in a time window ofΔ
t. Therefore, simulated annealing is applied to finding the global optima.


## 3.5. Improved Artificial Bees Live VM Allocation Policy

As illustrated in Figure1, the FP-ABC VM allocation policy can be described as shown in Algorithm 1.Algorithm 1
Input: the candidate target host queue CTHQ = h
1
,
h
2
,
…
,
h
n
Output: BestTargetHost
Pseudo-code as follows:
(1) CTHQ = h
1
,
h
2
,
…
,
h
n are marked unexplored; Set the SimMigTaskQueue;
(2) Set the maximum temperature (T_max), T = T_max and T_min;
(3) Initialize CandidateTargetHostQueue;
(4) Set NeighborHostQueue to be Null, and set BestTargetHost also to be Null;
(5) Set the number of following bees as K;
(6) Set the initial time point t, // set the number of n VM migration requests;
(7) While (T  ≥  T_min)
(8)      Select an undetected host randomly, and send scouts in candidate target host queue;
(9)      do
(10)  Parbegin
(12)        Calculates the host power // Sent K following bees near the scouts randomly
(13)        Use of gradient descent, calculation and evaluation function
J
E
=
1
2
∑
i
=
1
m
E
x
i
,
y
i
2
(14)    If (J
(
E
)
=
0)
(1
5)        Output the host number of current nearby following bee // find current local optima
(1
6)    else
(1
7)        in accordance with the rules of
min
⁡
f
x
i
+
α
∂
∂
x
i
E
x
i
,
y
j, min
⁡
f
y
j
+
α
∂
∂
x
i
E
x
i
,
y
j
to apply the program of the gradient descent
(18)          x
i
+
1
=
x
i
-
α
∂
∂
x
i
E
x
i
,
y
j,  y
j
+
1
=
y
j
-
α
∂
∂
y
j
E
x
i
,
y
j
(19)    Endif
(2
0)        use
E
x
i
-
α
∂
∂
x
i
E
=
min
α
>
0
⁡
E
x
i
-
α
∂
∂
x
i
E  to update α
k;
(2
1)    ParEnd
(2
2)    T
k
=
T
0
/
k
m // Make use of simulated annealing.
(2
3) Update fitness value,
F
i
,
j
=
tan
⁡
θ
=
E
σ
-
E
ω
(
x
i
-
x
j
)
2
+
(
y
i
-
y
j
)
2;
(2
4) While (F
i
,
j
=
0)
(2
5)  Following bees have returned, update current best target host;
(2
6)  Update unexplored candidate target host group;
(27)  Update the nearby hosts, candidate host queue and Top-N current best target host queue
(28)  Recording time t;
(29) Endwhile
(30) Δ
E
=
E
-
E
0 // Out of the current local optimal solution based on the Metropolis criterion
(31) If(exp
⁡
(
-
Δ
E
/
T
)
>
r
a
n
d
o
m
(
0,1
)
)
(3
2)  Return to Line
(
7
)
(3
3) else
(34)  Output BestTargetHost
(3
5) Endwhile
(3
6) Output similar target hostsFigure 1
Flowchart of FP-ABC VM allocation policy.


## 4. Results

### 4.1. Experimental Environment

The cloud simulator of CloudSim3.0 [3] is used to conduct a simulation experiment. Java programming language is adopted to get results from MyEclipse9.0. The experiment is done on Lenovo™ desktop. Its system parameters as follows:CPU: Intel(R) Core(™) i7-3770 CPU @ 3.40 GHz.
RAM: 4.00 GB.
System type: 64-bit operating system.
OS: Windows 7.PlanetLab [8] is a group of computers, which is tested for computer networking and distributed systems research. It was established in 2002 by Professor Larry L. Peterson and Professor David Culler, and it was composed of 1353 nodes at 717 sites worldwide in January 2016 [16]. 10-day sample data in PlantLab cloud computing environment are chosen as experimental data as shown in Table 1 [8]. Simulation data center is composed of 800 heterogeneous physical nodes, and half of these nodes are HP ProLiant ML100 G4 server (1860 MIPS) while the other halves are HP ProLiant ML110 G5 server (2660 MIPS) [8]. Energy consumption of these two servers at different loads is shown in Table 2. Server virtual machine is set as single-core; RAM can also be classified according to the number of VMs. The following are the main types of VMs: High-CPU Medium Instance (2500 MIPS, 0.85 GB), Extra Large Instance (2000 MIPS, 3.75 GB), Small Instance (1000 MIPS, 1.7 GB), and Micro Instance (500 MIPS, 613 MB).Table 1
Characteristics of the workload data (CPU utilization rate).
Date
The number of VMs
Mean
Standard deviation
Quartile 1
Median
Quartile 3
03/03/2011
1052
12.31%
17.09%
2%
6%
15%
06/03/2011
898
11.44%
16.83%
2%
5%
13%
09/03/2011
1061
10.70%
15.57%
2%
4%
13%
22/03/2011
1516
9.26%
12.78%
2%
5%
12%
25/03/2011
1078
10.56%
14.14%
2%
6%
14%
03/04/2011
1463
12.39%
16.55%
2%
6%
17%
09/04/2011
1358
11.12%
15.09%
2%
6%
15%
11/04/2011
1233
11.56%
15.07%
2%
6%
16%
12/04/2011
1054
11.54%
15.15%
2%
6%
16%
20/04/2011
1033
10.43%
15.21%
2%
4%
12%Table 2
Power consumption by the selected servers at different workload levels in Watts.
Workload level
0%
10%
20%
30%
40%
50%
60%
70%
80%
90%
100%
HP ProLiant G4
86
89.4
92.6
96
99.5
102
106
108
112
114
117
HP ProLiant G4
93.7
97
101
105
110
116
121
125
129
133
135The simulation is performed in CloudSim3.0,Δ
t is set as 30 seconds, and its safety parameter is 1.5.


### 4.2. Evaluating the Energy Consumption of FP-ABC with Different Approaches

In Figure2, FP-ABC can reduce the energy consumption of data center by 5.1% on the base of ABC_RS. The proposed energy evaluation model can be used to evaluate different VM allocation policies. Our proposed FP-ABC policy has advantage in saving energy.Figure 2
Energy consumption of the five algorithms.


### 4.3. Evaluating the Violation Rate of SLA with Different Approaches

Service Level Agreement (SLA) represents a guarantee under certain overload performance and reliability of service. In other words the service provider and the user-defined agreements are accepted by each other. SLAV is short for Violations of SLA. ASLAV is the average rate of SLAV. The QoS will be better if its ASLAV is lower. In Figure3, FP-ABC is the last one. Among these traditional policies, THR_RS has the worst performance. And it proves that VM allocation policy of THR_RS gets higher ASLAV value. The ASLAV value of FP-ABC is 10.4%, and it means that FP-ABC can reduce energy consumption with acceptable ASLAV. Therefore, the workload balance based policy can satisfy user’s requirement of QoS.Figure 3
ASLAV metric of the five algorithms.


### 4.4. Evaluating the Effectiveness of FP-ABC with Different VM Allocation Policies

The number of VM migrations is a statistic variable to measure the VM migration times which occurred in data centers. The cost will be lower if fewer VM migrations occurred. As shown in Figure4, FP-ABC and ABC_RS can reduce the frequency of VM migrations greatly. Furthermore, FP-ABC can reduce VM migrations by nearly 6.1% when compared with ABC_RS. An unreasonable VM allocation policy will increase the frequency of VM migrations. Therefore, FP-ABC policy can find best hosts as BestTargetHostList in Δ
t. As a result, we can save more energy.Figure 4
Number of VM migrations of the five algorithms.


### 4.5. Evaluating the Energy-Efficiency of FP-ABC with Different VM Allocation Policies

In formula (9), ESV is an energy-efficiency comprehensive index. It measures the tradeoff between performance and energy consumption. As we all know, the QoS will be violated when energy is saved greatly and vice versa. Therefore, achieving a good energy-efficiency tradeoff is difficult. However, FP-ABC has a good performance in the metric of ESV depicted in Figure 5. The first reason is that FP-ABC policy can reduce the VM migration frequency to keep live workload balance in data centers; the second reason is that the proposed energy consumption evaluation model can be used to make a better evaluation of energy consumption in data centers; the third reason is that idea of simulated annealing and gradient descent can improve the performance of ABC based policy. Evaluation model [8] is presented as follows:(9)
E
S
V
=
E
C
∗
S
L
A
V
.Figure 5
ESV metric of the five algorithms.


### 4.6. Evaluating the Decision Time of FP-ABC with Different VM Allocation Policies

In Figure6, based on the index of execution time mean in Cloudsim3.0, it can reduce the decision time 85% to THR_RS, 86% to IQR_RS, 88% to MD_RS, and 13.8% to ABC_RS. Compared with these traditional migration policies, the FP-ABC is more effective to minimize the decision-making time.Figure 6
ETM metric of the five algorithms.


## 4.1. Experimental Environment

The cloud simulator of CloudSim3.0 [3] is used to conduct a simulation experiment. Java programming language is adopted to get results from MyEclipse9.0. The experiment is done on Lenovo™ desktop. Its system parameters as follows:CPU: Intel(R) Core(™) i7-3770 CPU @ 3.40 GHz.
RAM: 4.00 GB.
System type: 64-bit operating system.
OS: Windows 7.PlanetLab [8] is a group of computers, which is tested for computer networking and distributed systems research. It was established in 2002 by Professor Larry L. Peterson and Professor David Culler, and it was composed of 1353 nodes at 717 sites worldwide in January 2016 [16]. 10-day sample data in PlantLab cloud computing environment are chosen as experimental data as shown in Table 1 [8]. Simulation data center is composed of 800 heterogeneous physical nodes, and half of these nodes are HP ProLiant ML100 G4 server (1860 MIPS) while the other halves are HP ProLiant ML110 G5 server (2660 MIPS) [8]. Energy consumption of these two servers at different loads is shown in Table 2. Server virtual machine is set as single-core; RAM can also be classified according to the number of VMs. The following are the main types of VMs: High-CPU Medium Instance (2500 MIPS, 0.85 GB), Extra Large Instance (2000 MIPS, 3.75 GB), Small Instance (1000 MIPS, 1.7 GB), and Micro Instance (500 MIPS, 613 MB).Table 1
Characteristics of the workload data (CPU utilization rate).
Date
The number of VMs
Mean
Standard deviation
Quartile 1
Median
Quartile 3
03/03/2011
1052
12.31%
17.09%
2%
6%
15%
06/03/2011
898
11.44%
16.83%
2%
5%
13%
09/03/2011
1061
10.70%
15.57%
2%
4%
13%
22/03/2011
1516
9.26%
12.78%
2%
5%
12%
25/03/2011
1078
10.56%
14.14%
2%
6%
14%
03/04/2011
1463
12.39%
16.55%
2%
6%
17%
09/04/2011
1358
11.12%
15.09%
2%
6%
15%
11/04/2011
1233
11.56%
15.07%
2%
6%
16%
12/04/2011
1054
11.54%
15.15%
2%
6%
16%
20/04/2011
1033
10.43%
15.21%
2%
4%
12%Table 2
Power consumption by the selected servers at different workload levels in Watts.
Workload level
0%
10%
20%
30%
40%
50%
60%
70%
80%
90%
100%
HP ProLiant G4
86
89.4
92.6
96
99.5
102
106
108
112
114
117
HP ProLiant G4
93.7
97
101
105
110
116
121
125
129
133
135The simulation is performed in CloudSim3.0,Δ
t is set as 30 seconds, and its safety parameter is 1.5.


## 4.2. Evaluating the Energy Consumption of FP-ABC with Different Approaches

In Figure2, FP-ABC can reduce the energy consumption of data center by 5.1% on the base of ABC_RS. The proposed energy evaluation model can be used to evaluate different VM allocation policies. Our proposed FP-ABC policy has advantage in saving energy.Figure 2
Energy consumption of the five algorithms.


## 4.3. Evaluating the Violation Rate of SLA with Different Approaches

Service Level Agreement (SLA) represents a guarantee under certain overload performance and reliability of service. In other words the service provider and the user-defined agreements are accepted by each other. SLAV is short for Violations of SLA. ASLAV is the average rate of SLAV. The QoS will be better if its ASLAV is lower. In Figure3, FP-ABC is the last one. Among these traditional policies, THR_RS has the worst performance. And it proves that VM allocation policy of THR_RS gets higher ASLAV value. The ASLAV value of FP-ABC is 10.4%, and it means that FP-ABC can reduce energy consumption with acceptable ASLAV. Therefore, the workload balance based policy can satisfy user’s requirement of QoS.Figure 3
ASLAV metric of the five algorithms.


## 4.4. Evaluating the Effectiveness of FP-ABC with Different VM Allocation Policies

The number of VM migrations is a statistic variable to measure the VM migration times which occurred in data centers. The cost will be lower if fewer VM migrations occurred. As shown in Figure4, FP-ABC and ABC_RS can reduce the frequency of VM migrations greatly. Furthermore, FP-ABC can reduce VM migrations by nearly 6.1% when compared with ABC_RS. An unreasonable VM allocation policy will increase the frequency of VM migrations. Therefore, FP-ABC policy can find best hosts as BestTargetHostList in Δ
t. As a result, we can save more energy.Figure 4
Number of VM migrations of the five algorithms.


## 4.5. Evaluating the Energy-Efficiency of FP-ABC with Different VM Allocation Policies

In formula (9), ESV is an energy-efficiency comprehensive index. It measures the tradeoff between performance and energy consumption. As we all know, the QoS will be violated when energy is saved greatly and vice versa. Therefore, achieving a good energy-efficiency tradeoff is difficult. However, FP-ABC has a good performance in the metric of ESV depicted in Figure 5. The first reason is that FP-ABC policy can reduce the VM migration frequency to keep live workload balance in data centers; the second reason is that the proposed energy consumption evaluation model can be used to make a better evaluation of energy consumption in data centers; the third reason is that idea of simulated annealing and gradient descent can improve the performance of ABC based policy. Evaluation model [8] is presented as follows:(9)
E
S
V
=
E
C
∗
S
L
A
V
.Figure 5
ESV metric of the five algorithms.


## 4.6. Evaluating the Decision Time of FP-ABC with Different VM Allocation Policies

In Figure6, based on the index of execution time mean in Cloudsim3.0, it can reduce the decision time 85% to THR_RS, 86% to IQR_RS, 88% to MD_RS, and 13.8% to ABC_RS. Compared with these traditional migration policies, the FP-ABC is more effective to minimize the decision-making time.Figure 6
ETM metric of the five algorithms.


## 5. Discussion

### 5.1. The Importance of Accelerating the Process of Finding Local Optimized Target Hosts with FP-ABC

A huge number of live migrant VMs are waiting to be allocated to their best target hosts inΔ
t. Therefore, the solutions should be given in some reasonable time window. Current state-of-the-art ABC based live VM allocation policy should be improved by accelerating the speed of finding the local optimized target hosts. To solve this problem, the idea of gradient descent is adopted to ABC based live VM allocation policy. Current ABC based policy only makes the judgment based on its fitness value, without considering the requirement of speed. The idea of achieving a local solution quickly is realized by gradient descent. It will accelerate the process of searching local optimization in order to accelerate the speed of FP-ABC policy. In Section 4.6, we see that value of execution time mean is reduced when compared with 3 traditional policies and ABC_RS policy. It is significant when facing with amount of applications and also can save energy.


### 5.2. The Importance of Adopting Idea of Simulated Annealing to Find Global Optimized Target Hosts

We want to find the global optimum target host for each migrant VM in VM allocation, because the unreasonable target host will increase irrational energy consumption. In CloudSim3.0, three traditional VM migration policies are not good at finding the global optimum results, since their decision is made only by workload balance without reasonability analysis. Furthermore, the state-of-the-art ABC based policy is easy to fall into local optimum. Therefore, we add the idea of simulated annealing into ABC based policy, which can make scout bees jump out of the current solution space on a certain probability to detect other solution space.


### 5.3. Tradeoff between Energy Consumption and Service Quality

In data centers, to reduce energy consumption or improve the quality of service simply is not a good energy-saving policy, because reducing the total energy consumption will decrease service quality; that is to say, it will increase the value of SLAV. The main objective of this paper is to achieve energy efficient goal and make the value of SLAV accepted. Experimental results show that FP-ABC can save energy effectively in the balance of the EC and SLAV, which is based on formula (9) introduced in Section 4.5.


## 5.1. The Importance of Accelerating the Process of Finding Local Optimized Target Hosts with FP-ABC

A huge number of live migrant VMs are waiting to be allocated to their best target hosts inΔ
t. Therefore, the solutions should be given in some reasonable time window. Current state-of-the-art ABC based live VM allocation policy should be improved by accelerating the speed of finding the local optimized target hosts. To solve this problem, the idea of gradient descent is adopted to ABC based live VM allocation policy. Current ABC based policy only makes the judgment based on its fitness value, without considering the requirement of speed. The idea of achieving a local solution quickly is realized by gradient descent. It will accelerate the process of searching local optimization in order to accelerate the speed of FP-ABC policy. In Section 4.6, we see that value of execution time mean is reduced when compared with 3 traditional policies and ABC_RS policy. It is significant when facing with amount of applications and also can save energy.


## 5.2. The Importance of Adopting Idea of Simulated Annealing to Find Global Optimized Target Hosts

We want to find the global optimum target host for each migrant VM in VM allocation, because the unreasonable target host will increase irrational energy consumption. In CloudSim3.0, three traditional VM migration policies are not good at finding the global optimum results, since their decision is made only by workload balance without reasonability analysis. Furthermore, the state-of-the-art ABC based policy is easy to fall into local optimum. Therefore, we add the idea of simulated annealing into ABC based policy, which can make scout bees jump out of the current solution space on a certain probability to detect other solution space.


## 5.3. Tradeoff between Energy Consumption and Service Quality

In data centers, to reduce energy consumption or improve the quality of service simply is not a good energy-saving policy, because reducing the total energy consumption will decrease service quality; that is to say, it will increase the value of SLAV. The main objective of this paper is to achieve energy efficient goal and make the value of SLAV accepted. Experimental results show that FP-ABC can save energy effectively in the balance of the EC and SLAV, which is based on formula (9) introduced in Section 4.5.


## 6. Conclusions

This paper presents a new live VM allocation policy to reach as far as possible to meet the SLAV value while saving energy consumption. We proposed the state-of-the-art ABC based policy with the idea of simulated annealing and the idea of gradient descent. The idea of gradient descent is used to find the optimal solution with higher speed. And the idea of simulated annealing is used to find the global optimal solutions inΔ
t. Simulation experiment has proved that FP-ABC policy can effectively reduce energy consumption with relative high level of QoS. In addition, FP-ABC can effectively reduce the energy consumption of data centers by 5.1%, when compared with the state-of-the-art algorithm of ABC_RS.In the future, the proposed the state-of-the-art ABC based policy should be adapted to the cloud of cloud. Cloud of cloud is a new business model to get an economic data center with good service performance. The improved ABC based optimized model should be implemented in new environment.



---

*Source: 9524379-2016-07-25.xml*