基于流量感知的虚拟机迁移调度算法

朱平哲

(三门峡职业技术学院 信息传媒学院，河南 三门峡 472000)

在动态环境中，随着时间的推移，总有新的虚拟机(virtual machine, VM)产生和消亡，不同VM的流量模式是动态的且随时间变化。假设每个VM都有一个固定的执行时间，即已知的先验时间，目标是通过减少迁移数量和最小化数据中心(data center, DC)间的流量来优化配置和进行迁移决策。因此，希望在保持系统性能稳定的基础上，尽可能地避免可能出现的链路拥塞问题。稳定性与执行的迁移次数成正比[1]，迁移次数越少越能提高系统的性能[2]。目前，学术界有关VM的研究很少涉及VM在配置和迁移决策中具有有限的租用期这一事实。文献[3]提出了一种将DC总能耗降至最低的方案，文献[4]提出了一种基于去激活的配置算法和一种周期性碎片整理算法，旨在最大限度地降低DC成本，文献[5]提出了两种VM调度算法来优化虚拟机到物理机的映射，目的是减少累计的开机时间以节省能源，文献[6]和文献[7]给出了VM再调度的正式定义。然而，从整体上看，针对单台物理机的阈值设置使数据中心整体负载过大，从而导致过多的VM找不到合适的物理机。基于静态阈值的设定，由于物理机负载引起的瞬时峰值容易发生频繁迁移导致了VM不必要的迁移，而通过预测模型获得的预测值与真实值之间存在一定的误差，可能会导致算法的性能差、系统能耗过高。此外，上述工作均没有涉及流量感知VM的布局问题。因此，本算法主要提出VM实时迁移调度问题的静态配置方案和启发式动态解决方案，研究VM生命周期对迁移决策和系统稳定性的影响。

1 问题描述

定义具有流量感知的虚拟机调度问题，涉及以下假设：

(1)时间被划分为等长的时隙t∈[0…T]。

(2)每个VMi都有一个开始时间si和一个终止时间ei。VM的生命周期εi是固定的，并被视为输入。需要注意的是，VM的生命周期εi定义为εi=ei-si。

(3)每个请求可能包括多个网络VM，但VM的请求均是独立的。

(4)假设VM的资源需求是静态的。

(5)考虑一系列可能的迁移。

(6)为不同VM的迁移分配了保留带宽。

(7)迁移可能需要若干个时隙。

1.1 静态配置方案

给出以下决策变量：

假设Oi表示VMi∈V产生的总流量，可得到Oi=∑j∈Vdij,∀i∈V。该公式的目标是最小化主干网流量，此流量包括通信流量和VM迁移生成的流量。这里的TS={∀t∈T:t≤ei且t≥si}。

(1)

需要满足以下条件：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

用式(12)替代约束条件(11)，可以得到

(13)

此外，还必须加上以下逻辑约束条件：

(14)

由于涉及大量的变量(O|N|4)，N表示问题的规模，式(14)显然需要消耗大量时间和计算资源。因此，本研究提出了一种启发式动态解决方案。

1.2 启发式动态方案

启发式动态算法的主要思想是通过考虑配置算法来减少迁移的次数，并在每个时隙的开始执行该算法，以便找到被视为迁移候选的VM，然后将当前的配置方案与配置算法提供的新方案进行比较。事实上，配置算法会产生大量的迁移，而过度迁移将会导致云系统的性能大幅下降[8-9]。对于每个时隙，启发式动态算法选择到达的VM并删除离开的VM，然后解决配置算法，可使用文献[10]中提出的配置算法，该算法已被证明可以高效地在最小化主干流量的同时解决VM配置问题。然而，该算法既没有考虑迁移成本，也没有考虑VM的剩余生命周期，所以需要提供新的VM配置方案。启发式动态算法计算了每个候选VM、迁移流量和通信流量，以确保所选VM值得迁移。此外，还对VM迁移是否违反DC容量限制进行了核实，迁移顺序对主干网上的流量循环量也有重要影响。因此，本研究所提出的启发式动态算法通过缩小规模，对将要迁移的VM列表进行了排序并执行了迁移。该算法如下：

