Virtual Machine Placement Using JAYA Optimization Algorithm

ABSTRACT

Cloud computing has become more popular with the ability to run HPC applications on cloud infrastructures. Improving the energy efficiency of these data centers become important for all the cloud providers. We observe that bin-packing heuristics such as Best-Fit Decreasing for energy-aware virtual machine (VM) allocation could not provide the optimal solution to minimize the total energy consumption of the data center. In this work, we explore the virtual machines provisioning considering multi-dimensional resources and energy consumption of the data center. We propose to use JAYA algorithm for optimal placement and minimizing the energy consumption of the data center. Our simulation results show the proposed algorithm could reduce the total energy consumption up to 34% and SLA by 15% compared with the Particle Swarm Optimization and power-aware best-fit decreasing.

Introduction

Cloud computing has been revolutionizing the IT industry, making computing and software as a utility. Cloud computing provides an extensive variety of services and applications to consumers in a pay-as-you-go model. It offers tremendous opportunities for online distribution of services using virtualized data centers. The energy consumption in the Information and communications technology (ICT) sector has increased exponentially over the last years (Shehabi et al. 2016). The world’s ICT infrastructure is estimated to consume 10% of global electricity usage. U.S Data centers consumed 1.4% and 1.8% of all the electricity used in U.S. in 2010 and 2014, respectively (Mills 2013; Van Heddeghem et al. 2014).

Figure 1 shows a graph regarding “2010 energy efficiency scenario” versus “current trends” of electricity consumption in data centers. It is forecasted that the energy consumption share of IT sector will rise up to 13% by 2030 (Reddy, Gangadharan, and Rao 2018) and data centers account for maximum greenhouse gas emissions on all parts of ICT (Whitehead et al. 2014). A survey by IBM indicates that the average resource utilization of several data centers is less than 20%. Further, 70% of power is consumed by idle servers in several data centers (Barbara et al. 2012; Pernici et al. 2012). Thus, we observe that a source of high energy consumption is not only the amount of computing resources used and power inefficiency of the hardware but also lies in the inefficient usage and dynamic power ranges of servers.

Figure 1. Datacenter energy consumption trends (Van Heddeghem et al. 2014).

Green IT offers the use of several green metrics (Reddy et al. 2017) that capture efficiency and environmental characteristics. The goal is to reduce the energy consumption of servers and thermal cooling costs by efficiently utilizing the available resources (Chaudhry et al. 2015). This is possible with an efficient virtual machine placement mechanism to decommission unused servers. Further, migration and dynamic placement of virtual machines becomes significant for efficient data center management (Fukunaga, Hirahara, and Yoshikawa 2017; Garg et al. 2014). During the provisioning of resources to virtual machines, the resource utilization should be maximized by reducing the number of active hosts (Ricciardi et al. 2011). We propose and develop an efficient virtual machine provisioning mechanism to reduce the amount of energy used in a homogeneous and heterogeneous data centers.

The paper is organized as follows. Firstly, the related work on virtual machine placement and consolidation is presented in Section 2. Then, in Section 3, we proposed to use JAYA algorithm for energy efficient VM provisioning. Section 4 reports the main findings and comparison of our proposed algorithm with state-of-the-art approaches. Finally, Section 5 presents the conclusion and the future work.

Literature Review

Rapid increase in the number of internet users and the potential of video streaming applications, on-line video games, and social networking requires more data centers throughout the world. World wide data center energy consumption is estimated at 26 GW, drawing near 1.4% of world electricity consumption with a growth rate of 12% per year (I. COP21 2016; Metz 2007). According to GeSI (Riva 2012), the share of total carbon dioxide (CO${ }_2$) emissions from ICT is estimated to grow from 1.3% of global emissions in 2002 to 2.3% in 2020. Governments are observing and analyzing the increasing energy consumption and Green House Gas (GHG) emission by IT industry. Thus, focus on improving the efficiency of the data center operations.

