基于互补机制的虚拟机放置算法*

孙素云

(广东轻工职业技术学院信息技术学院，广东 广州 510300)

云计算作为一种新型的资源供给模式，用户可以按需获取所需要的网络资源[1]。数据中心通过采用虚拟化技术，将服务器资源(如CPU、内存、带宽等)以虚拟机方式进行封装，然后按需提供给网络用户。虚拟机放置问题是指将用户请求的虚拟机放置到数据中心的服务器上，实现虚拟机到服务器之间的映射。目前中等规模数据中心通常由成千上万台服务器组成，数据中心的能耗已成为一个巨大的运营开销[2]，因此虚拟机放置算法的优劣不仅关系到用户服务水平协议(service level agreement，SLA)，而且影响数据中心的资源利用率和能耗效率[3]。

在数据中心中，将M个虚拟机放置到N(M≤N)个服务器中，其解空间为MN，这是一个典型NP-hard问题[3]。近几年，学者们对虚拟机放置问题进行了广泛的研究，提出许多启发式虚拟机放置算法[4]，例如：首次适应(first fit，FF)、最佳适应(best fit，BF)、降序首次适应(first fit decreasing，FFD)和降序最佳适应(best fit decreasing，FFD)等[5]。文献[2]根据数据中心的运行记录，提出了一个虚拟机资源预测模型，然后根据预测的虚拟机请求量和服务器资源量之间的互补关系，将虚拟机放置到服务器中。基于动态规划思想，文献[3]通过将虚拟机放置问题转化为多阶决策背包问题，然后采用动态规划算法对虚拟机放置问题进行求解。文献[6]通过计算CPU资源和内存资源的比值，然后按照比值大小依次将虚拟机放置到相应的服务器中。文献[7]采用偏斜度刻画CPU资源和内存资源等利用率的差异性，然后将虚拟机依次迁移到资源利用率均方差最小的服务器中。通过对虚拟机负载高峰特征进行建模，文献[8]提出了基于负载相似度矩阵的虚拟机放置算法。

综上所述，有的虚拟机放置算法有的只考虑一个或两个资源维度，有的只考虑虚拟机之间的互补关系，有的只考虑虚拟机和服务器的互补特性，特别是在设置分配权重时，大部分采用静态阈值方法，忽略了网络资源的动态变化特性。本文在现有研究工作的基础上，通过综合考虑虚拟机之间的互补关系，以及虚拟机和服务器之间的互补特性，通过提出动态阈值方法，使资源分配能适应资源状态的动态变化，从而有效地提高数据中心网络资源的利用效率。

1 问题描述

通过采用虚拟化技术将数据中心的网络资源，如CPU，内存和链路带宽资源等进行抽象化，使数据中心成为一个可扩展、可按需分配的虚拟资源池。在云计算模式中，用户的资源请求通过虚拟机进行封装，如图1所示的应用场景中，用户1，用户2，…，用户t向数据中心提交m个虚拟机请求，控制器根据服务器中资源状态，将m个虚拟机分别放置到k个服务器中(k≤n，n表示服务器的个数)，并为虚拟机分配相应的资源量。因此虚拟机放置问题其实质即为m个虚拟机和n个服务器之间的映射问题。

图1 用户请求虚拟机与虚拟机放置模型Fig.1 Virtual machine request and placement model

由于网络应用的异构性，不同的虚拟机资源请求量会存在差异性，如虚拟机1中CPU资源量较多，内存资源量较小，虚拟机2中CPU资源量较小，内存资源量较多。控制器在放置虚拟机请求的时候，如果随机地将虚拟机部署到服务器中，某些服务器中可能出现可用的CPU资源量为0，而内存资源量较多，从而影响资源的利用效率。另一方面，由于数据中心规模日益庞大，电能消耗已成为一个巨大的运营开销。不合理的资源分配不仅影响资源的利用效率，而且会导致运行的服务器个数增多，数据中心的能耗增大。通过提出一个基于资源互补机制的虚拟机放置算法，将虚拟机放置到资源互补的服务器中，使服务器中各种资源量呈现均衡分布状态，达到提高资源的利用效率以及降低数据中心能耗的目的。

