网络虚拟化中虚拟资源调度算法研究

摘 要：为了维护物理节点的负载均衡以提高资源的利用率，本文通过简单的装箱问题探讨了虚拟机与物理机的关系，在动态资源分配的过程中，主要研究了Bin Packing系列算法，细化并实现了其中的四种算法BF，FF，WF，NF。改进了BF，FF算法，通过Matlab对四种算法和改进的BF，FF算法进行了仿真和比较，验证了虚拟资源调度算法对负载均衡的积极意义。

关键词：动态资源调度算法；网络虚拟化；资源分配；资源利用率；负载均衡

中图分类号：TP393.01

Internet的出现使人们获取和交换信息的方式变得便捷，随着Internet的不断发展已面临巨大挑战。当前Internet的体系结构存在许多缺点，由于Internet由多个运营商共同提供，使Internet体系结构的变革难以实现，Internet的发展陷入僵局。网络虚拟化[1]是多元化Internet体系结构的组成部分，它支持来自不同服务提供者的异构网络体系结构共存，并使得这些网络体系结构可以共享由多个基层设施提供者管理的物理底层。通过网络虚拟化，Internet能够有效克服僵化问题，网络虚拟化使将来的Internet体系结构多元化为一系列相互独立的虚拟网络，这些虚拟网络共享基础设施提供者的资源，并支持多种网络体系结构、实验和业务。

资源分配是网络虚拟化中的一个基本问题，有效的资源分配能够提高基础设施提供者的物理资源利用率，并降低服务提供者租用资源所带来的成本。因此，如何设计有效的资源分配算法成为关键和难点问题。

本文第2节对相关工作进行讨论；第3节分析和比较当前比较主流的虚拟资源调度算法；第4节针对BinPacking系列算法进行仿真分析，针对其缺陷加入优化因子，提出改进算法，用仿真进行改进，对实验结果进行分析；第5节对所研究的内容进行总结并展望未来研究方向。

1 虚拟资源调度算法

虚拟资源调度系统中核心组成部分就是调度算法。文献[7]中提到调度算法根据针对的调度对象不同，分为服务器负载均衡算法，虚拟化系统动态资源调度等。在本文中主要讨论虚拟化系统中的负载均衡调度算法。对当前一些常用的调度算法进行分析，并比较其中各个算法的优缺点和适用环境。

1.1 Greedy算法

贪心算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪心决策的依据称为贪心准则（greedy criterion），也就是从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。

1.2 Bin Packing系列算法

装箱问题在计算机领域中有广泛的应用，多任务调度，多处理器调度，内存管理，Cache调度都是装箱问题的实例。