Garg et al. (2014) considered different Quality of Service (QoS) requirements of workloads and proposed a VM provisioning approach to maximize the resource utilization and profit. Buyya et al. (Beloglazov and Buyya 2010) proposed an energy efficient resource provisioning in a data center using a threshold-based heuristic algorithm. Addya et al. (2017) proposed a coalition-based cooperative structure to compute the pricing that users pay for their requested VMs and used Integer Linear Programming (ILP) for energy-aware virtual machine placement. Ripal et al. (Nathuji and Schwan 2007) proposed a Virtual Power approach with an aim to support the isolated and independent operation of virtual machines and to coordinate the effects of the diverse power management policies among the virtual machines. Implementing VPM rules are challenging in this model. This approach may reduce the server performance because of application-specific VM consolidation. Kim, Eom, and Yeom (2012) described a user-level load balancer for parallel applications, considering heterogeneous architectures. This approach improves the CPU utilization and coexist with the kernel-level load balancer. Li et al. (2013) proposed an approach based on a multi-dimensional space partition model for efficiently placing VMs to increase the resource utilization of data centers. However, SLA violations and VM migration cost are not taken into consideration.

Wang and Xia (2016) solved VM placement problem using a mixed-integer programming approach. This approach takes more time when there are many virtual machines requests to be placed. Duan et al. (2017) developed a model that considers the predictions from fractal mathematics model and schedules virtual machines using an improved ant colony algorithm. Based on load trend prediction, the model executes the scheduler while minimizing energy consumption. Wang et al. (2016) proposed an improved particle swarm optimization (PSO) to place data-intensive services with minimum energy consumption and with guaranteed quality of service(QOS) in a data center. Wu, Tang, and Fraser (2012) proposed an efficient VM Placement based on a Simulated Annealing (SA) approach. But this approach is not suitable for dynamic virtual machine consolidation. Goiri et al. (2012) examine the multifaceted resource management considering the cost of energy consumption, SLAs, outsourcing capabilities, heterogeneity management, and economic modeling in data centers. They proposed an algorithm that tries to find those combinations from the scoring matrix that maximizes the overall system benefit. However, they confined the number of movements per round because this algorithm has a chance to enter into a periodic cycle without converging. Dong et al. (2013) described the minimum cut for clustering of related VMs together to minimize the total network traffic. The algorithm helps to find the path that has a larger distance and less traffic between two virtual machines. Then, they used best-fit algorithm to reduce the energy consumption of the servers. But, this approach has not considered server overloading and network congestion.

Zhang et al. (2017) developed energy-efficient VM selection algorithms for overloaded hosts based on dynamic programming and greedy algorithm. Cao and Dong (2014) proposed an energy-aware heuristic framework for VM consolidation to achieve a better energy performance trade-off. Most of the researchers modeled VM consolidation as a bin packing problem and solved using greedy heuristics (Chen and Ye 2016; Li et al. 2012, 2013). Table 2 presents the summary of the said methods, focusing on the energy consumption of the data centers.

Table 1. Summary of the literature.

