Service-Oriented Virtual Machine Placement Optimization for Green Data Center

Abstract

The first service-oriented virtual machine (VM) placement for green data center is designed in this work. Integer Linear Programming (ILP) is the problem design basis. The Tree algorithm is proposed to place VM role instances at the lowest communication cost, economizing the construction cost with fewer physical servers. Another Forest algorithm is also proposed for balancing the computation load between the physical machines. Both of the proposed algorithms are formulated on the graph theoretic technique and evaluated and analyzed using the Best Fit algorithm in the simulations. Although the total power consumption and average utility of both proposed algorithms are slightly impaired, the unnecessary outbound communication cost is significantly eliminated and decreased, especially in the immense number of services. The results show that the proposed Tree and Forest algorithms provide lower communication cost than the Best Fit algorithm, and achieve green communications for large scale environment such as cloud or green data center.

1 Introduction

Virtualization technology was announced by the International Business Machines (IBM) Corporation in 1971 [1]. Many researchers have regarded it as the first step in migrating existing services into the cloud environment [2]. A cloud service is executed using various virtual machines (VMs). These VMs are packaged in a physical server or spread over several physical machines. Due to the increased popularity of cloud computing researchers have intensely investigated virtualization technology [3]. The renowned market research company Gartner [4] predicted this technique might be the first of ten important technologies in 2009 [5]. As mentioned, the virtualization technique is regarded as the principal step, fueling the evolution of cloud computing since 2009. Cloud computing was noted the most important technology Gartner predicted in 2010 [6] and 2011 [7], and it remained on the prediction list in 2012 [8]. According to state-of-the-art cloud development, it is obvious that virtualization technology must be extensively discussed and investigated.

Various virtual technique issues have been widely investigated widely. The problems that come from virtualization can be divided into two categories, the preliminary construction [9–11] and the subsequent management [12–14]. For instance, the resource allocation [15] and provisioning problem [16] for VMs placement in the data center. Researchers conducted an optimization strategy between the deployment cost and system performance. Researchers proposed a blind scheduling algorithm [17] to maintain the fairness at each time point in mobile media cloud, and further proposed a blind online scheduling algorithm [18] to achieve asymptotic optimality. Other researchers studied the VM migration condition and strategy, such as [19, 20]. When physical machine resources are exhausted the virtual machine migrates from the current infrastructure to other available machines. However, the existing services and tasks should be continued uninterrupted. A novel technology for VM management called Live Migration [21] has become well-known in recent years.

This paper investigates the Service-Oriented VM Placement Optimization problem (or simply SOVMPO throughout this paper) defined based on Integer Linear Programming (ILP). We propose two algorithms named the Tree and Forest algorithms for solving the SOVMPO problem. Both proposed algorithms are formulated based on the graph theoretical technique. The Forest algorithm is proposed for balancing the traffic load between VMs, but wastes construction and communication cost. The Tree algorithm is designed to minimize the communication cost between VMs that belong to the same service. This research has three major contributions: 1) we formulate the service-oriented VM placement problem which is called SOVMPO and propose two algorithms based on graph theory for solving this problem; 2) the calculation time for both algorithms increases linearly with the increased number of services; 3). The Tree algorithm reduces the total power consumption, enhances the average utility of physical servers and reduces the communication cost as well.

This paper is organized as follows. Section II introduces current VM placement research and compares the different approaches. Section III defines the ILP model for optimizing the VM placement problem and explains the proposed algorithms. In section IV we present the optimization results and discuss the simulation results. Conclusions from this research are drawn in section V.

2 Background and related works

The VM data center related problem was studied extensively in past literature, such as VM placement, resource allocation, resource provisioning, minimizing construction cost and network traffic load. This paper focuses on minimizing the communication cost [22, 23] based service-oriented virtual machine placement in data center networks. The data center network infrastructure and communication cost are discussed and studied. The differences in VM role instances are introduced because a job or service may be executed using several VM role instances in cloud computing.

2.1 Data center infrastructure

