# Toward Enhancing the Energy Efficiency and Minimizing the SLA Violations in Cloud Data Centers

Authors: E. I. Elsedimy; Fahad Algarni
Journal: Applied Computational Intelligence and Soft Computing
 (2021)

---

## Abstract

Recently, the problem of Virtual Machine Placement (VMP) has received enormous attention from the research community due to its direct effect on the energy efficiency, resource utilization, and performance of the cloud data center. VMP is considered as a multidimensional bin packing problem, which is a type of NP-hard problem. The challenge in VMP is how to optimally place multiple independent virtual machines into a few physical servers to maximize a cloud provider’s revenue while meeting the Service Level Agreements (SLAs). In this paper, an effective multiobjective algorithm based on Particle Swarm Optimization (PSO) technique for the VMP problem, referred to as VMPMOPSO, is proposed. The proposed VMPMOPSO utilizes the crowding entropy method to optimize the VMP and to improve the diversity among the obtained solutions as well as accelerate the convergence speed toward the optimal solution. VMPMOPSO was compared with a simple single-objective algorithm, called First-Fit-Decreasing (FFD), and two multiobjective ant colony and genetic algorithms. Two simulation experiments were conducted to verify the effectiveness and efficiency of the proposed VMPMOPSO. The first experiment shows that the proposed algorithm has better performance than the algorithms we compared it to in terms of power consumption, SLA violation, and resource wastage. The second indicates that the Pareto optimal solutions obtained by applying VMPMOPSO have a good distribution and a better convergence than the comparative algorithms.


---

## Body

## 1. Introduction

Cloud computing provides a promising approach through which pools of services are delivered to users over the Internet [1]. It can deliver infrastructures, platforms, and applications as hosted services to large numbers of users in the pay-as-you-go model [2]. Cloud users can purchase as more or as less computing resources as they need, since the resources of the cloud appear to be unlimited to them. To meet the high-performance expectations of cloud users in a cost-effective manner, cloud providers must consider several key challenges, such as large power consumption, high resource wastage, and high Service Level Agreement (SLA) violation [3]. In this context, energy management in cloud data centers has been a crucial issue since it has a direct effect on operating costs [3]. Statistics show that the infrastructure and power costs contribute about 75%, while the information technology contributes just 25% of the total cost of operating a cloud data center [4]. This high increase in power consumption is not only due to the badness of computing resources and the energy inefficiency of hardware but also due to the inefficient usage of the available resources. The gathered data from more than 5000 physical servers over six months have shown that although the majority of these servers are not idle most of the time, the utilization rarely reaches 100% [5]. Moreover, the active servers usually operate at 10–50% of their capacity, which leads to great waste of resources and power. Therefore, it is extremely important to reduce the large power consumption caused by idle servers to maximize a provider’s revenue while satisfying the Quality of Service (QoS) delivered to cloud consumers [6].One of the ways to address the power inefficiency and ineffective resource utilization of cloud data centers is to employ the capability of the virtualization [7] technologies to create multiple virtual machines (VMs) on a single server and turn off the idle server. With the support of virtualization, the resources of a single physical machine such as the amounts of CPUs, main memory, storage, and network bandwidth are partitioned into multiple execution environments for several VMs. Virtual Machine Placement (VMP) [8, 9] is an important issue in cloud environment virtualization, especially in the infrastructure as a service (IaaS) [10] model. VMP maps a set of VMs into a suitable set of physical servers. However, calculating all possible VM-server mappings in the cloud data center environment and selecting the best one is not feasible, since the complexity will grow quickly with the number of VMs and servers. Furthermore, different VM placement solutions may leave different numbers of physical resources and consume different amounts of power [11]. Therefore, how to optimally place virtual machines into the cloud data centers to minimize power consumption and resource wastage while ensuring the QoS delivered to cloud users is still a challenge for researchers.Up to now, several techniques have been applied to address the problem of VMP in virtualized data center’s infrastructure, such as Linear Programming (LP) [12], random greedy algorithm [13], heuristic bin packing [14], simulated annealing optimization [15], constraint programming [16], Genetic Algorithm (GA) [17], and a classical Ant Colony Optimization (ACO) algorithm [18]. Another approach to optimize VM placement is achieved based on a generalization of the Knapsack Problem [19]. The VM section algorithm attempts to automatically adjust its behavior depending on the workload of the submitted process. Although these approaches may found the solution for the VMP problem, they are easy to drop into local extreme solutions. Also, they focus on optimizing a single target such as power consumption, SLA, load balancing, or resource utilization.In this work, we propose a new algorithm for the VMP problem, called VMPMOPSO. The proposed algorithm combines the principles of the PSO technique and multiobjective optimization. It can be divided into four parts: (1) a suitable encoding scheme for the VMP problem is designed to map all possible solutions to the particle space; (2) the fitness values of all particles are evaluated; (3) the Pareto dominance rules are utilized to establish the preferences among the generated solutions; after that, the nondominated solutions are put into archive set; (4) finally, the crowding entropy method is used to promote the diversity among nondominated solutions. Compared to two existing multiobjective VMP algorithms presented in [20, 21] and a single-objective algorithm proposed in [22], the proposed algorithm has better performance in terms of power consumption, resource wastage, and SLA violation. Furthermore, the obtained solutions by the VMPMOPSO algorithm have better distribution and convergence than the existing algorithms.The remainder of this paper is organized as follows. In Section2, the recent related works in VMP approaches are discussed. The proposed management framework for VMP in the cloud data center’s infrastructure is described in Section 3. After that, Section 4 presents the problem statement and formulates the VMP problem. In Section 5, we provide background knowledge of the proposed VMPMOPSO algorithm. The simulation results and evaluations are given in Section 6. Finally, the conclusions and future work for this paper are presented in Section 7.


## 2. Related Work

In recent years, the problem of VMP has received significant attention, and a lot of studies have been conducted to overcome the limitations of conventional VMP approaches [23–27]. Babu and Samuel [28] propose a bin packing-based approach to optimize the VMP in the cloud data center environment. In this approach, each physical machine is considered as bins and the VMs as the targets to be inserted in the free bin. The goal is to minimize energy consumption by placing VMs into a few hosts. In [29], Verma et al. introduce a modified version of the First-Fit-Decreasing (FFD) algorithm in order to map VMs into the server that has enough resources to host them. Their objective is to minimize resource wastage by reducing the fragment leak that results from placing more than one VM in a single host. However, the authors did not discuss the violations in SLA due to VM allocation. Recently, Beloglazov and Buyya [30] present two novel algorithms, which can participate with each other in developing a dynamic VM consolidation approach. They firstly propose a Modified Best-Fit-Decreasing (MBFD) algorithm, which regards the problem of VMP as a bin backing problem. This algorithm can be divided into two parts: (1) VMs are sorted in decreasing order according to their current CPU utilization; (2) VMs are mapped into the servers that have enough resources and provide the minimum energy consumption due to this mapping. Finally, for eliminating servers’ overloads, they apply a Minimum Migration (MM) algorithm, which aims to control VMs’ migration among servers by applying the upper and lower threshold of their CPU utilization. The results show that the proposed algorithms outperform the other existing policies. However, the proposed MBFD algorithm often is basically the single point search, which concentrates only on the local solution and ignores the global optimum placement solution in a large-scale data center.Xu and Fortes [11] proposed an improved GA based on fuzzy multiobjective evaluation in order to effectively deal with a large solutions search space of a VMP problem. Their objective is to reduce power consumption, efficiently utilize multidimensional resources, and avoid hotspots. The authors also design a two-level control system for managing resources automatically in virtualized data centers. At the virtual-container level, in order to improve the SLA rate, a local controller is utilized to determine the number of resources demanded by applications and requests additional resources to avoid the degradation in performance. At the resource-pool level, the global controller is applied to manage VM placement and resource allocation, in which the physical resources are allocated as slices based on the demands of VM requests. Although the proposed approach achieves better results when compared to the other existing algorithms, it has more time complexity results from solving the multidimensional resources allocation based on the multidimensional matrix.Liu et al. [31] formulated the VMP problem as a multiobjective optimization problem and solved it by using an improved evolutionary multiobjective optimization algorithm named NS-GGA. This algorithm incorporates the fast nondominated sorting of NSGA-II into the grouping GAs. The analysis of the results shows that the proposed NS-GGA outperforms the existing algorithms. However, it focuses only on solving the VMP problem to obtain the Pareto optimal front while issues related to how to improve the diversity among the obtained solutions of the VMP problem have less attention in this work.Gao et al. [21] regard the problem of VMP in the virtualized data center as a multiobjective optimization problem and solve it by using an improved ACO system algorithm. The goal is to find a set of Pareto optimal solutions that improve resource utilization and energy efficiency together. However, how to guarantee users’ SLA has not been discussed in the paper.Zheng et al. [32] presented a novel approach for the VMP problem called VMPMBBO. The proposed approach applied a biogeography-based optimization to ensure convergence to the optimum solution in the large solutions’ search space of the VMP optimization problem. Their objective is to improve cloud data center efficiency by minimizing the total power consumption and resource wastage simultaneously. However, the influence of VMP operation on SLA violation has not been considered in their paper.In [33], Kumar and Raza adapted the PSO technique-based VM scheduling strategy in order to minimize the total resource wastage and psychical server utilizations. The proposed work achieves better results compared to traditional strategies such as Best-Fit, First-Fit, and Worst-Fit placement. However, this method can be trapped in local optima.Recently, Dashti and Rahman in [34] proposed a modified PSO to reallocate migrated VMs in the overloaded host. However, they considered only the server utilization and the migration cost to get the optimal solution for the VM placement process. Tripathi et al. [35] formulate the VM placement process as a multiobjective optimization problem with better energy consumption and resource usage. However, they ignore the SLA violations of the physical server.As discussed above, many approaches have been proposed by the researchers for addressing the VMP problem but none of them have considered all the issues of such problem which ensure the QoS delivered to the users and at the same time maximize the cloud provider’s revenue. Therefore, the development of a novel algorithm for the VMP problem is required in order to reduce the operating cost to the cloud provider and at the same time provide good services to the consumers.