Reference	Methodology	Remarks
Addya et al. (2017)	Integer Linear Programming	Does not consider the energy consumption
Buyya et al. (Beloglazov and Buyya 2012)	Adaptive threshold-based approach	Multiple resource types are not taken in to account and does not guarantee the optimal solution
Garg et al. (2014)	Non-Heuristic approach	Works better for non-interactive and transactional applications. Energy consumption and different resources are not considered.
Ripal et al. (Nathuji and Schwan 2007)	Policy based coordination	Multiple resource types are not taken in to account. This approach may reduce the server performance because of application specific VM consolidation.
Li et al. (2013)	Multi-dimensional space partition model	Energy consumption is considered. However SLA violations multiple resource types and VM migration cost are not taken into consideration.
Wang and Xia (2016)	Mixed integer programing (MIP)	Does not consider the energy consumption. This approach takes more time when there are many virtual machines requests.
Duan et al. (2017)	Improved ACO	Works Based on load trend prediction and multiple resource types are not taken in to account.
Wang et al. (2016)	Improved PSO	Multiple resource types are not taken in to account.
Kruekaew and Kimpan (2014)	Artificial Bee Colony (ABC)	Multiple resource types and energy consumption are not taken into consideration.
Wu, Tang, and Fraser (2012)	Simulated annealing	It is not suitable for dynamic virtual machine consolidation. Further multiple resource types are not taken in to account.
Goiri et al. (2012)	scoring matrix	This algorithm has a chance to enter into a periodic cycle without converging.
Dashti and Rahmani (2016)	Modified PSO	Multiple resource types are not taken in to account.
Dong et al. (2013)	minimum cut	Server overloading network congestion and energy consumption are not considered.

Table 2. Performance of MBFD algorithm.

	Energy Consumption (kWh)		SLA Violations		Migrations
Number 2of VMs	Env 1	Env 2	Env 1	Env 2	Env 1	Env 2
50	0.37	0.36	10	9.31	41	23
100	0.51	0.55	9.4	10.29	59	103
150	0.66	0.66	9.7	9	139	130
200	0.8	0.85	9.51	9.67	171	171
250	1	0.96	12.62	16.40	281	253
300	1.26	1.12	13.21	9.9	319	291

To overcome the said problems, we propose to minimize the total energy consumption of the data center using JAYA algorithm for energy efficient virtual machine placement in cloud data centers.

Proposed Work

Determining the optimal placement (allocation) of VMs is an essential aspect of the data center to boost the physical resource utilization to reduce the energy usage while satisfying the service level agreement (SLA). This section presents the modeling of virtual machine scheduling and proposes JAYA algorithm to solve this optimization problem in cloud data centers.

Problem Formulation

Virtual machine placement (VMP) in large data centers is a hard problem if the VM request are associated with multiple resources such as processing power, memory, storage. The VMP can be seen as a Multidimensional bin-packing problem (d-VBP) (Zhang et al. 2018), where each server resource is represented by a capacity in the bin and the requirements of each VM are represented as an item in the input list. The d-VBP problem is known as NP-hard for $\mathrm{\forall }$ d $\ge$ 1 (Panigrahy et al. 2011).

Our aim is to derive a mapping of virtual machine to the server to maximize the resource utilization in a data center with minimum SLA violations. We consider the cpu utilization of all the servers to calculate the resource utilization of the data center. CPU utilization refers to the percentage of all the logical CPU cores in the server that is used by workloads. Our objective is to maximize the resource utilization satisfying the following constraints while allocating a virtual machine:

1. Each virtual machine is placed on to only one server.

2. A virtual machine is allocated to a server if and only if all the resource requests by the virtual machine will not exceed the available capacity of each resource in the server.

Further, we can put a upper and lower threshold on the server utilization to ensure reliability.

Notations

Let M be the number of virtual machines to be placed on to N servers in a data center. Then, we can write V as a set of virtual machines and H as a set of available servers as shown in Equations 1 and 2. $V_i$ and $H_j$ are instances of a virtual machine and servers, respectively.

(1) $H=H_1,H_2,H_3.....H_n$(1)

(2) $V=V_1,V_2,V_3.....,V_m$(2)

To derive a mapping of VMs (V) to the servers (H), we proposed a mapping solution (M) as follows.

(3) $M=M_1,M_2,M_3.....M_n$(3)

where each $M_i$ in M represents the order of VMs to be placed onto the servers in data centers. We use the following notations in this paper:

● $H_i$: indicates the $i^{th}$ server in the set H.

● $v{m}_j$: indicates the $j^{th}$ virtual machine in the set $V$.

● $p_j$: Power consumption of a server $p_j$.

● A server is modeled as a five-tuple (ID, M, Cr, S, NB) where:

