云环境下基于CROTS算法的虚拟机放置策略

秦启飞　王世振　袁翔　胡志刚

摘 要：随着越来越多数据中心的构建和部署，能耗问题成为研究热点。作为一种有效的节能策略，虚拟机整合受到了研究人员和业界的关注。针对传统的虚拟机放置策略的不足，利用化学反应优化算法CRO求解数据中心的虚拟机放置问题，并通过禁忌搜索算法提高CRO算法中器壁无损碰撞对解的勘探能力。仿真实验表明，相对于传统的贪婪放置策略FFD和基于ACO的放置策略，提出的CROTS算法可有效降低数据中心物理机的使用个数，进而降低了数据中心的能耗。

关键词：云计算； 数据中心； 虚拟机放置； 能耗； 化学反应优化

中图分类号：TP391 文献标识码：A

Abstract：More and more data centers are created，and energy consumption becomes the research hotspot. As a kind of effective energy saving strategy， VM consolidation is focused by researcher and industry. Due to the shortage of the traditional VM consolidation，this paper used a new metaheuristic algorithm called CRO（Chemical Reactive Optimization）to solve the VM consolidation problem in data centers and used Local Search to improve the ability of seeking the solutions. Experimental results show that this method is more excellent than other methods， which can decrease the number of servers and can reduce the energy consumption of data centers.

Key words：cloud computing； data center； VM placement； energy； CROTS

1 引 言

云计算是一种新兴的计算模式，然而，在云计算技术促进IT发展并带来巨大经济效益的同时，也消耗了大量的电能。近期分析报告显示[1]：截至2011年，世界范围内的计算中心的年均耗电量已经超过3 兆kW，且其增长呈明显的加速趋势。因此，有效控制数据中心的能耗量已经成为各国科研和应用领域的一个亟待解决的问题。在数据中心，随着虚拟机的不断创建与撤销，分布在物理资源上的虚拟机必将分散，从而导致部分服务器的使用率非常低。如何合理地确定虚拟机到服务器的映射对整体物理资源池的利用率以及能耗有着直接影响，已经成为云计算领域的研究热点。

大多研究主要将虚拟机放置问题建模为装箱问题并采用贪婪算法去寻找一个近似最优的方案，常用的贪婪算法主要有：首次适配FFD，最优适配BFD和最差适配WFD（WorstFit Decreasing）三种。例如，IBM的Verma等[2]设计的pMapper采用FFD选择虚拟机的放置位置。文献[3]提出了一种虚拟机迁移框架EnaCloud，采用最优适配BFD的启发式算法确定虚拟机的放置。文献[4]提出了一种改进BFD（BestFit Decreasing）算法并应用到虚拟机放置问题中，通过模拟实验验证了其性能。文献[5，6]在一个同构的计算环境中将虚拟机放置建模为1维装箱问题，只考虑CPU资源，所提出的虚拟机迁移算法没有考虑当前的虚拟机分配情况。类似地，文献[7]和文献[8]也将虚拟机放置问题简化为一维分配问题，仅考虑了CPU和内存资源。除此之外，一些研究将VM放置问题建模为多维装箱问题，即MDBP问题。如文献[9]将异构计算环境下的虚拟机分配问题建模为MDBP，然后通过实验比较了多个贪婪算法的性能。在文献[10]中，李强等人则将能耗感知的虚拟机放置问题归结为多维QoS约束下的最优规划问题，并设计了一个基于遗传算法的求解策略。近期，Albert等人[11]提出了一种新的元启发式方法，称之为化学反应优化算法。该算法模拟化学反应中的分子碰撞，以及分子从高能状态向低能状态不断转变的过程，最终驱使分子进入最稳定的状态。CRO相对于以往的智能算法表现出了更强的问题求解能力。鉴于CRO算法求解的高效性，本文将禁忌搜索算法与之相结合以提高CRO局部搜索的能力，并应用到虚拟机放置问题的求解中，取得了较好的效果。

2 问题描述

虚拟机配置是数据中心的核心功能之一，其配置过程如图1所示。首先，根据来自用户应用的大量虚拟机配置请求，数据中心内的虚拟机配置规划器根据监控服务器或者通过负载预测获得的服务器负载信息，确定服务器是否过载。然后采用智能算法获得虚拟机配置的全局最优解（本文基于CRO和禁忌算法）。最后，数据中心的迁移规划器根据虚拟机的配置方案确定相应的迁移规划。其中，虚拟机实时迁移（Live Migration）是一种有效的迁移机制，已经在一些服务器中得到了应用。

