# Dynamic Placement of Virtual Machines with Both Deterministic and Stochastic Demands for Green Cloud Computing

Authors: Wenying Yue; Qiushuang Chen
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Cloud computing has come to be a significant commercial infrastructure offering utility-oriented IT services to users worldwide. However, data centers hosting cloud applications consume huge amounts of energy, leading to high operational cost and greenhouse gas emission. Therefore, green cloud computing solutions are needed not only to achieve high level service performance but also to minimize energy consumption. This paper studies the dynamic placement of virtual machines (VMs) with deterministic and stochastic demands. In order to ensure a quick response to VM requests and improve the energy efficiency, a two-phase optimization strategy has been proposed, in which VMs are deployed in runtime and consolidated into servers periodically. Based on an improved multidimensional space partition model, a modified energy efficient algorithm with balanced resource utilization (MEAGLE) and a live migration algorithm based on the basic set (LMABBS) are, respectively, developed for each phase. Experimental results have shown that under different VMs’ stochastic demand variations, MEAGLE guarantees the availability of stochastic resources with a defined probability and reduces the number of required servers by 2.49% to 20.40% compared with the benchmark algorithms. Also, the difference between the LMABBS solution and Gurobi solution is fairly small, but LMABBS significantly excels in computational efficiency.


---

## Body

## 1. Introduction

Cloud computing is a new paradigm for the dynamic provisioning of computing services supported by state-of-the-art data centers. With the rapid development of cloud computing, the data centers are growing at an unprecedented rate. However, an average data center consumes as much energy as 25,000 households [1] and it was estimated that the energy consumption from data centers would have accounted for about two percent of the worldwide energy consumption by 2020 [2]. High power consumption not only produces huge operational cost for data centers, but also significantly contributes to the growing environmental issues of global warming. Therefore, green cloud computing is driven to achieve high level service performance and to minimize energy consumption.Virtual machines are attractive to modern cloud data centers because they can significantly promote the efficiency and flexibility of resource management helping to cut back the power consumptions [3–5]. However, such an incentive highly relies on a well-designed VM placement scheme [6, 7]. When multiple VMs run on the same physical host or rack, they share all the physical resources. According to how resource-intensive applications are, users may customize different types of VMs such as CPU-intensive, memory-intensive, and bandwidth-intensive VMs. If all VMs in a cloud data center have the same intensive resource, VMP is then reduced to the classical one-dimensional VM placement problem. But a cloud data center often has VMs with different resource intensities [8], and, thus, an efficient multidimensional algorithm is required for the VMs placement.In cloud data centers the VM placement problem (VMP) has been tackled in both research work [7, 9–17] and commercial products [18, 19]. In most of the research work, VMP is formulated as a multidimensional bin packing problem, aiming to minimize the number of required servers and with constraints from various management fields [4], such as the resource demands of VMs, security/isolation policies (e.g., ensuring that certain VMs will not run on the same server), and compatibility/location policies (e.g., restrict the placement of certain VMs to certain servers). Variants of the classic packing algorithms such as First Fit (FF) and First Fit Decreasing (FFD) [20] are often used to solve VMP. In particular, Li et al. [17] proposed an energy efficient algorithm with balanced resource utilization. However, in these studies, the VMs’ demands are assumed to be deterministic for all resources and these algorithms are called deterministic resource algorithms.Recent studies [11, 21–23] indicate that VMs’ demands for some resources like network bandwidth are stochastic and highly volatile. Regarding the placement of VMs with stochastic demands, the deterministic resource algorithm can be adopted by using the mean or maximum of the demand as its estimated value. But this naive approach may lead to either poor user experience or resource waste. Wang et al. [24] and Breitgand and Epstein [25] assumed the VMs’ bandwidth demand to be normally distributed. They described VMP as a stochastic bin packing problem and used improved bin packing heuristics to solve it. Nevertheless, only the network resources with stochastic demands were considered in their study while system resources with deterministic demands were not included.In reality, the VMs’ demands for all resources have different characteristics. For some resources, such as CPU and memory, VMs’ demands are constant or have a very small fluctuation and, thus, can be considered as deterministic. For other resources, such as network bandwidth, VMs’ demands are time varying and have high volatility, and, thus, can be considered as stochastic. Yet, little work has focused on the placement of VMs with both deterministic and stochastic demands. Jin et al. [26] considered both kinds of demands and proposed a polynomial time algorithm to solve the multidimensional stochastic VM placement problem. In their work, the VM deployment requests were given beforehand and the VMs were placed in a static manner. Practically, VM requests dynamically arrive at the cloud data center.Taking into account VMs’ deterministic and stochastic demands, this paper studies the VMP problem in a practical dynamic cloud environment. The paper is organized as follows. Section2 formulates the instant-deployment problem for VMs and the periodic-consolidation problem for servers. Section 3 presents an improved multidimensional space partition model. Section 4 describes the execution procedures of the proposed two-phase optimization strategy, and two developed algorithms, respectively, for VM deployment and server consolidation based on the model in the previous section. In Section 5, the algorithms are validated by simulation experiments. Section 6 concludes the paper with a summary of results and future work directions.


## 2. Problem Formulation

Assume that servers are homogeneous in a cloud data center and there are sufficient server resources to meet all the VM requests. For VMs’ demands, the server resources fall into two types: deterministic resources and stochastic resources. DenoteD the set of deterministic resources and Q the set of stochastic resources. Servers should supply fixed-value deterministic resources required by VMs and provide an availability guarantee of stochastic resources with probability at least 1
-
α, where α is called target overflow probability specified in the service level agreements (SLAs).Let the time-slots be of equal lengthΔ
t. The deployment and removal of VMs only occur at each time instant [27]. As shown in Figure 1, VMs, on arrival, will be placed at the next time instant. In order to ensure high responsiveness, Δ
t needs to be properly chosen.Figure 1
The deployment and removal of VMs.For a cloud provider, quick response to the incoming VM requests is crucial for a high service quality. Thus, an instant-deployment strategy is adopted for VMs. However, VMs are being continuously removed over time, as shown in Figure1. Over a long time period, the infrastructure may be brought to a poor state (e.g., there are only a few VMs in some servers). Therefore, it is necessary to implement server consolidation periodically.


### 2.1. The Instant-Deployment for VMs

A newly arriving VM is denoted byv
k. The strategy is to select a suitable physical machine (PM) to deploy v
k in runtime. VM migration is not involved. Considering VMs’ deterministic and stochastic demands, a placement scheme is regarded as feasible only if it satisfies the following conditions: (
1
) for each deterministic resource of a server, the server’s capacity should not be exceeded by the total demand of all the VMs on the server; (
2
) for each stochastic resource of a server, the probability that the server’s capacity is exceeded is no larger than α.Denote VMv
i’s demand for a deterministic resource r as d
i
r and server h’s corresponding capacity as C
h
r.Condition(
1
) can be represented as
(1)
d
k
r
+
∑
i
∈
U
h
d
i
r
≤
C
h
r
,
∀
r
∈
D
.Condition(
2
) can be represented as
(2)
Pr
{
d
k
r
+
∑
i
∈
U
h
d
i
r
≤
C
h
r
}
≥
1
-
α
,
∀
r
∈
Q
U
h is the set of VMs running on server h.The VM instant-deployment problem is to find a VM placement scheme for a newly arriving VMv
k, which satisfies the above two conditions and minimizes the number of required servers.


### 2.2. The Periodic-Consolidation for Servers

Server consolidation refers to gathering VMs into as few servers as possible and then turning off the idle servers or putting them in a low energy mode. To formulate the strategy, a stochastic chance-constrained programming model is presented.Firstly, the notations used are listed in the following.(i) Parameters:
t: the time instant to trigger server consolidation.
V
(
t
): the set of VMs which have been deployed and will not be removed at time instant t.
P
(
t
): the set of PMs which are running at time instant t, P
(
t
)
=
{
1,2
,
…
,
h
,
…
,
n
p
(
t
)
}.
p
i
(
t
): the PM on which VM v
i is running at time instant t,i
∈
V
(
t
), p
i
(
t
)
∈
P
(
t
).
N: the total number of PMs in a cloud data center.
(ii) Decision variables:
the three variables below define the status of PMs and VMs after the server consolidation.
y
i
h
(
t
)
∈
{
0,1
}: is equal to 1 if VM i is mapped to PM h, 0 otherwise.
o
h
(
t
)
∈
{
0,1
}: is equal to 1 if PM h is used, 0 otherwise.
m
i
(
t
)
∈
{
0,1
}: is equal to 1 if VM i is migrated to another PM (namely, ∑
h
∈
P
(
t
)
h
·
y
i
h
(
t
)
≠
p
i
(
t
)), 0 otherwise.The most effective way to reduce power consumption is to decrease the total number of required servers. Given the overhead of live migration, the objective is to minimize the number of migrations, in addition to the number of required servers.Thus, the server consolidation problem for the VM setV
(
t
) can be formulated as
(3)
(
Model
_
0
)
min
⁡
f
1
=
∑
h
∈
P
(
t
)
o
h
(
t
)
(4)
min
⁡
f
2
=
∑
i
∈
V
(
t
)
m
i
(
t
)subject to(5)
o
h
(
t
)
≤
∑
i
∈
V
(
t
)
y
i
h
(
t
)
,
∀
h
∈
P
(
t
)
(6)
o
h
(
t
)
≥
y
i
h
(
t
)
,
∀
i
∈
V
(
t
)
,
∀
h
∈
P
(
t
)
(7)
-
m
i
(
t
)
·
N
≤
p
i
(
t
)
-
∑
h
∈
P
(
t
)
h
·
y
i
h
(
t
)
≤
m
i
(
t
)
·
N
,
∀
i
∈
V
(
t
)
(8)
∑
h
∈
P
(
t
)
y
i
h
(
t
)
=
1
,
∀
i
∈
V
(
t
)
(9)
∑
i
∈
V
(
t
)
y
i
h
(
t
)
·
d
i
r
≤
C
h
r
,
∀
h
∈
P
(
t
)
,
r
∈
D
(10)
Pr
{
∑
i
∈
V
(
t
)
y
i
h
(
t
)
·
d
i
r
≤
C
h
r
}
≥
1
-
α
,
∀
h
∈
P
(
t
)
,
r
∈
Q
(11)
y
i
h
(
t
)
∈
{
0,1
}
,
∀
i
∈
V
(
t
)
,
∀
h
∈
P
(
t
)
(12)
o
h
(
t
)
∈
{
0,1
}
,
∀
h
∈
P
(
t
)
(13)
m
i
(
t
)
∈
{
0,1
}
,
∀
i
∈
V
(
t
)
.In (3), f
1 defines the number of required servers after the server consolidation. In (4), f
2 defines the number of migrations needed during the server consolidation. Constraints (5)–(7) define the implicit relations between the decision variables. Constraint (8) states each VM (i
∈
V
(
t
)) is placed on a single server. Constraint (9) states that for each deterministic resource of a server, the total demand of all the VMs on the server must not exceed the server’s capacity. Constraint (10) states that for each stochastic resource of a server, the demands of all the VMs on the server should be satisfied with the given probability 1
-
α. Constraints (11)–(13) define the domain of the variables.