## 3. System Architecture and Problem Formulation

This section presents the system architecture for VM management in the cloud environment and formulates the VM placement as a multiple-objective optimization problem.


### 3.1. System Architecture

On the cloud computing IaaS platform, the computing resources are provided to consumers as a service and by needs, and consumers can buy as much or as little computing power as they demand. Cloud users can access computing resources via any electronic device connected to the Internet, such as a laptop, PC, PDA, and mobile phone. Today, many IaaS providers such as Google Compute Engine [36] and Amazon AWS [37] provide users with an exclusive infrastructure in the form of VM instances. They offer several types of VM instances with varying configurations and different prices. As there are a large number of users who request VM instances simultaneously, so how to optimally place these VMs on the cloud data centers to maximize the cloud provider’s profit while satisfying users’ requirements is a significant problem to solve. To address this issue, we present our proposed system architecture for VM management in the cloud environment as shown in Figure 1.Figure 1
The system architecture for VM management in the cloud environment.On cloud data centers, first, cloud users request VMs from a cloud IaaS provider using a VM description template. The configuration of each VM is defined in terms of physical resource metrics such as CPUs cores, disk storage, memory capacity, and network bandwidth. Second, the VM scheduler accepts and handles the incoming requests from cloud users for renting the VM instances. At the same time, two actions were performed automatically: provisioning of virtual resources and monitoring of these resources. Therefore, in this paper, we employ an optimization policy coupled with our proposed algorithm to optimize the placement of VMs into different servers taken into account the conflicting goals of cloud providers and consumers. The objective of the proposed algorithm is to find a set of Pareto optimal solutions that optimize multiobjectives such as SLA violations, power consumption, and resource wastage. To improve the diversity among the obtained solutions and accelerate the convergence speed toward the optimal solution, the proposed algorithm utilizes a crowding entropy mechanism to estimate the crowding distance around each obtained solution accurately.


### 3.2. Problem Formulation

The cloud IaaS providers periodically receive a large number of computing resource requests, such as CPU, main memory, storage, and network bandwidth, from different users. These resources are packed as VMs and then be placed on different servers at the cloud provider infrastructure based on specific constraints, such as meeting the SLA requirements, improving the energy efficiency, and reducing the wastage of resources. Here, both the VM’s resources and the server’s resources are represented by a multidimensional vector. We use two dimensions to represent a VM and a server-CPU and memory. The resources of each server can be expressed usingRk=Rkcpu,Rkmem,1≤k≤m, where m represents the total number of servers, Rkcpu represents the capacities of CPU, and Rkmem represents the size of main memory. Similarly, the resources requested by each VM can be represented by the vector Vi=Vicpu,Vimem,1≤i≤n, where n is the total number of VMs requests. We use a binary variable xk to refer to whether server k is used (xk=1) or not (xk=0). Additionally, by assuming that a single server is able to host multiple independent VMs, we define the decision variable yik which represents whether VM i is mapped to server k (yik=1) or not (yik=0).


#### 3.2.1. SLA Violation Modeling

In the cloud computing environment, placing the VMs into a suitable host that provides the least violation in SLA is extremely important for both cloud providers and consumers. Beloglazov and Buyya [38, 39] define the SLA violation due to VM allocation as a fraction of the difference between the total demands of processing units of CPU resources by all virtual machines and the actually allocated processing units of CPU relatively to the total requested of processing units of CPU over the lifetime of the virtual machines. However, these studies only consider the performance degradation due to the lack of CPU resources, rather than other resources such as storage, main memory, and network bandwidth. Here, we quantify the SLA violation taking into account a two-dimensional vector of resources (CPU and memory), rather than a CPU resource only, as shown in the following:(1)SLA  violation=SALVkcpu=∑i=1nDikcpu−Aikcpu∑i=1nDikcpu,SLAVkmem=∑i=1nDikmem−Aikmem∑i=1nDikmem,SLAVk=SALVkcpu+SLAVkmem2,where Dikcpu and Dikmem are demands of CPU and main memory resources by VM i carried on physical machine k, respectively, 1≤i≤n, and n represents the total number of VMs. Similarly, Aikcpu and Aikmem are the amounts of CPU and main memory resources allocated to VM i.Based on the above definition of SLA violation,SLA violationk is introduced to quantify the SLA violations caused by physical machine k, as shown in (2)SLA violationk=xk×∑i=1nyik×Dikcpu−Aikcpu/∑i=1nDikcpu+∑i=1nyik×Dikmem−Aikmem/∑i=1nDikmem2.


#### 3.2.2. Resource Wastage Modeling

The residual resources available on each physical server may vary greatly with different VMP solutions. Therefore, it is necessary to develop a high-effective VMP approach to increase resource utilization of the physical server and keep the remaining resources on each server balanced along different dimensions. Here, we define the resource wastageWk as the average value between different dimension residual resources (CPU and memory) and the whole physical machine resources, as seen in the following:(3)resource wastage=Wkcpu=kTcpukcpu,Wkmem=kTmemkmem,Wk=Wkcpu+Wkmem2.Based on the above consideration,resource wastagek is introduced to calculate the total wasted resources of the k-th server, as seen in (4)resource wastagek=xk×∑i=1nyik×kTcpu/Kcpu+kTmem/Kmem2.


#### 3.2.3. Power Consumption Modeling

Recent studies [40] show that the total power consumption of the physical server is linearly proportional to CPU utilization. These studies indicate that an idle server consumes approximately 70% of the energy consumed when the CPU is fully utilized. Therefore, in order to save power, idle servers should be turned off. Finally, as seen in equation (5), power consumptionk is presented to compute the total power consumption by k-th server.(5)power consumptionk=xk×Pkbusy−Pkidel×∑i=1nyik×Dikcpu+Pkidel,where Pkidel and Pkbusy refer to the power consumption by server k at idle and full load, respectively. Dikcpu represents the number of CPU demands by VM i carried on server k. In our simulation experiments, Pkidel and Pkbusy are set to 162 and 215 Watt, respectively.


#### 3.2.4. Optimization Formulation

The VMP problem is described as follows. Assume that there aren of VMs which are to be placed on m of servers in the cloud data center, and none of these VMs require that computing resources exceed the capacity of a single server. The goal is to simultaneously minimize SLA violations, wastage of resources, and power consumption. Therefore, we formulate the VMP problem as follows:(6)minimize:∑k=1mSLA violationk,(7)minimize:∑k=1mresource wastagek,(8)minimize:∑k=1mpower consumptionk,subject to(9)∑k=1m∑i=1nyik=1,∀i=1,…,n;k=1,…,m,(10)∑k=1m∑i=1nyik⋅Vikcpu≤∑k=1mxk⋅RKcpu,(11)∑k=1m∑i=1nyik⋅Vikram≤∑k=1mxk⋅RKram.The objectives in equations (6) and (7), respectively, aim to minimize the SLA violation and resource wastage by all the physical servers, and the objective in equation (8) aims to reduce the total power consumption. The constraint in equation (9) ensures that each VM is mapped into one, and only one, host. Constraints in equations (10) and (11) ensure that the requested resources by all VMs do not exceed the full capacity of the available server’s resources.


