一种面向云计算非比例资源消耗特性的虚拟机放置算法
2019-09-10罗香玉辛刚桂小林
罗香玉 辛刚 桂小林
摘 要：虛拟机放置是云计算中的一个基本问题。 通过将多台虚拟机聚集在单台物理机上，云计算可极大降低系统的资源以及能源消耗。虚拟机放置的目标之一是开启最少数量的物理机来满足所有虚拟机的资源需求。一个重要的挑战在于各虚拟机对不同类型资源消耗的比例往往与物理机所配备的各类资源的比例并不相同。一旦物理机上某类资源消耗殆尽，该物理机上其它类型的资源将无法得到利用，随之导致所开启物理机总数以及能耗成本增加。文中借助多种不同配置的物理机来解决上述问题。首先，虚拟机被划分为若干子集合。划分的约束条件是保证各个虚拟机子集合作为一个整体所消耗的各类资源恰与某一类型物理机各类资源的配置成比例。然后，利用同构环境的虚拟机放置算法，完成各虚拟机子集合在相应类型物理机上的放置。实验结果表明，文中算法能够协调各类资源的使用，从而有效减少物理机使用总量，降低能耗成本13.0%～57.6%.
关键词：虚拟机放置;非比例资源消耗;云计算;能耗节约;多维度资源
中图分类号：TP 393 文献标志码：A
文章编号：1672-9315（2019）05-0889-09
Abstract：Virtual machine placement is a basic problem in cloud computing.By consolidating several virtual machines onto one single physical machine，cloud computing reduces both resource costs and energy consumption.One of the optimization objectives of virtual machine placement is to use a minimum number of physical machines to accommodate all the virtual machines requested by customers.The challenge lies in that the multi-dimensional resources required by a virtual machine are typically not proportional to that provided by a physical machine.Once a single dimension of resource is exhausted in a physical machine，the rest of all the other dimensions of resources will stay unutilized，leading to a great amount of resource waste.This paper proposes a new virtual machine placement algorithm that mixes multiple kinds of physical machines to tackle the problem of unsufficientresource utilization.Firstly，virtual machines are divided into several subsets.For each subset as a whole，different dimensions of resources requested are approximately proportional to that provided by a kind of physical machine.Secondly，virtual machines in each subset are separately placed onto the corresponding kind of physical machines.Experimental results show that the proposed algorithm coordinates the utilization of different types of resources and achieves power reduction ranging from 13.0% to 57.6%.
Key words：virtual machine placement;non-proportional resource consumption;cloud computing;power reduction;multidimensional resources
0 INTRODUCTION
Nowadays cloud computing is a popular way of offering computation services.It enables customers to enjoy computation services as conveniently as they enjoy electricity and water[1].Customers are typically served by virtual machines.By consolidating several virtual machines onto one single physical machine，the whole cloud computing system achieves both more efficient utilization of resources and lower power consumption.
A cloud computing system is a large-scale distributed system composed of thousands of or even more physical machines[2].A basic problem is how to place the virtual machines such that the number of the consumed physical machines can be minimized while satisfying multiple resource constraints.
To accommodate several virtual machines，a physical machine is required to provide available CPU，memory and other resources no less than that requested by the virtual machines.Once a single dimension of resource is exhausted in a physical machine，all the rest of the other dimensions of resources on it will stay unutilized[3].Therefore，an ideal virtual machine placement algorithm should assign each physical machine with several virtual machines that just use up each dimension of resource on it.
However，the challenge lies in that different dimensions of resources required by a virtual machine are typically not proportional to that provided by a physical machine.Existing studies mainly aim to make the best-effort optimization of resource utilization under the assumption that the candidate physical machines are deterministic and unchangeable.They rarely investigate how to adaptively adjust the candidate physical machines’ configuration according to the virtual machines’ requirements to make further improvements.In the situations that the virtual machines differ significantly with the physical machines in the proportions of the multiple dimensions of resources，the best-effort optimization is usually unsatisfactory.
Our contributions mainly include the following three aspects.Firstly，we redefine the virtual machine placement problem and divide it into two sub-problems.One is how to adaptively adjust the configuration of the physical machines according to the requirements of the virtual machines.The other is how to map the virtual machines to the candidate physical machines.Secondly，we propose an algorithm，namely CORE（COordinating multiple REsources），to resolve the problem.Finally，extensive experiments have been conducted to evaluate the efficiency of the algorithm.The results show that it can achieve power reduction ranging from 13.0% to 57.6%.
The paper is organized as follows.Section 1 summarizes the related work.Section 2 explains the motivations of our work.Section 3 redefines the virtual machine placement problem.Section 4 elaborates the CORE algorithm.Section 5 gives the experimental results and Section 6 concludes the whole paper.
1 RELATED WORK
The virtual machine placement algorithm greatly affects the performance and the efficiency of clouds and attracts many researchers’ attention[4].
According to the assumption for the resources，existing virtual machine placement algorithms could be classified into single dimensional resource oriented and multi-dimensional resource oriented algorithms.F.Pan et al.proposed a single resource oriented algorithm that only considers the CPU resource[5].L.Chen et al.proposed a multi-dimensional resource oriented algorithm RIAL that considers CPU，memory and the network resources[6].It assigns different weights to different resources and calculates the resource intensity of each physical machine based on the weights.By this way，the multi-dimensional problem is transformed into a single dimensional one.R.Li et al.proposed a true multidimensional solution which aims to keep balanced usage of each dimensional resource[7].However，the physical machines were assumed to be determined in advance and only best-effort utilization was provided.Besides，the relationships among the resource utilization，the characteristics of virtual machine requirements and the configuration of the physical machines were not investigated.
According to the assumption for the characteristic of the workload，existing virtual machine placement algorithms can be classified into static and dynamic ones.Static algorithms assume that the workload of each virtual machine is constant.Many approximation algorithms for bin packing can be used for static virtual machine placement[8].Besides，genetic or other intelligent optimization algorithms can also work[9].Dynamic algorithms[10-11]migrate virtual machines from one physical machine to another as the workload changes.
From the point of view of the optimization objectives，existing virtual machine placement algorithms can be classified into single-objective oriented and multi-objective oriented ones.The optimization objects include minimizing SLA violation，maximizing resource utilization，minimizing energy consumption，etc[12-13].W.Wang et al.proposed a single objective oriented algorithm that aims for energy minimization[14].J.Xu and J.Fortes proposed an algorithm that simultaneously minimizes resource wastage，power consumption and thermal dissipation costs[15].H.Zhao proposed an algorithm that ensures both low power consumption and high performance guarantee[16].
Besides，the state-of-art research also addresses the virtual machine placement problem in edge cloud systems[17-19].
However，to the best of our knowledge，existing literatures mainly concentrate on virtual machine placement optimization under the assumption that the candidate physical machines are determined in some artificial way.There is no solution that automatically changes the candidate physical machines according to the virtual machines’ resource requirements.
2 MOTIVATIONS
For economic and environmental reasons，cloud computing aims to employ a minimum number of physical machines to accommodate the virtual machines requested by customers，reducing both resource costs and power consumption.For a given set of virtual machines，both the resource costs and the power consumption are affected by not only the virtual machine placement algorithm itself，but also the configuration of the physical machines.
Suppose that there are 500 virtual machines.For half of them，each one requires 3 cores CPU and 0.5 GB RAM.For the other half，each one requires 1 core CPU and 1.5 GB RAM.Therefore，the total amount of CPU required by the virtual machines equals 1 000 cores，and the total amount of required RAM equals 500 GB.With the physical machines configured with 4 cores CPU and 8 GB RAM，the least number of the powered-on physical machines cannot be smaller than 250 and the utilization efficiency of RAM cannot be greater than 25%，whatever virtual machine placement algorithm is adopted.However，with the physical machines configured with 4 GB RAM and 8 cores CPU，only 125 physical machines need to be powered on and both the two types of resources can be sufficiently utilized.
For the above scenario，changing the physical machine’s configuration leads to more efficient resource utilization and lower power consumption.However，it is not always practical to do so in reality.Virtual machines are created and removed dynamically，and each of them may have different resource requirements.Hence the optimal physical machine configuration changes frequently.It is not practical to alter the physical machine’s configuration all the time.
Therefore，we mix several kinds of physical machines to mimic physical machines with arbitrary kind of configuration.We assume that the cloud providers purchase several kinds of physical machines with different resource configurations and the number of each kind of physical machines is large enough.For a given set of virtual machines，the placement algorithm automatically adjusts the number of each kind of physical machines to power on，ensuring that the multiple resources provided by the whole powered-on physical machines always proportional to that requested by the whole virtual machines.For cloud providers，the most important thing is not to purchase but to power on the least number of physical machines，because the budget for power consumption is much higher than the infrastructure costs.
In a word，for a given set of virtual machines，the efficiency of resource utilization is greatly affected by the physical machines’ configuration.With unsuitable physical machine configuration，resource waste is inevitable，whatever placement algorithm is adopted.We aim to mix several kinds of physical machines to keep the mimic configuration always suitable to the virtual machines，so that the placement results can be improved compared with those obtained with a deterministic configuration.
3 PROBLEM STATEMENT
Suppose that there are K kinds of physical machines with different resource configurations.The number of each kind of physical machine is large enough for accommodating an arbitrary set of virtual machines.The i th kind of physical machine is represented with a vector pi composed of C elements with each element pij corresponding to the amount of the j th type of resource provided by the i th kind of physical machine.There are N virtual machines to be placed onto the physical machines.Each virtual machine is expressed with a vector vi′ also composed of C elements，with each element vi′j representing the amount of the j th type of resource requested by the i′ th virtual machine.Here 1≤i≤K，1≤i′≤N，1≤j≤C，K，N and C are known numbers.
The virtual machine placement problem is divided into two sub-problems.Firstly，for accommodating a given set of virtual machines，how many each kind of physical machines should be powered on？ Secondly，how to map the virtual machines to the powered-on physical machines？ The optimization objective is to minimize the total number of the powered-on physical machines while satisfying each virtual machine’s resource requirements.
4 THE CORE ALGORITHM
4.1 Basic idea
Let ni denote the number of the powered-on physical machines with the i th kind of configuration and VSi denote the set of the virtual machines mapped to the i th kind of physical machines.Hence {VSi|1 ≤i≤K} defines a partitioning on the whole set of the virtual machines.
Once we obtain a proper partitioning of the virtual machines，through placing the virtual machines in each subset VSi to the ith kind of physical machines，ni can be figured out.Therefore，the partitioning of the virtual machines is at the heart of the problem.
The CORE algorithm works in three steps.Firstly，it partitions the whole virtual machine set into K subsets ensuring that each subset VSi consumes the multiple resources proportionally to the provisioning of the ith kind of physical machines.Secondly，it separately calculates the mappings between the virtual machines in each subset VSi and the ith kind of physical machines.Thirdly，it merges the results of the second step，the number of each kind of physical machines to be powered on（i.e.，ni）is obtained，and the mappings between the whole virtual machines and the whole powered-on physical machines are also figured out.
4.2 Elaboration of the algorithm
The CORE algorithm is depicted in Algorithm 1.In the algorithm，there are two inputs PS and VS.PS is the set of physical machine types with each element pi representing the configuration of the i th type of physical machine，and VS is the set of virtual machines with each element vi′ representing the resource requirements of the vi′ th virtual machine.Both pi and vi′are vectors composed of C elements.The j th element of pi denoted by pij represents the amount of the j th type of resource provided by the i th kind of a single physical machine，and the j th element of vi′ denoted by vi，j represents the amount of the j th type of resource requested by the i′th virtual machine.There are two outputs NS and MS.NS is a set of numbers with each element ni representing the number of the powered-on physical machines with the i th kind of configuration.MS is a set of tuples with each element
Algorithm 1：The CORE algorithm
The main body of the algorithm calls three sub-algorithms as shown in Algorithm 1.The partitioning sub-algorithm is responsible for partitioning the virtual machine set VS into K subsets，the placement sub-algorithm is responsible for placing the virtual machines in a subset VSi to the i th kind of physical machines，and the merging sub-algorithm is responsible for combining the placement results to obtain the number of the powered-on physical machine for each kind of configuration，and the mappings between the whole virtual machines and the whole powered-on physical machines.In the algorithm description，π represents the partition on VS and π={VSi|1 ≤ i ≤ K}.MSi represents the mapping of the virtual machines in subset VSi and the i th kind of physical machines.
4.2.1 The partitioning sub-algorithm
As discussed in the subsection 4.1，the partitioning of the virtual machines is at the heart of the problem.For the virtual machines as a whole，the multiple resources requested may be not proportional to any kind of the existing physical machines.With proper partitioning，the multiple resources requested by each virtual machine subset could be proportional to a certain kind of physical machines.
Let Rij denote the amount of the j th type of resource requested by the virtual machines of the subset VSi.VSi satisfies proportional resource consumption means that for each j between 1 and C，Rij/pij is almost the same.We define θ to measure the degree of proportionality，with θ=min{Rij/pij|1≤j≤C}/max{Rij/pij|1≤j≤C}.θ is a number between 0 and 1.A larger θ means a higher degree of proportionality.It should be noted that max{Rij/pij|1≤j≤C} is a lower bound of the number of the ith kind of physical machines to power on.
The partitioning sub-algorithm aims to guarantee that each virtual machine subset VSi satisfies proportional resource consumption，and the lower bound of the whole powered-on physical machines，i.e.，1≤i≤K（max{Rij/pij|1≤j≤C}），is minimized.The partitioning sub-algorithm adopts a greedy strategy described in Algorithm 2.For each virtual machine，the algorithm assigns it to the subset that makes the least increase of 1≤i≤K（max{Rij/pij|1≤j≤C}）.
4.2.2 The placement sub-algorithm
The placement sub-algorithm is responsible for placing the virtual machines in a subset VSi to the ith kind of physical machines.Although other placement strategies also work，we adopt the FirstFit strategy for simplicity.Since the partitioning sub-algorithm ensures that the multiple resources requested by the virtual machine subset VSi are approximately proportional to that provided by the ith kind of physical machines，even if the FirstFit strategy is qualified to generate ideal placement results.Experimental results also validate the conjecture，as exposed in Section 5.The placement sub-algorithm is described in Algorithm 3.In the description，
The results indicate that，the 2nd configuration can lead to high utilization of the two types of resources as well as low power consumption.Moreover，the number of the consumed physical machines（.i.e.，266）is very near to nmin（i.e.，253）.Therefore，as long as the configuration of the physical machines is suitable to the virtual machines，even if the First Fit algorithm can generate near-optimal placement results.More complex placement algorithms are not very necessary.
The results also indicate that，with unsuitable configuration，at least one type of resource generates a great amount of waste.Meanwhile，there is little room for further optimization by improving placement strategy，since the number of physical machines consumed already approaches the lower bound nmin.With the 1st configuration，the number of the consumed physical machines equals 507 while nmin equals 496.With the 3rd configuration，the number of the consumed physical machines equals 530 while nmin equals 506.Whatever virtual machine placement algorithm is adopted，the reduction of the number of the consumed physical machines cannot be greater than 4.5%.
In summary，compared to the placement strategy，the configuration of the physical machine really matters.The most important thing is to make the configuration always suitable to the virtual machines.Once the configuration is determined，there is little room for further optimization whatever placement strategy is adopted.Meanwhile，the requirements of the virtual machines are dynamic，and any single kind of physical machine configuration can not always meet the virtual machines’ requirements.Therefore，the CORE algorithm adaptively adjusts the number of each kind of physical machines powered on to make the different kinds of physical machines as a whole always suitable to the requirements of the virtual machines.
5.3 Evaluation of CORE’s performance
In the experiment，we use the synthetic virtual machine generator to obtain 1 000 virtual machines’ resource requirements.The parameters are set as follows：a1=1，b1=7，a2=1 and b2=19.In the experiment，the total amount of CPU requirement equals 4 046 cores，and the total amount of RAM requirement equals 9 887 GB.
We adopt the First Fit algorithm to place the virtual machines onto the physical machines with each kind of configuration respectively and adopt the CORE algorithm to place them onto the three kinds of physical machines as well.Besides，we calculate the optimal value of the power consumption and the resource utilization for the three configurations.The results are shown in TABLE Ⅳ.
The results show that，through properly mixing the three kinds of physical machines，the CORE algorithm reduces the power consumption and improves the resource utilization efficiency.The power consumption reduction ranges from 13.0% to 57.6%.
For further analysis，we calculate the degree of proportionality θ.We have θ（1）=0.15，θ（2）=0.61 and θ（3）=0.41 respectively with the three different configurations.It means that the second configuration fits the requirements of the virtual machines best，while the first configuration is the worst.Therefore，the situation where only the physical machines with the first configuration are adopted leads to the maximum power consumption，and the CORE reduces the power consumption with the highest ratio（i.e.，57.6%）.
6 CONCLUSION
The efficiency of virtual machine placement is affected by not only the placement strategy itself but also the configuration of the physical machines.The improper configuration leads to a waste of both resource costs and energy consumption.This paper proposes the idea of mixing several kinds of physical machines to mimic a new kind of configuration that properly fits the resource requirements of the virtual machines.Furthermore，we devise the algorithm CORE to realize the idea.It divides the virtual machines into several subsets，with each subset satisfying proportional resource consumption to a certain kind of physical machines.Experimental studies show that the algorithm achieves 13.0% to 57.6% energy reduction compared with those adopt any single kind of physical machines.
REFERENCES：
[1] Zhao L，Lu L，Jin Z，et al.Online virtual machine placement for increasing cloud provider's revenue[J].IEEE Transactions on Services Computing，2017，10（2）：273-285.
[2]Chaisiri S，Lee B，Niyato D.Optimization of resource provisioning cost in cloud computing[J].IEEE Transactions on Services Computing，2012，5（2）：164-177.
[3]Zhang J，He Z，Huang H，et al.SLA aware cost efficient virtual machines placement in cloud computing[C]//Proceedings of IEEE International Conference on Performance，Computing and Communications，2014：1-8.
[4]Masdari M，Nabavi S，Ahmadi V.An overview of virtual machine placement schemes in cloud computing[J].Journal of Network & Computer Applications，2016，66（C）：106-127.
[5]Pan F，Jiang C，Xu X，et al.Placement strategy of virtual machines based on workload characteristics[J].Journal of Chinese Computer Systems，2013，34（3）：520-524.
[6]Chen L，Shen H，Sapra K.RIAL：resource intensity aware load balancing in clouds[C]//Proceedings of IEEE Conference on Computer Communications（INFOCOM），2014：1294-1302.
[7]Li R，Zheng Q，Li X，et al.A novel multi-objective optimization scheme for rebalancing virtual machine placement[C]//Proceedings of IEEE International Conference on Cloud Computing，2016：710-717.
[8]Bansal N，Caprara A，Sviridenko M.Improved approximation algorithms for multidimensional bin packing problems[C]//Proceedings of IEEE Symposium on Foundations of Computer Science，2006：697-708.
[9]Kaaouache M，Bouamama S.Solving bin packing problem with a hybrid genetic algorithm for VM placement in cloud[J].Procedia Computer Science，2015，60（1）：1061-1069.
[10]Zhang M，Ren H，Xia C.A dynamic placement policy of virtual machine based on MOGA in cloud environment[C]//Proceedings of IEEE ISPA/IUCC，2017：885-891.
[11]Hyser C，Mckee B，Gardner R，et al.Autonomic virtual machine placement in the data center[R].HP Labs Technical Report，HPL-2007-189，2007.
[12]Gaggero M，Caviglione L.Model predictive control for energy-efficient，quality-aware，and secure virtual machine placement[J].IEEE Transactions on Automation Science and Engineering，2019，16（1）：420-432.
[13]Guerrero C，Lera I，Bermejo B，et al.Multi-objective optimization for virtual machine allocation and replica placement in virtualized hadoop[J].IEEE Transactions on Parallel and Distributed Systems，2018，29（11）：2568-2581.
[14]Wang W，Jiang Y，Wu W.Multiagent-based resource allocation for energy minimization in cloud computing systems[J].IEEE Transactions on Systems Man & Cybernetics Systems，2017，47（2）：205-220.
[15]Xu J，Fortes J.Multi-objective virtual machine placement in virtualized data center environments[C]//Proceedings of IEEE International Conference on Green Computing and Communications，2010：179-188.
[16]Zhao H，Wang J，Liu F，et al.Power-aware and performance-guaranteed virtual machine placement in the cloud[J].IEEE Transactions on Parallel & Distributed Systems，2018，29（6）：1385-1400.
[17]Li K，Nabrzyski J.Networked virtual machine placement in edge cloud systems[C]//Proceedings of IEEE International Symposium on Parallel and Distributed Computing，2019：23-31.
[18]Tziritas N，Koziri M，Bachtsevani A，et al.Data replication and virtual machine migrations to mitigate network overhead in edge computing systems[J].IEEE Transactions on Sustainable Computing，2017，2（4）：320-332.
[19]Tao Z，Xia Q，HAO Z，et al.A survey of virtual machine management in edge computing[J].Proceedings of the IEEE，2019，107（8）：1482-1499.
[20]Calheiros R，Ranjan R，Beloglazov A，et al.CloudSim：a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J].Software Practice & Experience，2011，41：23-50.