## 2.1. The Instant-Deployment for VMs

A newly arriving VM is denoted byv
k. The strategy is to select a suitable physical machine (PM) to deploy v
k in runtime. VM migration is not involved. Considering VMs’ deterministic and stochastic demands, a placement scheme is regarded as feasible only if it satisfies the following conditions: (
1
) for each deterministic resource of a server, the server’s capacity should not be exceeded by the total demand of all the VMs on the server; (
2
) for each stochastic resource of a server, the probability that the server’s capacity is exceeded is no larger than α.Denote VMv
i’s demand for a deterministic resource r as d
i
r and server h’s corresponding capacity as C
h
r.Condition(
1
) can be represented as
(1)
d
k
r
+
∑
i
∈
U
h
d
i
r
≤
C
h
r
,
∀
r
∈
D
.Condition(
2
) can be represented as
(2)
Pr
{
d
k
r
+
∑
i
∈
U
h
d
i
r
≤
C
h
r
}
≥
1
-
α
,
∀
r
∈
Q
U
h is the set of VMs running on server h.The VM instant-deployment problem is to find a VM placement scheme for a newly arriving VMv
k, which satisfies the above two conditions and minimizes the number of required servers.


## 2.2. The Periodic-Consolidation for Servers

Server consolidation refers to gathering VMs into as few servers as possible and then turning off the idle servers or putting them in a low energy mode. To formulate the strategy, a stochastic chance-constrained programming model is presented.Firstly, the notations used are listed in the following.(i) Parameters:
t: the time instant to trigger server consolidation.
V
(
t
): the set of VMs which have been deployed and will not be removed at time instant t.
P
(
t
): the set of PMs which are running at time instant t, P
(
t
)
=
{
1,2
,
…
,
h
,
…
,
n
p
(
t
)
}.
p
i
(
t
): the PM on which VM v
i is running at time instant t,i
∈
V
(
t
), p
i
(
t
)
∈
P
(
t
).
N: the total number of PMs in a cloud data center.
(ii) Decision variables:
the three variables below define the status of PMs and VMs after the server consolidation.
y
i
h
(
t
)
∈
{
0,1
}: is equal to 1 if VM i is mapped to PM h, 0 otherwise.
o
h
(
t
)
∈
{
0,1
}: is equal to 1 if PM h is used, 0 otherwise.
m
i
(
t
)
∈
{
0,1
}: is equal to 1 if VM i is migrated to another PM (namely, ∑
h
∈
P
(
t
)
h
·
y
i
h
(
t
)
≠
p
i
(
t
)), 0 otherwise.The most effective way to reduce power consumption is to decrease the total number of required servers. Given the overhead of live migration, the objective is to minimize the number of migrations, in addition to the number of required servers.Thus, the server consolidation problem for the VM setV
(
t
) can be formulated as
(3)
(
Model
_
0
)
min
⁡
f
1
=
∑
h
∈
P
(
t
)
o
h
(
t
)
(4)
min
⁡
f
2
=
∑
i
∈
V
(
t
)
m
i
(
t
)subject to(5)
o
h
(
t
)
≤
∑
i
∈
V
(
t
)
y
i
h
(
t
)
,
∀
h
∈
P
(
t
)
(6)
o
h
(
t
)
≥
y
i
h
(
t
)
,
∀
i
∈
V
(
t
)
,
∀
h
∈
P
(
t
)
(7)
-
m
i
(
t
)
·
N
≤
p
i
(
t
)
-
∑
h
∈
P
(
t
)
h
·
y
i
h
(
t
)
≤
m
i
(
t
)
·
N
,
∀
i
∈
V
(
t
)
(8)
∑
h
∈
P
(
t
)
y
i
h
(
t
)
=
1
,
∀
i
∈
V
(
t
)
(9)
∑
i
∈
V
(
t
)
y
i
h
(
t
)
·
d
i
r
≤
C
h
r
,
∀
h
∈
P
(
t
)
,
r
∈
D
(10)
Pr
{
∑
i
∈
V
(
t
)
y
i
h
(
t
)
·
d
i
r
≤
C
h
r
}
≥
1
-
α
,
∀
h
∈
P
(
t
)
,
r
∈
Q
(11)
y
i
h
(
t
)
∈
{
0,1
}
,
∀
i
∈
V
(
t
)
,
∀
h
∈
P
(
t
)
(12)
o
h
(
t
)
∈
{
0,1
}
,
∀
h
∈
P
(
t
)
(13)
m
i
(
t
)
∈
{
0,1
}
,
∀
i
∈
V
(
t
)
.In (3), f
1 defines the number of required servers after the server consolidation. In (4), f
2 defines the number of migrations needed during the server consolidation. Constraints (5)–(7) define the implicit relations between the decision variables. Constraint (8) states each VM (i
∈
V
(
t
)) is placed on a single server. Constraint (9) states that for each deterministic resource of a server, the total demand of all the VMs on the server must not exceed the server’s capacity. Constraint (10) states that for each stochastic resource of a server, the demands of all the VMs on the server should be satisfied with the given probability 1
-
α. Constraints (11)–(13) define the domain of the variables.


## 3. An Improved Multidimensional Space Partition Model

### 3.1. The Model for Deterministic Resources

