云环境下一种联盟形成博弈的虚拟机迁移算法

秦海燕,彭飞,陈敏，吴杨

(1.扬州市职业大学现代教育技术中心，江苏扬州225000；2.博世创新与软件开发中心，江苏苏州215000)

1 引言

云计算作为一种新兴的计算模型受到了广泛的关注和应用。服务供应商越来越愿意将服务从本地集群迁移到云数据中心。云数据中心将虚拟化技术作为实现计算资源多样化、促进系统管理高效化的关键技术。虚拟机通过虚拟化技术创建，被部署在物理机上。在云场景中，服务供应商请求资源，平台将任务请求部署到资源池的主机中。但是，云数据中心通常无法高效运行。效率低下主要是因为虚拟机的分配方式不合理，导致物理机资源负载不平衡，一些物理机过载，一些物理机无法充分利用[1]。虚拟机迁移算法是一种帮助云供应商提供有效、自主管理云资源的方法。虚拟机迁移使用迁移技术将负载从一台物理机转移到另一台物理机，以平衡物理机之间的负载，提高物理机利用效率。

在虚拟机迁移过程中要考虑两个关键问题。一方面，如何从高载物理机中选择出待迁移的虚拟机。云平台中，两个位于不同物理节点的虚拟机的通信成本比位于同一个物理节点的要高，因为数据通过内存传输比通过网络传输成本低。因此，无论是迁移还是保留高载物理机中的虚拟机，都应该考虑通信成本。另一方面，应该选择哪个低载物理机来放置待迁移的虚拟机。当有许多虚拟机需要迁移，并且有多个低载物理机满足迁移条件时，待迁移虚拟机和低载物理机的映射关系就要考虑。

虚拟机迁移算法很多，如装箱算法[2-3]、遗传算法[4-5]、蚁群优化算法[6]等。本文提出了一种基于联盟形成博弈的虚拟机迁移算法(简称VMM-CFG)。联盟博弈是一个设计公平、稳健和高效协作策略的非常强大的理论[7]。联盟形成博弈是联盟博弈论的一个分支，与经典博弈和联盟图博弈不同，网络结构和合作成本在联盟形成博弈中起着重要作用。本文将虚拟机迁移问题建模为基于合并和拆分算法的联盟形成博弈。首先，从高载物理机中筛选出待迁移的虚拟机。接着，待迁移的虚拟机根据相应的约束自主形成联盟结构。待迁移的虚拟机可以通过不断执行合并和拆分操作来更新联盟结构，直到形成稳定的联盟结构。联盟结构中的每个联盟都映射到相应的低载物理机。最后，根据待迁移的虚拟机和低载物理机之间的映射，执行迁移。

2 问题模型

如图1所示，数据中心由v台虚拟机部署在p台物理机上构成，P={1,2,...,p}表示物理机集合，V={1,2,...,v}表示虚拟机集合。物理机i∈P与虚拟机j∈V的映射关系用xij表示，如果xij= 1，表示虚拟机j∈V部署在物理机i∈P上。VMi={j|xij=1,∀j∈V}表示部署在物理机i上的虚拟机集合；函数f(j)表示虚拟机j∈V所在的物理机。

图1 数据中心结构示例图

图Gi=(VMi,Ei)表示部署在物理机i上的虚拟机间的数据通信结构，若虚拟机j,k∈VMi间存在数据通信，则存在边(j,k) ∈Ei，权值wjk为其数据通信量。G={G1,G2,...,Gp}表示所有物理机的数据通信结构。

每个虚拟机j∈V均配置一定量的物理资源，如CPU、内存和网络等，不失一般性，本文仅考虑内存资源。mj表示虚拟机j所需的内存资源量，Mi和Mi′分别表示物理机i∈P的最大内存容量和负载安全阈值表示物理机i∈P实际的内存使用量，即：

若Mi′<≤Mi，则称物理机i∈P是高负载的；否则是低负载的。高载物理机集合表示为H={i|Mi′<≤Mi,i∈P}，低载物理机集合表示为L={i|≤Mi′,i∈P}。虚拟机迁移最主要的目标是最小化高载物理机数目 ||H，实现负载均衡[1]。

3 基于联盟形成博弈的虚拟机迁移方法

考虑到动态迁移的实时性以及时间性能要求，本文研究设计一种基于联盟形成博弈的迁移方法，具体方法如图2 所示。1)制定选择规则，从高载物理机中筛选出待迁移的虚拟机；2)待迁移虚拟机之间运用联盟形成博弈理论自主演化形成稳定的联盟，最终完成联盟与低载物理机间的映射，并实现迁移。

图2 一种基于联盟形成博弈的迁移方法

3.1 虚拟机选择算法

待迁移虚拟机选择算法目标有两个：1)使高载物理机的实际资源使用量不高于负载安全阈值；2)使通信紧密的虚拟机保留在原物理机，即将与其他虚拟机无通信或通信较少的虚拟机迁出。算法的具体描述见算法1。对于每个高载物理机i∈H，首先计算每个虚拟机j∈VMi的通信量cj，即与该物理机中其他虚拟机之间的数据通信量之和：

然后，根据通信量cj进行升序排列。如果序列中第一个虚拟机迁出，该物理机仍然高载，则将该虚拟机加入待迁移虚拟机集合VMList，继续判断下一个虚拟机，直到该物理机低载。依次遍历所有高载物理机。

