面向低能耗的虚拟机部署和迁移策略

摘 要： 为提高数据中心的资源利用率并降低能耗，提出了面向低能耗的虚拟机部署和迁移策略，包括虚拟机初始部署算法BT-MPA和虚拟机动态迁移算法MMT-MMA。BT-MPA算法基于回溯法实现虚拟机集合和主机集合的最优初始映射，MMT-MMA算法基于最小迁移时间策略实现虚拟机动态迁移。仿真验证了所提出策略能够在降低数据中心总能耗的同时避免了不必要的迁移开销。

0 引言

随着云计算的快速发展，数据中心能源成本不断上涨[1]。在2011年，我国数据中心总耗电量已经占到全 会用电量的1.5%[2]。高能耗的主要原因在于设备数量增加和资源使用率低[3]。

目前数据中心常用的节能技术有：动态电压频率调整（Dynamic Voltage and Frequency Scaling，DVFS）和虚拟化技术[4]。其中虚拟化技术能够将一个服务器虚拟成多个服务器，提高资源的利用率，降低成本[5]。

目前有许多关于虚拟机部署和迁移算法的研究。参考文献[4]提出了一种面向系统能耗优化的虚拟机部署算法，该算法能够有效降低能耗，但最终部署结果不是最优结果。参考文献[6]为了降低能耗给出了一种节能算法，并提到迁移时间的概念，但在迁移虚拟机时没有考虑迁移时间。参考文献[7]提出一种虚拟机放置方案，该方案能够优化能源效率，但没有涉及迁移问题。

1 虚拟机动态部署

1.1 虚拟机部署问题

可将虚拟机部署问题描述为：数据中心有n台主机和m台等待部署的虚拟机，每台主机和虚拟机均配置k种资源，目标是完成部署后总能耗最小，其中虚拟机的资源总和不能超越主机的资源上限，虚拟机最多只能被部署到一个主机上。

以上描述等价为：D=（H1，…，Hn），Hi=（hri1，…，hrik），V=（vm1，…，vmm），vmj=（vrjl，…，vrjk），其中1≤i≤n，1≤j≤m。

其中，h（j）是虚拟机j被分配到的主机，vrjl是虚拟机j的第l种资源量，hril是主机i的第l种资源量，powi是主机i的能耗。对于集成DVFS技术的主机，开启时可根据参考文献[8]提出的能耗模型计算powi：

powi=pmin+（pmax-pmin）×ui（2）

其中，ui是主机i的CPU利用率，pmin是空闲状态下的能耗，pmax是ui最大时的能耗。

1.2 基于回溯法的虚拟机动态部署算法

BT-MPA的步骤是：首先将主机按照开启关闭状态排序，相同状态的主机按照可用资源大小降序排列；接着依次选择主机，用回溯法从虚拟机集合中选出最优子集部署到主机中；然后从集合中移除已被部署的虚拟机，继续以上步骤直至虚拟机集合为空。

2 虚拟机动态迁移

虚拟机迁移问题可分为两个子问题：何时触发迁移和选择哪些虚拟机迁移。

2.1 触发迁移

2.2 选择虚拟机

过载主机中虚拟机的选择有随机和最小迁移时间（Minimum Migration Time，MMT）两种策略。MMT策略是选择迁移时间最小的虚拟机集合迁出，它等价于选择一组总迁移时间最大的虚拟机集合留在主机上：

其中，uj（cpu）是虚拟机j使用的CPU和主机总CPU的比值[7]，mtj是迁移时间，用虚拟机内存与所在主机空闲带宽的比值衡量[3]。式（3）具有最优子结构性质，能够使用贪心和动态规划算法来解决。

2.2.1 贪心选择策略

使用贪心算法解决MMT问题的步骤是：首先将虚拟机按照迁移时间与MIPS的比值非降序排列，然后依次选择虚拟机加入迁出队列，直至主机的CPU利用率不大于Tup。该算法的时间复杂度为O（nlogn）[9]。

2.2.2 动态规划选择策略

动态规划将问题分解成若干子问题，通过结合子问题的解得到最终解[9]。假设F（j，ri）是子问题的最优解，则可以建立如下递归关系：

F（j，ri）=max{F（j-1，ri），F（j-1，ri-mj）+mtj}，ri≥mjF（j-1，ri）， ri<mj（4）

其中，F（j，ri）指的是当主机CPU值为ri，虚拟机集合为1，…，j时的最大迁移时间，mj是虚拟机j的CPU资源值。

该策略能得到式（3）的最优解，最优解对应的虚拟机就是留在主机上的最优集合。该算法的时间复杂度是O（2n）[9]。

2.3 虚拟机迁移算法

3 仿真实验和分析

3.1 实验环境

首先在仿真系统中建立1个数据中心和20台主机，主机的资源根据表1随机配置。

系统中需部署的虚拟机数量范围是[10，80]，增加步长为10，虚拟机的资源根据表2随机配置。

虚拟机上运行的应用负载按照占用虚拟机资源的比例可分为轻、中、重三型，不同型 虚拟机上运行负载的概率空间相同，如表3所示。

3.2 实验结果

图2是使用不同的虚拟机选择策略进行动态迁移的结果。从图可看出，基于MMT选择策略的迁移时间远远低于RC策略，贪心选择策略的迁移时间相对于RC策略平均减少48%，动态规划选择策略相对于RC策略平均降低57%，动态规划相对于贪心选择策略平均降低18%。这也与理论相符合，动态规划较贪心选择策略结果更优，但时间复杂度更大，因此数据中心可综合考虑迁移时间和计算时间来选择具体策略。

4 结论

参考文献

[1] SCHULZ G. 绿色虚拟数据中心[M].韩毅刚，李亚娜，王欢，译.北京：人民邮电出版 ，2010.

[2] 王肇国，易涵，张为华.基于机器学习特性的数据中心能耗优化方法[J].软件学 ，2014，25（7）：1432-1447.

[3] BELOGLAZOV A， BUYYA R. Optimal online deterministic algorithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in cloud data centers[J]. Concurrency and Computat-ion： Practice and Experience， 2012（24）：1397-1420.

[4] 王加昌，曾辉，何腾蛟，等.面向数据中的虚拟机部署及优化算法[J].计算机应用，2013，33（10）：2772-2777.

[5] 高林，宋相倩，王洁萍.云计算及其关键技术研究[J].微型机与应用，2011，30（10）：5-7.

[6] 周舟，胡志刚.云环境下面向能耗降低的虚拟机部署算法[J].华南理工大学学 ，2014，42（5）：109-114.

[7] 董健康，王洪波.IaaS环境下改进能源效率和 络性能的虚拟机放置方法[J].通信学 ，2014，35（1）：72-81.

[8] 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）：755-768.

[9] 王晓东.计算机算法设计与分析[M].北京：电子工业出版 ，2012.