Most existing algorithms (such as Next Fit and First Fit) simply perform the placement computation by comparing the VM’s demand with the server’s available capacity, without considering the balanced utilization of multidimensional resources. However, as long as an arbitrary dimensional resource of a server is exhausted, even when all other dimensional resources are sufficient, no more VMs can be placed on the server. In order to avoid this and reduce resource waste, Li et al. [17] proposed a multidimensional space partition model and based on the model presented anenergy efficientalgorithm with balanced resource utilization (EAGLE for short). Figure 2 shows the two-dimensional space partition model. In the figure, the vertical and horizontal axes, respectively, stand for the utilization ratios of resource 1 and resource 2 in server h; the point E
(
1.0,1.0
) indicates the two types of resources are exhausted, while the point O
(
0,0
) means server h is idle.Figure 2
The multidimensional space partition model [17].In the partition model, there are three domains: the AD domain which implies all resources are nearly exhausted, the FD domain which indicates there is an obvious disequilibrium of multidimensional resource utilization, and the SD domain which represents the balanced case. As shown in Figure2, the unit square is partitioned into three parts by three quarter circles. The AD domain is one quarter circle with center E and radius r
0(r
0
∈
[
0,1.0
]). The FD domain is divided into two subparts by two symmetrical quarter circles, with the same radius R
0(R
0
∈
[
0,1.0
]). The point O
1 is the center of the red quarter circle and the point O
2 is the center of the green quarter circle. The SD domain is bounded by the three quarter circles and square edges.Generally, in theM-dimensional space partition model, one point is corresponded to each usage state, expressed as U
S
h
=
(
η
h
1
,
η
h
2
,
…
,
η
h
r
,
…
,
η
h
M
). η
h
r represents the utilization ratio of resource r in server h. Given U
S
h, the parameters r
0 and R
0, the domain determination function f can be defined as
(14)
f
(
U
S
h
)
=
{
AD
,
if
distance
(
U
S
h
,
E
)
≤
r
0
,
SD
,
else
if
(
∀
r
,
distance
(
U
S
h
,
O
r
)
≤
R
0
)
∥
(
∀
r
,
η
h
r
≤
1
-
R
0
)
∥
(
∀
r
,
η
h
r
≥
R
0
)
,
FD
,
otherwise
distance
(
U
S
h
,
O
r
) means the Euclidean distance between the two points U
S
h and O
r. The point O
r is represented as (
x
1
,
x
2
,
…
x
k
,
…
,
x
M
), where
(15)
x
k
=
{
1
-
R
0
,
if
k
=
r
;
R
0
,
otherwise
.Denotev
k as a VM to be deployed. According to EAGLE in [17], for each running PM h, firstly compute the posterior usage state, expressed as P
S
h
,
v
k, which refers to the new usage state when VM v
k is placed on it, then determine the domain f
(
P
S
h
,
v
k
) for each PM h, which has sufficient resources to host VM v
k, and finally select a PM Host
(
v
k
) for VM v
k by following the steps below.(1)
Check whetherP
AD is empty, where P
AD is a PM set in which each PM h satisfies f
(
P
S
h
,
v
k
)
=
AD;
(2)
ifP
AD is nonempty, then let Host
(
v
k
)
=
h
AD, where h
AD
∈
P
AD is the PM with the highest overall resource utilization, otherwise check whether P
SD is empty, where P
SD is a PM set in which each PM h satisfies f
(
P
S
h
,
v
k
)
=
SD and go to the next step;
(3)
ifP
SD is nonempty, then let Host
(
v
k
)
=
h
SD, where h
SD
∈
P
SD is the PM with the most balanced utilization of multidimensional resource, otherwise turn on a PM h
New and let Host
(
v
k
)
=
h
New.By comparing the experimental results of EAGLE and First Fit, Li et al. [17] validated that EAGLE work efficiently on the balanced utilization of multidimensional resources, and, thus, reduce the number of required servers. Besides, they analyzed the impact of model parameters (R
0 and r
0) on the algorithm performance and got that the least number of servers is required when R
0 is equal to 0.8 and r
0 is equal to 0.1. In this paper, it is adopted that R
0
=
0.8 and r
0
=
0.1.


### 3.2. An Improved Model for Both Deterministic and Stochastic Resources

As with [17], this work focuses on the VMP with multidimensional resources and aims to reduce the number of required servers. However, different from [17], VMs’ stochastic demands and periodic server consolidation are taken into account in this paper. Considering these characteristics, a new partition is presented for the M-dimensional resource usage state space.For a PMh with P
S
h
,
v
k
≤
0.2 and f
(
P
S
h
,
v
k
)
=
SD, it can be regarded as a candidate for the subsequent server consolidation, thus the criterion for selecting Host
(
v
k
) from these PMs should focus on migration cost reduction. In view of this, the original SD domain is partitioned and then a new domain LD is obtained where the utilization ratio is less than 0.2 for all resources. Besides, for a usage state U
S
h
≥
0.8, it takes on a high and balanced utilization of M-dimensional resources, which is the feature of states in the AD domain. So these states are incorporated into the AD domain and then a new domain HD is obtained where the utilization ratio is higher than 0.8 for all resources. Figure 3 shows the improved two-dimensional space partition model. The improved model includes four domains as follows.(i)
Unbalanced utilization domain (NBD): this domain indicates that there is an obvious disequilibrium of multidimensional resource utilization, which should be avoided.
(ii)
Balanced utilization domain (BD): this domain represents the balanced case.
(iii)
High utilization domain (HD): this domain implies that all resources are nearly exhausted, which is an ideal case for all PMs.
(iv)
Low utilization domain (LD): this domain indicates that the utilization ratio is very low for all resources. The PMs whose corresponding usage state lies in this domain may be candidates for the subsequent server consolidation.Figure 3
The improved multidimensional space partition model.For theM-dimensional space partition model, according to U
S
h, the parameters r
0 and R
0, the domain determination function f
′ can be defined as
(16)
f
′
(
U
S
h
)
=
{
HD
,
if
∀
r
,
η
h
r
≥
R
0
LD
,
else
if
∀
r
,
η
h
r
≤
1
-
R
0
BD
,
else
if
∀
r
,
distance
(
U
S
h
,
O
r
)
≤
R
0
NBD
,
otherwise
.In related studies, the stochastic resources refer primarily to the network bandwidth. Moreover, it is shown in [22, 24] that the VMs’ bandwidth demands approximately follow a normal distribution. So this paper assumes VM v
i’s demand d
i
r
(
r
∈
Q
) follows a normal distribution N
(
μ
i
r
,
(
σ
i
r
)
2
). Based on this assumption, for the stochastic resource r, the upper confidence limits of the total demand of all the VMs on the server h can be calculated as
(17)
∑
i
∈
U
h
μ
i
r
+
Φ
-
1
(
1
-
α
)
∑
i
∈
U
h
(
σ
i
r
)
2
,
∀
r
∈
Q
,
where Φ
-
1
(
1
-
α
) is the quantile of N
(
0,1
) at probability α.Thus,η
h
r can be defined as
(18)
η
h
r
=
∑
i
∈
U
h
d
i
r
C
h
r
,
∀
r
∈
D
,
η
h
r
=
∑
i
∈
U
h
μ
i
r
+
Φ
-
1
(
1
-
α
)
∑
i
∈
U
h
(
σ
i
r
)
2
C
h
r
,
∀
r
∈
Q
.


## 3.1. The Model for Deterministic Resources

Most existing algorithms (such as Next Fit and First Fit) simply perform the placement computation by comparing the VM’s demand with the server’s available capacity, without considering the balanced utilization of multidimensional resources. However, as long as an arbitrary dimensional resource of a server is exhausted, even when all other dimensional resources are sufficient, no more VMs can be placed on the server. In order to avoid this and reduce resource waste, Li et al. [17] proposed a multidimensional space partition model and based on the model presented anenergy efficientalgorithm with balanced resource utilization (EAGLE for short). Figure 2 shows the two-dimensional space partition model. In the figure, the vertical and horizontal axes, respectively, stand for the utilization ratios of resource 1 and resource 2 in server h; the point E
(
1.0,1.0
) indicates the two types of resources are exhausted, while the point O
(
0,0
) means server h is idle.Figure 2
The multidimensional space partition model [17].In the partition model, there are three domains: the AD domain which implies all resources are nearly exhausted, the FD domain which indicates there is an obvious disequilibrium of multidimensional resource utilization, and the SD domain which represents the balanced case. As shown in Figure2, the unit square is partitioned into three parts by three quarter circles. The AD domain is one quarter circle with center E and radius r
0(r
0
∈
[
0,1.0
]). The FD domain is divided into two subparts by two symmetrical quarter circles, with the same radius R
0(R
0
∈
[
0,1.0
]). The point O
1 is the center of the red quarter circle and the point O
2 is the center of the green quarter circle. The SD domain is bounded by the three quarter circles and square edges.Generally, in theM-dimensional space partition model, one point is corresponded to each usage state, expressed as U
S
h
=
(
η
h
1
,
η
h
2
,
…
,
η
h
r
,
…
,
η
h
M
). η
h
r represents the utilization ratio of resource r in server h. Given U
S
h, the parameters r
0 and R
0, the domain determination function f can be defined as
(14)
f
(
U
S
h
)
=
{
AD
,
if
distance
(
U
S
h
,
E
)
≤
r
0
,
SD
,
else
if
(
∀
r
,
distance
(
U
S
h
,
O
r
)
≤
R
0
)
∥
(
∀
r
,
η
h
r
≤
1
-
R
0
)
∥
(
∀
r
,
η
h
r
≥
R
0
)
,
FD
,
otherwise
distance
(
U
S
h
,
O
r
) means the Euclidean distance between the two points U
S
h and O
r. The point O
r is represented as (
x
1
,
x
2
,
…
x
k
,
…
,
x
M
), where
(15)
x
k
=
{
1
-
R
0
,
if
k
=
r
;
R
0
,
otherwise
.Denotev
k as a VM to be deployed. According to EAGLE in [17], for each running PM h, firstly compute the posterior usage state, expressed as P
S
h
,
v
k, which refers to the new usage state when VM v
k is placed on it, then determine the domain f
(
P
S
h
,
v
k
) for each PM h, which has sufficient resources to host VM v
k, and finally select a PM Host
(
v
k
) for VM v
k by following the steps below.(1)
Check whetherP
AD is empty, where P
AD is a PM set in which each PM h satisfies f
(
P
S
h
,
v
k
)
=
AD;
(2)
ifP
AD is nonempty, then let Host
(
v
k
)
=
h
AD, where h
AD
∈
P
AD is the PM with the highest overall resource utilization, otherwise check whether P
SD is empty, where P
SD is a PM set in which each PM h satisfies f
(
P
S
h
,
v
k
)
=
SD and go to the next step;
(3)
ifP
SD is nonempty, then let Host
(
v
k
)
=
h
SD, where h
SD
∈
P
SD is the PM with the most balanced utilization of multidimensional resource, otherwise turn on a PM h
New and let Host
(
v
k
)
=
h
New.By comparing the experimental results of EAGLE and First Fit, Li et al. [17] validated that EAGLE work efficiently on the balanced utilization of multidimensional resources, and, thus, reduce the number of required servers. Besides, they analyzed the impact of model parameters (R
0 and r
0) on the algorithm performance and got that the least number of servers is required when R
0 is equal to 0.8 and r
0 is equal to 0.1. In this paper, it is adopted that R
0
=
0.8 and r
0
=
0.1.


## 3.2. An Improved Model for Both Deterministic and Stochastic Resources

As with [17], this work focuses on the VMP with multidimensional resources and aims to reduce the number of required servers. However, different from [17], VMs’ stochastic demands and periodic server consolidation are taken into account in this paper. Considering these characteristics, a new partition is presented for the M-dimensional resource usage state space.For a PMh with P
S
h
,
v
k
≤
0.2 and f
(
P
S
h
,
v
k
)
=
SD, it can be regarded as a candidate for the subsequent server consolidation, thus the criterion for selecting Host
(
v
k
) from these PMs should focus on migration cost reduction. In view of this, the original SD domain is partitioned and then a new domain LD is obtained where the utilization ratio is less than 0.2 for all resources. Besides, for a usage state U
S
h
≥
0.8, it takes on a high and balanced utilization of M-dimensional resources, which is the feature of states in the AD domain. So these states are incorporated into the AD domain and then a new domain HD is obtained where the utilization ratio is higher than 0.8 for all resources. Figure 3 shows the improved two-dimensional space partition model. The improved model includes four domains as follows.(i)
Unbalanced utilization domain (NBD): this domain indicates that there is an obvious disequilibrium of multidimensional resource utilization, which should be avoided.
(ii)
Balanced utilization domain (BD): this domain represents the balanced case.
(iii)
High utilization domain (HD): this domain implies that all resources are nearly exhausted, which is an ideal case for all PMs.
(iv)
Low utilization domain (LD): this domain indicates that the utilization ratio is very low for all resources. The PMs whose corresponding usage state lies in this domain may be candidates for the subsequent server consolidation.Figure 3
The improved multidimensional space partition model.For theM-dimensional space partition model, according to U
S
h, the parameters r
0 and R
0, the domain determination function f
′ can be defined as
(16)
f
′
(
U
S
h
)
=
{
HD
,
if
∀
r
,
η
h
r
≥
R
0
LD
,
else
if
∀
r
,
η
h
r
≤
1
-
R
0
BD
,
else
if
∀
r
,
distance
(
U
S
h
,
O
r
)
≤
R
0
NBD
,
otherwise
.In related studies, the stochastic resources refer primarily to the network bandwidth. Moreover, it is shown in [22, 24] that the VMs’ bandwidth demands approximately follow a normal distribution. So this paper assumes VM v
i’s demand d
i
r
(
r
∈
Q
) follows a normal distribution N
(
μ
i
r
,
(
σ
i
r
)
2
). Based on this assumption, for the stochastic resource r, the upper confidence limits of the total demand of all the VMs on the server h can be calculated as
(17)
∑
i
∈
U
h
μ
i
r
+
Φ
-
1
(
1
-
α
)
∑
i
∈
U
h
(
σ
i
r
)
2
,
∀
r
∈
Q
,
where Φ
-
1
(
1
-
α
) is the quantile of N
(
0,1
) at probability α.Thus,η
h
r can be defined as
(18)
η
h
r
=
∑
i
∈
U
h
d
i
r
C
h
r
,
∀
r
∈
D
,
η
h
r
=
∑
i
∈
U
h
μ
i
r
+
Φ
-
1
(
1
-
α
)
∑
i
∈
U
h
(
σ
i
r
)
2
C
h
r
,
∀
r
∈
Q
.


## 4. Strategy and Algorithms

### 4.1. A Two-Phase Optimization Strategy

Figure4(a) shows the interactions between the two phases in optimization, which are, respectively, for VM deployment and server consolidation. At each time instant t, firstly checks whether there are newly arriving VMs to be deployed; if there are, then enter into the VM deployment phase and place these VMs in the order they arrive. The procedure to deploy a VM is shown in Figure 4(b), where P
1 represents the set of the PMs with some VMs running.Figure 4
The flowchart of the two-phase optimization strategy.When the server consolidation is triggered, an optimal scheme can be obtained by solving the model in Section2.2. According to formula (17), the deterministic form equivalent with the chance constraint (10) can be derived as follows:
(19)
∑
i
∈
V
(
t
)
y
i
h
(
t
)
·
μ
i
r
+
Φ
-
1
(
1
-
α
)
∑
i
∈
V
(
t
)
y
i
h
(
t
)
·
(
σ
i
r
)
2
≤
C
h
r
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
∀
h
∈
P
(
t
)
,
r
∈
Q
.Based on the equivalent form, the Model_0 can be transformed into a deterministic model called Model_1, which includes (3)–(9), (11)–(13), and (19). Model_1 is a multiobject integer programming model. From a service provider’s perspective, minimizing the number of required servers can reduce more cost than minimizing the number of migrations, so the two objectives can be arranged in order of importance, given that, the Lexicographic method [28] is adopted to solve Model_1. However, the method is only applied to solve a small-scale problem of server consolidation. As the scale of the problem gets larger, it may happen that the general solver such as Gurobi and Cplex cannot get a feasible solution in a reasonable time. Thus, a heuristic algorithm of live migration is designed in Section 4.3.


### 4.2. A Modified EAGLE Algorithm for VM Deployment

Based on the improved multidimensional space partition model, a modified EAGLE algorithm (MEAGLE) is proposed. With the MEAGLE algorithm, the steps below can be followed to selectHost
(
v
k
) for VM v
k.(1)
For each PMh in P
1, compute the posterior usage state P
S
h
,
v
k. Let P
fea
(
v
k
)
=
{
h
∣
h
∈
P
1
and
P
S
h
,
v
k
≤
1
}.
(2)
For each PMh in P
fea
(
v
k
), determine the domain f
′
(
P
S
h
,
v
k
) according to the formula (16) and P
S
h
,
v
k.
(3)
DivideP
fea
(
v
k
) into four sets: P
HD,P
LD, P
BD, P
NBD. P
HD is a PM set in which each PM h satisfies f
′
(
P
S
h
,
v
k
)
=
HD, and the definitions of P
LD, P
BD, P
NBD are similar with P
HD.
(4)
Check whetherP
HD is empty. If P
HD is nonempty, then let Host
(
v
k
)
=
h
HD, where h
HD
∈
P
HD is the PM with the highest overall resource utilization, otherwise go to step (
5
).
(5)
Check whetherP
BD is empty. If P
BD is nonempty, then let Host
(
v
k
)
=
h
BD, where h
BD
∈
P
BD is the PM with the most balanced utilization of multidimensional resource, otherwise go to step (
6
).
(6)
Check whetherP
LD is empty. If P
LD is nonempty, then let Host
(
v
k
)
=
h
LD, where h
LD
∈
P
LD is the PM with the largest number of VMs, otherwise turn on a PM h
New and let Host
(
v
k
)
=
h
New.For a PMh with the usage state (
η
h
1
,
η
h
2
,
…
,
η
h
r
,
…
,
η
h
M
), the overall resource utilization R
h and the equilibrium degree of M-dimensional resource utilization D
h can be calculated as follows:
(20)
R
h
=
1
M
∑
r
∈
D
∪
Q
η
h
r
D
h
=
∑
r
∈
D
∪
Q
(
η
h
r
-
1
M
∑
r
∈
D
∪
Q
η
h
r
)
2
.


### 4.3. A Live Migration Algorithm for Server Consolidation

Based on the improved multidimensional space partition model and MEAGLE algorithm, a live migration algorithm based on the basic set (LMABBS) is proposed. Let the basic setP
BS
=
{
h
∣
f
′
(
U
S
h
)
=
HD
or
I
h
=
max
⁡
j
∈
P
1
⁡
I
j
} and the nonbasic set P
NBS
=
P
1
∖
P
BS, where I
j indicates the number of VMs on the PM j. The key idea of LMABBS is to turn off as many PMs in P
NBS as possible by live migration. The algorithm is terminated when P
NBS is empty or there is no server in P
NBS as a candidate for server consolidation. Here a candidate means a PM on which all VMs can be migrated to other PMs.The functionJudgeMigratable
⁡
(
h
i
) in Algorithm 1 describes the procedures to determine whether a PM h
i is a candidate and returns a plan for VMs’ migrations if so. The main points of the function are as follows.(1)
Firstly according to MEAGLE, check each VMv
i on server h
i in the ascending order of VMs’ ID, to see whether it can be migrated into a directly-deployed server, on which the original VMs need not be migrated out before VM v
i’s migration.
(2)
If there is only one VMv
l without directly-deployed servers, then go on looking for an indirectly-deployed server, into which v
l can be migrated after some original VMs on it are migrated out, otherwise judge that the PM h
i is not a candidate.
(3)
In order to keep migration cost as low as possible, three types of indirectly-deployed servers are considered: (a) a PM on which an original VM is needed to migrate out before VMv
i’s migration, (b) a PM on which two original VMs are needed to migrate out before VM v
i’s migration, and (c) a PM on which an original VM is needed to be exchanged with a VM on the other non-h
i PM before VM v
i’s migration.
(4)
If there are two VMs on serverh
i, and there exists one VM without directly-deployed and indirectly-deployed servers, then return to step (
1
) and check each VM again in the descending order of VMs’ ID.Algorithm 1:The procedures to judge whether a PM h
i is a candidate for server consolidation.
Procedure MigPlan = JudgeMigratable(
h
i
)
(1) InitializeS
t
(
h
i
) as the set of VMs on server h
i at time instant t
(2)n
←
S
t
(
h
i
). size
(3)for  k
=
1 to n  do
(4)   According to MEAGLE, search for the Host(
v
k
) for v
k, where v
k
∈
S
t
(
h
i
).
(5)if  Host(
v
k
)
∈
P
1
∖
{
h
i
}
(6)      MigPlan = [MigPlan;v
k
h
i Host(
v
k
)]
(7)      Update the usage state of Host(
v
k
) after v
k is placed on it.
(8)else
(9)l
←
k;
(10)n
count
←
n
count
+
1
(11)if  n
count
>
1
(12)       /*InS
t
(
h
i
), there exists more than one VM without directly-deployed servers.
(13)MigPlan
=
[
];
(14)return  MigPlan
(15)end  if
(16)end  if
(17)end  for
(18)if  n
count
=
=
1
(19)  /*InS
t
(
h
i
), there is only one VM v
l without directly-deployed servers.
(20)if  ∃
h
1, h
2
∈
P
1
∖
{
h
i
}, v
l can be placed on h
1
after an original VM onh
1 is migrated into h
2, then
(21)      Update MigPlan
(22)else  if  ∃
h
1, h
2, h
3
∈
P
1
∖
{
h
i
}, v
l can be placed on h
1
after two original VMs onh
1 are respectively migrated into h
2 and h
3, then
(23) Update MigPlan
(24)else  if  ∃
h
1, h
2
∈
P
1
∖
{
h
i
}, v
l can be placed on h
1
after an original VM onh
1 is exchanged with a VM on h
2, then
(25)    Update MigPlan
(26)else
(27)MigPlan
=
[
]
(28)return MigPlan
(29)end  if
(30)end  if
(31)return  MigPlan


## 4.1. A Two-Phase Optimization Strategy

Figure4(a) shows the interactions between the two phases in optimization, which are, respectively, for VM deployment and server consolidation. At each time instant t, firstly checks whether there are newly arriving VMs to be deployed; if there are, then enter into the VM deployment phase and place these VMs in the order they arrive. The procedure to deploy a VM is shown in Figure 4(b), where P
1 represents the set of the PMs with some VMs running.Figure 4
The flowchart of the two-phase optimization strategy.When the server consolidation is triggered, an optimal scheme can be obtained by solving the model in Section2.2. According to formula (17), the deterministic form equivalent with the chance constraint (10) can be derived as follows:
(19)
∑
i
∈
V
(
t
)
y
i
h
(
t
)
·
μ
i
r
+
Φ
-
1
(
1
-
α
)
∑
i
∈
V
(
t
)
y
i
h
(
t
)
·
(
σ
i
r
)
2
≤
C
h
r
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
∀
h
∈
P
(
t
)
,
r
∈
Q
.Based on the equivalent form, the Model_0 can be transformed into a deterministic model called Model_1, which includes (3)–(9), (11)–(13), and (19). Model_1 is a multiobject integer programming model. From a service provider’s perspective, minimizing the number of required servers can reduce more cost than minimizing the number of migrations, so the two objectives can be arranged in order of importance, given that, the Lexicographic method [28] is adopted to solve Model_1. However, the method is only applied to solve a small-scale problem of server consolidation. As the scale of the problem gets larger, it may happen that the general solver such as Gurobi and Cplex cannot get a feasible solution in a reasonable time. Thus, a heuristic algorithm of live migration is designed in Section 4.3.


## 4.2. A Modified EAGLE Algorithm for VM Deployment

Based on the improved multidimensional space partition model, a modified EAGLE algorithm (MEAGLE) is proposed. With the MEAGLE algorithm, the steps below can be followed to selectHost
(
v
k
) for VM v
k.(1)
For each PMh in P
1, compute the posterior usage state P
S
h
,
v
k. Let P
fea
(
v
k
)
=
{
h
∣
h
∈
P
1
and
P
S
h
,
v
k
≤
1
}.
(2)
For each PMh in P
fea
(
v
k
), determine the domain f
′
(
P
S
h
,
v
k
) according to the formula (16) and P
S
h
,
v
k.
(3)
DivideP
fea
(
v
k
) into four sets: P
HD,P
LD, P
BD, P
NBD. P
HD is a PM set in which each PM h satisfies f
′
(
P
S
h
,
v
k
)
=
HD, and the definitions of P
LD, P
BD, P
NBD are similar with P
HD.
(4)
Check whetherP
HD is empty. If P
HD is nonempty, then let Host
(
v
k
)
=
h
HD, where h
HD
∈
P
HD is the PM with the highest overall resource utilization, otherwise go to step (
5
).
(5)
Check whetherP
BD is empty. If P
BD is nonempty, then let Host
(
v
k
)
=
h
BD, where h
BD
∈
P
BD is the PM with the most balanced utilization of multidimensional resource, otherwise go to step (
6
).
(6)
Check whetherP
LD is empty. If P
LD is nonempty, then let Host
(
v
k
)
=
h
LD, where h
LD
∈
P
LD is the PM with the largest number of VMs, otherwise turn on a PM h
New and let Host
(
v
k
)
=
h
New.For a PMh with the usage state (
η
h
1
,
η
h
2
,
…
,
η
h
r
,
…
,
η
h
M
), the overall resource utilization R
h and the equilibrium degree of M-dimensional resource utilization D
h can be calculated as follows:
(20)
R
h
=
1
M
∑
r
∈
D
∪
Q
η
h
r
D
h
=
∑
r
∈
D
∪
Q
(
η
h
r
-
1
M
∑
r
∈
D
∪
Q
η
h
r
)
2
.


## 4.3. A Live Migration Algorithm for Server Consolidation

Based on the improved multidimensional space partition model and MEAGLE algorithm, a live migration algorithm based on the basic set (LMABBS) is proposed. Let the basic setP
BS
=
{
h
∣
f
′
(
U
S
h
)
=
HD
or
I
h
=
max
⁡
j
∈
P
1
⁡
I
j
} and the nonbasic set P
NBS
=
P
1
∖
P
BS, where I
j indicates the number of VMs on the PM j. The key idea of LMABBS is to turn off as many PMs in P
NBS as possible by live migration. The algorithm is terminated when P
NBS is empty or there is no server in P
NBS as a candidate for server consolidation. Here a candidate means a PM on which all VMs can be migrated to other PMs.The functionJudgeMigratable
⁡
(
h
i
) in Algorithm 1 describes the procedures to determine whether a PM h
i is a candidate and returns a plan for VMs’ migrations if so. The main points of the function are as follows.(1)
Firstly according to MEAGLE, check each VMv
i on server h
i in the ascending order of VMs’ ID, to see whether it can be migrated into a directly-deployed server, on which the original VMs need not be migrated out before VM v
i’s migration.
(2)
If there is only one VMv
l without directly-deployed servers, then go on looking for an indirectly-deployed server, into which v
l can be migrated after some original VMs on it are migrated out, otherwise judge that the PM h
i is not a candidate.
(3)
In order to keep migration cost as low as possible, three types of indirectly-deployed servers are considered: (a) a PM on which an original VM is needed to migrate out before VMv
i’s migration, (b) a PM on which two original VMs are needed to migrate out before VM v
i’s migration, and (c) a PM on which an original VM is needed to be exchanged with a VM on the other non-h
i PM before VM v
i’s migration.
(4)
If there are two VMs on serverh
i, and there exists one VM without directly-deployed and indirectly-deployed servers, then return to step (
1
) and check each VM again in the descending order of VMs’ ID.Algorithm 1:The procedures to judge whether a PM h
i is a candidate for server consolidation.
Procedure MigPlan = JudgeMigratable(
h
i
)
(1) InitializeS
t
(
h
i
) as the set of VMs on server h
i at time instant t
(2)n
←
S
t
(
h
i
). size
(3)for  k
=
1 to n  do
(4)   According to MEAGLE, search for the Host(
v
k
) for v
k, where v
k
∈
S
t
(
h
i
).
(5)if  Host(
v
k
)
∈
P
1
∖
{
h
i
}
(6)      MigPlan = [MigPlan;v
k
h
i Host(
v
k
)]
(7)      Update the usage state of Host(
v
k
) after v
k is placed on it.
(8)else
(9)l
←
k;
(10)n
count
←
n
count
+
1
(11)if  n
count
>
1
(12)       /*InS
t
(
h
i
), there exists more than one VM without directly-deployed servers.
(13)MigPlan
=
[
];
(14)return  MigPlan
(15)end  if
(16)end  if
(17)end  for
(18)if  n
count
=
=
1
(19)  /*InS
t
(
h
i
), there is only one VM v
l without directly-deployed servers.
(20)if  ∃
h
1, h
2
∈
P
1
∖
{
h
i
}, v
l can be placed on h
1
after an original VM onh
1 is migrated into h
2, then
(21)      Update MigPlan
(22)else  if  ∃
h
1, h
2, h
3
∈
P
1
∖
{
h
i
}, v
l can be placed on h
1
after two original VMs onh
1 are respectively migrated into h
2 and h
3, then
(23) Update MigPlan
(24)else  if  ∃
h
1, h
2
∈
P
1
∖
{
h
i
}, v
l can be placed on h
1
after an original VM onh
1 is exchanged with a VM on h
2, then
(25)    Update MigPlan
(26)else
(27)MigPlan
=
[
]
(28)return MigPlan
(29)end  if
(30)end  if
(31)return  MigPlan


## 5. Simulation Experiment

### 5.1. Simulation Configuration

Consider a cloud data center with 200 servers with the same capacity. Each VM is assumed to have three types of resources demands: CPU, memory, and bandwidth. SetD
=
{
CPU
,
memory
}, Q
=
{
bandwidth
}, and α
=
5
%. The ratio of the resource demand to server capacity is employed to identify the demand intensity of each resource. Among all resources, the resource with the largest DCR value is defined as the intensive resource and others are defined as the nonintensive resources. To emulate a typical data center setting, four groups of VMs are generated: CPU-intensive VMs, memory-intensive VMs, bandwidth-intensive VMs, and general VMs, where each group contains a quarter of all VMs. For each VM in the first three groups, the intensive resource randomly selects its DCR value from a higher range [
30
%
,
40
%
] and other nonintensive resources randomly select their DCR values from a lower range [
5
%
,
10
%
], which is based on the data generation method in [26]. For each VM in the fourth group, all resources select their DCR value from a general range [
3
%
,
10
%
] to validate the MEAGLE algorithm when R
0
=
0.8. For the stochastic bandwidth demand, the selected DCR value represents the ratio between the mean of the bandwidth and the server capacity. Coefficients of variation for all VMs’ bandwidth demands are set 0.2 by default.Assume that the number of VM requests reaching the cloud data center in a period follows a Poissonian distribution with a meanλ. Here a period includes 60 time instants. In order to evaluate the performance of our MEAGLE and LMABBS, respectively, the experiment consists of two parts: (
1
) comparing the solutions of MEAGLE and EAGLE and (
2
) comparing the solutions of LMABBS and Gurobi. The Gurobi solutions are obtained by using Gurobi 5.5.0 to solve Model_1, which is formulated by YALMIP [29] in MATLAB environment. All experiments are performed on a computer with Intel Core i7 3.40 GHz CPU and 4 GB RAM.


### 5.2. The Result and Analysis

#### 5.2.1. Comparison between MEAGLE and EAGLE

This subsection is conducted to evaluate the performance of MEAGLE on the instant-deployment for VMs. Assume that there is no VM on each server att
=
0. Eighty periods are considered and 220 VMs on average are arriving in a period (i.e., λ
=
220). According to the settings, a VM set is generated and called VmSet which includes all the VMs arriving during the eighty periods. The VMs are deployed instantly as soon as they arrive. For each VM v
k
∈
VmSet, EAGLE, SEAGLE, and MEAGLE are, respectively, adopted to search Host
(
v
k
). A VM’s bandwidth demand is constant and taken as the mean in EAGLE while it is regarded as a random variable in SEAGLE and MEAGLE. When using SEAGLE, firstly for each PM h in P
1, compute the posterior usage state P
S
h
,
v
k according to formula (18) then perform the same steps as EAGLE described in Section 3.Figure5(a) shows the number of required servers at each time instant. The reduction of the servers at some time instants is a result of turning off the idle servers as some VMs are removed. To further validate the actual overflow probability, the following procedures are carried out. Firstly, for each VM’s bandwidth demand at per time instant, we sample the trace to obtain 1000 samples of the momentary value of bandwidth consumption. Then for each packing obtained by the algorithms at per time instant and for each server in the packing, we sum up the total momentary bandwidth consumption per server and check whether the server capacity constraint is broken. Figure 5(b) shows the cumulative distribution function (CDF) of server compliance with the overflow probability. From Figure 5, it can be seen, by EAGLE the number of required servers at each time instant is the least but only about 42% of servers respect the target overflow probability α
=
5
%. For MEAGLE and SEAGLE, almost all servers obey the target overflow probability, yet MEAGLE uses a smaller number of servers.The comparisons of simulation results.
(a)
The number of required servers at each time instant
(b)
Overflow probability and target overflow probability 0.05In order to better evaluate the performance of MEAGLE, a series of eight experiments is performed to deploy the VMs inVmSet under different coefficients of variation with respect to VMs’ bandwidth demands. Here the coefficient of variation characterizes the variation in demand. The simulation results are shown in Table 1, where ω
i(i
=
1,2
,
3) represents the average number of required servers in a time unit and τ
i (i
=
1,2
,
3) refers to the proportion of servers violating the target overflow probability. From Table 1, it can be seen, (
1
) with the same volatility (or coefficient of variation), τ
1 is significantly larger than τ
2 and τ
3 while the difference between τ
2 and τ
3 is very small; (
2
) as the coefficient of variation increases, τ
1 is rising sharply while τ
2 and τ
3 are keeping at very low level; (
3
)
ω
3 is 2.49%–20.40% less than ω
2 with the same coefficient of variation and ω
3 is the least when the variation coefficient is 0.01 and 0.05.Table 1
The simulation results with different variation coefficients.
Variation coefficients
EAGLE
SEAGLE
MEAGLE
ω
1
τ
1
ω
2
τ
2
ω
3
τ
3
0.01
108.7139
6.03%
107.6639
0.11%
104.9861
0.15%
0.05
108.7139
28.28%
114.1208
0.55%
107.8042
0.60%
0.1
108.7139
44.58%
127.7708
0.46%
113.0083
1.48%
0.15
108.7139
53.28%
141.9153
0.37%
118.6417
1.42%
0.2
108.7139
57.30%
151.4569
0.37%
122.4278
1.27%
0.25
108.7139
59.13%
157.0264
0.39%
124.9875
1.34%
0.3
108.7139
60.56%
163.4546
0.83%
131.5111
2.48%
0.35
108.7139
62.70%
163.7028
1.64%
136.9597
4.33%From the results shown in Table1, it can be concluded that SEAGLE and MEAGLE work well to obey the target overflow probability, while EAGLE brings a high proportion of servers violating the target overflow probability as it cannot detect the change of VM’s burst level. Furthermore, though MEAGLE is slightly inferior to SEAGLE in lowering the overflow probability of servers as shown in Figure 5(b), MEAGLE uses a smaller number of servers than SEAGLE does. This is primarily due to the fact that by SEAGLE, a VM v
k must not be placed on a PM h with f
(
P
S
h
,
v
k
)
=
FD and a new PM will be turned on if there is no proper server to host v
k. VMs in our study have different resource intensities and a PM is more likely to incur an imbalanced utilization of multidimensional resources after it hosts a nongeneral VM (such as a CPU-intensive VM). Therefore, according to the procedures of SEAGLE and MEAGLE, SEAGLE will use more servers than MEAGLE obviously.


#### 5.2.2. Comparison between LMABBS and Gurobi

Within the two-phase optimization strategy, the server consolidation is implemented for every 4 periods. In order to test the performance of LMABBS,λ
=
11,12
,
…
,
26 is set and twenty running states are chosen for each value of λ. A running state for server consolidation is regarded as a problem instance and then 320 instances are generated. For each instance, the corresponding problem is solved, respectively, by the LMABBS and Gurobi. As a note, when solving large scale problems by Gurobi, one bad case that may arise is that solutions cannot be obtained due to out of memory. So the values of λ in this subsection are relatively smaller than that in the previous subsection. Here set the solving time limit as 30 minutes for Gurobi. Then all instances are divided into five groups, according to all possible results (C
1

~

C
5) obtained by Gurobi shown in Table 2. Δ represents the variation in the number of required servers by server consolidation. The state with “the best feasible solution” represents that Gurobi cannot get an optimal solution but can get a feasible solution in 30 minutes, while the state with “no solution” means that Gurobi cannot produce a feasible solution in 30 minutes. Let S
i denote a set of the problem instances, where i
=
1,2
,
…
,
5. Each instance in S
i has the same result as C
i if it is solved by Gurobi.Table 2
The possible results obtained by Gurobi.
The type of results
Δ
The state of solution
The percentage of instances withC
i
C
1
Decrease
Optimal solution
44.52%
C
2
Decrease
The best feasible solution
31.45%
C
3
Invariant
Optimal solution
4.42%
C
4
Invariant
The best feasible solution
5.65%
C
5
—
No solution
13.95%By statistical analysis on experimental results, the following points can be found out:(
1
) for the 80.95% instances in S
1, the LMABBS solution coincides with Gurobi solution on the number of required server and migrations; (
2
) by LMABBS, though there exist 19.05% instances in S
1 without optimal solutions, there are still 29.17% of these instances with the minimum number of required servers (Let S
^
1 represent the set of the 19.05% instances in S
1); (
3
) in S
2, there are 74% instances for which the solutions of the two methods are identical to the number of required server and there are 60% instances for which the solutions of the two methods are identical to the number of required server and migrations; (
4
) for the instances in S
3 and S
4, LMABBS as well as Gurobi cannot obtain a valid consolidation solution which can reduce the number of required servers; and (
5
) in S
5, there are 76.19% instances with valid consolidation solutions by LMABBS and the number of required servers declines by 15.98% on average.For different sets of instances, the comparison results of LMABBS solution with Gurobi solution are shown in Table3, where ρ
h, ρ
m, and ρ
t, respectively, represent the ratios between the number of required servers, between the migration number, and between the computation time on the LMABBS solution and Gurobi solution. As one can see, ρ
m are both equal to 0 for some instances in S
^
1 and S
2. This is because that the servers to turn off are chosen only from the nonbasic set when implementing server consolidation; in other words, if there exists a server in the basic set that is a candidate for server consolidation, the server will not be turned off by live migration because of high migration cost. Besides, according to the comparison results for S
3 and S
4, it can be seen that LMABBS can rapidly identify a situation that the deployment of VMs on the collection of hosts is compact enough and, thus, spend little time looking for an invalid consolidation solution. Taken together, the comparison results suggest that the difference is fairly small between the number of required servers obtained by LMABBS and Gurobi and LMABBS has a significant advantage in lowering migration cost and improving the computational efficiency.Table 3
Comparison of LMABBS solution with Gurobi solution.
The sets of instances
ρ
h
ρ
m
ρ
t
Ave
Max
Min
Ave
Max
Min
Ave
Max
Min
S
^
1
1.1003
1.2500
1.000
0.6988
1.25
0
0.0197
0.1159
1.5621
×
1
0
-
5
S
2
1.0286
1.2000
1.000
0.9022
1.50
0
0.0001
0.0008
5.0555
×
1
0
-
6
S
3
∪
S
4
1.000
1.000
1.0000
—
—
—
4.7288
×
1
0
-
5
0.0002
5.3054
×
1
0
-
6


## 5.1. Simulation Configuration

Consider a cloud data center with 200 servers with the same capacity. Each VM is assumed to have three types of resources demands: CPU, memory, and bandwidth. SetD
=
{
CPU
,
memory
}, Q
=
{
bandwidth
}, and α
=
5
%. The ratio of the resource demand to server capacity is employed to identify the demand intensity of each resource. Among all resources, the resource with the largest DCR value is defined as the intensive resource and others are defined as the nonintensive resources. To emulate a typical data center setting, four groups of VMs are generated: CPU-intensive VMs, memory-intensive VMs, bandwidth-intensive VMs, and general VMs, where each group contains a quarter of all VMs. For each VM in the first three groups, the intensive resource randomly selects its DCR value from a higher range [
30
%
,
40
%
] and other nonintensive resources randomly select their DCR values from a lower range [
5
%
,
10
%
], which is based on the data generation method in [26]. For each VM in the fourth group, all resources select their DCR value from a general range [
3
%
,
10
%
] to validate the MEAGLE algorithm when R
0
=
0.8. For the stochastic bandwidth demand, the selected DCR value represents the ratio between the mean of the bandwidth and the server capacity. Coefficients of variation for all VMs’ bandwidth demands are set 0.2 by default.Assume that the number of VM requests reaching the cloud data center in a period follows a Poissonian distribution with a meanλ. Here a period includes 60 time instants. In order to evaluate the performance of our MEAGLE and LMABBS, respectively, the experiment consists of two parts: (
1
) comparing the solutions of MEAGLE and EAGLE and (
2
) comparing the solutions of LMABBS and Gurobi. The Gurobi solutions are obtained by using Gurobi 5.5.0 to solve Model_1, which is formulated by YALMIP [29] in MATLAB environment. All experiments are performed on a computer with Intel Core i7 3.40 GHz CPU and 4 GB RAM.


## 5.2. The Result and Analysis

### 5.2.1. Comparison between MEAGLE and EAGLE

This subsection is conducted to evaluate the performance of MEAGLE on the instant-deployment for VMs. Assume that there is no VM on each server att
=
0. Eighty periods are considered and 220 VMs on average are arriving in a period (i.e., λ
=
220). According to the settings, a VM set is generated and called VmSet which includes all the VMs arriving during the eighty periods. The VMs are deployed instantly as soon as they arrive. For each VM v
k
∈
VmSet, EAGLE, SEAGLE, and MEAGLE are, respectively, adopted to search Host
(
v
k
). A VM’s bandwidth demand is constant and taken as the mean in EAGLE while it is regarded as a random variable in SEAGLE and MEAGLE. When using SEAGLE, firstly for each PM h in P
1, compute the posterior usage state P
S
h
,
v
k according to formula (18) then perform the same steps as EAGLE described in Section 3.Figure5(a) shows the number of required servers at each time instant. The reduction of the servers at some time instants is a result of turning off the idle servers as some VMs are removed. To further validate the actual overflow probability, the following procedures are carried out. Firstly, for each VM’s bandwidth demand at per time instant, we sample the trace to obtain 1000 samples of the momentary value of bandwidth consumption. Then for each packing obtained by the algorithms at per time instant and for each server in the packing, we sum up the total momentary bandwidth consumption per server and check whether the server capacity constraint is broken. Figure 5(b) shows the cumulative distribution function (CDF) of server compliance with the overflow probability. From Figure 5, it can be seen, by EAGLE the number of required servers at each time instant is the least but only about 42% of servers respect the target overflow probability α
=
5
%. For MEAGLE and SEAGLE, almost all servers obey the target overflow probability, yet MEAGLE uses a smaller number of servers.The comparisons of simulation results.
(a)
The number of required servers at each time instant
(b)
Overflow probability and target overflow probability 0.05In order to better evaluate the performance of MEAGLE, a series of eight experiments is performed to deploy the VMs inVmSet under different coefficients of variation with respect to VMs’ bandwidth demands. Here the coefficient of variation characterizes the variation in demand. The simulation results are shown in Table 1, where ω
i(i
=
1,2
,
3) represents the average number of required servers in a time unit and τ
i (i
=
1,2
,
3) refers to the proportion of servers violating the target overflow probability. From Table 1, it can be seen, (
1
) with the same volatility (or coefficient of variation), τ
1 is significantly larger than τ
2 and τ
3 while the difference between τ
2 and τ
3 is very small; (
2
) as the coefficient of variation increases, τ
1 is rising sharply while τ
2 and τ
3 are keeping at very low level; (
3
)
ω
3 is 2.49%–20.40% less than ω
2 with the same coefficient of variation and ω
3 is the least when the variation coefficient is 0.01 and 0.05.Table 1
The simulation results with different variation coefficients.
Variation coefficients
EAGLE
SEAGLE
MEAGLE
ω
1
τ
1
ω
2
τ
2
ω
3
τ
3
0.01
108.7139
6.03%
107.6639
0.11%
104.9861
0.15%
0.05
108.7139
28.28%
114.1208
0.55%
107.8042
0.60%
0.1
108.7139
44.58%
127.7708
0.46%
113.0083
1.48%
0.15
108.7139
53.28%
141.9153
0.37%
118.6417
1.42%
0.2
108.7139
57.30%
151.4569
0.37%
122.4278
1.27%
0.25
108.7139
59.13%
157.0264
0.39%
124.9875
1.34%
0.3
108.7139
60.56%
163.4546
0.83%
131.5111
2.48%
0.35
108.7139
62.70%
163.7028
1.64%
136.9597
4.33%From the results shown in Table1, it can be concluded that SEAGLE and MEAGLE work well to obey the target overflow probability, while EAGLE brings a high proportion of servers violating the target overflow probability as it cannot detect the change of VM’s burst level. Furthermore, though MEAGLE is slightly inferior to SEAGLE in lowering the overflow probability of servers as shown in Figure 5(b), MEAGLE uses a smaller number of servers than SEAGLE does. This is primarily due to the fact that by SEAGLE, a VM v
k must not be placed on a PM h with f
(
P
S
h
,
v
k
)
=
FD and a new PM will be turned on if there is no proper server to host v
k. VMs in our study have different resource intensities and a PM is more likely to incur an imbalanced utilization of multidimensional resources after it hosts a nongeneral VM (such as a CPU-intensive VM). Therefore, according to the procedures of SEAGLE and MEAGLE, SEAGLE will use more servers than MEAGLE obviously.


### 5.2.2. Comparison between LMABBS and Gurobi

Within the two-phase optimization strategy, the server consolidation is implemented for every 4 periods. In order to test the performance of LMABBS,λ
=
11,12
,
…
,
26 is set and twenty running states are chosen for each value of λ. A running state for server consolidation is regarded as a problem instance and then 320 instances are generated. For each instance, the corresponding problem is solved, respectively, by the LMABBS and Gurobi. As a note, when solving large scale problems by Gurobi, one bad case that may arise is that solutions cannot be obtained due to out of memory. So the values of λ in this subsection are relatively smaller than that in the previous subsection. Here set the solving time limit as 30 minutes for Gurobi. Then all instances are divided into five groups, according to all possible results (C
1

~

C
5) obtained by Gurobi shown in Table 2. Δ represents the variation in the number of required servers by server consolidation. The state with “the best feasible solution” represents that Gurobi cannot get an optimal solution but can get a feasible solution in 30 minutes, while the state with “no solution” means that Gurobi cannot produce a feasible solution in 30 minutes. Let S
i denote a set of the problem instances, where i
=
1,2
,
…
,
5. Each instance in S
i has the same result as C
i if it is solved by Gurobi.Table 2
The possible results obtained by Gurobi.
The type of results
Δ
The state of solution
The percentage of instances withC
i
C
1
Decrease
Optimal solution
44.52%
C
2
Decrease
The best feasible solution
31.45%
C
3
Invariant
Optimal solution
4.42%
C
4
Invariant
The best feasible solution
5.65%
C
5
—
No solution
13.95%By statistical analysis on experimental results, the following points can be found out:(
1
) for the 80.95% instances in S
1, the LMABBS solution coincides with Gurobi solution on the number of required server and migrations; (
2
) by LMABBS, though there exist 19.05% instances in S
1 without optimal solutions, there are still 29.17% of these instances with the minimum number of required servers (Let S
^
1 represent the set of the 19.05% instances in S
1); (
3
) in S
2, there are 74% instances for which the solutions of the two methods are identical to the number of required server and there are 60% instances for which the solutions of the two methods are identical to the number of required server and migrations; (
4
) for the instances in S
3 and S
4, LMABBS as well as Gurobi cannot obtain a valid consolidation solution which can reduce the number of required servers; and (
5
) in S
5, there are 76.19% instances with valid consolidation solutions by LMABBS and the number of required servers declines by 15.98% on average.For different sets of instances, the comparison results of LMABBS solution with Gurobi solution are shown in Table3, where ρ
h, ρ
m, and ρ
t, respectively, represent the ratios between the number of required servers, between the migration number, and between the computation time on the LMABBS solution and Gurobi solution. As one can see, ρ
m are both equal to 0 for some instances in S
^
1 and S
2. This is because that the servers to turn off are chosen only from the nonbasic set when implementing server consolidation; in other words, if there exists a server in the basic set that is a candidate for server consolidation, the server will not be turned off by live migration because of high migration cost. Besides, according to the comparison results for S
3 and S
4, it can be seen that LMABBS can rapidly identify a situation that the deployment of VMs on the collection of hosts is compact enough and, thus, spend little time looking for an invalid consolidation solution. Taken together, the comparison results suggest that the difference is fairly small between the number of required servers obtained by LMABBS and Gurobi and LMABBS has a significant advantage in lowering migration cost and improving the computational efficiency.Table 3
Comparison of LMABBS solution with Gurobi solution.
The sets of instances
ρ
h
ρ
m
ρ
t
Ave
Max
Min
Ave
Max
Min
Ave
Max
Min
S
^
1
1.1003
1.2500
1.000
0.6988
1.25
0
0.0197
0.1159
1.5621
×
1
0
-
5
S
2
1.0286
1.2000
1.000
0.9022
1.50
0
0.0001
0.0008
5.0555
×
1
0
-
6
S
3
∪
S
4
1.000
1.000
1.0000
—
—
—
4.7288
×
1
0
-
5
0.0002
5.3054
×
1
0
-
6


## 5.2.1. Comparison between MEAGLE and EAGLE

This subsection is conducted to evaluate the performance of MEAGLE on the instant-deployment for VMs. Assume that there is no VM on each server att
=
0. Eighty periods are considered and 220 VMs on average are arriving in a period (i.e., λ
=
220). According to the settings, a VM set is generated and called VmSet which includes all the VMs arriving during the eighty periods. The VMs are deployed instantly as soon as they arrive. For each VM v
k
∈
VmSet, EAGLE, SEAGLE, and MEAGLE are, respectively, adopted to search Host
(
v
k
). A VM’s bandwidth demand is constant and taken as the mean in EAGLE while it is regarded as a random variable in SEAGLE and MEAGLE. When using SEAGLE, firstly for each PM h in P
1, compute the posterior usage state P
S
h
,
v
k according to formula (18) then perform the same steps as EAGLE described in Section 3.Figure5(a) shows the number of required servers at each time instant. The reduction of the servers at some time instants is a result of turning off the idle servers as some VMs are removed. To further validate the actual overflow probability, the following procedures are carried out. Firstly, for each VM’s bandwidth demand at per time instant, we sample the trace to obtain 1000 samples of the momentary value of bandwidth consumption. Then for each packing obtained by the algorithms at per time instant and for each server in the packing, we sum up the total momentary bandwidth consumption per server and check whether the server capacity constraint is broken. Figure 5(b) shows the cumulative distribution function (CDF) of server compliance with the overflow probability. From Figure 5, it can be seen, by EAGLE the number of required servers at each time instant is the least but only about 42% of servers respect the target overflow probability α
=
5
%. For MEAGLE and SEAGLE, almost all servers obey the target overflow probability, yet MEAGLE uses a smaller number of servers.The comparisons of simulation results.
(a)
The number of required servers at each time instant
(b)
Overflow probability and target overflow probability 0.05In order to better evaluate the performance of MEAGLE, a series of eight experiments is performed to deploy the VMs inVmSet under different coefficients of variation with respect to VMs’ bandwidth demands. Here the coefficient of variation characterizes the variation in demand. The simulation results are shown in Table 1, where ω
i(i
=
1,2
,
3) represents the average number of required servers in a time unit and τ
i (i
=
1,2
,
3) refers to the proportion of servers violating the target overflow probability. From Table 1, it can be seen, (
1
) with the same volatility (or coefficient of variation), τ
1 is significantly larger than τ
2 and τ
3 while the difference between τ
2 and τ
3 is very small; (
2
) as the coefficient of variation increases, τ
1 is rising sharply while τ
2 and τ
3 are keeping at very low level; (
3
)
ω
3 is 2.49%–20.40% less than ω
2 with the same coefficient of variation and ω
3 is the least when the variation coefficient is 0.01 and 0.05.Table 1
The simulation results with different variation coefficients.
Variation coefficients
EAGLE
SEAGLE
MEAGLE
ω
1
τ
1
ω
2
τ
2
ω
3
τ
3
0.01
108.7139
6.03%
107.6639
0.11%
104.9861
0.15%
0.05
108.7139
28.28%
114.1208
0.55%
107.8042
0.60%
0.1
108.7139
44.58%
127.7708
0.46%
113.0083
1.48%
0.15
108.7139
53.28%
141.9153
0.37%
118.6417
1.42%
0.2
108.7139
57.30%
151.4569
0.37%
122.4278
1.27%
0.25
108.7139
59.13%
157.0264
0.39%
124.9875
1.34%
0.3
108.7139
60.56%
163.4546
0.83%
131.5111
2.48%
0.35
108.7139
62.70%
163.7028
1.64%
136.9597
4.33%From the results shown in Table1, it can be concluded that SEAGLE and MEAGLE work well to obey the target overflow probability, while EAGLE brings a high proportion of servers violating the target overflow probability as it cannot detect the change of VM’s burst level. Furthermore, though MEAGLE is slightly inferior to SEAGLE in lowering the overflow probability of servers as shown in Figure 5(b), MEAGLE uses a smaller number of servers than SEAGLE does. This is primarily due to the fact that by SEAGLE, a VM v
k must not be placed on a PM h with f
(
P
S
h
,
v
k
)
=
FD and a new PM will be turned on if there is no proper server to host v
k. VMs in our study have different resource intensities and a PM is more likely to incur an imbalanced utilization of multidimensional resources after it hosts a nongeneral VM (such as a CPU-intensive VM). Therefore, according to the procedures of SEAGLE and MEAGLE, SEAGLE will use more servers than MEAGLE obviously.


## 5.2.2. Comparison between LMABBS and Gurobi

Within the two-phase optimization strategy, the server consolidation is implemented for every 4 periods. In order to test the performance of LMABBS,λ
=
11,12
,
…
,
26 is set and twenty running states are chosen for each value of λ. A running state for server consolidation is regarded as a problem instance and then 320 instances are generated. For each instance, the corresponding problem is solved, respectively, by the LMABBS and Gurobi. As a note, when solving large scale problems by Gurobi, one bad case that may arise is that solutions cannot be obtained due to out of memory. So the values of λ in this subsection are relatively smaller than that in the previous subsection. Here set the solving time limit as 30 minutes for Gurobi. Then all instances are divided into five groups, according to all possible results (C
1

~

C
5) obtained by Gurobi shown in Table 2. Δ represents the variation in the number of required servers by server consolidation. The state with “the best feasible solution” represents that Gurobi cannot get an optimal solution but can get a feasible solution in 30 minutes, while the state with “no solution” means that Gurobi cannot produce a feasible solution in 30 minutes. Let S
i denote a set of the problem instances, where i
=
1,2
,
…
,
5. Each instance in S
i has the same result as C
i if it is solved by Gurobi.Table 2
The possible results obtained by Gurobi.
The type of results
Δ
The state of solution
The percentage of instances withC
i
C
1
Decrease
Optimal solution
44.52%
C
2
Decrease
The best feasible solution
31.45%
C
3
Invariant
Optimal solution
4.42%
C
4
Invariant
The best feasible solution
5.65%
C
5
—
No solution
13.95%By statistical analysis on experimental results, the following points can be found out:(
1
) for the 80.95% instances in S
1, the LMABBS solution coincides with Gurobi solution on the number of required server and migrations; (
2
) by LMABBS, though there exist 19.05% instances in S
1 without optimal solutions, there are still 29.17% of these instances with the minimum number of required servers (Let S
^
1 represent the set of the 19.05% instances in S
1); (
3
) in S
2, there are 74% instances for which the solutions of the two methods are identical to the number of required server and there are 60% instances for which the solutions of the two methods are identical to the number of required server and migrations; (
4
) for the instances in S
3 and S
4, LMABBS as well as Gurobi cannot obtain a valid consolidation solution which can reduce the number of required servers; and (
5
) in S
5, there are 76.19% instances with valid consolidation solutions by LMABBS and the number of required servers declines by 15.98% on average.For different sets of instances, the comparison results of LMABBS solution with Gurobi solution are shown in Table3, where ρ
h, ρ
m, and ρ
t, respectively, represent the ratios between the number of required servers, between the migration number, and between the computation time on the LMABBS solution and Gurobi solution. As one can see, ρ
m are both equal to 0 for some instances in S
^
1 and S
2. This is because that the servers to turn off are chosen only from the nonbasic set when implementing server consolidation; in other words, if there exists a server in the basic set that is a candidate for server consolidation, the server will not be turned off by live migration because of high migration cost. Besides, according to the comparison results for S
3 and S
4, it can be seen that LMABBS can rapidly identify a situation that the deployment of VMs on the collection of hosts is compact enough and, thus, spend little time looking for an invalid consolidation solution. Taken together, the comparison results suggest that the difference is fairly small between the number of required servers obtained by LMABBS and Gurobi and LMABBS has a significant advantage in lowering migration cost and improving the computational efficiency.Table 3
Comparison of LMABBS solution with Gurobi solution.
The sets of instances
ρ
h
ρ
m
ρ
t
Ave
Max
Min
Ave
Max
Min
Ave
Max
Min
S
^
1
1.1003
1.2500
1.000
0.6988
1.25
0
0.0197
0.1159
1.5621
×
1
0
-
5
S
2
1.0286
1.2000
1.000
0.9022
1.50
0
0.0001
0.0008
5.0555
×
1
0
-
6
S
3
∪
S
4
1.000
1.000
1.0000
—
—
—
4.7288
×
1
0
-
5
0.0002
5.3054
×
1
0
-
6


## 6. Conclusions

This paper studies the dynamic placement of VMs with deterministic and stochastic demands for green cloud computing. A two-phase optimization strategy is presented including instant VM deployment and periodic server consolidation. The innovations of the strategy can be listed as follows:(
1
) taking into account stochastic resources, the VMs’ resource demands are described as random variables and the equivalent form of chance constraints is introduced to guarantee the availability for these resources; (
2
) when deploying VMs, the migration cost generated in the subsequent server consolidation is considered; and (
3
) given that this work focuses on the VMs with different resource intensities and the VMs with complementary demands can be placed on the same server, a temporary imbalanced utilization of multidimensional resources is allowed in our method.For VM deployment and server consolidation, a modified EAGLE algorithm (MEAGLE) and a live migration algorithm based on the basic set (LMABBS) are proposed, respectively. The simulation results demonstrate that MEAGLE not only virtually ensures as good performance of user application as SEAGLE, but also reduces the number of required servers by 2.49% to 20.40% compared with SEAGLE. In addition, there is fairly small difference between the number of required servers obtained by LMABBS and Gurobi, but LMABBS has a computational efficiency unmatched by Gurobi. For the instances without a feasible solution in a reasonable time by Gurobi, LMABBS can obtain valid consolidation solutions and lower the number of required servers by an average of 15.98%.For the public clouds that do not provide explicit SLAs guarantees on VM bandwidth today, the application of MEAGLE algorithm will achieve a specified quality-of-service and then help to enhance their credibility and win more customers. Besides, the LMABBS algorithm will help to improve the efficiency of implementing server consolidation and reduce the waste of energy consumption effectively. Thus the proposed two-phase optimization strategy based on MEAGLE and LMABBS will provide a good solution to achieve high level service performance and to minimize energy consumption for green cloud computing. As a future work, we will intend to draw a specific migration plan for the implementation of server consolidation, with considering the intermediate migrations needed when a deadlock occurs in the actual migration process.



---

*Source: 613719-2014-07-07.xml*