## 3.1. System Architecture

On the cloud computing IaaS platform, the computing resources are provided to consumers as a service and by needs, and consumers can buy as much or as little computing power as they demand. Cloud users can access computing resources via any electronic device connected to the Internet, such as a laptop, PC, PDA, and mobile phone. Today, many IaaS providers such as Google Compute Engine [36] and Amazon AWS [37] provide users with an exclusive infrastructure in the form of VM instances. They offer several types of VM instances with varying configurations and different prices. As there are a large number of users who request VM instances simultaneously, so how to optimally place these VMs on the cloud data centers to maximize the cloud provider’s profit while satisfying users’ requirements is a significant problem to solve. To address this issue, we present our proposed system architecture for VM management in the cloud environment as shown in Figure 1.Figure 1
The system architecture for VM management in the cloud environment.On cloud data centers, first, cloud users request VMs from a cloud IaaS provider using a VM description template. The configuration of each VM is defined in terms of physical resource metrics such as CPUs cores, disk storage, memory capacity, and network bandwidth. Second, the VM scheduler accepts and handles the incoming requests from cloud users for renting the VM instances. At the same time, two actions were performed automatically: provisioning of virtual resources and monitoring of these resources. Therefore, in this paper, we employ an optimization policy coupled with our proposed algorithm to optimize the placement of VMs into different servers taken into account the conflicting goals of cloud providers and consumers. The objective of the proposed algorithm is to find a set of Pareto optimal solutions that optimize multiobjectives such as SLA violations, power consumption, and resource wastage. To improve the diversity among the obtained solutions and accelerate the convergence speed toward the optimal solution, the proposed algorithm utilizes a crowding entropy mechanism to estimate the crowding distance around each obtained solution accurately.


## 3.2. Problem Formulation

The cloud IaaS providers periodically receive a large number of computing resource requests, such as CPU, main memory, storage, and network bandwidth, from different users. These resources are packed as VMs and then be placed on different servers at the cloud provider infrastructure based on specific constraints, such as meeting the SLA requirements, improving the energy efficiency, and reducing the wastage of resources. Here, both the VM’s resources and the server’s resources are represented by a multidimensional vector. We use two dimensions to represent a VM and a server-CPU and memory. The resources of each server can be expressed usingRk=Rkcpu,Rkmem,1≤k≤m, where m represents the total number of servers, Rkcpu represents the capacities of CPU, and Rkmem represents the size of main memory. Similarly, the resources requested by each VM can be represented by the vector Vi=Vicpu,Vimem,1≤i≤n, where n is the total number of VMs requests. We use a binary variable xk to refer to whether server k is used (xk=1) or not (xk=0). Additionally, by assuming that a single server is able to host multiple independent VMs, we define the decision variable yik which represents whether VM i is mapped to server k (yik=1) or not (yik=0).


### 3.2.1. SLA Violation Modeling

In the cloud computing environment, placing the VMs into a suitable host that provides the least violation in SLA is extremely important for both cloud providers and consumers. Beloglazov and Buyya [38, 39] define the SLA violation due to VM allocation as a fraction of the difference between the total demands of processing units of CPU resources by all virtual machines and the actually allocated processing units of CPU relatively to the total requested of processing units of CPU over the lifetime of the virtual machines. However, these studies only consider the performance degradation due to the lack of CPU resources, rather than other resources such as storage, main memory, and network bandwidth. Here, we quantify the SLA violation taking into account a two-dimensional vector of resources (CPU and memory), rather than a CPU resource only, as shown in the following:(1)SLA  violation=SALVkcpu=∑i=1nDikcpu−Aikcpu∑i=1nDikcpu,SLAVkmem=∑i=1nDikmem−Aikmem∑i=1nDikmem,SLAVk=SALVkcpu+SLAVkmem2,where Dikcpu and Dikmem are demands of CPU and main memory resources by VM i carried on physical machine k, respectively, 1≤i≤n, and n represents the total number of VMs. Similarly, Aikcpu and Aikmem are the amounts of CPU and main memory resources allocated to VM i.Based on the above definition of SLA violation,SLA violationk is introduced to quantify the SLA violations caused by physical machine k, as shown in (2)SLA violationk=xk×∑i=1nyik×Dikcpu−Aikcpu/∑i=1nDikcpu+∑i=1nyik×Dikmem−Aikmem/∑i=1nDikmem2.


### 3.2.2. Resource Wastage Modeling

The residual resources available on each physical server may vary greatly with different VMP solutions. Therefore, it is necessary to develop a high-effective VMP approach to increase resource utilization of the physical server and keep the remaining resources on each server balanced along different dimensions. Here, we define the resource wastageWk as the average value between different dimension residual resources (CPU and memory) and the whole physical machine resources, as seen in the following:(3)resource wastage=Wkcpu=kTcpukcpu,Wkmem=kTmemkmem,Wk=Wkcpu+Wkmem2.Based on the above consideration,resource wastagek is introduced to calculate the total wasted resources of the k-th server, as seen in (4)resource wastagek=xk×∑i=1nyik×kTcpu/Kcpu+kTmem/Kmem2.


### 3.2.3. Power Consumption Modeling

Recent studies [40] show that the total power consumption of the physical server is linearly proportional to CPU utilization. These studies indicate that an idle server consumes approximately 70% of the energy consumed when the CPU is fully utilized. Therefore, in order to save power, idle servers should be turned off. Finally, as seen in equation (5), power consumptionk is presented to compute the total power consumption by k-th server.(5)power consumptionk=xk×Pkbusy−Pkidel×∑i=1nyik×Dikcpu+Pkidel,where Pkidel and Pkbusy refer to the power consumption by server k at idle and full load, respectively. Dikcpu represents the number of CPU demands by VM i carried on server k. In our simulation experiments, Pkidel and Pkbusy are set to 162 and 215 Watt, respectively.


### 3.2.4. Optimization Formulation

The VMP problem is described as follows. Assume that there aren of VMs which are to be placed on m of servers in the cloud data center, and none of these VMs require that computing resources exceed the capacity of a single server. The goal is to simultaneously minimize SLA violations, wastage of resources, and power consumption. Therefore, we formulate the VMP problem as follows:(6)minimize:∑k=1mSLA violationk,(7)minimize:∑k=1mresource wastagek,(8)minimize:∑k=1mpower consumptionk,subject to(9)∑k=1m∑i=1nyik=1,∀i=1,…,n;k=1,…,m,(10)∑k=1m∑i=1nyik⋅Vikcpu≤∑k=1mxk⋅RKcpu,(11)∑k=1m∑i=1nyik⋅Vikram≤∑k=1mxk⋅RKram.The objectives in equations (6) and (7), respectively, aim to minimize the SLA violation and resource wastage by all the physical servers, and the objective in equation (8) aims to reduce the total power consumption. The constraint in equation (9) ensures that each VM is mapped into one, and only one, host. Constraints in equations (10) and (11) ensure that the requested resources by all VMs do not exceed the full capacity of the available server’s resources.


## 3.2.1. SLA Violation Modeling

In the cloud computing environment, placing the VMs into a suitable host that provides the least violation in SLA is extremely important for both cloud providers and consumers. Beloglazov and Buyya [38, 39] define the SLA violation due to VM allocation as a fraction of the difference between the total demands of processing units of CPU resources by all virtual machines and the actually allocated processing units of CPU relatively to the total requested of processing units of CPU over the lifetime of the virtual machines. However, these studies only consider the performance degradation due to the lack of CPU resources, rather than other resources such as storage, main memory, and network bandwidth. Here, we quantify the SLA violation taking into account a two-dimensional vector of resources (CPU and memory), rather than a CPU resource only, as shown in the following:(1)SLA  violation=SALVkcpu=∑i=1nDikcpu−Aikcpu∑i=1nDikcpu,SLAVkmem=∑i=1nDikmem−Aikmem∑i=1nDikmem,SLAVk=SALVkcpu+SLAVkmem2,where Dikcpu and Dikmem are demands of CPU and main memory resources by VM i carried on physical machine k, respectively, 1≤i≤n, and n represents the total number of VMs. Similarly, Aikcpu and Aikmem are the amounts of CPU and main memory resources allocated to VM i.Based on the above definition of SLA violation,SLA violationk is introduced to quantify the SLA violations caused by physical machine k, as shown in (2)SLA violationk=xk×∑i=1nyik×Dikcpu−Aikcpu/∑i=1nDikcpu+∑i=1nyik×Dikmem−Aikmem/∑i=1nDikmem2.