装箱问题数学形式表示为：给定n个物品，物品的大小为，每一个箱子的大小都为V，找到一个整数m和对{l，2，…，n）的m个划分P1 P2 … Pn使得对任意的j=l，…，m，均有优化的目标是使得m最小，即使用的箱子数目最少。在虚拟化动态调度中，每一个箱子相当于是具有一定资源容量的物理机，而每一个物品，则是虚拟机，通过设定特定的V（物理机负载峰值），使得整个系统的负载均衡。

装箱问题（Bin Packing）是典型的NP-hard问题，有多种求解方法，可以采用近似算法或者优化算法如遗传算法，蚁群算法搜索解空间求解。最为直接的求解思路是使用贪婪策略，使用诸如First Fit，Best Fit，Worst Fit，Next Fit等。

（1）First Fit（FF）：对每一个要装入的物品，从头开始检查当前打开的箱子，找到第一个可以放入该物品的箱子，将物品放入；如果当前打开的所有箱子中没有一个能够装入该物品，则打开一个新箱子，将该物品放入。

（2）Next Fit（NF）。始终维持这一个当前打开的箱子，对每一个要放入的物品，检查该物品是否可以放入到当前打开的箱子中，如果可以，则将该物品放入：否则打开一个空箱子，放入该物品，以该箱子作为当前的箱子，并关闭上一个箱子。当下一个物品到来时，持续此过程，直至所有的物品都放完为止。

（3）Best Fit（BF）。与首次适应算法（FF）类似，唯一的区别是当物品装箱时，不是直接装在第一个可装入的箱子中，而是装入在最适合该物体的箱子中（装入后使得箱子最满），如果没有任意一个箱子可以放入该物品，则开启空箱子。

（4）Worst Fit（WF）。与最优适应算法（BF）不同，当物品装箱时，不是装在装入物品后的箱子容积最满的箱子中，而是装入到最不适合该物体的箱子中（装入后使得箱子的体积最空），如果没有任意一个箱子可以放入该物品，则开启空箱子。

1.3 Linear Programing算法

线性规划是调配资源的一种应用数学方法，在运筹学中使用较多。它的基本思路就是在满足一定的约束条件下，使预定的目标达到最优。当每一次负载情况发生变化时，都需要建立并重新求解线性规划，需要耗费大量的计算时间。并需要对整个虚拟机和物理机的布局进行全盘的重新分配，带来大量的迁移开销，因此，在虚拟化系统的动态调度中主要用到调度资源初始化和虚拟机初始放置场景中。

1.4 Sand-Piper算法

Sand.Piper是Xen虚拟机用来检测热点物理机的检测机制。它是通过将资源整合为一个维度，然后贪婪的选择物理机，并决定将该物理机上的虚拟机放置到哪一台物理机上来实现负载均衡和热点解除。

2 实验仿真与结果分析

对以上几种调度算法进行对比和分析可以看出，贪心算法由于只考虑局部最优，有可能的不到最优解，在极端情况下，算法无法终止，甚至会产生迁移振荡。Bin packing算法中四种算：BF，FF，WF，NF各有优缺点，不过整体来说，bin packing算法能通过简单的物品装箱问题直观的表示出资源调度的情况。Linear Programing算法通过线性规划得到虚拟机在物理机上的调度情况，不过由于当每一次负载情况发生变化时，都需要建立并重新求解线性规划，耗费了大量的计算时间。Sand-Piper算法算法核心思想就是利用Greedy的思想来进行Worst Fit。但由于Sand-Piper算法直接将三个维度的资源合成一个维度，降维处理比较简单，并没有综合考虑虚拟机和物理机资源维度之间的互补关系，因此，实现起来效果不尽如人意。虚拟化系统中的虚拟机部署问题和调度问题可以看做是装箱问题的变体，因此对网络虚拟化中的资源调度问题，可以选择BinPacking系列算法并进行改进。

2.1 四种算法的比较（FF，BF，WF，NF）

FF算法的优点是实现起来简单，但缺点是当物品从小到大放置时，结果可能会比较坏；NF算法的优点是实现简单，算法复杂度低，但是由于每一个物品放置时，只有当前的箱子和空箱子可以选择，效率低下，还会造成箱子的浪费；BF优点是实现简单，易于理解，但如果当物品从小到大放置时，结果有可能极坏并且还有遍历所有可以放入的箱子；WF优点是实现简单，但是实现效果不是很好。

在这次仿真实验中，我们首先设置了几项基础参数如下：

根据仿真图，X轴代表物品数目，也就是代表虚拟机的个数，Y轴代表需要使用的箱子数目，也就是代表有限的物理资源。从图片中我们可以看出，当物品数目在小于200时，BF FF NF WF四种算法所使用的箱子数目基本差不多。当物品数目达到500左右时，WF和NF算法已经产生了明显的劣势（即需要使用的箱子数目明显增多，其中NF算法使用的箱子数目最多（即最差），WF其次。而BF和FF算法还没有产生差距。当物品数目达到1000时，BF和FF算法产生了交集，物品数目1000时，BF和FF算法所需要使用的箱子数目相同。不过物品数目在达到1000以后，BF和FF算法也并没有产生太大的差距，BF算法稍占优势。

根据图1，可得出结论：当物品数目增多时，4种算法之间的优劣性差距显著提升，其中，算法性能从优到劣分别是：BestFit，FirstFit，WorstFit，NextFit。

2.2 FirstFit和BestFit的改进算法

从2.1中，我们看出BestFit和FirstFit算法具有较好的性能，那么能否将他们再进行改进呢？于是我们在离线的情况下，在FF和BF的基础上提出加强的FFD和对BFD算法，以下是算法分析以及仿真实验比较。

First Fit Decreasing（FFD）：针对FF算法中物品可能升序出现，先对物品按降序排序，再按照FF算法进行装箱。但该算法是在知道所有物品信息的情况下才能对物品按照大小进行排序，因此是一个离线（OffLine）模型。FFD的优点是所得到的结果较为精确，缺点是只适用于离线模型，即要知道所有的物品大小，同时还要进行排序操作，开销较大。

可得出结论：当物品增多时，FFD算法较FF算法的优越性逐渐提升，FFD在某种程度上对FF进行了性能上的提升。在物品数目200之前，FF和FFD算法没有产生太大的差异，在物品数目在500左右时，FF和FFD算法产生了交集。当物品数目达到1000时，FF和FFD算法产生了差距，FFD算法较FF算法产生了优势。在物品数目相同时，FFD算法需要使用的箱子数目更少。

Best Fit Decreasing（BFD）：针对BF算法中物品可能升序出现，先对物品按降序排序，再按照BF算法进行装箱。和FFD一样，该算法也是要求知道所有物品的大小信息。

可得出结论：当物品增多时，FFD算法较FF算法的优越性逐渐提升，FFD在某种程度上对FF进行了性能上的提升。在物品数目200之前，BF和BFD算法相同的物品数目所使用的箱子数目差不多。当物品数目500时，BFD和BF算法有相同的作用，相同的物品数目所需要的箱子数目相同。在物品数目达到1000时，BFD比BF算法更好，不过两种算法产生的函数图趋于平稳，没有产生太大的差距。

2.3 BinPacking算法总结

本节主要围绕网络虚拟化中的动态分配资源问题展开讨论，提出了一种动态资源分配的算法。该算法主要是通过动态地迁移虚拟节点来实现负载在物理节点上的均衡分布，同时考虑了节点迁移对虚拟网络性能和物理网络负载分布的影响，并定义了综合

影响因子来衡量节点迁移带来的综合影响。通过一定数量的物品所需要的箱子数目反应出物理网络负载情况。

3 结束语

资源分配是网络虚拟化面临的主要挑战之一。有效的资源分配有利于物理络的负载均衡，提高物理网络资源的利用率，增加物理网络承载虚拟网络的数目，减少SPs的成本。本文研究了网络虚拟化中的资源分配问题和当前已有资源分配算法，进行了详细分析、比较和仿真。并对仿真结果进行了理论分析。仿真结果表明，本文提出改进的资源分配算法能够更为有效地调整负载在物理节点上的分布，但是该算法只能平衡物理节点间的负载，不能对物理链路的负载进行平衡，所以该算法在整个物理网络的负载平衡方面具有一定的局限性。

参考文献：

[1]N.M.M.K.Chowdhury，work virtualization：state of the art and research challenges，IEEE Communications Magazine，2009：（47）：2026.

[2]陈磊.一种启发式网络虚拟化资源分配算法[D].湖南大学信息与工程学院，2012（42）：22-40.

作者简介：彭红姣（1975-），女，湖南祁东人，实验师，硕士，博士研究生，研究方向：网络虚拟化、云计算、网络与通信、计算机应用。

作者单位：南京邮电大学计算机学院，南京 210023

基金项目：江苏省高校研究生科研创新计划项目（项目编号：CXZZ13_0494）；江苏省高校自然科学研究计划资助项目（项目编号：12KJB520007）；江苏省自然科学基金项目（项目编号：No.BK2011754）。