The Cisco data center network infrastructure is a three-tier architecture [24] that includes the core common services, aggregation and server access. The data center infrastructure is shown in Fig. 1, composed of a tree structure according to the current data center architecture diagram. The network architecture and topology effect on the network resource in data center [25]. The three-layer architecture is adopted in most of enterprises and data centers. Most of intra-data traffic traverses within switch and physical server, thereby we consider and investigate the service-oriented VM placement. Although the fat-tree architecture is mentioned and studied in recent researches [26, 27], we adopted the original three-tier architecture structured as a tree topology in the data center infrastructure. Because this architecture is more suitable for fitting the real data center environment data center infrastructure modification is unneeded.

Fig. 1

Data center network infrastructure

The top layer is the core router which connects with all middle-tier aggregations but does not connect with other core routers. The middle layer is the aggregation that only connects to one or two edge switches for access. This implies that the switches and physical servers under the middle-tier aggregation comprise a local area network (LAN). The bottom layer is the edge switch, with one or more physical servers accessing the edge switch for routing data information. Without loss of generality, the communication cost for two arbitrary physical servers in the same LAN is lower than two separate LANs. In other words, the cost of inbound communication within a LAN is lower than the cost of outbound communication between two LANs.

2.2 VM role instances

The identity of VM role instances is determined according to their working categories. For instance, the different VM role instances are in charge of different works. Windows Azure [28] has two VM roles which are web role and worker role.

The first type of VM instance is the web role instance. It executes the interactions between web applications or HTTP services. The web role instance is responsible for the communication between user and the operating process. On the other hand, the worker role instance is a background process that executes the tasks or jobs in Windows Azure. In order to achieve the elastic computing in cloud environment an application service or job may be executed by many VM instances. When the computing resource is insufficient in the same service type, the number of worker role instances can be increased and scaled up dynamically. Therefore, the number of worker role instances is always greater than the web role instances. Two types of VM instances are considered by this research in the SOVMPO problem. The communication cost and utility rate are calculated from these VM role instances. We assume that a service is preceded by a web role and four worker role instances.

2.3 Related works

In the existing literature some researchers focused on placing VMs in different data center architectures [26, 27, 29] while others investigated the VM placement in distinct orientations [30, 31].

The works most related to ours are [26, 27, 30, 31]. In [26, 27], the three-tier architecture in data center is also considered. However, the researchers in [26] surveyed the influences of TCP Incast and congestion notification unlike the communication cost of inbound and outbound in our work. The traffic characteristic is not covered in [26] but we eliminate the costs from the outbound communication, which minimizes the traffic loads within different LANs. Although the data center architecture is considered, two parts differentiate [27] our work. First, in spite of the considered architecture, the VL2 [32], fat-tree [26] and BCube [33] architecture are adopted in [27], but we follow the three-tier architecture of traditional data center networks in this work. Second, the proposed work in [27] is based on traffic-aware VM placement while in our work the proposed algorithms are based on service-oriented VM placement. In [30, 31] both researches are based on application-aware viz. AppAware. Although the proposed scheme in [30] is based on the graph theoretical technique as our work, the authors focus on the application-aware VM migration unlike the data center placement problem in our work. The VM demand, physical machine capacity and communication are considered in [30] which is similar to our work, but the authors investigated the communication frequency performance unlike the communication cost in this paper. Finally, the distinct orientation towards VM placement is considered in [31], but some parts are still different. First of all, the AppAware orientation is completely differentiated from our service-oriented VM placement algorithms. The authors propose an application-aware VM placement algorithm based on the convex optimization theory unlike the proposed algorithms in this paper based on ILP model and graph theoretical technique. We propose a novel VM placement scheme based on service and investigate a vital issue minimizing the inbound and outbound communication costs which are frequently neglected in other studies.

3 Proposed algorithms

3.1 Problem definition

The virtual machine optimization problem for service-oriented cloud networks is formulated based on integer linear programming (ILP). The definitions of variables used in SOVMPO are listed in Table 1.

Table 1 Definition of symbols

In the cloud infrastructure a tree structure is used to connect the hardware which includes the routers, middle-tier aggregations, switches and servers. The same structure is also applied to the virtual machines within the physical servers. Therefore, we let V be a set of nodes and E be a set of edges between nodes. Given a graph G = (V, E), where V = V ₁ ∪ V ₂ and E = E ₁ ∪ E ₂. It can be easily shown that V ₁ ∩ V ₂ = ∅ and E ₁ ∩ E ₂ = ∅. Assume that V ₁ = {z ₁, …, z _k } with |V ₁| = k, and V ₂ = {q ₁, …, q _s } with |V ₂| = s.