示例图2表示ID为3和4的虚拟机放在1号物理机上，ID为2和7的虚拟机放在2号物理机上，ID为1、3和6的虚拟机放在3号物理机上。

3.2 基本化学反应操作的设计

CRO有4种分子反应，即无损器壁碰撞、无损分子间碰撞、分解和合成。

1）无损器壁碰撞

在这个反应中，一个分子将撞击容器并导致分子结构发生局部改变。通过这个反应，原始的解w′将从它的邻域w1中得到一个新的结构w，相当于局部搜索。为了提高分子加快算法的收敛速度，本文使用禁忌搜索算法实现无损器壁碰撞，具体步骤如下。

（1）给定算法参数，每一次迭代都把当前分子w′作为禁忌算法的当前解，置禁忌表为空，藐视准则定义为：当前解的物理机使用个数少于best so far，则忽视禁忌表属性，用当前解代替best so far。；

（2）判断算法终止条件是否满足？若是，则结束算法并输出优化结果；否则，继续以下步骤；

（3）利用当前解的邻域函数产生其所有（或若干）邻域解，并从中确定若干候选解；

（4）判断候选解是否满足藐视准则？若满足，则用满足藐视准则的最佳状态y替代x成为新的当前解，即x=y，并用与y对应的禁忌对象替换最早进入禁忌表的禁忌对象，同时用y替换“best so far”状态，然后转步骤6；否则，继续以下步骤；

（5）判断候选解对应的各对象的禁忌属性，选择候选解集中非禁忌对象对应的最佳状态为新的当前解，同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素；

（6）转步骤（2）。

2）分解反应

发生分解反应时，一个分子w将变成两个新的分子w1和w2。这两个新分子的结构与原来的分子结构有很大的差异。本文算法中，用Order Crossover（OX）算子实现分解。

在OX算子中，第一个母体是原来的分子w，第二个母体是随机创建的一个解。w1由w的前半部分和随机解的后半部分组合得到。而w2由w的后半部分和随机解的前半部分组合得到。

3）无损分子碰撞反应

无损分子碰撞是两个分子碰撞后发生微小的变化又分开。这个反应有点类似无损器壁碰撞，但是不同的是这个反应涉及到两个分子，并且没有分子动能（KE）丢失到中央能量缓冲区。我们用OX算子实现这个反应。

4）合成反应

3.3 算法描述

在算法开始之初，需要初始化如下参数：PopSize， KELossRate， MoleColl， buffer， InitialKE，α，β。其中PopSize表示种群大小，KELossRate表示动能丢失率，MoleColl取值为[0，1]，是每次迭代时判断单分子碰撞和多分子碰撞的参数。α，β分别代表单分子碰撞和多分子碰撞选择的极限值。当一个分子的撞击次数超过α后，它的优越性还没提升则会发生分解反应。β代表一个分子所拥有的最小的动能，如果低于这个值则会发生合成反应。目标函数值就等价于分子的势能值，要找最小的函数值就得找到最稳定的势能最小的分子。

迭代开始之后，会随机产生一个[0，1]之间的整数K，当K大于MoleColl时则发生单分子碰撞，反之则发生多分子碰撞。迭代过程会一直继续直到达到停止标准，最终输出一个近似最优解。

4 实验与分析

4.1 实验环境设置

在Myeclipse中采用面向对象的java语言实现CROTS算法，并将该算法与CRO、ACO和FFD等算法进行性能上的比较，同时也分析了算法在不同的虚拟机请求规模时的性能。模拟的集群系统包含600个物理服务器（设置了600个物理服务器是为了考虑最差的放置情况，一台虚拟机占用一台物理服务器），每个服务器包含CPU，内存，存储和带宽四种资源，为了更方便的考察该算法性能，在本次实验中只考虑物理结点一个因素，假设QOS、SLA等其他因素都满足条件，本次实验适用在同构环境，600台物理服务器的性能是一样的，分别是10000MIPS、50GB内存、1TB存储、10G的带宽。实验模拟的虚拟机数目在{100， 200， 300， 400， 500，，600}内取值。类似于Amazon EC2的虚拟机实例，实验设置了四种虚拟机类型，其资源请求数目分别为：（1000， 4， 20，1）， （2000， 8， 50， 2）， （3000， 16， 100， 2）， （5000， 24， 200，4）。基于文献[ 11]对实际服务器（Dell PowerEdge1950）功耗的测量，实验设定服务器在空闲pidle和满负载pmax 时的功耗大小分别为171瓦特和218瓦特。为了对比不同算法的能耗大小，实验设定计算周期T为24小时。

4.2 实验结果与分析

