VNE-AFS：基于人工鱼群的网络虚拟化映射算法

朱强，王慧强，吕宏武，王振东

（哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨 150001）

1 引言

云计算环境追求以较低的成本提供可伸缩的多样性服务，而网络虚拟化是目前实现该目标最有效的技术手段[1～3]。网络虚拟化允许在共享底层网络资源的基础之上建立多个独立、异构的虚拟网络，使服务提供商（SP, service provider）能够依据用户需求提供可定制的个性化服务。虚拟网络请求中节点和链路通常带有约束条件。依据基础设施提供商（InP, infrastructure provider）当前资源情况，通过映射算法在虚拟网络构建需求与底层网络资源之间进行匹配，为虚拟网络请求分配合理的底层节点和链路资源被称为虚拟网络映射，它是一个NP-hard问题[4]。虚拟网络映射问题通常采用基于启发式算法的方法求解，然而为了降低映射的难度和提高启发式算法的效率，已有的成果通常对映射问题的空间进行诸多限制：1）假设底层节点资源和链路资源是无限的[5,6]；2）底层网络需要支持路径分割[7]；3）映射算法评估指标不完善[8]；4）忽略虚拟网络节点对位置的需求[9,10]等。同时映射求解过程还存在过于复杂和开销大的问题。

针对上述问题，本文在底层网络资源有限和不支持路径分割的前提下，提出了一种基于人工鱼群的网络虚拟化映射算法，利用虚拟网络请求对底层网络节点和链路的约束关系建立二进制组合优化模型，并通过人工鱼群算法对底层网络资源进行近似最优化映射，有效地降低底层网络开销和求解时间，提高虚拟网络映射的成功率、平均收益和资源平均利用率。

2 网络建模及虚拟网络映射问题描述

影响虚拟网络映射的节点和链路因素有很多,为了简化映射问题并清晰地描述映射过程，节点一般考虑CPU、内存和位置因素，而链路一般考虑带宽因素[3]。本节基于上述因素对底层网络、虚拟网络请求以及两者之间的映射问题进行描述。

2.1 底层网络描述

虚拟网络映射问题可抽象为一个图论问题。底层网络使用带权无向图描述，其中，NS和ES分别代表底层网络节点集和链路集。每个底层节点nS∈NS的属性集合用ASN表示。节点的属性分别为可用CPU资源占用比cpu(nS)、可用内存占用比memory(nS)和位置loc(nS)。节点i和j之间链路eS(i,j)∈ES的属性集为ASE，链路的属性为可用带宽占用比b(eS)。使用PS表示底层网络所有无环路径的集合，节点i和j之间的无环路径集为PS(i,j)。图1为一虚拟网络请求到底层网络的映射方案。其中，图1(b)是底层网络，链路上的数字代表链路可用带宽，节点周围长方形内的数字分别代表可用CPU和内存资源占用比。

图1 虚拟网络请求的映射方案

2.2 虚拟网络请求描述

2.3 虚拟网络映射问题描述

虚拟请求的映射表示为从VG到SG′的一个映射f，SG′为SG的一个子集，并且能够满足VG的约束条件。

其中，NS′⊂NS，PS′⊂PS，RN和RE分别为分配给虚网请求的节点和链路资源。虚拟映射可以分为节点映射Nf和链路映射Ef2部分。

如图1(b)所示，虚拟网络请求VN1和VN2的节点映射方案分别为{a→C,b→B,c→G}和{d→H, e→D,f→F}。链路映射方案分别为{(a,b)→{(C,A),(A,B)},(a,c)→{(C,D),(D,G)}}和{(d,e)→{(H,G),(G,D)},(d,f)→{(H,F)},(e,f)→{(D,E),(E,F)}}。节点和链路的分配同时满足虚拟网络请求的约束条件。

3 虚拟网络映射评价指标

从InP的角度看，虚拟网络映射算法需要提高平均收益和资源利用率，并降低映射的平均花费。与文献[5,7,9]相似，定义为InP接受第i个虚拟网络请求所获得的收益，由虚拟网络的CPU、内存资源和可用带宽需求组成。

假设0到T时间段内接受的虚拟网络请求集合为I。底层网络的平均运营收益为

InP接受一个虚拟网络请求的花费为分配给该请求的所有相关底层资源花费的总和为

0到T时间段内底层网络对虚拟网络请求映射的平均花费为

底层网络链路资源的平均利用率为

从SP的角度来看，映射算法需要满足更多的虚拟网络映射需求。虚拟网络的映射成功率表示为