The nodes in V ₁ are the equipment in cloud infrastructure, which can be core routers, middle-tier aggregations, edge switches and physical servers. Hence, z _i  ∈ {0, m _CR , m _MA , m _ES , m _PS }. We then consider the available links between z _i and z _j in V ₁. Let available link

$$ {x}_{i,j}=\left\{\begin{array}{l}1,\kern0.5em if\ \left({z}_i,{z}_j\right)\in {E}_1\ and\ {z}_i\cdot {z}_j\ne 0\hfill \\ {}0,\kern0.1em otherwise\hfill \end{array}\right.. $$

(1)

The nodes in V ₂ are the virtual machines within the physical servers, which can be classified into web and worker roles within two types of instances. That is, q _i  ∈ {0, n _Web , n _worker }. The same structure is also applied to the virtual machine, in which each cloud service contains one worker role instance and may contain multiple worker role instances.

We next consider the available links between the physical server z _i and virtual machine q _j . The available links between web role instance q _i and worker role instance q _j are considered. Let available link

$$ {y}_{i,j}=\left\{\begin{array}{l}1,\kern0.1em if\ \left({z}_i,{q}_j\right)\notin \varnothing\ and\ {z}_i\cdot {q}_j\ne 0\hfill \\ {}1,\kern0.1em if\ \left({q}_i,{q}_j\right)\in {E}_2\ and\ {q}_i\cdot {q}_j\ne 0\hfill \\ {}0,\kern0.1em otherwise\hfill \end{array}\right.\ . $$

(2)

The web role instance q _i must be executed in a physical server, defined as ${w}_{q_j}={w}_{PS}$, where q _j  ∈ n _Web . However, a worker role instance q _j may subordinated a physical server or a web role instance, which is defined as

$$ {w}_{q_j}=\left\{\begin{array}{l}{w}_{PS},\kern0.1em if\ {q}_j\ is\ nested\ in\ a\ physical\ server\hfill \\ {}{w}_{web},\kern0.1em if\ {q}_j\ is\ nested\ in\ a\ web\ role\ in stance\hfill \\ {}0,\kern0.1em if\kern0.1em {q}_j=0\hfill \end{array}\ .\right. $$

(3)

For service-oriented virtual machine optimization, because a single service may be executed by several virtual machines, we consider the communication cost between the virtual machine instances in a service. The virtual machine service type q _j is defined as ${\xi}_{q_j}^k$, where k ∈ Ν and q _i  ≠ 0. Moreover, the utility of a virtual machine q _j in a physical server z _i is considered in our model, which is defined as ${u}_{i,j}={y}_{i,j}{w}_{q_j}$.

In this given tree graph we assume that a communication cost exists for each available link between two vertices. The communication cost between virtual machine q _i and q _j in service k is defined as

$$ Cos{t}_{i,j}^k=\left\{\begin{array}{l}{C}_{i,j}^k,\kern0.5em if\ {x}_{i,j}\cdot {y}_{i,j}\ne 0\hfill \\ {}0,\kern0.5em if\ {x}_{i,j}\cdot {y}_{i,j}=0\hfill \end{array}\right.. $$

(4)

The ILP model for SOVMPO problem is defined as follows.

Minimize

$$ {\displaystyle {\sum}_{i=1}^i{\displaystyle {\sum}_{j=1}^j{\displaystyle {\sum}_{k=1}^k{C}_{i,j}^k}}} $$

(5)

subject to

$$ {z}_k\ge 0,\mathrm{f}\mathrm{o}\mathrm{r}\ \forall k\in V $$

(6)

$$ {q}_s\ge 0,\mathrm{f}\mathrm{o}\mathrm{r}\ \forall s\in E $$

(7)

$$ {x}_{i,j}\in \left\{0,1\right\},\mathrm{f}\mathrm{o}\mathrm{r}\ \forall i,j\in {E}_1 $$

(8)

$$ {y}_{i,j}\in \left\{0,1\right\},\mathrm{f}\mathrm{o}\mathrm{r}\ \forall i,j\in {E}_2 $$

(9)

$$ {\xi}_{q_j}^k\ge 0,\mathrm{f}\mathrm{o}\mathrm{r}\ \forall k\in N $$

(10)

$$ {\displaystyle \sum {u}_{i,j}\le \delta,\ \mathrm{f}\mathrm{o}\mathrm{r}\ \forall i\in {V}_1\ \mathrm{and}\ \forall k\in {V}_2} $$

(11)

$$ {C}_{i,j}^k\ge 0,\mathrm{f}\mathrm{o}\mathrm{r}\ \forall i,j\in V $$

(12)

3.2 Tree algorithm

The Tree algorithm is proposed to optimize the web role instances and worker role instances such that the communication cost is minimized. Some notations are clarified before introducing the Tree algorithm.

The definition of the vector q, whose i-th element denotes the placement condition on the corresponding position. From this point of view, q _x denotes the role instance in the vector q corresponding to the vertex x ∈ V ₂. For example, if a web role instance is placed on the vertex x, then from the indication vector point of view, q _x  = c _web . This concept can be generalized so that ${q}_X$ is well-defined, where X ⊆ V ₂. The definition of vector z, whose i-th element denotes the physical server condition on the corresponding location. For example, z _x denotes the physical server in the vector z corresponding to the vertex x ∈ V ₁. Moreover, we define the U(z) as the utility of the physical server z.

Let G = (V, E) be a graph. Denote X and Y as subsets of vertices. Then, f _d (G, X, Y) is used to generate a descendant ordered list $S$ of the elements in X acccording to the adjacent number of vertices in $Y$ based on G. For example, if there are 3 and 4 adjacent vertices in Y for the vertex x ₁ ∈ X and x ₂ ∈ X, respectively, then x ₁ is behind x ₂ in the ordered list S. Note that the order of the vertices with the same degree can be arbitrary. Since S is an ordered list, S[i] is denoted as the i-th vertex in S. In addition, N(G, x) is defined as the set of neighboring vertices of the vertex x on the graph G. γ(G, X) be the vertex-induced subgraph of G with the set of vertices V\X. After introducing the functions, the descriptions of Tree algorithm are shown as Algorithm 1.

 Algorithm 1: Tree Algorithm ( G, z, δ )

Input: G: underlying graph

z: vector indicating the placement of web and worker role instance

     δ: maximum utility of physical server

01 Ω₁ = V ₁, Ω₂ = V ₂, Δ = ϕ

02 repeat

03 S = f _d (G, Ω₁, Ω₂)

04 Δ = Δ ∪ S[1]

05 Ω₁ = Ω₁\S[1] and Ω₂ = Ω₂\N(G, S[1])

06 until Ω₂ = ϕ

07 ${G}_r=\gamma \left(G,{\Omega}_1\right),\ where\ {G}_r=\left({V}_G,\ {E}_{G_r}\right)$

08 ${q}_{V_{G_r}}={n}_{worker}$, where ${\xi}_{V_{G_r}}^k=k$

09 while G _r is disconnected and U(z) < δ

10 S = f _d (G _r , V ₁\Ω₁, Ω₁)

11 G _r  = γ(G, Ω₁ ∪ S[1])

12 ${z}_{V_{G_r}}={n}_{web}$

13 repeat

14 $S={f}_d\left({G}_r,{\mathrm{V}}_{G_r},{\Omega}_2\right)$

15 z _s[1] = n _web

16 until U(z) = δ

Lines 2 to 8 are used to determine the service type in the subset of virtual machine. The chosen subset in the Tree algorithm is based on the number of covered virtual machines given as the same service type. Since the same virtual machine service type in lines 2 to 8 could be disconnected, lines 9 to 12 are used to link the unconnected virtual machines. In line 13 to 16, we examined the utility of a physical server. The physical server utility property should be limited within δ. Because the characteristic of our problem, the linear programming in the paper is always able to have a feasible solution.

The Tree algorithm performance is dominated by lines 2 to 6. A sorting of O (n) elements is required in each iteration leading to O (nlog n) time complexity. O (n) iterations are needed in the worst case. Therefore, O (n ² log n) time complexity is required.

3.3 Forest algorithm

According to the Tree algorithm notations we introduce only the new functions used in the Forest algorithm. Let BFS(G, x) be a subgraph constructed by applying breath-first-search on the graph G rooted at the vertex x. Let ${f}_{BFS,{\xi}^k}(G)$ be the graph composed of subgraphs constructed by service type ${\xi}_{q_j}^k$ breadth-first-search on the graph G. The Forest algorithm descriptions are shown as Algorithm 2 after introducing the functions.

 Algorithm 2: Forest Algorithm ( G, z, δ )

Input: G: underlying graph

z: vector indicating the placement of web and worker role instance

     δ: maximum utility of physical server

01 Ω₁=V ₁, Ω₂ = V ₂, Δ = ϕ

02 repeat

03 S = f _d (G, Ω₁, Ω₂)

04 Δ = Δ ∪ S[1]

05 Ω₁ = Ω₁\S[1] and Ω₂ = Ω₂\N(G, S[1])

06 until Ω₂ = ϕ

07 ${G}_r=\gamma \left(G,{\Omega}_1\right), where\ {G}_r=\left({V}_G,\ {E}_{G_r}\right)$

08 i = 0, Ω ^′₁  = Ω₁

09 repeat

10 i = i + 1

11 randomly choose a vertex x from ${V}_{G_r}$

12 G ^s _i  = BFS(G _r , x), where G ^s _i  = (V ^s _i , E ^s _i )

13 Ω ^′₁  = Ω ^′₁ /x

14 until Ω ^′₁  = ϕ

15 for j = 1 to i

16 S = f _d (G ^s _j , Ω₁, Ω₂)

17 ${z}_{s\left[1\right]}={n}_{web\;}and\ {z}_{s\setminus s\left[1\right]}={n}_{worker},where\;{\xi}_{V_{G_r}}^k=k$,

18 while U(z) ≤ δ

19 S = f _d (G _r , Ω₁, Ω₂)

20 z _s[1] = n _web

21 until U(z) = δ

In Algorithm 2, lines 2 to 14 are used to construct the physical server subset on which either the web role instance or work role instance are appropriately executed. Note that the selected physical server is still empty now and the web role or work role instance placement needs to be determined later. Since the physical server selected in lines 2 to 14 could constitute a forest, line 15 to 17 are used to place at least one web role in each service type. Lines 18 to 21 are used to guarantee that the utility of vertex z does not exceed the maximum utility of a physical server.

The Forest algorithm performance is dominated by lines 2 to 6. A sorting of O (n) elements is required in each iteration leading to O (nlog n) time complexity. O (n) iterations are needed in the worst case. Therefore, O (n ² log n) time complexity is required.

3.4 Proof of NP-hard problem

In this subsection we prove that the SOVMPO problem in cloud computing environment is a NP-hard problem. Therefore it cannot be solved in polynomial time. In other words, there is no efficient algorithm for minimizing the communication cost between VM role instances. We find the traveling-salesman problem (TSP) [34] is quite similar to our SOVMPO problem. TSP is a classical and well-known NP-hard problem. A brief description is given below. A list of cities and their pair distances, the TSP problem is to find out the shortest potential route that visits each city once and then back to the original city. Given an undirected graph G = (V, E), and each edge (u, v) ∈ E has a non-negative integer cost c(u, v). Then, find a Hamiltonian cycle of G with minimum cost ∑c(u, v).

After introducing the TSP problem we prove that the proposed problem is polynomial time reducible to TSP problem, that is SOVMPO ≤ _p TSP. The given graph G in TSP problem corresponds to the given graph G in the SOVMPO problem, which means the geographic map is fully mapped to the cloud environment, including the infrastructure, physical and virtual machines. The set of cities V is mapped to the cloud infrastructures V ₁ and VM role instance V ₂. The set of edges E is mapped to the communication links E ₁ and E ₂. Finally, the non-negative integer cost c(u, v) in TSP can be matched with the proposed communication cost C ^k _i,j between the virtual machines q _i and q _j in service k. In other words, to find a Hamiltonian cycle of G with minimum cost is equal to finding a service-oriented VM placement method with minimum cost. From the above explanation, the proposed SOVMPO problem can be reduced to the TSP problem. Because the TSP problem is NP-hard, we conclude that the SOVMPO problem in our approach is also a NP-hard problem.

3.5 Queuing analysis

Let λ, r _source , and n be the rate at which messages arrive at physical servers, the rate the virtual machines emit a message, and the average number of virtual machines associated with a physical, respectively. For simplicity, we assume that the processing time at physical machines can be neglected.

Afterwards, we can regard the physical server as an M/G/1 queuing system due to the fact that the arrival process is Poisson with a rate λ. Let the random variable s and p denote the message service time and the probability that the queue is idle when a message is incoming, respectively. In addition, assume that the rate at which the physical server emits the message is ${r}_{PS}=\frac{1}{T_{PS}}$. As for the service time $s$, with the probability $p$ it will experience an average service time $\frac{T_{PS}}{2}$ and with the probability 1 – p its average service time is T _PS . After the calculation, we can obtain

$$ E\left[s\right]=p\cdot \frac{T_{PS}}{2}+\left(1-p\right){T}_{PS}, $$

(13)

and

$$ E\left[{s}^2\right]=p\cdot \frac{T_{PS}^2}{3}+\left(1-p\right){T}_{PS}^2. $$

(14)

In addition, we can also know from the queuing theory that p = 1 − λ ⋅ s. Then, we have

$$ E\left[s\right]=\frac{T_{PS}}{2-\lambda \cdot {T}_{PS}}, $$

(15)

and

$$ E\left[{s}^2\right]=\left(1-\lambda E\left[s\right]\right)\frac{T_{PS}^2}{3}+\lambda \cdot E\left[s\right]\cdot {T}_{PS}^2. $$

(16)

As a result, the average delay d for each message at the physical server can be calculated as

$$ d=E\left[s\right]+\frac{\lambda \left({E}^2\left[s\right]+E\left[{s}^2\right]\right)}{2\cdot \left(1-\lambda E\left[s\right]\right)}. $$

(17)

4 Simulation results

4.1 Planning case

We illustrate the Tree and Forest algorithm with a simulated optimization case in this section. In this VM optimization case there are 12 physical servers and 4 service types, which means that 4 web role instance are placed within 12 servers. Moreover, there are 14 worker role instances in 4 service types. The network topology of the cloud infrastructure is constructed as a fat-tree structure. The VM placement results for Tree and Forest algorithms are shown in Figs. 2 and 3.

Fig. 2

The VM optimization result by Tree algorithm

Fig. 3

The VM optimization result by Forest algorithm

Before explaining the optimization result we have four assumptions in our optimization algorithm. First, we assume that all network equipment are connected, which means there are no disconnection links between the current layer and upper layer. For instance, the physical server can connect with the edge switch and the edge switch is able to connect to the middle-tier aggregation. The same situation exists with the middle-tier aggregation and core router. Second, we assume that there are two kinds of communication costs between virtual machines. The first is the inbound communication cost which represents that the web role and work role instances exist within the same physical server. The second one is the outbound communication cost, which means that the work role instance is placed in a different physical server than the web role instance. Then, we utilize subnetting approach to subnet data center network. The left child under a middle-tier aggregation is assigned to the same class, and the right child is another class. Therefore, we can evaluate the number of inbound and outbound communication cost by calculating the classified packets. One thing should be mentioned, the outbound communication cost outweighs the inbound communication cost. The third assumption is that the power consumption of each physical server is calculated. Moreover, the server can be shut down if the utility is lower than a specified threshold. Finally, we assume that the web role instance must be connected directly to a physical server. Unlike the web role instance, the worker role instance is able to connect with a physical server or a web role instance, which means that the worker role instance can link to the physical server through a web role instance.

The VM optimization result for the Tree algorithm is shown in Fig. 2. The Tree algorithm inclines the VM placement in the same physical server until the utility reaches the maximum utility δ. This implies that the depth-first-search method is applied in the Tree algorithm. We adopt the concept of service-oriented when deploy the different types of VMs. In order to decrease the unnecessary outbound communication cost, the proposed Tree algorithm utilizes depth-first-search approach to place the same service type of VMs into the same physical server. According to our assumptions the Tree algorithm achieves high power consumption efficiency with a lower communication cost. Furthermore, most of the idle servers are able to shut down to eliminate consuming power. However, an implicit problem of the Tree algorithm is that used servers are always in high utility. If the workloads of these servers increase, the server and system may crash due to overload. Therefore, the Tree algorithm requires a compatible migration mechanism.

The VM optimization result for the Forest algorithm is shown in Fig. 3. According to the breath-first-search method applied to the Forest algorithm, most physical servers are executed using few VM role instances. The Forest algorithm achieves better computation load balancing between physical servers, hence the probability of system failure is much lower than that for the Tree algorithm. Nevertheless, parts of VM role instances in the same service may execute between different physical servers. As stated before, the outbound communication cost of the Forest algorithm is greater than that for the Tree algorithm. The average server utility is low, meaning that most of the power consumption is wasted.

4.2 Simulation results

To verify the performance and improvement we used Dev-C++ 5 to implement the proposed algorithms. Each result is repeatedly simulated five times to the average. The proposed algorithms are compared with the benchmark method named Best Fit algorithm, which represents the VM placement method without the service-oriented concept. The Best Fit algorithm always places the most suitable VM in the same physical server according to its’ utility and deploys the VMs to a new physical server until the utility of previous server is full. In the simulation experiment the number of physical servers was 30. Each service includes at least one web role instance and one worker role instance. Therefore, we assume that the number of web roles is the same as the number of services and the worker role instances are always three times the number of web role instances. For example, if the number of services is 100, the number of web role instances is also 100 and the worker role instances number 300. There are 50 web role instances and 150 worker role instances in the general simulation case. The cloud infrastructure network topology is the Tree structure and the VM placement structure is a tree structure. We assume that the maximum power of one physical server is 500 watts per hour, and the server idle status threshold is 300 watts per hour. One thing that should be noted is that if the power consumption of a server is lower than 30 %, the server is regarded as an idle server. The maximum utility rate represents that the highest utility rate of a physical server is defined as 90 %. All simulation parameters are shown in Table 2.

Table 2 Simulation parameters

We increased the number of services to ten for each step from 10 to 100, and the numbers of web role instances with it. The worker role instances are then three times the number of web role instances. As Fig. 4 shows, the calculation time in both proposed algorithms and Best Fit algorithm are linear and approximately 1 to 2.5 s. Although the proposed algorithms spend more time than the Best Fit algorithm in the optimization procedure, the difference is smaller than 1 s and acceptable. According to this result, we can say that both proposed algorithms are appropriate for VM optimization and efficient even if the number of services is large. Originally, the computational cost of our formulated problem grows exponentially with the number of services. However, now the computational cost grows linearly with the number of services. Therefore, our proposed algorithm has an efficient calculation time on a NP-hard problem.

Fig. 4

Simulation results of calculation time

In [35] the authors pointed out the non-energy proportionality problem. A physical server consumes almost 50 % of the total energy usage when it is in the idle state. Therefore, we consider that the status of most physical servers should be power off in the beginning because it is unnecessary to switch on numerous servers when there are no service requests. A comparison of the total power consumption of both proposed algorithms is shown in Fig. 5. The total power consumption of the Tree and Forest algorithm is always higher than that of the Best Fit algorithm. The Best Fit algorithm fills up the active physical servers by fitting VMs as many as possible, hence its total power consumption is the lowest. Although the power consumption of Tree algorithm is higher than the Best Fit algorithm, the disparity is small. The Forest algorithm increases acutely when the number of services increases from 10 to 30 because most of the physical servers start up due to the VM placement. In other words, most of the physical servers are active when there are 30 service requests. However, the active servers are working at a low utility rate and waste much power when the server is in idle status. The Tree and Best Fit algorithms efficiently preserve power consumption.

Fig. 5

Simulation results of total power consumption

In [36] the authors showed the low utilization server problem in the data center. The low utilization problem also implies a power efficiency problem. The average server utilization was reported to be 30 % even in the Google data center. The average physical server utility is shown in Fig. 6. Before discussing the results a definition of average utility is stated. We only calculate the utility rate of physical servers in which VM instances are executed. The result shows that the average utility of the Best Fit algorithm is always the highest, because it places the most appropriate VM instances based on the relation between VM utility and physical server. In the Tree algorithm VM instances with the same service have the higher priority for placement in the same physical server. Although the average utility of the Tree algorithm is slightly lower than the Best Fit algorithm, active servers are effectively utilized. Unlike the Tree algorithm the Forest algorithm awakens more physical servers because the breath-first-search method is applied and achieves better load balancing. The Best Fit algorithm achieves higher energy efficiency and maximizes the server utility. The Tree algorithm is similar. Both the Best Fit and Tree algorithms are more suitable for use in green data centers compared to the Forest algorithm.

Fig. 6

Simulation results of average utility

The communication cost with different numbers of servers is shown in Fig. 7. It can be easily understood that higher communication cost accompanies more services. In order to reduce the outbound communication cost for the same service, the proposed Tree algorithm always places VM role instances of the same service type in the same physical server, except when the server utility rate exceeds the maximum utility limitation. Moreover, regardless if the number of services is big or small, the outbound communication cost of the Tree algorithm is significantly lower than the Best Fit algorithm. Unlike the Tree algorithm, the Forest algorithm separates the VM instances for server load balancing. However, the outbound communication cost of the Forest algorithm is lower than that for the Best Fit algorithm when the number of services is greater than 70. It is very important that the Tree algorithm hugely eliminates unnecessary outbound communication cost in any scale network, while the Forest algorithm fits large scale networks such as the cloud environment or data center networks.

Fig. 7

Simulation results of communication cost

The utility rate stands for the benchmark of a physical server, hence a higher utility rate serves more VM instances. We adjusted the maximum utility rate limitation from 50 to 90 % and observed the communication cost from both algorithms, as shown in Fig. 8. In this scenario the number of physical servers and services were 30 and 50. The web and worker role instances were 50 and 150. If the maximum utility rate is reduced, the amount of outbound communication cost will increase because of the VM instances in the same service might be separated into different servers. However, the outbound communication cost of both proposed algorithms are always lower than that from the Best Fit algorithm. Regardless of the scenario, both proposed algorithms deployed VM instances within the same service type on a physical server as first priority. We summarize that both proposed algorithms reduce the outbound communication cost and agree with the higher utility rate. This also implies that both proposed algorithms provide energy efficiency for green cloud services.

Fig. 8

Simulation results of communication cost with different utility rate

5 Conclusions

This paper investigated the service-oriented VM placement problem in cloud data centers. We formulated the service-oriented VM placement optimization problem viz. SOVMPO problem based on ILP and proved it is a NP-hard problem by reducing it to the well-known traveling-salesman problem. Two heuristic algorithms, the Tree and Forest algorithms were proposed based on service-oriented VM placement and solving the SOVMPO problem in linear time. Lastly, both proposed algorithms were evaluated and compared with the Best Fit algorithm, standing in for non-service oriented VM placement in the simulation results.

For VM placement planning in current data center networks, green communication is a vital issue due to the three-tier architecture. We proposed the Tree and Forest algorithms to construct a network based on the service-oriented VM placement concept. Although the familiar Best Fit algorithm used the least power consumption and sustained the highest average utility in simulations, it led to enormously redundant outbound communications. Both proposed algorithms consumed slightly extra power consumption due to the service-oriented VM placement, but accomplished green communication with less outbound costs significantly. The Tree algorithm shuts down unnecessary physical servers to reserve power, while the Forest algorithm takes the computation loading into consideration during load balancing. The simulation results show that both proposed algorithms achieve less unnecessary outbound and more valuable inbound communication costs than the Best Fit algorithm. The Forest algorithm decreases 22 % outbound communication cost, and Tree algorithm decreases 92 % outbound communication cost significantly. We believe that our proposed algorithms are suitable for service-oriented VM placement in cloud data centers, particularly suited for large scale green data centers. We will investigate dynamic VM allocation with service-oriented concept in the future. In addition, the network architecture and topology in data center will be studied also.