1.1 资源消耗模型

(1)

(2)

(3)

(4)

式(1)表示每个虚拟机只能放置在一个服务器中，式(2)表示当服务器放置了虚拟机后，变量yj的值为1，否则yj的值为0，式(3)表示服务器中所有虚拟机第k维的资源请求量总和不能大于服务器的第k维可用资源量，式(4)表示数据中心中运行的服务器个数。

1.2 能耗模型

合理的虚拟机放置算法不仅可以提高资源的利用效率，而且可以降低数据中心的电能消耗。数据中心的电能消耗通常包括服务器的能耗、制冷设备的能耗和照明设备的能耗等。数据中心的能耗可以用服务器的能耗进行近似计算[3]，单个服务器的能耗和整个数据中心的能耗定义为：

(5)

(6)

(7)

2 基于互补的虚拟机放置

2.1 基于互补机制的虚拟机组合算法

为了提高虚拟机放置算法的网络性能，在虚拟机放置到服务器之前，采用基于互补机制对虚拟机进行组合，使新组合的虚拟机(可视为新的虚拟机)中各种资源量尽可能均衡的分布，见图2。

图2 虚拟机与虚拟机互补示例图Fig.2 The complementary examples among virtual machines

图2中竖线和横线方框分别表示CPU、内存资源量，方框高度表示资源请求量大小。如图2所示，如果将虚拟机1和虚拟机2组合在一起，新组合的虚拟机中CPU和内存资源量呈现均衡分布，如果将虚拟机1和虚拟机3组合在一起，新组合的虚拟机中CPU和内存资源量分布不均衡。通过对虚拟机组合问题进行分析，我们提出虚拟机之间的互补关系模型。

(8)

表1 基于互补的虚拟机组合算法Table 1 Algorithm of virtual machine combination based on complementary

算法1中第5行表示，对虚拟机中各种资源量先做正则化处理，然后计算虚拟机中最大资源请求量与最小资源请求量的比值，并按照比值进行降序排列，使得资源分布最不均衡的虚拟机优先查找互补的虚拟机，以此改善虚拟机中资源的分布状态。第7到第10表示，对资源请求量大于服务器资源量平均值的虚拟机不进行虚拟机组合操作。第11行到第18行表示为虚拟机查找具有互补关系的虚拟机，并将它们组合为新的虚拟机。通过运行算法1后，虚拟机中资源分布状态将得到改善。算法1的时间复杂度为O(m2)，其中，m表示虚拟机请求个数。

2.2 基于互补机制的虚拟机放置算法

通过进行虚拟机组合操作后，虚拟机中资源请求量均衡度将得到改善。由于虚拟机中资源维度个数较多，仍然有可能是不均衡分布的。特别是，有的虚拟机没有进行组合操作，它们不均衡分布状态更加严重。因此在放置虚拟机的时候，需要考虑虚拟机和服务器之间的资源状态，把虚拟机放置到具有互补关系的服务器中，提高计算资源的利用效率，见图3。

图3 虚拟机和服务器互补示例图Fig.3 The complementary examples between VMs and servers

图3中竖线和横线方框分别表示CPU、内存资源量，方框高度表示资源量大小。图3(a)表示虚拟机和服务器的资源分布状态。在图3(b)中，当将虚拟机i放置到服务器1中，服务器1的CPU资源和内存资源均衡度得到改善, 当将虚拟机i放置到服务器2时，服务器2的CPU资源和内存资源不均衡度更严重。通过对虚拟机放置问题进行分析，提出虚拟机和服务器的资源互补关系模型。

(9)

算法2为虚拟机在数据中心中查找具有互补关系的服务器，使虚拟机放置到服务器后，服务器中各种资源量尽可能均衡分布。第6行用于保证服务器中可用的资源量能满足虚拟机的需求量。如果待放置的虚拟机是组合型虚拟机，则表示将组合之前的虚拟机放置在服务器中。算法2的时间复杂度为O(m·n)，其中，m表示虚拟机请求个数，n表示服务器个数(表2)。