M is the processing capacity, ID is the identifier, Cr represents the number of cores, S is the storage capacity, and NB is network bandwidth capacity.

● A virtual machine is modeled as a four-tuple (ID, M, S, NB) where:

ID is the identifier, and M,S,and NB represents the required processing capacity, storage, and network bandwidth respectively.

● Particle Position: Let ‘m’ virtual machines are to be placed on to any of the ‘n’ heterogeneous servers in the data center. A “particle” is denoted as X and is a list of servers in a virtualized data center where it is not allowed to store duplicate values in X. Let $v_1,v_2,v_3,......,v_m$ are the virtual machine request that are to be placed on to the servers. Then, these virtual machines are packed into the servers in the order given in X.

(4) $X_i(t)=(H_1,H_5,H_4,.....,H_j,...,H_n,.....,H_k)$(4)

Power Consumption Model

In this work, we use the simple server power consumption model proposed in (Reddy, Gangadharan, and Rao 2017). Let, $u_i$ be CPU utilization of the $H_i$ at any given time point then the power consumption of the physical server ($p_i$) is formulated as follows:

(5) $p_i=a_k+(a_{k+1}-a_k)\ast (10\ast u_i-k)$(5)

where k = floor(10*$u_i$) and $a_i$ represents the power consumption of the server at k% utilization. Our aim is to decrease the total energy consumption of the servers (T) as given below.

(6) $Fitnessfunction=T=\sum _{k=1}^n{p}_i$(6)

VM Placement Using JAYA Approach

A majority of the nature-inspired algorithms with the emphasis on swarm and evolutionary computation are probabilistic in nature. The proper tuning of the algorithm-specific parameters for these approaches is an important aspect which affects the performance of a method. To overcome this problem, Rao (2016) proposed JAYA algorithm without any algorithm-specific parameters. JAYA algorithm is a population-based algorithm. This algorithm updates each of the solution using best and worst solutions and makes them to reach the best solution by avoiding the worst solution. Rao et al. (Rao 2016; Rao, Rai, and Balic 2016; Zhang et al. 2016) reported that JAYA algorithm has shown better results than the state-of-the-art approaches.

The pseudocode for virtual machines placement with JAYA algorithm is presented in Algorithm 1. Each solution/candidate is a randomized list of servers in this case. Initially, we take the first VM request and place it on to the server which lies first in the particle data if the said conditions are satisfied. Then, the fitness for each candidate in the population is calculated according to the Equation 6. Then, we select the candidates with a minimum and maximum fitness values as the Best and Worst solutions, respectively. After each iteration, all particles are updated according to the best and worst as shown in Equation 7. This update makes the candidates to move closer to the best and avoid the worst solution. All the candidates of the population are manipulated till the target is achieved or the max-iterations are completed.

Let f(X) is the objective function, population size is n and number of design variables are m. Let B be a best candidate that has the best objective function value (minimum in our case) and W be the worst candidate that has maximum objective function value. If $X_i$ is a candidate during the $i^{th}$ iteration, then it is updated for the next iteration as per the Equation 7

(7) $X_{i+1}=X_i+ran{d}_{1,i}(B_i-|X_i|)-ran{d}_{2,i}(W_i-|X_i|)$(7)

Algorithm 1: Optimal VM provisioning with JAYA algorithm

Input: List of servers and VMs

1 Set the parameters Max-iterations, h, and population size.

2 Initialize the population by generating a random permutation of a finite sequence (P).

3 foreach candidate $\in$ population do

4 $fitness[candidate]=\sum _{j=1}^{n}E(p_j)$.

5 $B_i,W_i$ = candidate with minimum and maximum fitness values in the population.

6 repeat

7   foreach candidate $\in$ population do

8    //Update each particle

$X_{i+1}=X_i+ran{d}_{1,i}\times (B_i-X_i)+ran{d}_{2,i}\times (W_i-X_i);$