## 3.2.2. Resource Wastage Modeling

The residual resources available on each physical server may vary greatly with different VMP solutions. Therefore, it is necessary to develop a high-effective VMP approach to increase resource utilization of the physical server and keep the remaining resources on each server balanced along different dimensions. Here, we define the resource wastageWk as the average value between different dimension residual resources (CPU and memory) and the whole physical machine resources, as seen in the following:(3)resource wastage=Wkcpu=kTcpukcpu,Wkmem=kTmemkmem,Wk=Wkcpu+Wkmem2.Based on the above consideration,resource wastagek is introduced to calculate the total wasted resources of the k-th server, as seen in (4)resource wastagek=xk×∑i=1nyik×kTcpu/Kcpu+kTmem/Kmem2.


## 3.2.3. Power Consumption Modeling

Recent studies [40] show that the total power consumption of the physical server is linearly proportional to CPU utilization. These studies indicate that an idle server consumes approximately 70% of the energy consumed when the CPU is fully utilized. Therefore, in order to save power, idle servers should be turned off. Finally, as seen in equation (5), power consumptionk is presented to compute the total power consumption by k-th server.(5)power consumptionk=xk×Pkbusy−Pkidel×∑i=1nyik×Dikcpu+Pkidel,where Pkidel and Pkbusy refer to the power consumption by server k at idle and full load, respectively. Dikcpu represents the number of CPU demands by VM i carried on server k. In our simulation experiments, Pkidel and Pkbusy are set to 162 and 215 Watt, respectively.


## 3.2.4. Optimization Formulation

The VMP problem is described as follows. Assume that there aren of VMs which are to be placed on m of servers in the cloud data center, and none of these VMs require that computing resources exceed the capacity of a single server. The goal is to simultaneously minimize SLA violations, wastage of resources, and power consumption. Therefore, we formulate the VMP problem as follows:(6)minimize:∑k=1mSLA violationk,(7)minimize:∑k=1mresource wastagek,(8)minimize:∑k=1mpower consumptionk,subject to(9)∑k=1m∑i=1nyik=1,∀i=1,…,n;k=1,…,m,(10)∑k=1m∑i=1nyik⋅Vikcpu≤∑k=1mxk⋅RKcpu,(11)∑k=1m∑i=1nyik⋅Vikram≤∑k=1mxk⋅RKram.The objectives in equations (6) and (7), respectively, aim to minimize the SLA violation and resource wastage by all the physical servers, and the objective in equation (8) aims to reduce the total power consumption. The constraint in equation (9) ensures that each VM is mapped into one, and only one, host. Constraints in equations (10) and (11) ensure that the requested resources by all VMs do not exceed the full capacity of the available server’s resources.


## 4. An Introduction to the Multiobjective Improved PSO

In this section, we firstly provide an overview of PSO algorithm principles and then present background knowledge of multiobjective optimization. Finally, we give a brief description of a Multiobjective Particle Swarm Optimization (MOPSO) algorithm coupled with the crowding entropy mechanism to optimize the VMP.


### 4.1. Particle Swarm Optimization Algorithm

TheParticle Swarm Optimization (PSO) is a popular computational technique [41] inspired by the social behavior of fish schooling and bird flocking to seek foods. Recent studies [42, 43] show that PSO performs better in distributed and grid computing environments compared with GA. The PSO also can achieve better convergence on the search than GA [42]. Furthermore, Reyes-Sieraa and Coello [44] note that the PSO uses simple operations with few parameters to produce very good results at a low computational cost.In PSO, a population of all possible solutions, called particles, was firstly initialized. Then, these particles are allowed to fly with an adaptable velocity searching for the optimum solution in the solution search space. Each particle can store the best location obtained so far (locally optimal), as well as the best position tracked by the entire swarm (global optimal). Here, we use the quadrupleSi,Vi,Pi,Gi to represent each particle in the swarm, where Si=Si1,Si2,…,Sid,… and Vi=Vi1,Vi2,…,Vid,… are the position and velocity vectors of the ith particle, respectively.Pi=Pi1,Pi2,…,Pid,… denotes the local best position obtained by ith particle and Gi=Gi1,Gi2,…,Gid,… represents the global optimum position searched by the entire swarm, where d represents the dimension of particles.At each iterationt, the PSO algorithm updates particle’s velocity and position-based equations (12) and (13), respectively.(12)Vidt+1=ϕ⋅Vidt+ψ1⋅ϑ1⋅Pidt−Sidt+ψ2⋅ϑ2⋅Pgdt−Sidt,(13)Sidt+1=Sidt+Vidt+1,where ψ1andψ2 are the acceleration coefficients. The parameters ϑ1andϑ2 are positive random numbers uniformly distributed between 0 and 1. ϕ is the inertia weight, 0≤ϕ≤1, utilized to control the unlimited growth of the particle’s velocity. The inertia weight is defined as follows:(14)ϕ=ϕmax−ϕmax−ϕmintmax×t,where ϕmax and ϕmin denote the maximum and minimum inertia’s values, respectively, t denotes the current iteration value, and tmax denotes the maximum number of iterations, where the higher the value of tmax is, the smaller the weight ϕ will be.


### 4.2. Definition of Multiobjective Optimization

Most real-world problems have more than one of the objectives which are usually in conflict with each other, and optimizing these objectives simultaneously is very difficult. Multiobjective Optimization (MOO) addresses this problem. Many multiobjective evolutionary algorithms have been developed to solve MOO problems such as NSGA-ΙΙ [45], SEPA [46], and MOPSO [47] algorithms. The experimental results in [48] show that the MOPSO algorithm performs better than traditional multiobjective algorithms for MOO problems. Also, it can achieve less computing time and high searching ability than PAES and NSGA-ΙΙ algorithms. Since the first effort is introduced in [49] by Parsopoulos and Vrahatis to employ the principles of the traditional PSO algorithm in MOO problems, many authors have presented different attempts to improve the performance of MOPSO, for example, Durillo et al. [50], Nebro et al. [51], and Moubayed et al. [52]. The majority of these efforts focused on improving convergence and diversity among the generated solutions. The work in [53] incorporates a nondominated sorting mechanism in the MOPSO algorithm, for improving the global searching scale. His mechanism started well, but with the large size of search space, controlling the number of the best solution is difficult and the mechanism may be tended to drop into local optima. To avoid the MOPSO fall into a local solution, Li [54] suggested using a maximin strategy coupled with a random inertia weight. In this strategy, the maximin fitness function is utilized to sort solutions and determine Pareto dominance without the need for clustering or niching procedure. Although the proposed strategy improves the diversity of the swarm, its power in global searching is not satisfied.The target of MOO is to find those values of an n-dimensional decision variable vectorx1,…,xnT for which the values of an m-dimensional objective vector fx1,…,xmT are minimized (or maximized). The best solutions for the MOO problem are called Pareto optimal solutions, which result from the preference among several objectives. MOO problem can be described in the following manner:(15)miny=Fx=f1x,f2x,…,fmxT,s.t.gix≤0,i=1,2,…,Q,hjx=0,j=1,2,…,P,where x=x1,…,xnT∈X⊂Rn is known as a decision vector, X represents the set of feasible solutions, y=y1,…,ymT∈Y is known as an objective vector, and Y is an objective space.gix refers to the ith inequality constraint while hjx is the jth equality constraint. As discussed above, we search for Pareto optimum. More formally, we have the following.Definition 1 (dominance).
Given two decision vectorsu⟶=u1,…,um∈X and v⟶=v1,…,vm∈X, we say that u⟶ dominates v⟶, denoted by u⟶≺v⟶, if and only if (if) ∀j∈1,2,…,m: fju⟶≤fjv⟶ and ∃i∈1,2,…,m:fiu⟶≤fiv⟶.Definition 2 (Pareto optimality).
A vectoru⟶ is Pareto optimal solution with respect to X if, ∄v⟶∈X:v⟶≻u⟶.Definition 3 (Pareto optimal set).
P∗ is known as the Pareto optimal set that contains all Pareto optimal solutions and defined as(16)P∗=v⟶∈X|∄v⟶∈X:v⟶≻u⟶.


