基于资源需求分布特征的异构云环境虚拟机放置算法

薛弘晔，朱天磊，罗香玉，冯 健

(西安科技大学 计算机科学与技术学院，西安 710054)

基于资源需求分布特征的异构云环境虚拟机放置算法

薛弘晔，朱天磊，罗香玉*，冯 健

(西安科技大学 计算机科学与技术学院，西安 710054)

针对异构云环境中的虚拟机放置(VMP)问题，提出一种基于虚拟机资源需求分布特征的放置算法(RDDFPA)。首先，建立基于CPU资源和内存资源比例系数的虚拟机需求和物理机配置描述方法，并根据该比例系数对所有虚拟机进行排序；其次，通过分析虚拟机需求与物理机配置各自在CPU资源和内存资源比例方面的关系，确定比例分界点，完成虚拟机集合的划分，每个虚拟机子集合的规模反映出对相匹配的不同配置物理机的需求比例;最后，利用启发式算法如首次适应(First Fit)算法完成虚拟机子集合在相匹配配置的物理机子集合上的放置。理论分析和仿真实验结果表明，与采用任意单一配置的物理机总数量相比，所提算法所需物理机的总台数减少了2%～17%。RDDFPA能够根据虚拟机资源需求分布的不同，确定各类配置物理机的数量，高效完成虚拟机的放置，在提高资源利用率的同时，降低了系统能耗。

云计算；数据中心；虚拟机放置；异构云环境；能源效率

0 引言

随着云服务市场的迅速发展，数据中心能耗问题愈发突出[1]。2015年，我国数据中心总量已超40万个，年耗电量超过全社会用电量的1.5%[2]。提高数据中心服务器资源利用率，降低能耗，成为了当前数据中心亟待解决的问题[3]。解决该问题的一个常见手段是利用虚拟化技术进行服务整合：也就是把服务请求进行整合，减少活动物理机数量，从而提高资源利用率，减少能源消耗[4]。由此产生了虚拟机放置(Virtual Machine Placement, VMP)问题：根据一定的方法和策略，把虚拟机(Virtual Machine, VM)放置在最适合的物理机 (Physical Machine, PM)中。

目前对于VMP的研究，一般是在假设数据中心物理机完全同构的前提下，仅着眼于改进放置算法本身。有些研究虽然考虑了物理机异构，但是没有分析虚拟机资源需求分布特征与异构云环境之间的关联。现实生活中，数据中心往往拥有多种物理机资源配置，是一个异构的云环境，而虚拟机需求的分布特征也多种多样。虚拟机需求分布的变化，反映到异构物理机上就会使得所需异构物理机数量也发生变化。

针对异构云环境下的虚拟机放置问题，本文依据虚拟机资源需求分布特征的变化并将其与异构物理机的配置比例关系相联系，提出一种分两步进行的基于虚拟机资源需求分布特征的放置算法(Resource Demand Distribution Feature based Placement Algorithm, RDDFPA)。首先，利用异构物理机资源配置和虚拟机资源需求分布特征的比例关系对虚拟机需求集合进行划分，虚拟机需求子集合的变化使得不同配置物理机产生数量变化；其次，利用启发式算法，在对应配置物理机上，对划分后的虚拟机需求进行放置。实验结果表明，相比直接在同构物理机上执行启发式算法进行放置，应用该算法在异构云环境下进行的虚拟机放置使用的活动物理机数量更少，资源利用率更高，能耗更低。

1 现有VMP研究

VMP的难点在于它是一种NP-Hard问题，甚至是NP-完全问题，难以在多项式时间内解决[5]。根据云环境的同构与异构来对现有研究进行分类。

在同构云环境基础下，主要以改进放置算法本身为主。常用算法有两种，即启发式算法和元启发式算法。

启发式算法的特点在于它可以在物理机和虚拟机数量较多，求最优解难度较大、耗时较长的情况下，以较小的开销找到一个相对合理的近似解[6]。经典的算法有首次适应(First Fit)算法、最佳适应(Best Fit)算法等[7]。改进算法如Lee等[8]提出的两个具有节能效果的启发式服务整合算法，其目的是最大化物理机的利用率，从而减少活动物理机数量，节约能耗。

元启发式算法的特点在于该类算法能较好地找出全局最优解，但是其时间复杂度较高，导致可扩展性和实时性较差[6]。较为常见的元启发式算法有蚁群算法：Gao等[9]把同构环境下虚拟机的放置问题看作一个多目标优化问题，提出了一种多目标蚁群算法，以降低系统的能源消耗、提高物理机的资源利用率。还有诸如遗传算法[10]和模拟退火算法[11]等。