9     $fitness[candiate]=\sum _{j=1}^{n}E(p_j)$.

10   $B_{i+1},W_{i+1}$ = particle with minimum and maximum tness values in the updated population.

11   C: Store the best candidate in the population.

12   if $B_{i+1}<B_i$ then

13    C: Update the best candidate in the population.

14    Improve = True;

15    checkout ++;

16    if Improve == True and checkout $>$ h then

17     Return C.

18

19

20 until Max-iterations;

21 Return C.

where $B_i,W_i$ represent the best and worst candidates for iteration i. $X_{i+1}$ is the updated value of $X_i$, and $ran{d}_{1,i}$ and $ran{d}_{2,i}$ are two real-valued random numbers. The term “$r_{1,i}(B_i-|X_i|)$“ makes the candidate to reach the best candidate, and the term “$r_{2,i}(W_i-|X_i|)$ makes the current candidate to move away from the worst candidate. We keep $X_{i+1}$, if it has a better fitness value than the previous iteration. These accepted values are given as input to the next iteration. All the candidate solutions tries to move close to the best (B) by avoiding the worst (W).

Performance Evaluation

Experiment Setup

Using CloudSim (Calheiros et al. 2011), we generate a maximum number of 300 virtual machines and 100 servers with different configurations. There are three types of virtual machines with (30 MIPS, 613 MB RAM), (40 MIPS, 870 MB RAM), and (50 MIPS, 1740 MB RAM). The bandwidth and storage requirements of each of these virtual machines is 100 MBPS and 0.25 GB. In each simulation, we vary the number of virtual machines from 50 to 300 and the number of servers is fixe to 100. The characteristics of the servers used in our experimental are presented in Table 1.

We tested the performance our algorithm in a homogeneous and a heterogeneous environment. For a homogeneous environment, HP ProLiant ML110 Generation 4 servers are used. For heterogeneous environment, we use HP ProLiant ML110 Generation 4, IBM x3550 M3 Rack Intel Xeon X5675 and HP ProLiant ML110 Generation 5 servers. The workload is modeled to be composed of 300 task units, with each task unit requiring 432,000 million instructions (simulation of 24 min in a host with full utilization) to be executed on a host. We used Java language to implement the JAYA algorithm and simulations have been executed on a 64 bit Linux/Ubuntu operating system running on Dell Inspiron 3.5 GHz with Intel Core i7, 16 GB RAM, and 1 TB hard drive.

Results

Experiment is conducted for varying number of virtual machines in homogeneous (Env 1) and heterogeneous (Env 2) environments. For comparison and analysis, we implemented particle swarm optimization (PSO) and modified best fit decreasing (MBFD). The results are illustrated in Tables 2–4. Each table shows the energy consumption, SLA Violation, VM Migration and the number of hosts shutdown for the varying number of VMs in both the environments. We observed that the proposed approach reduced the number of active hosts and SLA violations.

Table 3. Performance of JAYA algorithm.

	Energy (kWh)		SLA Violations		Migrations
Number of VMs	Env 1	Env 2	Env 1	Env 2	Env 1	Env 2
50	0.36	0.35	10	10	42	42
100	0.49	0.52	10	10.14	83	86
150	0.57	0.61	10.74	9.14	151	116
200	0.61	0.72	8.87	10	124	140
250	0.67	0.78	9.29	10	185	150
300	0.69	0.91	10.32	9.17	215	158

Table 4. Performance of PSO algorithm.

	Energy Consumption (kWh)		SLA Violations		Migrations
Number of VMs	Env 1	Env 2	Env 1	Env 2	Env 1	Env 2
50	0.36	0.35	10	10	42	42
100	0.55	0.49	9.78	10.72	60	121
150	0.67	0.71	10	10.26	145	192
200	0.75	0.78	10	10.03	218	214
250	0.95	0.87	10	9.65	308	298
300	1.1	1.02	8.93	8.56	305	340

