云计算环境下资源评级的虚拟机部署算法

刘　秀，李　烨

(上海理工大学 光电信息与计算机工程学院，上海200093)



云计算环境下资源评级的虚拟机部署算法

刘秀，李烨

(上海理工大学 光电信息与计算机工程学院，上海200093)

摘要针对虚拟机(VM)大范围集群部署时容易引发数据中心(DC)总体负载不均衡、VM部署拒绝率居高不下等问题。提出一种基于资源评级的VM部署算法，根据构建VNF的VM之间的亲和关系、物理机之间的拓扑关系及链路的带宽，选择出最适合部署VNF的一台或多台物理机(PM)。仿真结果表明，在资源相同的情况下，该算法较已有算法具有更高的资源均衡度和更低的部署拒绝率。

关键词云计算；虚拟机部署；负载均衡；拒绝率；资源评级

虚拟机技术[1-2](VirtualMachine，VM)的出现提高了云计算平台的资源利用率。但随着云端VM数目的增多，减少VM部署时的性能开销、缩短用户等待时间、利用有限的资源部署更多的VM等问题，成为虚拟机快速部署时面临的新挑战。

针对上述问题，运营商和学者提出了多种部署算法。大多数算法选择将VM部署在性能最优的物理机(PhysicalMachine，PM)上，由于不同用户对负载指标要求的差异[3]，采用不同的优化目标，比如减短用户响应时间、降低部署资源开销等。文献[4]提出的iVDA算法根据底层物理资源容量和动态负载的映射关系来选择宿主机，减少VM部署过程中模板镜像复制时间，对多VM快速部署效用不明显。文献[5]采用改进的遗传算法使PM物理资源利用达到最大化，但未考虑用户请求部署的VM之间的约束关系，不利于VM集群的部署。文献[6]提出扩展降序最佳适应算法，利用初始长度概念，将宿主机和VM资源量化，在减少宿主机的数量上优势明显，但会引起宿主PM资源使用不均衡。文献[7]提出PM-LB算法根据承载业务对资源依赖程度不同设定资源权重向量，计算待部署VM与PM性能向量的相对距离，选择最近的PM作为宿主机。算法具有较强的业务灵活性，但没有考虑VM之间的业务关联性，不利于NFV的构建。

本文提出一种基于云资源评级的VM部署算法RRPA，根据构建VNF的VM的亲和关系、PM拓扑关系选择出最适合部署VNF的若干台PM。算法旨在提升VM集群部署成功率以及DC资源均衡度。

1云平台部署模型

云平台将地理位置分散的、异构的PM资源集中起来[8]，根据功能不同可分为不同种类的云。本文采用的VM部署模型是计算云平台上一种常见的金字塔结构，如图1所示。计算云由若干数据中心(DataCenter，DC)和电信云编排器(CarrierCloudOrchestrator，CCO)组成。CCO作为调度中心，主要用于数据处理和存储，一般由多个DC共享。DC是一个逻辑概念，是由PM组成的计算机系统和PM之间的通信系统。每个DC包含一个或多个虚拟机管理器(VMManager，VMM)。

图1　云平台部署模型

CCO存有调度范围内所有DC的拓扑关系，包括DC外联路由器个数、链路带宽等参数，并保存DC内所有PM的4种主要资源：CPU、内存、磁盘空间及网卡带宽。除此之外，CCO中也保存有VM规格参数表。VM规格参数由VM所需资源种类和大小组成。按照资源规格占用比例不同将VM分类，如存储VM磁盘容量大，用于转发信令的VM所需CPU个数相对较多等。

VMM是PM上的应用程序，当收到CCO下发的策略指令后，VM的创建、删除、迁移以及资源的分配或释放都由VMM来决策。CCO是系统的大脑，VMM是系统的中心枢纽，PM节点整个系统的基础，不仅为VM创建提供软件技术支持和底层硬件资源支持，也是VM启动和运行的载体[9-11]。

2基于资源评级的虚拟机部署算法

在分布式系统[12]中，选择放置VM的宿主PM，不仅要考虑宿主PM资源是否充足，还有对部署位置、资源依赖程度等的要求。RRPA算法根据各VM的亲和关系将其分成若干簇，并根据各种资源对VM上承载业务的依赖性计算出PM和DC的资源评级值，评级值越高可用资源越多，资源使用越均衡。

2.1基于亲和关系的VM聚簇

设用户请求构建一个VNF，用一组VM表示，记为(vm1,vm2,…,vmi)。VM之间的约束关系是一种业务属性，随着VNF的功能不同而变化。用(x1,x2,…,xi)表示VM组中某个VM与其他VM之间的亲和关系，其中xi∈{-1,0,1}。xi=-1表示VMi与该VM属性相斥，不能部署在同一PM上；xi=1表示VMi与该VM属性相合，属性相合的VM之间具有较高的通信流量，部署在同一PM上可以提高VM的工作效率；xi=0表示VMi与VM亲和关系不确定。例如对于一个VM组{vm1,vm2,vm3,vm4,vm5}，其中vm1与vm2互斥，vm3与vm5属性相合，vm4与vm5属性相合，考虑资源均衡以及VM属性，可以将VM组分为三簇：{vm1}；{vm2}；{vm3,vm4,vm5}。