算法1 虚拟机选择算法输入：H,G输出：VMList 1. VMList ←∅2.for i ∈H do 3.for j ∈VMi do 4.cj =∑(j,k) ∈Eiwjk 5.end for 6.VMi′←{ j|cj is sorted by an ascending sort}7.for j ∈VMi′do 8.if∑k ∈VMi′{ j}mk ≥Mi′then 9.VMList ←VMList ⋃{ j},VMi′←VMi′{ j}10.end if 11.end for 12.end for

3.2 虚拟机联盟形成算法

筛选出待迁移的虚拟机集合后，要考虑如何将这些虚拟机迁移到低载物理机，即待迁移虚拟机与低载物理机间的二次映射问题，类似于装箱问题[2]和二次分配问题[8]，是NP难问题。在映射过程中，既要考虑物理机的内存容量，又要考虑网络通信成本。

本节运用联盟形成博弈理论，让待迁移虚拟机自主形成虚拟机群，整体映射到同一个低载物理机。下面给出一些定义：

定义1：待迁移虚拟机集合VMList的任意子集称为联盟C⊆VMList，若 存 在 一 个 低 载 物 理 机i∈L，使 得，则联盟C为有效联盟。VMList的一个划分称 为 联 盟 结 构 ∏={C1,C2,...Ch}，满 足Cg⋂Cl=∅,∀g,l∈{1,2,...,h},g≠l且∪k∈{1,2,...,h}Ck=VMList。Σ(Π) 表 示所有可能的联盟结构。同样，若联盟结构∏内所有联盟均为有效联盟，则Π称为有效联盟结构。

定义2：给定联盟结构Π ∈Σ(Π)，其值v(Π)定义为所有虚拟机之间总的通信成本，即：

d(f(j),f(k))表示物理机f(j)和f(k)的单位通信成本，如果j和k部署在同一个物理机，则d(f(j),f(k)) = 0。

定义3：给定联盟结构Π 和Π′，∏优于∏′当且仅当v(Π)

依据上述两种操作，联盟形成过程如下：首先，将每个待迁移虚拟机视为单一联盟，形成初始联盟结构。接着随机选择两个联盟并判断能否合并，若满足合并条件则合并，直到不存在任意两个联盟能合并为止。在某个低载物理机中的资源足以支持新联盟的条件下，新联盟被映射到相应的低载物理机中。映射过程由算法2 中的MapProcess(·)执行。随后遍历任意联盟，判断是否存在其划分满足分割条件，若满足则进行分割，将分割的联盟分别映射到低载物理机。最后，迭代执行上述合并和分割过程，直到达到迭代次数或联盟结构无变化为止。算法的具体描述见算法2。

算法2 待迁移虚拟机联盟形成算法输入：VMList输出：Π 1.Π ={{ j} j ∈VMList}2.repeat//Merge Process 3.repeat 4.Select coalition Ci,Cj ∈Π randomly 5.MapProcess(Ci ⋃Cj)6.if Ci ⋃Cj ⊳ m{Ci,Cj}then 7.Ci ←{Ci,Cj},Cj ←∅8.end if 9.until There are no two coalitions satisfying the merging condition//Split Process 10.for all Ci ∈Π and|Ci| > 1 do 11.for all the partitions {Cj,Ck} of Ci where both Cj,Ck are effective coalitions do 12.MapProcess(Cj),MapProcess(Ck)13.if{Cj,Ck}⊳ sCithen 14.Ci ←Cj,Π ←Π ⋃Ck 15.end if 16.end for 17.end for 18.until Π no change or loop number is reached

4 基于联盟形成博弈的虚拟机迁移方法

本节中，根据迁移前后高载物理机的数量的变化、物理机负载标准差的变化来评估VMM-CFG的性能。

4.1 参数设置

假设有x个物理机。对于每个物理机，容量最小为200，容量最大为300。物理机容量和阈值之间的差值随机分布在(0,50]。物理机的最大通信带宽为50。假设有3x个虚拟机，用户所需的最小和最大虚拟机数量分别为4和8。虚拟机所需的资源从10到20不等。

4.2 结果分析

由图3 可知，随着物理机数量的增加，高载物理机数量也成比例地增加。基于VMM-CFG算法迁移后，高载物理机的数量明显下降，实现了物理机间负载均衡的目标，且随着物理机数量的增加，高载物理机数量的降幅增加，这意味着物理机规模越大，物理机间的负载均衡效果越明显。因此，VMM-CFG算法更适合于物理机数量庞大的云环境下。

图3 迁移前后高载物理机的数量和物理机负载的标准差变化

在虚拟机迁移前，物理机负载的标准差数值较大。虚拟机迁移后，物理机负载的标准差降幅明显，这说明VMM-CFG 算法实现了物理机间的负载均衡，且效果明显。另外，随着物理机数量增加，物理机负载的标准差趋于平稳，这意味着物理机的规模越大，物理机的负载更加均衡。

5 结论

本文研究了云数据中心的虚拟机迁移问题。在虚拟机迁移过程中，主要考虑了两个问题：哪些虚拟机应该从高载物理机中迁移；待迁移的虚拟机应该放置在哪些低载物理机上。为了最大限度地降低通信成本，减少高载物理机的数量，将基于联盟形成博弈的虚拟机迁移算法引入虚拟机迁移中。仿真结果表明，VMM-CFG算法在实现物理机负载均衡方面具有优势。