表2 基于互补的虚拟机放置算法(CBVMP)Table 2 Algorithm of virtual machine placement based on complementarity

3 仿真实验

为了分析CBVMP算法的网络性能，实验中实现了first fit(FF)[10]、first fit decreasing sum(FFDSum)[11]以及compVM-Grp算法[2]。CBVMP算法首先进行虚拟机组合操作，然后基于互补机制实施虚拟机放置操作。FF算法将虚拟机放置到满足其资源请求量编号最小的服务器中。FFDSum首先计算每个服务器中所有资源量的累积和，然后采用贪婪算法将虚拟机放置到累积和最小的服务器中。compVM-Grp首先将虚拟机随机进行组合，然后采用compVM-Grp中互补模型将虚拟机放置到相应的服务器中。

3.1 实验环境设置

CloudSim[9]是一个虚拟化仿真实验平台，支持按需资源分配和管理操作。实验中采用CloudSim对上述四个虚拟机放置算法进行仿真。仿真实验期间，数据中心服务器的数量为600台。实验中其它参数，如服务器类型、虚拟机类型和服务器的电能消耗模型如表3、表4和表5所示。

表3 服务器类型描述Table 3 Server type description

表4 虚拟机类型描述Table 4 Virtual machine type description

表5 服务器能耗和利用率Table 5 Server energy consumption and utilization W

3.2 实验结果与分析

根据服务器的运行个数、数据中心的能耗，CPU、内存和硬盘资源的平均利用率等评价上述四个算法的网络性能。服务器的运行个数表示为放置虚拟机而启动的服务器个数，数据中心的能耗表示启动的服务器消耗电能总量，服务器的运行个数越少，数据中心的能耗越低，虚拟机放置算法的网络性能也越好。资源的平均利用率表示所有启动的服务器中CPU、内存和硬盘资源的平均利用率，平均利用率越高，虚拟机放置算法的网络性能也越好。实验结果如图4～图6所示。

图4显示了在3种不同虚拟机请求个数时，四个算法为满足虚拟机请求而启动的服务器个数。图4显示： FF算法中运行的服务器个数最多，特别是在虚拟机个数较多时，FF算法运行的服务器个数比CBVMP算法高出25%以上。主要原因是FF算法根据服务器的编号顺序依次将虚拟机放置到服务器中，没有考虑虚拟机中资源请求量和服务器中可用资源量的相互关系，使服务器中可用资源量分布不均匀，导致运行的服务器个数增多。服务器的电能消耗和运行的服务器个数以及运行状态有关，从图5可以看出，FF算法的能耗也较大，进一步说明FF算法的资源分配效率和能耗效率都较低。

图4 数据中心运行的服务器个数Fig.4 The number of running servers in the data center

图5 数据中心的能耗Fig.5 Energy consumption in the data center

图6 三种资源的平均利用率Fig.6 Average utilization rate of three resources

图6显示了四个算法的CPU、内存和硬盘资源的平均利用率。从图6可以看出， FF算法资源的平均利用率最低，CBVMP算法资源的平均利用率最高。图6显示FF算法和FFDSum算法内存资源的利用率明显低于硬盘资源的利用率、compVM-Grp算法硬盘资源的利用率明显高于其它资源的利用率、CBVMP算法3种资源的平均利用率基本接近。实验结果表明：基于互补机制的虚拟机放置算法能动态地适应网络资源状态，合理地将虚拟机放置到最互补关系的服务器中，均衡地分配服务器中计算资源，提高资源的利用效率和能耗效率。

4 结 语

文章通过建立数学优化模型，分析虚拟机放置问题中资源消耗和能源消耗的关系，并通过虚拟机放置实例，阐述虚拟机放置过程中需要考虑虚拟机与服务器之间的资源分布状态。为了提高服务器资源的利用效率，文章基于互补关系模型，提出了基于互补机制的虚拟机放置算法，在虚拟机放置过程中动态考虑网络中各个资源的分布状态。实验结果表明：CBVMP算法取得了较好的网络性能，有效地提高了数据中心的资源效率和能耗效率。