其中，VN(t)和VN′(t)分别为0到t时刻虚拟网络请求总数和接受的虚拟网络请求数。

4 虚拟网络映射问题的二进制组合优化模型

与文献[5～8]不同，本文在底层网络资源有限和不支持路径分割的前提下，以降低底层网络映射开销为目的，建立虚拟网络映射问题的二进制组合优化模型。

首先，定义底层节点nS∈NS的剩余可用CPU、内存资源分别为cpu′(nS)和memory′(nS)，底层链路eS∈ES的剩余可用带宽资源为b′(eS)。

其中，nV⊥nS定义为虚拟节点nV被分配到底层节点nS，eV⊥eS定义为虚拟链路nV被分配到底层链路eS。

任意路径P∈PS的可用带宽表示为2个底层节点之间沿着该路径的最小剩余带宽。

4.1 节点及约束条件

令MN为二进制m×n矩阵，代表节点的映射关系。每个行向量和列向量分别代表一个虚拟节点和底层节点，当虚拟节点被分配到底层节点nSj上时，MN(i,j)值为1，否则为0。对于同一个虚拟网络请求，每个虚拟节点只能够被分配到一个底层节点，并且2个虚拟节点不能够同时分配到同一个底层节点，约束条件形式化为

4.2 链路及约束条件

4.3 目标函数

对于虚拟网络请求，映射虚拟节点所分配的资源（CPU和内存）是相同的，而虚拟链路分配的底层链路长度会因方案不同而存在差异，因此使用底层链路的总使用带宽来衡量映射成本。目标函数为最小化链路映射成本。

5 VNE-AFS算法

虚拟网络映射问题的二进制组合优化本质上是NP-hard问题[11]，直接进行全局最优解的求取十分困难。因此，本文通过使用人工鱼群智能启发式算法求取近似最优解。人工鱼群是一种模拟鱼群行为的群体智能算法，通过模拟鱼的觅食、聚群、追尾等行为实现全局寻优[12]。本文基于人工鱼群的虚拟网络映射算法主要由解的表达、生成与适应度函数的确定，人工鱼距离与感知距离的定义，人工鱼的行为及其选择方式3部分组成。

5.1 解的表达、生成与适应度函数

人工鱼个体的状态对应映射问题的解。其当前状态Xi=（xi1,xi2,…,xid）表示映射问题的第i个解，维数d表示虚拟网络请求中节点的个数。xij表示虚拟节点j分配到底层节点的编号。采用如下方法进行节点选取并采用随机路径方法生成初始解。

步骤1 依据虚拟节点对底层节点的位置约束，为每个虚拟节点niV

建立可映射节点的集合。

步骤2 若集合Ω(i)=θ(niV)∩{nS∈NS|MN(i,j)=1}为空集，表明底层网络已经没有符合该虚拟节点映射需求的节点，虚网请求被拒绝，转到步骤5；否则，转到步骤3。

其中，Pbk为与相邻节点之间的路径。ω1和ω2分别为节点剩余CPU、内存的权值。

式(11)～式(15)对节点的约束条件，分配成功；否则，映射失败。

人工鱼Xi的适应度函数与虚拟网络映射的d(i,j)目标函数有关，定义为

fit(Xi)值越大，表明链路映射成本越低，对应的映射方案越好。

5.2 人工鱼距离与感知距离

2条人工鱼iX和jX的距离如下

式(21)表示向量Xi与向量Xj有对不同的分量，本文将Xj中这样的分量即路径的集合记为wj(i,j)。

定义vd(i)为人工鱼Xi的感知距离，所有满足d(i,j)＜vd(i)的人工鱼Xj构成Xi的邻域。

5.3 人工鱼的行为及选择

人工鱼的行为主要有觅食、追尾、聚群和杂交行为。人工鱼对行为的选择会导致其位置的调整，同时对应着映射方案的调整。人工鱼的具体行为描述如下。

1) 人工鱼Xi的觅食行为描述如下。

步骤1 设定TN，tn=0。

步骤2 设定人工鱼移动的步长step，拥挤度因子δ。

步骤3 对于人工鱼Xi，在其邻域内任意选择人工鱼Xj。

步骤4 如果fit(Xj)≤fit(Xi)，转到步骤5；否则，Xi向Xj方向进行一次移动：随机产生整数k(1≤k≤step)。如果k≥d(i,j)，则k=d(i,j)；在wj(i,j)中任选k条路径进行随机变换，路径需满足式（10）和式（16）的约束条件，觅食行为结束。