针对异构云环境，目前的研究相对较少。Beloglazov等[12]考虑了异构性问题，提出一个能源感知的资源分配启发式算法，将虚拟机放置在一个使系统能源消耗增加最少的物理机上。但该算法只考虑CPU需求，并没有考虑所需资源的多维性。周东清等[4]考虑了资源的多维性，提出一个启发式算法，在异构物理机上利用权重来分配虚拟机，同时保持一定的负载均衡。Shi等[13]考虑了服务器的异构性，提出了按照物理机不同资源配比进行虚拟机分配的启发式算法。这些研究都没有考虑到虚拟机需求的分布变化，并将其与异构物理机的配置或数量相联系。

2 异构云环境下资源需求分布的具体描述

2.1 虚拟机资源需求分布的具体描述

虚拟机需求集合由一系列的虚拟机需求组成，定义为Svm。Svm中的每个虚拟机需求对不同类型资源需求往往具有偏向性。按照偏向性，可把集合中的虚拟机划分为两类：CPU处理能力偏重的计算密集型和内存空间偏重的数据密集型。假设第k个虚拟机包括两种资源需求：CPU处理能力CPUvmk和内存空间MEMvmk，CPU处理能力的单位为每秒百万条指令(Million Instructions Per Second, MIPS)，内存空间(MEMory, MEM)的单位为GB。虚拟机需求配置比例计算公式为：

ratevmk=CPUvmk/MEMvmk

(1)

根据每个虚拟机的配置比例ratevm，从小到大对Svm内的虚拟机需求进行排序，便得到一个排序后的虚拟机资源需求分布序列sortedListvm={vm1,vm2,…,vmn}。

2.2 异构云环境的具体描述

本文中，异构云环境由两种具有不同资源偏向性且和虚拟机资源需求分布相对契合的物理机组成。结合实际，选出两种物理机构成异构物理机组pairpm={pmleft,pmright}。其中pmleft为数据密集型，配置比例为：

ratepmleft=CPUpmleft/MEMpmleft

(2)

另一种物理机pmright为计算密集型，配置比例ratepmright大于ratepmleft。

2.3 虚拟机资源需求分布的跨度分类

虚拟机资源需求分布的变化，体现为序列sortedListvm分布范围的不同，在以资源配置的比例为坐标的数轴上，即表现为从ratevm1至ratevmn的区间长度。依据区间长度在数轴上做椭圆，来表示sortedListvm的分布范围，本文称其为分布跨度。而根据物理机资源配置的比例也可以在该数轴上标识异构物理机组的位置。至此，数轴就可以直观地展示出sortedListvm和pairpm的关系。根据虚拟机需求分布可能出现的情况，并结合异构物理机组的配置比例，如图1所示，大体可以使用四种跨度情况来囊括。

图1 跨度情况分类Fig. 1 Span situation classification

2.4 问题描述

在本文提出的算法中，通过研究异构物理机组和虚拟机资源需求分布特征之间的资源比例关系，在执行虚拟机放置算法之前对虚拟机资源需求分布进行划分处理，从而更好地放置虚拟机，达到减少活动物理机、节约能耗的效果。具体问题可以分解为以下几个部分：

1)依据虚拟机资源需求集合特征和异构物理机组的关系，判定跨度情况；

2)划分虚拟机资源需求集合，使其分别与两种异构物理机相匹配；

3)在两种物理机上分别进行虚拟机放置。

3 算法描述

本文提出的RDDFPA具体可以分为两大阶段：

第一阶段 依据虚拟机需求分布和物理机资源配比的关系，在排序后的sortedListvm上取得一个划分点；

第二阶段 在取得划分点后，将划分后的虚拟机需求分别在相应侧物理机上使用启发式算法进行放置。

其中第一阶段可以细分为：比例数轴的预处理；确定虚拟机资源需求分布跨度；获取虚拟机序列分界点；判断划分点。

3.1 比例数轴的预处理

如图1所示，本文以pmleft的资源比例ratepmleft和pmright的资源比例ratepmright之间的中点作为数轴的中心点，称为异构物理机组中心点center。center的作用在于：依据不同配置的pairpm确定相应的center，由此可以界定虚拟机资源需求的偏向性，即位于center左侧的虚拟机资源需求为计算密集型，位于右侧则被认为是数据密集型。