In the homogeneous environment with the proposed JAYA approach, we observe similar energy consumption for 50 VMs, but achieved 12%, 15%, 29%, 51%, and 82% energy savings in other cases. In a Env 2, PSO is able to reduce energy consumption upto 4% with 300 hosts. But in case of JAYA, energy savings with 150, 200, 250, and 300 VMs are 16%, 18%, 23%, and 23%, respectively.

In case of the JAYA algorithm with homogeneous hosts, the energy consumed with 150, 200, 250, and 300 VMs are 0.57, 0.61, 0.67, and 0.69 (in kWh) respectively, whereas with heterogeneous hosts the energy consumed with 150, 200, 250, and 300 VMs are 0.61, 0.72, 0.78, and 0.91 (in kWh) respectively. From Tables 2–4, we observed that energy consumed with heterogeneous hosts using the proposed approach is less compared to MBFD and PSO with the increasing number of VMs. The number of virtual machine migrations are significantly less in case of JAYA algorithm in both cases. This proves that the proposed algorithm gives high energy savings and less VM migrations even with an increasing number of VMs.

Analysis

We analyze the performance of the proposed algorithm considering the following performance metrics:

● Total Energy consumption by the data center.

● SLA Violation: SLA violation occurs when the hosts cannot allocate the requested MIPS. It is an important measure for the negotiation of Quality of Service (QoS) between the cloud user and the cloud provider.

● VM Migrations: This gives the number of virtual machines migrated.

The average energy consumption of each algorithm in both the environments with the number of VMS varying from 50 to 300 is shown in Figures 2 and 3. In all our experiments, we use the total energy consumption in the CloudSim (kWh). Based on Figures 2 and 3, we notice that our proposed method consumes less energy compared to MBFD and PSO methods. The graph shows that data center energy consumption with PSO and MBFD approaches is much higher compared to JAYA approach that has a slight increase in energy consumption for 200, 250, and 300 VMs.

Figure 2. Energy comparison in homogeneous environment for PSO, MBFD, and JAYA.

Figure 3. Energy consumption in heterogeneous environment for PSO, MBFD, and JAYA.

Figure 4. SLA Violation in homogeneous environment for PSO, MBFD, and JAYA.

Figure 5. SLA Violation in heterogeneous environment for PSO, MBFD, and JAYA.

In the case of the heterogeneous environment (see Figure 3), there is not much difference in energy consumption with 50, 100, and 150 VMs. But with 200, 250, and 300 VMs the energy consumption is less in case of the JAYA algorithm. The SLA violation is also less in the case of the proposed algorithm as shown in Table 3 for both the environments. There is an abrupt increase in SLA Violation (16.40%) with 250 hosts with heterogeneous hosts with MBFD approach, whereas it is very less in case of the JAYA and PSO algorithms as shown in Figure 4 and Figure 5. Further, we notice that the number of migrations are less in most of the cases as shown in Figures 6 and 7 except with 50 VMs in the case of heterogeneous hosts.

Figure 6. VM Migration in homogeneous environment for PSO, MBFD, and JAYA.

Figure 7. VM Migration in a heterogeneous environment for PSO, MBFD, and JAYA.

Conclusion

This paper makes research and elaboration on virtual machine provisioning strategy which is the key technology to reduce the energy consumption in a data center. This paper presents an efficient virtual machine placement in cloud data centers. We presented the mathematical model for VM placement problem. In particular, we developed JAYA algorithm for energy ware virtual machines placement. We present the detailed analysis and design of the energy aware virtual machine scheduling. The experimental results shows that the use of JAYA algorithm significantly reduce the energy consumption in a data center when compared with PSO and MBFD.

In our future work, we plan to implement the VM provisioning methods in OpenStack software, a set of open source tools for building and managing cloud computing platforms and test it in a real cloud environment. Further, we consider more advanced machine learning methods to predict resource utilization to make energy efficient resource allocation.