实验中，为了考虑到公平性，对所有算法的虚拟机请求序列设置为一样，对虚拟机数目分别为100、200、300、400、500、600时进行10次运算最终取平均值。本文中算法的优化目标是使物理机数最少和降低能耗，根据公式（6）中的能耗模型，物理机数和它的资源利用率对能耗有直接影响，通过实验证明了真实性。

图3显示不同虚拟机数目情况下4种放置算法得到的能耗比较情况。随着虚拟机数目的增多，四种算法得到的能耗也逐渐增大。与FFD和ACO算法相比，CRO算法在能耗指标上平均降低了13.5%和9.9%。而与CRO算法相比，CROTS算法在能耗指标上平均降低了3.1%。这主要因为物理服务器的使用数目与数据中心的能耗有直接的关系，CRO和CROTS算法相对于FFD和ACO算法来说，能够获得更优的放置解。

图4比较了不同虚拟机配置数目情况下四种算法得到的物理服务器的数目比较。随着虚拟机数目的增多，四种算法的物理服务器的数目也在增大。其中，FFD算法的性能最差，其所需要的平均物理服务器数目分别是ACO、CRO、CROTS算法的1.04、1.09、1.13倍。表明算法CROTS相对于其他三种算法，具有最好的求解能力。而且从图4中可以看出当虚拟机规模越大，CROTS算法的性能越好，这是因为CROTS适合求解大规模优化问题。

为了进一步说明CROTS算法的求解效率，实验对ACO、CRO以及CROTS三种算法的收敛性情况进行了实验比较。

从图5可以看出CROTS混合算法的收敛速度要比ACO和CRO快，因为在CRO算法无损器壁碰撞反应中加入禁忌搜索，使得解的收敛速度更快，在60000次评估左右就基本上达到稳定。表明CROTS在寻找最优解方面具有明显优势。

5 总 结

随着数据中心基础设施规模的增大，能耗问题越来越突出。虚拟机整合能够有效的降低能耗，本文提出基于CROTS的虚拟机放置策略。通过CRO与禁忌搜索算法相结合，进一步提高了CRO算法的性能。实验结果与传统的贪婪算法和ACO相比，所提出的混合算法能够有效的减少物理结点的使 用数量，从而达到节约能耗的目的。下一步的工作将考虑多目标同时优化以及CROTS算法在解决虚拟机放置问题上的各个参数的最优设置。参考文献

[1] RICCIARDI S，CAREGLIO D，BOADA G S， et al. Saving energy in data center infrastructures [C]. Proceedings of the First International Conference on Data Compression， Communications and Processing， 2011：265-270.

[2] VERMA A，AHUJA P，NEOGI A. pmapper： power and migration cost aware application placement in virtualized systems[C]. In proceedings of 9th ACM/IFIP/USENIX international conference on middleware， 2008，243-264.

[3] Bo Li， Jianxin Li， Jinpeng Huai， et al. Enacloud： An energysaving application live placement approach for cloud computing environments[C]. In proceedings of international conference on Cloud computing， 2009.

[4] BELOGLAZOV A，BUYYA R.Adaptive thresholdbased approach for energyefcient consolidation of virtual machines in cloud data centers[C]. In proceedings of the 8th workshop on Middleware for Grids， Clouds and e-Science. 2010， 41-46.

[5] BORGETTO D，COSTA G D，PIERSON J M，et al. Energyaware resource allocation[C]. In Proceedings of the 10th IEEE/ACM International Conf on Grid Computing. 2009， 183-188.

[6] SUBRAMANIAN C，VASAN A，SIVASUBRAMANIAM A.Reducing data center power with server consolidation： Approximation and evaluation[C]. In Proceedings of the 17th IEEE Conf on High Performance Computing， 2010， 1-10.

[7] KHAN S U，ARDIL C.Energy efficient resource allocation in distributed computing systems[C]. In proceedings of International Conference on Distributed， High Performance and Grid Computing， 2009， 667-673.

[8] KHARGHARIA B，HARIRI S，SZIDAROVSZKY F，et al. Autonomic power & performance management for largescale data centers[C]. In proceedings of the 21th IEEE Conf on High Performance Computing， 2007， 1-8.

[9] STILLWELL M，SCHANZENBACH D，VIVIEN F，CASANOVA H.Resource allocation algorithms for virtualized service hosting platforms[J].Journal of Parallel and Distributed Computing， vol.70， no.9， pp. 962-974， 2010.

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

[11]FELLER E，RILLING L，MORIN C.EnergyAware Ant Colony Based Workload Placement in Clouds[C]. In proceedings of the 12th IEEE/ACM International Conferece on Grid Computing， 2011， 26-33.