根据ratepmleft和ratepmright，在数轴上标识出pairpm的具体位置，得出比例跨度[ratepmleft,ratepmright]，并依据它确定数轴的异构物理机组中心点center。

center的具体取值方式为：center并非数轴上两种物理机之间的距离中点，而是比例中点，此例中center应位于1/1处。对两侧物理机的CPU处理能力之和与内存空间之和求商，便可得到正确的center比值ratecenter，即使用式(3)计算:

(3)

3.2 确定虚拟机资源需求分布跨度

在sortedListvm={vm1,vm2,…,vmn}中，取得首尾两个虚拟机需求的比例ratevm1以及ratevmn，据此确定sortedListvm在数轴上的分布跨度为[ratevm1,ratevmn]。将[ratevm1,ratevmn]和pairpm比例跨度[ratepmleft,ratepmright]进行对比，即可确定虚拟机资源需求分布跨度情况。必须使得pairpm跨度情况为图1(c)或图1(d)所示，即pairpm的比例跨度[ratepmleft,ratepmright]需要满足以下条件：ratevmn>ratecenter或ratecenter>ratevm1。

3.3 跨度情况3下的分界点获取

(4)

在比例Lsumratevmk与左侧物理机资源配置比例ratepmleft最为接近或完全相同时，遍历停止，并记录下当前vmk的编号k，也就是左侧虚拟机需求的分界点POINTleft。

从右侧开始对sortedListvm进行倒序遍历，以最右侧虚拟机作为起点vm1，计算：

(5)

使用与左侧类似方法得到右侧分界点POINTright。

3.4 跨度情况3下的划分点判断

当取得两侧分界点后，又面临两种可能：分界点相交或不相交。

(6)

在不相交的情况下，两侧都能达到各自最佳匹配位置。对于不相交的序列部分overlapList={vma,…,vmb}，则要判断它与center的比例ratecenter的关系，如图2所示。

图2 划分点判定情况分类Fig. 2 Classification of divide point determination situation

①当ratevmb≤ratecenter，即overlapList位于center左侧时，则划分点Divide应定为右侧分界点POINTright；

②当ratevma≥ratecenter，即位于center右侧时，划分点Divide应定为左侧分界点POINTleft；

③当ratevma≤ratecenter≤ratevmb时，则应以center的位置作为划分点Divide。

3.5 跨度情况4下的分界与划分

跨度情况4下，只需判断出对应侧虚拟机序列分界点即可完成划分处理。还是以左侧为例：获得的分界点POINTleft位于center左侧时，使用center作为Divide；当分界点POINTleft位于center右侧时，以此POINTleft作为Divide。

3.6 对划分后的序列进行放置

判定划分点Divide后，sortedListvm被分为两个子集合。两个子集合的资源需求的大小对应了pairpm中相应配置物理机数量对比。使用同构情况下的启发式算法对Divide左侧的虚拟机需求子集合在pmleft上进行放置， Divide右侧虚拟机需求子集合在pmright上进行放置。至此得到具体的虚拟机需求放置结果，得出具体需要的两种活动物理机数量。

4 仿真实验及分析

对本文提出的RDDFPA性能进行评估实验，并与不经划分直接在同构环境下进行放置的常规方法进行对比。统一使用First Fit算法作为双方使用的启发式算法。将每10 000个虚拟机需求作为一组数据，随机取20组进行实验。假设虚拟机的CPU需求以及MEM需求都在0～8内随机取值，虚拟机资源需求分布跨度中点在CPU和MEM资源比例为1∶1的位置。通过调整资源配置构成不同异构物理机组，来模拟sortedListvm和pairpm的不同搭配情况。假设5组异构物理机组，左侧物理机称为A，右侧物理机称为B，并逐渐增大每一组资源配置比例之间的差异。5组配置如下：

组合一：

A:CPUleft=8 MIPS,MEMleft=10 GB,rateleft=4∶5

B:CPUright=10 MIPS,MEMright=8 GB,rateright=5∶4

组合二：

A:CPUleft=8 MIPS，MEMleft=12 GB，rateleft=2∶3

B:CPUright=12 MIPS，MEMright=8 GB，rateright=3∶2

组合三：

A:CPUleft=8 MIPS，MEMleft=16 GB，rateleft=1∶2

B:CPUright=16 MIPS，MEMright=8 GB，rateright=2∶1

组合四：

A:CPUleft=8 MIPS，MEMleft=32 GB，rateleft=1∶4