步骤5 tn=tn+1。如果tn＜TN，转步骤3；否则，人工鱼Xi随机移动一步：在wj(i,j)中任选k条边进行随机变换，觅食行为结束。

2) 人工鱼Xi的聚群行为描述如下。

步骤1 将人工鱼Xi邻域范围内所有人工鱼组成集合Ri。

步骤2 对Ri的中心位置进行确定。其中，是Ri中人工鱼在第x个分量上使用最多的边。

i觅食行为步骤4相同的方法向Xc方向移动；否则，执行觅食行为，聚群行为结束。

3) 人工鱼Xi的追尾行为描述如下。

步骤1 从Ri中选取适应度值最大的Xu，

步骤2 确定与bestX相对应的bestR。如果，则iX用与觅食行为步骤4相同的方法向bestX方向移动；否则，执行觅食行为，追尾行为结束。

4) 人工鱼iX的杂交行为描述如下。

步骤1 设定有限次循环次数limit，变化量阈值ε；

5) 人工鱼Xi的行为选择

采用常用的试探法选择人工鱼的行为。对人工鱼Xi分别模拟执行觅食、聚群和追尾行为。分别得到Xi在执行相应行为后的适应度函数值fit(Xi)p、fit(Xi)s和fit(Xi)f。执行与fit(Xi)p、fit(Xi)s和fit(Xi)f中最大值对应的行为，如果有多个值相同的行为，则随机选取一个行为。

5.4 VNE-AFS算法流程

本文设计的基于人工鱼群的网络虚拟化映射算法流程描述如下。

步骤1 初始化人工鱼种群规模SN、总迭代次数NI，NI=1，人工鱼移动的步长step，拥挤度因子δ。依据5.1节生成SN个解构成初始人工鱼集合

步骤2 计算每条人工鱼Xi的适应度fit(Xi)，记录当前适应度值最大的人工鱼Xi为Xbest。

步骤3 对于每条人工鱼，按照5.3节进行行为选择，并执行选定的行为。若Xj的适应度值更高fit(Xj)＞fit(Xi)，表明新的映射方案要优于原方案，则有Xbest=Xj。

步骤4 假定某些解连续经过limit次循环之后没有得到明显改善，即变化量低于ε时，对其进行杂交操作。

步骤5 记录下当前最优的人工鱼位置。若当前的迭代次数Ni小于NI，Ni=Ni+1，跳转至步骤3；否则，算法结束。

6 仿真实现与性能评价

在验证算法有效性的过程中，为了降低求解的复杂性，本文使用GT-ITM(georgia tech internet work topology models)拓扑生成器对VNE-AFS算法进行辅助求解。

为了方便实验对比，参照文献[5～8]，底层网络设置为一具有100个节点和约500条链路的拓扑结构，与一个中等规模InP的能力相当，节点之间的连接概率为0.5。底层节点的CPU和内存资源符合[40,100]的均匀分布，底层链路资源符合[50,100]的均匀分布。虚拟网络请求的拓扑是随机的，每个虚拟网络请求的节点数符合[2,10]的均匀分布，每个虚拟网络请求的生存时间符合指数分布，平均生存时间为1 000个时间单元。假设虚拟网络请求符合每100个时间单元平均到达4个的泊松分布。对底层节点CPU和内存资源的需求符合[0,20]的均匀分布，对底层链路的需求符合[50,100]的均匀分布。人工鱼群的种群规模SN取20，迭代次数NI为500，控制参数limit取值20，适应度函数变化的阈值ε取0.02，预选取可行节点权值1ω、2ω和3ω分别为0.2、0.2和0.6。

本文分别从底层网络的虚拟网络的映射成功率、平均运营收益、底层网络链路资源的平均利用率和虚拟网络请求映射的平均花费4个方面，将VNE-AFS算法与经典的G-MCF[5]、G-SP[7]、R-VINE[8]和D-VNMA[6]算法进行比较。4种对比算法的描述如表1所示。仿真结果如图2～图6所示。

表1 参与对比的算法

由于预先筛选性能较高的节点，能够最大限度避免如G-MCF算法和G-SP算法产生节点过载；同时人工鱼群算法具有较强的寻优能力，随着时间的推移和虚拟网络请求的增多， VNE-AFS算法在虚网映射成功率和底层网络的平均收益上明显高于4种对比算法，如图2和图3的实验结果所示，分别稳定在0.82和29左右。与对比算法中性能最好的D-VNMA相比，映射成功率和平均收益分别提升了9.2%和14.6%。

图2 虚拟网络请求映射成功率