(1)ListVMs:所有的VM请求列表；

(2)S:所选择的VM列表；

(3)L:将要迁移的VM列表；

(4)CandidateMig:将要迁移的候选VM列表；

(15)

(16)

(17)

2 实验仿真

为了验证本算法的有效性，在一台拥有Intel Xeon 3.3 GHz CPU和8 GB内存的计算机上进行了仿真实验，并使用商业解决方案CPLEX 12.5[11]来解决ILP问题。假设DC的数量为6，VM的开始时间和结束时间随机生成，在24 h内执行这些算法，并在每小时开始时进行一次结果采集，流量矩阵的数值为0～100，随机生成。

2.1 启发式动态算法的性能

为了评估启发式动态算法的质量，将启发式动态算法提供的解与文献[10]中给出的配置算法提供的解进行了比较：

(18)

式中：Sh为启发式动态算法提供的解；S*为文献[10]提供的最优解；G为两种解之间的差距。

表1给出了两种算法间的平均最优差距G。不难发现，当VM数量为1 000、每个租户占用的VM数量为20和80时，启发式动态配置解决方案与静态配置算法提供的解决方案间的差距分别为12.32%和12.00%。随着VM数量的不断增加，20个VM/租户和80个VM/租户的最优差距并未出现等比例增加，相反，当VM数量达到4 000时，20个VM/租户的差距反而比VM数量为2 000和3 000时要低。纵观全部数据可知，启发式动态配置解决方案与静态配置算法提供的解决方案的差距最大不超过13.57%，这意味着启发式动态配置解决方案与静态配置算法提供的解决方案较为接近。然而，与静态配置算法相比，启发式动态算法在进行配置决策时考虑了VM生存周期和迁移成本。

表1 平均最优差距Tab.1 Average optimality gap

2.2 系统稳定性

将启发式动态算法的迁移次数与文献[10]中提出的最优配置算法的迁移次数进行了比较。图1至图4给出了文献[10]的VM配置模型和VM调度启发式算法在24 h内执行的迁移次数变化情况。不难发现，与启发式算法获得的迁移数量相比，配置算法产生的迁移数量十分巨大，且执行的迁移数量随着VM数量的增加而增加。在图1中，当VM数量为2 000、20个VM/租户时，配置算法产生的迁移数量基本维持在启发式算法的4倍以上。在图3中，配置算法产生的迁移数量相比图1对应的数量几乎增加了1倍，而启发式算法的对应数值仍维持在较低的水平。在图2、图4中，随着VM数量和每个租户占用VM数量的增加，启发式算法和配置算法的曲线趋势类似，但在绝对数值上启发式算法产生的迁移数量仍占有显著优势。因此，在迁移决策过程中考虑VM的生存周期有助于提高系统的稳定性，并防止执行过度迁移。

图1 两种算法的VM迁移量(2 000个VM，20个VM/租户)Fig.1 VM migration of two algorithms(2 000 VM,20 VM/tenant)

图2 两种算法的VM迁移量(2 000个VM，80个VM/租户)Fig.2 VM migration of two algorithms(2 000 VM,80 VM/tenant)

图3 两种算法的VM迁移量(4 000个VM，20个VM/租户)Fig.3 VM migration of two algorithms(4 000 VM,20 VM/tenant)

图4 两种算法的VM迁移量(4 000个VM，80个VM/租户)Fig.4 VM migration of two algorithms(4 000 VM, 80 VM/tenant)

3 结语

通过对虚拟化服务的研究，讨论了VM分层结构，并提出了VM的静态和启发式动态实例化方法。对启发式动态配置解决方案与静态配置算法提供的解决方案间的差距进行仿真实验，将启发式动态算法的迁移次数与文献[10]提出的最优配置算法的迁移次数进行比较，结果表明本算法具有良好的应用性能。VM动态实例化的改进方案是下一步努力和研究的方向，未来将尝试把本研究成果拓展到云间环境，以优化协作云的整体性能，包括实现或代理实现基础设施中的管理程序组件以更有效地监控模拟时间，并通过使用更高级的调度启发式方法和算法来增强调度过程。