B:CPUright=32 MIPS，MEMright=8 GB，rateright=4∶1

组合五：

A:CPUleft=8 MIPS，MEMleft=40 GB，rateleft=1∶5

B:CPUright=40 MIPS，MEMright=8 GB，rateright=5∶1

其中：CPUleft、MEMleft、rateleft分别代表左侧A的CPU资源、内存资源以及配置比例。右侧B相关符号意义与A近似。

使用本文提出的RDDFPA进行放置，所需要的两种异构物理机的台数之和，与直接在某一种物理机上进行放置所需要的同构物理机台数对比如图3所示。

图3 物理机放置结果比较Fig. 3 Comparison of physical machine placement results

根据图3中的数据，对随机数据集中20组数据的结果取平均值，得出不同异构物理机组合与单一配置物理机A、B相比节约的物理机台数与百分比，来展示实际算法应用的效果，如表1所示。

从组合一到组合三，异构物理机组的CPU和内存资源配比从8∶10和10∶8一直扩大到8∶16和16∶8。随着异构物理机组差距增大，优化效果也从对比仅使用A时节约大概121台，比例约为2%，以及对比仅使用B时节约大概209台，比例约为3%，逐渐提升到对比左右侧均能节约大概900台，节约比例均约为17%。但是从组合四和组合五中也可以看出，在扩大两侧物理机资源配比差异时，优化效果并非随之线性扩大，而是逐渐趋于平稳，应将配置差异限定在一定范围内。

由以上对比实验可以看出，本文提出的RDDFPA，在异构物理机的资源配置具有一定差异时，相比单一配置物理机较为显著地减少了活动物理机数量，同时节约了能耗。

表1 不同组合相对单一配置的实验结果Tab. 1 Experimental results of different combinations relative to single configurations

5 结语

针对异构云环境下的虚拟机放置问题，本文提出一种利用变化的虚拟机资源需求分布特征与异构物理机配置的比例关系，对虚拟机需求进行划分,使得虚拟机子集合的变化反映为对应异构物理机数量变化，再对其放置的方法。实验结果表明，所提的算法能够在异构物理机配置差异较大且虚拟机资源分布和物理机资源配比相互较为契合的前提下，有效减少活动物理机的总数量，达到较好的优化效果。未来可以进一步研究在虚拟机分布的跨度和物理机配置偏离时如何避免算法退化的问题。

References)

[1] 谷立静,周伏秋,孟辉.我国数据中心能耗及能效水平研究[J].中国能源,2010,32(11):42-45.(GU L J, ZHOU F Q, MENG H. Research on energy consumption and energy efficiency of data center in our country [J]. Energy of China, 2010, 32(11): 42-45.)

[2] 佚名.国家绿色数据中心试点工作方案[J].石油和化工节能,2015(3):1-4.(ANONYMITY. National green data center pilot program [J]. Petroleum & Chemical Energy Conservation, 2015(3): 1-4.)

[3] 叶可江,吴朝晖,姜晓红,等.虚拟化云计算平台的能耗管理[J].计算机学报,2012,35(6):1262-1285.(YE K J, WU C H, JIANG X H, et al. Power management of virtualized cloud computing platform [J]. Chinese Journal of Computers, 2012, 35(6): 1262-1285.)

[4] 周东清,佀庆乾.异构云平台中能源有效的虚拟机部署研究[J].计算机科学,2015,42(3):81-84.(ZHOU D Q, SI Q Q. Energy-efficient virtual machine placement for heterogeneous cloud platform [J]. Computer Science, 2015, 42(3): 81-84.)

[5] AROCA J A, ANTA A F, MOSTEIRO M A, et al. Power-efficient assignment of virtual machines to physical machines [J]. Future Generation Computer Systems, 2016, 54(C): 82-94.

[6] 童俊杰,赫罡,符刚.虚拟机放置问题的研究综述[J].计算机科学,2016,43(6A):249-254.(TONG J J, HE G, FU G. Research survey of virtual machine placement problem [J]. Computer Science, 2016, 43(6A): 249-254.)

[7] PIRES F L, BARN B. A virtual machine placement taxonomy [C]// Proceedings of the 2015 15th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing. Piscataway, NJ: IEEE, 2015: 159-168.

[8] LEE Y C, ZOMAYA A Y. Energy efficient utilization of resources in cloud computing systems [J]. Journal of Supercomputing, 2012, 60(2): 268-280.