### 4.3. Crowding Distance-Based External Archive

To improve the diversity among the obtained solution by the MOPSO algorithm and enhance the searching capability, a good crowding distance method is required to measure the crowding degree around each generated solution in the external archive accurately. Several methods have been applied to estimate the crowding degree, such as an adaptive hypercube used in MOPSO [47], the density estimation strategy used with SPEA2 in [55], and a crowding distance method proposed in [45]. These methods have effectively contributed to the MOPSO algorithm, but the diversity preservation for the obtained Pareto optimal set and the global optimum update strategy are very complex, leading to high time complexity. Here, the crowding entropy method, proposed by Wang et al. in [56], is incorporated in MOPSO to find the perfect solutions with good diversity. This method coupled the entropy distribution with the crowding distance strategy in order to estimate the density around each particle more accurately. It can be defined as follows:(17)CEi=∑j=1mβijHijfjmax−fjmin,where(18)Hij=−elijlog2elij+euijlog2euij,elij=δlijβij,euij=δuijβij,βij=δlij+δuij,where fjmax and fjmin represent the maximum and minimum values of the jth objective function, respectively, and m is the total number of objectives. δlij and δuij represent the distances of the ith particle to its lower and upper closest neighbor particles along the jth objective function, respectively.Finally, to extend the crowding entropy method to MOPSO, the most important issue is the modification of the preferred method. Therefore, the preference rules of MOPSO can be defined in the following manner:(19)u⟶,u⟶≺v⟶,v⟶,v⟶≺u⟶,LCu⟶,v⟶,v⟶≺¯u⟶∧v⟶≺¯u⟶,where LCu⟶,v⟶ represents the less crowded distance between u⟶andv⟶ decision vectors. According to the dominance relation between two solution vectors u⟶ and v⟶, there are at most three cases: (1) u⟶ dominates v⟶; (2) v⟶ dominates u⟶ ; (3) u⟶ and v⟶ are nondominated with each other (v⟶≺¯u⟶∧v⟶≺¯u⟶).


## 4.1. Particle Swarm Optimization Algorithm

TheParticle Swarm Optimization (PSO) is a popular computational technique [41] inspired by the social behavior of fish schooling and bird flocking to seek foods. Recent studies [42, 43] show that PSO performs better in distributed and grid computing environments compared with GA. The PSO also can achieve better convergence on the search than GA [42]. Furthermore, Reyes-Sieraa and Coello [44] note that the PSO uses simple operations with few parameters to produce very good results at a low computational cost.In PSO, a population of all possible solutions, called particles, was firstly initialized. Then, these particles are allowed to fly with an adaptable velocity searching for the optimum solution in the solution search space. Each particle can store the best location obtained so far (locally optimal), as well as the best position tracked by the entire swarm (global optimal). Here, we use the quadrupleSi,Vi,Pi,Gi to represent each particle in the swarm, where Si=Si1,Si2,…,Sid,… and Vi=Vi1,Vi2,…,Vid,… are the position and velocity vectors of the ith particle, respectively.Pi=Pi1,Pi2,…,Pid,… denotes the local best position obtained by ith particle and Gi=Gi1,Gi2,…,Gid,… represents the global optimum position searched by the entire swarm, where d represents the dimension of particles.At each iterationt, the PSO algorithm updates particle’s velocity and position-based equations (12) and (13), respectively.(12)Vidt+1=ϕ⋅Vidt+ψ1⋅ϑ1⋅Pidt−Sidt+ψ2⋅ϑ2⋅Pgdt−Sidt,(13)Sidt+1=Sidt+Vidt+1,where ψ1andψ2 are the acceleration coefficients. The parameters ϑ1andϑ2 are positive random numbers uniformly distributed between 0 and 1. ϕ is the inertia weight, 0≤ϕ≤1, utilized to control the unlimited growth of the particle’s velocity. The inertia weight is defined as follows:(14)ϕ=ϕmax−ϕmax−ϕmintmax×t,where ϕmax and ϕmin denote the maximum and minimum inertia’s values, respectively, t denotes the current iteration value, and tmax denotes the maximum number of iterations, where the higher the value of tmax is, the smaller the weight ϕ will be.


## 4.2. Definition of Multiobjective Optimization

Most real-world problems have more than one of the objectives which are usually in conflict with each other, and optimizing these objectives simultaneously is very difficult. Multiobjective Optimization (MOO) addresses this problem. Many multiobjective evolutionary algorithms have been developed to solve MOO problems such as NSGA-ΙΙ [45], SEPA [46], and MOPSO [47] algorithms. The experimental results in [48] show that the MOPSO algorithm performs better than traditional multiobjective algorithms for MOO problems. Also, it can achieve less computing time and high searching ability than PAES and NSGA-ΙΙ algorithms. Since the first effort is introduced in [49] by Parsopoulos and Vrahatis to employ the principles of the traditional PSO algorithm in MOO problems, many authors have presented different attempts to improve the performance of MOPSO, for example, Durillo et al. [50], Nebro et al. [51], and Moubayed et al. [52]. The majority of these efforts focused on improving convergence and diversity among the generated solutions. The work in [53] incorporates a nondominated sorting mechanism in the MOPSO algorithm, for improving the global searching scale. His mechanism started well, but with the large size of search space, controlling the number of the best solution is difficult and the mechanism may be tended to drop into local optima. To avoid the MOPSO fall into a local solution, Li [54] suggested using a maximin strategy coupled with a random inertia weight. In this strategy, the maximin fitness function is utilized to sort solutions and determine Pareto dominance without the need for clustering or niching procedure. Although the proposed strategy improves the diversity of the swarm, its power in global searching is not satisfied.The target of MOO is to find those values of an n-dimensional decision variable vectorx1,…,xnT for which the values of an m-dimensional objective vector fx1,…,xmT are minimized (or maximized). The best solutions for the MOO problem are called Pareto optimal solutions, which result from the preference among several objectives. MOO problem can be described in the following manner:(15)miny=Fx=f1x,f2x,…,fmxT,s.t.gix≤0,i=1,2,…,Q,hjx=0,j=1,2,…,P,where x=x1,…,xnT∈X⊂Rn is known as a decision vector, X represents the set of feasible solutions, y=y1,…,ymT∈Y is known as an objective vector, and Y is an objective space.gix refers to the ith inequality constraint while hjx is the jth equality constraint. As discussed above, we search for Pareto optimum. More formally, we have the following.Definition 1 (dominance).
Given two decision vectorsu⟶=u1,…,um∈X and v⟶=v1,…,vm∈X, we say that u⟶ dominates v⟶, denoted by u⟶≺v⟶, if and only if (if) ∀j∈1,2,…,m: fju⟶≤fjv⟶ and ∃i∈1,2,…,m:fiu⟶≤fiv⟶.Definition 2 (Pareto optimality).
A vectoru⟶ is Pareto optimal solution with respect to X if, ∄v⟶∈X:v⟶≻u⟶.Definition 3 (Pareto optimal set).
P∗ is known as the Pareto optimal set that contains all Pareto optimal solutions and defined as(16)P∗=v⟶∈X|∄v⟶∈X:v⟶≻u⟶.


## 4.3. Crowding Distance-Based External Archive

To improve the diversity among the obtained solution by the MOPSO algorithm and enhance the searching capability, a good crowding distance method is required to measure the crowding degree around each generated solution in the external archive accurately. Several methods have been applied to estimate the crowding degree, such as an adaptive hypercube used in MOPSO [47], the density estimation strategy used with SPEA2 in [55], and a crowding distance method proposed in [45]. These methods have effectively contributed to the MOPSO algorithm, but the diversity preservation for the obtained Pareto optimal set and the global optimum update strategy are very complex, leading to high time complexity. Here, the crowding entropy method, proposed by Wang et al. in [56], is incorporated in MOPSO to find the perfect solutions with good diversity. This method coupled the entropy distribution with the crowding distance strategy in order to estimate the density around each particle more accurately. It can be defined as follows:(17)CEi=∑j=1mβijHijfjmax−fjmin,where(18)Hij=−elijlog2elij+euijlog2euij,elij=δlijβij,euij=δuijβij,βij=δlij+δuij,where fjmax and fjmin represent the maximum and minimum values of the jth objective function, respectively, and m is the total number of objectives. δlij and δuij represent the distances of the ith particle to its lower and upper closest neighbor particles along the jth objective function, respectively.Finally, to extend the crowding entropy method to MOPSO, the most important issue is the modification of the preferred method. Therefore, the preference rules of MOPSO can be defined in the following manner:(19)u⟶,u⟶≺v⟶,v⟶,v⟶≺u⟶,LCu⟶,v⟶,v⟶≺¯u⟶∧v⟶≺¯u⟶,where LCu⟶,v⟶ represents the less crowded distance between u⟶andv⟶ decision vectors. According to the dominance relation between two solution vectors u⟶ and v⟶, there are at most three cases: (1) u⟶ dominates v⟶; (2) v⟶ dominates u⟶ ; (3) u⟶ and v⟶ are nondominated with each other (v⟶≺¯u⟶∧v⟶≺¯u⟶).