图3 虚拟网络请求映射的平均收益

图4描述底层链路的平均使用率情况。VNE-AFS能够使底层网络利用率维持在0.35～0.5之间，仅在个别时间点略低于D-VNMA算法，其余时刻均高于或等于D-VNMA算法。从图4实验结果可以看出，与4种对比算法相比，VNE-AFS能够使底层网络资源具有较高的平均使用率和映射成功率。

图4 底层网络链路资源的平均利用率

通过图5和图6实验结果可知，VNE-AFS算法降低虚拟网络请求映射的平均花费最高为47.8%（与G-SP算法相比），最低为24.2%（与D-VNMA算法相比），较好地控制了资源的平均花费；在运行时间方面，与4种映射算法相比，VNE-AFS最高降低了76.7%（与G-SP算法相比），最低降低了32.7%（与D-VNMA算法相比）。主要原因是4种对比算法求取的不一定是最优解，而人工鱼群算法有较强的寻优能力，并可以获得近似全局最优解，能够在确保底层网络对虚拟网络请求映射保持较低的资源开销的同时降低算法的运行时间。

图5 虚拟网络请求映射的平均花费

图6 虚拟网络映射算法运行时间对比

7 结束语

传统的网络虚拟化映射算法存在资源开销大、效率低和对映射问题空间进行限制等问题。本文在底层网络资源有限和不支持路径分割的前提下，结合人工鱼群仿生智能算法，提出一种新的映射算法VNE-AFS。算法以二进制组合优化问题为基础，利用人工鱼群算法较强的寻优能力对虚拟网络映射进行近似最优的分配。实验结果表明，随着时间的增长和虚拟网络请求的增多，该算法在映射成功率、资源利用率和平均收益上较传统的G-MCF、G-SP、R-VINE和D-VNMA算法有较为明显的提升，并且有效地降低了底层网络的平均花费和求解时间。下一步的工作将对节点选取过程中的权值1ω和2ω进行最优确定，并针对底层网络支持路径分割的情况展开。

[1] ARMBRUS M, FOX A, GRIFFITH R, etal. A view of cloud computing[J]. Communications of the ACM, 2010, 53(4): 50-58.

[2] ZHANG Q, LU C, RAOUF B. Cloud computing: state-of-the-art and research challenges[J]. Journal of Internet Services and Applications,2010, 1(1): 7-18.

[3] CHOWDHURY N M M K, BOUTABA R. A survey of network virtualization[J]. Computer Networks, 2010, 54(5): 862-876.

[4] ANDERSEN D G. Theoretical approaches to node assignment[EB/OL].http://www.cs.cmu.edu/～ dga/papers/index.html,2002.

[5] YU M, YI Y, REXFORD J, etal. Rethinking virtual network embedding substrate support for path splitting and migration[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 17-29.

[6] HOUIDI, LOUATI W, DJAMAL Z, etal. A distributed virtual network mapping algorithm[A]. IEEE International Conference on Communications(ICC’09)[C]. Beijing: Chinese Academy of Science, China,2009. 5634-5640.

[7] CHOWDHURY N M M K, RAHMAN M R, BOUTABA B. ViNEYard: virtual network embedding algorithms with coordinated node and link mapping[J]. IEEE/ACM Transactions on Networking, 2012,20(1): 206-219.

[8] ZHU Y, AMMAR M. Algorithms for assigning substrate network resources to virtual network components[A]. Proceedings of 25th IEEE International Conference on Computer Communications (INFOCOM2006)[C].Barcelona, Spain, 2006.1-12.

[9] CHENG X, SU S, ZHANG Z. Virtual network embedding through topology-aware node ranking[J]. ACM SIGCOMM Computer Communication Review, 2011, 41(2): 39-47.

[10] 姜明，王保进，吴春明等.网络虚拟化与网映射算法研究[J]. 电子学报,2011, 39(6): 1315-1320.JIANG M, WANG B J, WU C M, etal. Research on network virtualization and virtual network mapping algorithm[J]. Chinese Journal of Electronics, 2011, 39(6): 1315-1320.

[11] KOLLIOPOULOS S G, STEIN C. Improved approximation algorithms for unsplittable flow problems[A]. The 38th Annual Symposium on foundations of Computer Science[C]. Miami Beach, 1997.426-436.

[12] 李晓磊.一种新型的智能优化方法—人工鱼群算法[D]. 杭州: 浙江大学, 2003.LI X L. A New Intelligent Optimization Method-Artificial Fish School Algorithm[D]. Hangzhou: Zhejiang University, 2003.