[9] GAO Y Q, GUAN H B, QI Z W, et al. A multi-objective ant colony system algorithm for virtual machine placement in cloud computing [J]. Journal of Computer & System Sciences, 2013, 79(8): 1230-1242.

[10] ZHENG Q H, LI R, LI X Q, et al. A multi-objective biogeography-based optimization for virtual machine placement [C]// Proceedings of the 2015 15th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing. Piscataway, NJ: IEEE, 2015: 687-696.

[11] WU Y Q, TANG M L, FRASER W. A simulated annealing algorithm for energy efficient virtual machine placement [C]// Proceedings of the 2012 IEEE International Conference on Systems, Man, and Cybernetics. Piscataway, NJ: IEEE, 2012: 1245-1250.

[12] BELOGLAZOV A, ABAWAJY J, BUYYA R. Energy-aware resource allocation heuristics for efficient management of data centers for Cloud computing [J]. Future Generation Computer Systems, 2012, 28(5): 755-768.

[13] SHI J Y, DONG F, ZHANG J H, et al. Two-phase online virtual machine placement in heterogeneous cloud data center [C]// Proceedings of the 2015 IEEE International Conference on Systems, Man, and Cybernetics. Piscataway, NJ: IEEE, 2015: 1369-1374.

This work is partially supported by the Natural Science Foundation of Shaanxi Province (2017JQ6053), the Scientific Research Program Funded by Shaanxi Provincial Education Department (15JK1468), the Ph. D. Start-up Fund of Xi’an University of Science and Technology (2015QDJ031).

XUEHongye, born in 1960, Ph. D., professor. His research interests include network and high performance processing, image real-time processing.

ZHUTianlei, born in 1992, M. S. candidate. His research interests include distributed and parallel computing.

LUOXiangyu, born in 1984, Ph. D., lecturer. Her research interests include distributed and parallel computing, fault-tolerant theory.

FENGJian, born in 1973, Ph. D., associate professor. Her research interests include complex network, network security.

Virtualmachineplacementalgorithmforheterogeneouscloudenvironmentbasedonresourcedemanddistributionfeature

XUE Hongye, ZHU Tianlei, LUO Xiangyu*, FENG Jian

(CollegeofComputerScienceandTechnology,Xi’anUniversityofScienceandTechnology,Xi’anShaanxi710054,China)

Focusing on the problem of Virtual Machine Placement (VMP) in heterogeneous cloud environment, a Resource Demand Distribution Feature based Placement Algorithm (RDDFPA) for virtual machines was proposed. Firstly, a method of describing virtual machine requirements and physical machine configuration based on scale factor of CPU resource and memory resource was established. Based on the scale factor, all the virtual machines were sorted. Secondly, by analyzing the proportion relationship of virtual machine requirements and physical machine configuration in the CPU resources and memory resources, the proportion demarcation point was determined, and the partition of virtual machine set was completed. The requirement proportion of matched physical machines with different configurations was reflected by the size of each virtual machine subset.Finally, by using the heuristic algorithm such as the First Fit algorithm, the virtual machine subset was placed on the subset of physical machines with matched configuration. Theoretical analysis and simulation experimental results show that, compared with the total number of physical machines with any single configuration, the total number of physical machines required by the proposed algorithm is reduced by 2%-17%.The proposed RDDFPA can determine the number of physical machines with various configurations according to the distribution of virtual machine resource requirements, and efficiently complete the placement of virtual machines, which can improve the resource utilization rate and reduce the system energy consumption.

cloud computing; data center; Virtual Machine Placement (VMP); heterogeneous cloud environment; energy efficiency

2017- 06- 22;

2017- 08- 23。

陕西省自然科学基础研究计划项目(2017JQ6053);陕西省教育厅专项科学研究计划项目(15JK1468);西安科技大学博士启动基金资助项目 (2015QDJ031)。

薛弘晔(1960—)，男，陕西扶风人，教授，博士，CCF会员，主要研究方向：网络与高性能处理、图像实时处理； 朱天磊(1992—)，男，河南商丘人，硕士研究生，主要研究方向：分布式与并行计算； 罗香玉(1984—)，女，河北宁晋人，讲师，博士，CCF会员，主要研究方向：分布式与并行计算、容错理论； 冯健(1973—)，女，陕西西安人，副教授，博士，CCF会员，主要研究方向：复杂网络、网络安全。

1001- 9081(2017)12- 3386- 05

10.11772/j.issn.1001- 9081.2017.12.3386

(*通信作者电子邮箱luoxiangyu@xust.edu.cn)

TP301.6

A