## 5. The Proposed VMPMOPSO Approach

In this section, a Multiobjective Particle Swarm Optimization (MOPSO) algorithm, extended with crowding entropy method, referred to as VMPMOPSO, has been proposed for the problem of VMP. The goal of the VMPMOPSO algorithm is to find the optimal placement solution that effectively minimizes the violation in SLA and resource wastage while saving energy, as well.The pseudocode of the proposed VMPMOPSO algorithm is listed in Algorithm1. This algorithm starts its work with the initialization of some parameters, such as the particle’s position and velocity, the swarm size, and the maximum iterations. Then, each particle is evaluated based on fitness functions 6, 7, and 8, respectively. The obtained nondominated solutions during the evaluation process are stored in the archive set. By continuing to add the new nondominated solutions into the archive set, the external archive is formed. When there are repeated solutions that have the same crowding entropy value, the proposed algorithm deletes them and keeps one. After that, the crowding entropy is applied to improve the diversity among the obtained solutions. The solution with the highest crowding entropy value has a better chance to be chosen as the global best. After selecting the global best, the velocity and location of each particle are updated from the iteration t to t + 1 using equations (12) and (13), respectively. Finally, VMPMOPSO checks the termination condition to ensure if the loop excessed the maximum iteration or not. If the loop excessed the maximum iteration, stop; and return the Pareto set that stores the optimal solutions of the VMP problem; otherwise, continue until the end of a loop.Algorithm 1: Pseudocode of the proposed VMPMOPSO.
Input:n, number of the VMs;m, number of the physical servers;R, population size;D, dimension of particlesEmax, maximum size of archiveE;tmax, maximum number of iteration;bmin, bmax, minimum and maximum bounds of random number.Output: E: the archive set (Pareto set) of the optimal VM placement solutions.01: Sett = 0, Sid=Randbmin,bmax, Vid=0, A=∅, i = (1, 2, …, R), d = (1, 2, …, D),02:Repeat03:fori = 1 to Rdo04:Generate a random position Si=Si1,Si2,…,Sid,…, for the ith particle;05:Evaluate the fitness value of Si for all i using formulas (6), (7), and (8);06:    /∗ External archive updating ∗/07:ifSi≻∀Eλthen08:    UpdateE: E←E∩E¯θ∪Si,θis the do minated solution;09:else if (Si⊀∀E)⋀(Si⊁∀E) then10:    UpdateE:E←E∪Si;11:end if12:ifE>Emaxthen13:forj=1toEdo14:    Calculate the crowding entropyCE of each solution in E according to formula (17);15:    Sort archiveE in descending CE values;16:    UpdateE:E←E∩E¯δ, δ is the removed solution (redundant solutions);17:     Select the global best positionPgd randomly from the top of E18:end for19:end if20:   Personal best positionPid update;21:end for22:fori = 1 to Rdo23:ford = 1 to Ddo24:    Update the velocityVid using formula (12);25:    Compute the new positionSid using formula (13)26:end for27:end for28:t = t + 1;//increment steps29:Untilt>tmax30:Output archive E (the Pareto set)


### 5.1. Particle Definition

In order to apply the proposed VMPMOPSO algorithm successfully for the VMP problem, it is necessary to develop a high-effective encoding scheme to map the solutions of the VMP problem to the particle space. It is a critical step because the best mapping of the problem solutions into the particle leads to more efficiency and better performance of the VMPMOPSO algorithm. Here, we define the position matrix of particlesSit that represent all possible solutions of the VMP problem as follows:(20)Sit=y11ty12t…y1kt…y1nty21ty22t…y2kt…y2nt⋮⋮⋮⋮⋮⋮yi1tyi2t…yikt…yint⋮⋮⋮⋮⋮⋮ym1tym2t…ymkt…ymnt,where i represents the ith possible solutions and t denotes the iteration number. Also, there are n of VMs that are to be placed on m physical servers. We use a decision variable yik to represent whether VM i is allocated to server k or not. If VM i is allocated to server k, yik=1; if not, yik=0.


### 5.2. Update Strategy for Global Optimum

In VMPMOPSO, the crowding entropy mechanism incorporates into MOPSO specifically on the global optimum selection. The goal is to improve convergence to true Pareto optimal and control the capacity of the archive by deleting the redundant solutions in the archive set. Based on the crowding entropy, the crowding distance values of all nondominated solutions in the archive were calculated and ranked in a descending order. After that, the solutions with the highest crowding values have a better chance to be selected as the global optimum. For example, given two solution vectorsu⟶,v⟶∈E, E is an archive set, E=N, and the solution vector u⟶ is said to the global optimum along jth objective function if the following conditions satisfied:(1)
If a solution vectoru⟶ has crowding entropy value that dominates a solution vector v⟶ along the jth objective function, denoted as CEu⟶j≺CEv⟶j, then the solution u⟶ is more crowded than solution v⟶(2)
If the crowding entropy value of a solution vectoru⟶ dominates all solutions in archive E along the jth objective function, denoted as CEu⟶j≺∑i=1NCEij, then the solution u⟶ is selected as the global optimum


## 5.1. Particle Definition

In order to apply the proposed VMPMOPSO algorithm successfully for the VMP problem, it is necessary to develop a high-effective encoding scheme to map the solutions of the VMP problem to the particle space. It is a critical step because the best mapping of the problem solutions into the particle leads to more efficiency and better performance of the VMPMOPSO algorithm. Here, we define the position matrix of particlesSit that represent all possible solutions of the VMP problem as follows:(20)Sit=y11ty12t…y1kt…y1nty21ty22t…y2kt…y2nt⋮⋮⋮⋮⋮⋮yi1tyi2t…yikt…yint⋮⋮⋮⋮⋮⋮ym1tym2t…ymkt…ymnt,where i represents the ith possible solutions and t denotes the iteration number. Also, there are n of VMs that are to be placed on m physical servers. We use a decision variable yik to represent whether VM i is allocated to server k or not. If VM i is allocated to server k, yik=1; if not, yik=0.


## 5.2. Update Strategy for Global Optimum

In VMPMOPSO, the crowding entropy mechanism incorporates into MOPSO specifically on the global optimum selection. The goal is to improve convergence to true Pareto optimal and control the capacity of the archive by deleting the redundant solutions in the archive set. Based on the crowding entropy, the crowding distance values of all nondominated solutions in the archive were calculated and ranked in a descending order. After that, the solutions with the highest crowding values have a better chance to be selected as the global optimum. For example, given two solution vectorsu⟶,v⟶∈E, E is an archive set, E=N, and the solution vector u⟶ is said to the global optimum along jth objective function if the following conditions satisfied:(1)
If a solution vectoru⟶ has crowding entropy value that dominates a solution vector v⟶ along the jth objective function, denoted as CEu⟶j≺CEv⟶j, then the solution u⟶ is more crowded than solution v⟶(2)
If the crowding entropy value of a solution vectoru⟶ dominates all solutions in archive E along the jth objective function, denoted as CEu⟶j≺∑i=1NCEij, then the solution u⟶ is selected as the global optimum


## 6. Results and Discussion