2.2DC评级

DC评级采用DC绝对剩余资源可用度与相对剩余资源可用度共同描述，定义如下

DCR=DCRabsolute+DCRrelative

(1)

(2)

(3)

(4)

(5)

(2)相对剩余资源可用度量化定义为

DCRrekuive=(1-UsagePM)×Ravg/Rdev

(6)

其中，

UsagePM=Numuse/NumDC

(7)

(8)

(9)

相对剩余资源可用度取决于待部署的VNF对资源的需求，UsagePM为将VM组按照约束关系聚簇后，所需最少的PM数占DC内PM数的比例；Utilizationj为DC内PM总资源减去VNF所需资源后的剩余可用资源；Ravg是资源平均值，nres是算法中评估的资源种类；ndev是所有资源可用度绝对偏差。DCR的大小反应了DC的资源剩余和NFV对DC资源均衡利用的影响。DC内剩余资源越多，资源利用越平均，DCR越大。

2.3PM资源均衡度评级

VM聚簇部署时，选择宿主PM时除了考虑资源是否充足之外的另一个重要因素是资源使用是否均衡，定义PM资源均衡度评级量化公式(PMResourceLevelingRating，PRLR)如下

(10)

2.4宿主PM的选择

CCO将用户请求的VM组按照聚簇规则重组为若干VM簇，并计算出调度范围内的所有DC的DCR和每个DC内PM的PRLR。部署VM簇时，选择DCR高的DC和DC内PRLR值低的PM进行部署，更PM的剩余资源Utilization。若选择的DC内所有PM资源都不足以提供该VM簇部署所需资源，将VM簇拆分成单个VM，并尽可能的将同一用户请求的VM部署在同一是相邻的PM上，以减少通信链路跳数、缩短用户响应时间、降低功率消耗。

3仿真分析

采用离散事件机理的云仿真平台，该平台提供图形化的界面配置，利用网络建模的方式来提高客户仿真构建、运行与分析效率。

3.1算法性能指标

定义VM部署拒绝率和DC资源均衡度两个指标衡量算法性能。

(1)VM部署拒绝率

Rrej=1-∑vmsuccess/∑vmrequest

(11)

其中，vmsuccess为部署成功的VM个数，vmrequest为待部署VM个数。Rrej越小，VM部署成功率越高。

(2)资源不均衡度。由于频繁申请或释放资源，会造成资源碎片，导致虽然总的空闲资源满足要求，但无法申请到用户所需大小的资源。定义DC内平均资源利用率和资源利用标准差为

(12)

(13)

式中，n为DC内PM数目；Utilizationi为第i台PM的资源利用率。σ为资源不均衡度，其取值越大，资源利用越不均衡。

3.2不同算法性能对比

一个计算云由调度中心CCO和26台PM构成，PM之间通过路由器连接，VMM运行在其中一台PM上。PM资源规格及数目如表1所示，用户请求的虚拟机种类及数目比例如表2所示，VM之间两两亲和。在仿真场景上分别添加50,100,150,200和250个VM，输出各场景下VM部署的拒绝率以及DC资源均衡度。

表1　可用资源信息

表2　虚拟机模板种类

与GREED、POLLING以及ALUScore算法进行对比研究。GREED和POLLING是典型的装箱问题启发式算法，区别在于前者是First-Fit式，按照PM信息在调度中心保存的顺序开始部署，这样最大程度利用了排位靠前的PM的资源。POLLING算法依序询问每一个PM可用剩余资源，VM部署结束后询问下一个PM。ALUScore算法利用PM各类资源利用率K次方和计算出PM的资源可用度，根据资源可用度大小从高到低依次选择。RRPA算法不考虑资源依赖对资源均衡度及部署拒绝率的影响，资源权重向量取值WT=(1/3,1/3,1/3)T，实验结果如图2和图3所示。

图2　DC资源不均衡度比较

由图2可见，当部署VM数目较少、PM资源充足时，RRPA算法优势不明显，但随着部署VM数目增多，PM可用资源逐渐减少，DC内资源不均衡度显著低于其它3种算法。GREED算法的DC资源不均衡度最为严重，这是因为其First-Fit特性使得排位靠前的PM资源使用达到最大阈值。当部署VM的数目增加到一定数目时，资源不均衡度的变化会逐渐趋于平缓。POLLING算法按照PM排位依序选择部署的宿主机，当部署VM数目较少时，有良好的资源均衡度。但受VM之间拓扑约束与亲和约束的影响，均衡度随VM部署个数增多而逐渐降低。ALUScore算法完全根据PM剩余资源多少部署VM，当VM增多时，资源浪费明显，资源不均衡度急速上升。

图3　VM部署拒绝率比较

图3显示RRPA算法的部署拒绝率远低于其它算法。由于RRPA算法的聚簇部署特性，将属性相近的VM聚簇部署，减少了因属性相斥而引起的部署失败。同时，聚簇部署还可以减少部署空间搜索，提高网络宽带利用率。

3.3资源权重对算法性能的影响

验证VM资源依赖对DC内资源均衡度及VM部署拒绝率的影响，表2中VM请求各类型VM占有比例及资源需求，结合经验值取资源权重向量WT=(0.42,0.38,0.2)T，实验结果图4和图5所示。

图4　DC资源不均衡度比较

由图4可见，在部署资源充足的情况下，加权RRPA算法与不加权RRPA算法相比，DC内资源不均衡度低至少1%。随着部署资源的减少，不加权算法的资源不均衡度波动较大，而加权算法相对稳定。

图5　VM部署拒绝率比较

图5显示资源权重对VM部署成功率的影响。总体来说，加权后部署的资源均衡度更高，从而降低了VM部署拒绝率。

4结束语

针对如何提高VM部署成功率并均衡DC内资源的问题，提出一种基于资源评级的VM部署算法。利用VM约束关系聚类部署，压缩资源占用空间，减少资源消耗；利用资源对DC及PM评级排序，使DC内资源均衡使用，并提高部署成功率。仿真结果验证了算法的有效性，如果将RRPA静态算法与VM迁移的动态算法结合，将有可能大幅降低PM使用数目，对节省硬件和软件资源使用起到关键作用。

参考文献

[1]ZhiyunRen,XiaoSong.Avirtualmachinedeploymentapproachusingknowledgecurvesincloudsimulation[C].HongKong:IndustrialInformatics, 2012.

[2]UhligR,NeigerG,RodgersD,etal.IntelVirtualizationTechnology[J].Computer, 2005(38): 48-56.

[3]GuoYudong,WangXiaorui,WeiyuDong,etal.Acooperativemodelvirtual-machinemonitorbasedonmulti-coreplatform[C].Xi’an:FutureComputerandCommunication, 2010.

[4]HuangFeng,LiDongsheng.Efficientvirtualmachinedeploymentinlargescaleresourceenvironment[J].ParallelandDistributedSystems, 2012(72): 752-757.

[5]ZhongH,TaoK,ZhangXJ.Anapproachtooptimizedresourceschedulingalgorithmforopen-sourcecloudsystem[C].Beijing:TheFifthChinaGridAnnualConference,2010.

[6]冯少冲,邸彦强,朱元昌,等.IaaS云计算中虚拟机部署算法研究[J].华中科技大学学报：自然科学版, 2012，40(S1): 359-364.

[7]杨星,马自堂,孙磊. 云环境下基于性能向量的虚拟机部署算法[J].计算机应用, 2012(1):16-19.

[8]师雪霖,徐恪. 云虚拟机资源分配的效用最大化模型[J].计算机学报, 2013,36(2): 252-262.

[9]魏亮,黄韬,陈建亚,等.基于工作负载预测的虚拟机整合算法[J].电子与信息学报,2013,35(6):1271-1276.

[10] 张蓓蓓,陈宁江,胡丹丹. 基于BP神经网络负载预测的虚拟机部署策略[J].华中科技大学学报:自然科学版, 2012,40(S1):120-123.

[11]LaurikainenR,LaitinenJ,LenhtovuoriP,etal.Improvingtheefficiencyofdeployingvirtualmachinesinacloudenvironment[J].CloudandServiceComputer，2012(2): 232-239.

[12] 周舟,胡志刚.云环境下面向能耗降低的虚拟机部署算法[J].华南理工大学学报:自然科学版, 2014,42(5):109-114.

[13] 李强,郝沁汾,肖利民,等. 云计算中虚拟机放置的自适应管理与多目标优化[J]. 计算机学报,2011,34(12):2253-2264.

Algorithm for Virtual Machine Deployment in Cloud Computing Environment Based on Resource Rating

LIUXiu,LIYe

(SchoolofOptical-ElectricalandComputerEngineering,UniversityofShanghaiforScienceandTechnology,

Shanghai200093,China)

AbstractMany problems may occur during a large scale deployment of VMs, such as overall load imbalance in data center and high VM deployment rejection rate. This paper proposes a resources rating based placement algorithm (RRPA). By considering the affinity relationship between VMs, the topological relationship between PMs, and the connection link bandwidth, one or several PMs mostly appropriate for VNFs deployment are chosen. The simulation results show that RRPA has a higher degree of resource equilibrium and lower rejection rate of deployment than existing methods under the same condition.

Keywordscloud computing; VM deployment; load balance; rejection rate; resources rating

收稿日期:2015- 11- 18

基金项目:沪江基金资助项目(C14002)

作者简介:刘秀(1991-)，女，硕士研究生。研究方向：云计算。李烨(1974-)，男，博士，高级工程师。研究方向：信息融合等。

doi:10.16180/j.cnki.issn1007-7820.2016.07.015

中图分类号TP391

文献标识码A

文章编号1007-7820(2016)07-051-04