In this section, we have conducted two simulation experiments to verify the effectiveness and efficiency of our proposed VMPMOPSO algorithm. We compare the performance of the proposed algorithm with three competing algorithms including a traditional single-objective algorithm FDD [52] and two multiobjective algorithms MGGA [19] and VMPACS [20] in terms of energy consumption, SLA violation, and resource wastage. We use CloudSim toolkit [57] to simulate and evaluate our proposed algorithm which was coded in java language and run on Intel Core i3 with 1.90 GHz CPU and 4 GB RAM. For our experiments, we use one cloud data center with 200 physical machines. We randomly generated 200 VMs instances. Each instance requests CPU and memory resources. We present the linear correlations of CPU and memory utilizations into the VM instances and use the method in [22] listed in Algorithm 2 to generate VM deployment requests.where both Dicpu and Dimem form the VM deployment request. εh, εn, and µ are random numbers verified randomly in the interval [0, 1]. DCPU¯ and Dmem¯represent the reference values of CPU and main memory demands, respectively.Algorithm 2: VM deployment request generator.
1:fori = 1 : 200 do2:Dicpu=2×Dcpu¯×εh3:Dimem=2×Dmem¯×εn5:if ((µ < P) && (Dicpu≥Dcpu¯)||(µ ≥ P) && (Dicpu<Dcpu¯)) then6:Diram = Dimem + Dmem¯10:end if11:end forTo control the generated VM deployment requests under different parameters, we assume two cases. In the first case, the range of generated CPU and memory resources is in the interval [0, 50), and the references valuesDCPU¯ and Dmem¯ are set to 25%, in which the probability value that controls the correlation between different reference values, denoted as P, is varying and set to 0.0, 0.25, 0.50, 0.75, and 1.0. Also, the average correlation coefficients of CPU and memory demands are set to −0.754, −0.348, −0.072, 0.371, and 0.755 per deployment request. These five correlation coefficient statuses represent strong-negative, weak-negative, no, weak-positive, and strong-positive. In the second case, the range of generated CPU and memory demands is in the interval [0, 90%), and the reference values DCPU¯andDmem¯ are set to 45%, in which the average correlation coefficient of CPU and main memory demands, referred to as the term “corr.”, is −0.755, −0.374, −0.052, 0.398, and 0.751.The parameter values of the optimization method in our VMPMOPSO algorithm are randomly verified as follows. The population size is limited to 300 particles, and the maximum number of iterationstmax is 500. The inertia weight ϕ was determined randomly in the interval [0, 0.8], the acceleration constants ψ1,ψ2 were verified randomly in the interval [1.5, 2.5], and the random numbers ϑ1,ϑ2 were verified randomly in the interval [0, 1].


### 6.1. Experiment I

We verified the performance of our proposed VMPMOPSO algorithm by comparing it with three algorithms, namely, FDD [52], MGGA [19], and VMPACS [20]. Figure 2 shows the total power consumption, wastage resource, and SLA violation of the four algorithms (FDD, MGGA, VMPACCS, and VMPMPSO) when the reference value is set to DCPU¯ = Dmem¯ = 25%, and the correlation coefficient is 0.754, −0.348, −0.072, 0.371, and 0.755, respectively. As shown in Figure 2(a), the VMPMOPSO algorithm can reduce power consumption significantly. It is easy to find that the VMPMOPSO algorithm has the least power consumption compared to FDD, MGGA, and VMPACCS. This is because the proposed VMPMOPSO based on crowding entropy can effectively improve the diversity among the obtained solutions of the VM placement problem and explore more feasible solutions in unknown regions and, therefore, increase the probability of finding the most optimal placement solution that minimizes the total power consumption. Similarly, we compare the resource wastage of FDD, MGGA, VMPACS, and VMPMOPSO algorithms, as shown in Figure 2(b). We can observe that the VMPMOPSO algorithm is superior to FFD, MGGA, and VMPACS algorithms in all scenarios. VMPMOPSO can effectively find the optimal placement solution that leaves the least amount of resource wastage. Finally, the third parameter to evaluate is SLA violation which is defined as the degradation of performance in servers after placing VM. For the four algorithms (FDD, MGGA, VMPACS, and VMPMOPSO) with different correlation coefficients (−0.754, −0.348, −0.072, 0.371, and 0.755) and when DCPU¯ = Dmem¯ = 25%, the SAL violation is shown in Figure 3(c). It is easy to find that VMPMOPSO leads to the least SLA violation compared with FDD, MGGA, and VMPACS, respectively. The reason is that the VMPMOPSO algorithm considers CPU utilization and memory usage of the physical server before making the placement decision.Figure 2
(a) Power consumption, (b) resource wastage, and (c) SLA violation of different algorithms in the case ofDCPU¯andDRAM¯ = 25%.
(a)(b)(c)Figure 3
(a) Power consumption, (b) resource wastage, and (c) SLA violation of different algorithms in the case ofDCPU¯andDRAM¯ = 45%.
(a)(b)(c)Figure3 reports the results of the second scenario when the reference value is DCPU¯ = Dmem¯ = 45% and Corr. is set to −0.755, −0.374, −0.052, 0.398, and 0.751, respectively. As shown in Figures 3(a)–3(c), once again our proposed VMPMOPSO algorithm is compared to FFD, MGGA, and VMPACS algorithms in terms of power consumption, resource wastage, and SLA violation. It is shown that, in this scenario also, our proposed VMPMOPSO algorithm offers better results.To demonstrate the effectiveness of the VMPMOPSO algorithm, we conducted another simulation experiment to compare MGGA, VMPACS, and our proposed VMPMOPSO algorithm. Figures4 and 5 show the convergence curves of the three algorithms. Each point on the curve refers to an optimal solution for the problem of VMP in the large-scale data center. In addition, the set of solutions that are not dominated by any other point combined together in a set of nondominated solutions is called the Pareto set. Here, three objective functions are defined as follows: f1 represents SLA violation, f2 represents power consumption, and f3 represents resource wastage. The distribution of the Pareto optimal solutions of MGGA, VMPACS, and VMPMOPSO after running 100 generations is shown in Figure 4. Similarly, the distribution of the Pareto optimal solutions of MGGA, VMPACS, and VMPMOPSO after running 500 generations is shown in Figure 5. As shown in Figures 4 and 5, the Pareto solution set given by the VMPMOPSO algorithm has better distribution and convergence than that from MGGA and VMPACS. It can be seen that the VMPMOPSO algorithm can quickly move toward the Pareto front, and the results are closer to the Pareto optimal solution than MGGA and VMPACS. Additionally, we observe that the obtained solutions by VMPMOPSO do not concentrate on a small region but distribute over the large search space of the target problem that leads to more diversity on the search and increased the chance to converge the Pareto optimal solution with high speed.Figure 4
The distribution of Pareto optimal solution set of (a) MGGA, (b) VMPACS, and (c) VMPMOPSO after 100 generations.
(a)(b)(c)Figure 5
The distribution of Pareto optimal solution set of (a) MGGA, (b) VMPACS, and (c) VMPMOPSO after 500 generations.
(a)(b)(c)


### 6.2. Experiment II

In this section, we carried out another experiment to evaluate the performance of the VMPMOPSO algorithm with two multiobjective algorithms: MGGA and VMPACS. We calculated two metrics, Generational Distance (GD) [58] and Spacing (SP) [59], for each algorithm. GD and SP can be defined as follows:(21)GD=1n∑i=1ndi2,where di is the Euclidean distances of the ith solution to the true Pareto front and n is the number of nondominated solutions. The smaller the value of GD, the better the convergence toward the Pareto front.(22)SP=1N−1∑i=1Nd¯−di2,where di=minj∑k=1mfki−fkj,i,j=1,2,…,n,f is the objective function, d¯ is the average of all di, and m is the number of objectives. The value of SP close to 0 indicates that the solutions that have been found by the algorithm are a good solution set. Table 1 shows the GD and SP obtained by VMPMOPSO and VMPACS algorithms. In this table, the column “Corr.” shows the correlation coefficients for the CPU utilization and memory usage.Table 1
GD and SP performance comparison of VMPMPSO, VMPACS, and MGGA.
Reference valueCorr.GDSPMGGAVMPACSVMPMPSOMGGAVMPACSVMPMPSODCPU¯ = Dmem¯ = 25%−0.7540.073210.045130.021720.53910.22650.1731−0.3480.058640.035200.018340.38730.16700.1213−0.0720.053930.032740.010250.32350.13830.11340.3710.032750.021450.008310.28360.11520.10870.7500.023810.019560.005470.16780.07780.0542DCPU¯ = Dmem¯ = 45%−0.7550.035400.025450.013250.19530.10820.1024−0.3740.041710.026380.014730.22840.11630.1133−0.0520.048380.031560.018910.28450.13610.12580.3920.025760.016720.007390.15700.06740.05320.7510.018390.008780.003240.10790.04950.0270As revealed in Table1, we can conclude that the average GD values of VMPMOPSO are less than those of the other two algorithms (MGGA and VMPACS). These results were due to the fact that the obtained solutions by the VMPMOPSO algorithm are closer to the true Pareto front than the other solutions given by MGGA and VMPACS. Regarding the SP metric, it is clear that the VMPMOPSO algorithm performs the best results compared to the MGGA and VMPACS algorithms. In other words, the distribution of the optimal solution set of VMPPSO is more uniform than the other optimal solutions set of MGGA and VMPACS algorithms.


## 6.1. Experiment I

We verified the performance of our proposed VMPMOPSO algorithm by comparing it with three algorithms, namely, FDD [52], MGGA [19], and VMPACS [20]. Figure 2 shows the total power consumption, wastage resource, and SLA violation of the four algorithms (FDD, MGGA, VMPACCS, and VMPMPSO) when the reference value is set to DCPU¯ = Dmem¯ = 25%, and the correlation coefficient is 0.754, −0.348, −0.072, 0.371, and 0.755, respectively. As shown in Figure 2(a), the VMPMOPSO algorithm can reduce power consumption significantly. It is easy to find that the VMPMOPSO algorithm has the least power consumption compared to FDD, MGGA, and VMPACCS. This is because the proposed VMPMOPSO based on crowding entropy can effectively improve the diversity among the obtained solutions of the VM placement problem and explore more feasible solutions in unknown regions and, therefore, increase the probability of finding the most optimal placement solution that minimizes the total power consumption. Similarly, we compare the resource wastage of FDD, MGGA, VMPACS, and VMPMOPSO algorithms, as shown in Figure 2(b). We can observe that the VMPMOPSO algorithm is superior to FFD, MGGA, and VMPACS algorithms in all scenarios. VMPMOPSO can effectively find the optimal placement solution that leaves the least amount of resource wastage. Finally, the third parameter to evaluate is SLA violation which is defined as the degradation of performance in servers after placing VM. For the four algorithms (FDD, MGGA, VMPACS, and VMPMOPSO) with different correlation coefficients (−0.754, −0.348, −0.072, 0.371, and 0.755) and when DCPU¯ = Dmem¯ = 25%, the SAL violation is shown in Figure 3(c). It is easy to find that VMPMOPSO leads to the least SLA violation compared with FDD, MGGA, and VMPACS, respectively. The reason is that the VMPMOPSO algorithm considers CPU utilization and memory usage of the physical server before making the placement decision.Figure 2
(a) Power consumption, (b) resource wastage, and (c) SLA violation of different algorithms in the case ofDCPU¯andDRAM¯ = 25%.
(a)(b)(c)Figure 3
(a) Power consumption, (b) resource wastage, and (c) SLA violation of different algorithms in the case ofDCPU¯andDRAM¯ = 45%.
(a)(b)(c)Figure3 reports the results of the second scenario when the reference value is DCPU¯ = Dmem¯ = 45% and Corr. is set to −0.755, −0.374, −0.052, 0.398, and 0.751, respectively. As shown in Figures 3(a)–3(c), once again our proposed VMPMOPSO algorithm is compared to FFD, MGGA, and VMPACS algorithms in terms of power consumption, resource wastage, and SLA violation. It is shown that, in this scenario also, our proposed VMPMOPSO algorithm offers better results.To demonstrate the effectiveness of the VMPMOPSO algorithm, we conducted another simulation experiment to compare MGGA, VMPACS, and our proposed VMPMOPSO algorithm. Figures4 and 5 show the convergence curves of the three algorithms. Each point on the curve refers to an optimal solution for the problem of VMP in the large-scale data center. In addition, the set of solutions that are not dominated by any other point combined together in a set of nondominated solutions is called the Pareto set. Here, three objective functions are defined as follows: f1 represents SLA violation, f2 represents power consumption, and f3 represents resource wastage. The distribution of the Pareto optimal solutions of MGGA, VMPACS, and VMPMOPSO after running 100 generations is shown in Figure 4. Similarly, the distribution of the Pareto optimal solutions of MGGA, VMPACS, and VMPMOPSO after running 500 generations is shown in Figure 5. As shown in Figures 4 and 5, the Pareto solution set given by the VMPMOPSO algorithm has better distribution and convergence than that from MGGA and VMPACS. It can be seen that the VMPMOPSO algorithm can quickly move toward the Pareto front, and the results are closer to the Pareto optimal solution than MGGA and VMPACS. Additionally, we observe that the obtained solutions by VMPMOPSO do not concentrate on a small region but distribute over the large search space of the target problem that leads to more diversity on the search and increased the chance to converge the Pareto optimal solution with high speed.Figure 4
The distribution of Pareto optimal solution set of (a) MGGA, (b) VMPACS, and (c) VMPMOPSO after 100 generations.
(a)(b)(c)Figure 5
The distribution of Pareto optimal solution set of (a) MGGA, (b) VMPACS, and (c) VMPMOPSO after 500 generations.
(a)(b)(c)


## 6.2. Experiment II

In this section, we carried out another experiment to evaluate the performance of the VMPMOPSO algorithm with two multiobjective algorithms: MGGA and VMPACS. We calculated two metrics, Generational Distance (GD) [58] and Spacing (SP) [59], for each algorithm. GD and SP can be defined as follows:(21)GD=1n∑i=1ndi2,where di is the Euclidean distances of the ith solution to the true Pareto front and n is the number of nondominated solutions. The smaller the value of GD, the better the convergence toward the Pareto front.(22)SP=1N−1∑i=1Nd¯−di2,where di=minj∑k=1mfki−fkj,i,j=1,2,…,n,f is the objective function, d¯ is the average of all di, and m is the number of objectives. The value of SP close to 0 indicates that the solutions that have been found by the algorithm are a good solution set. Table 1 shows the GD and SP obtained by VMPMOPSO and VMPACS algorithms. In this table, the column “Corr.” shows the correlation coefficients for the CPU utilization and memory usage.Table 1
GD and SP performance comparison of VMPMPSO, VMPACS, and MGGA.
Reference valueCorr.GDSPMGGAVMPACSVMPMPSOMGGAVMPACSVMPMPSODCPU¯ = Dmem¯ = 25%−0.7540.073210.045130.021720.53910.22650.1731−0.3480.058640.035200.018340.38730.16700.1213−0.0720.053930.032740.010250.32350.13830.11340.3710.032750.021450.008310.28360.11520.10870.7500.023810.019560.005470.16780.07780.0542DCPU¯ = Dmem¯ = 45%−0.7550.035400.025450.013250.19530.10820.1024−0.3740.041710.026380.014730.22840.11630.1133−0.0520.048380.031560.018910.28450.13610.12580.3920.025760.016720.007390.15700.06740.05320.7510.018390.008780.003240.10790.04950.0270As revealed in Table1, we can conclude that the average GD values of VMPMOPSO are less than those of the other two algorithms (MGGA and VMPACS). These results were due to the fact that the obtained solutions by the VMPMOPSO algorithm are closer to the true Pareto front than the other solutions given by MGGA and VMPACS. Regarding the SP metric, it is clear that the VMPMOPSO algorithm performs the best results compared to the MGGA and VMPACS algorithms. In other words, the distribution of the optimal solution set of VMPPSO is more uniform than the other optimal solutions set of MGGA and VMPACS algorithms.


## 7. Conclusions

In this paper, we propose a novel VMP algorithm called VMPMOPSO. VMPMOPSO treats the problem of VMP as a multiobjective optimization problem and uses MOPSO to optimally solve the VMP problem. The proposed approach optimizes multiobjectives such as SLA violations, power consumption, and resource wastage. We have conducted two simulation experiments to evaluate the effectiveness and efficiency of the VMPMOPSO algorithm. VMPMOPSO was compared with a single-objective FDD algorithm and two existing multiobjective algorithms, MGGA and VMPACS. The experimental results show that VMPMOPSO is more effective and efficient than FDD, MGGA, and VMPACS algorithms. Furthermore, VMPMOPSO with the help of the crowding entropy method maintains good population diversity and can quickly move toward the Pareto front. In general, the VMPMOPSO algorithm can find the optimal VMP solution that offers the best compromises among different objectives and not only helps providers to maximize the profit by reducing energy consumption but also helps them to keep the SLA at the desired level. Future work will focus on using VMPMOPSO to handle some real-world multiobjective problems.



---

*Source: 8892734-2021-01-13.xml*