一种负载感知的虚拟网络映射算法∗

许建平

（海军装备研究院 北京 100073）

1 引言

针对日益丰富的网络应用，传统网络体系结构在灵活性、实时性、便捷性等方面越来越难以适应［1］。为解决该问题，一部分学者对虚拟网络技术进行了研究，为该问题的解决开辟了新的途径［2］。虚拟网络是指通过抽象、分配、隔离机制，在一个公共物理网络上支持多个虚拟互连架构，各个虚拟互连架构之间协议体系相互独立的逻辑分成网络。具有链路和节点资源约束的虚拟网络到物理网络的映射问题被称为虚拟网络映射问题。

针对虚拟网络映射问题，Wang等［3］所提出了一种自适应虚拟网构建算法（BACA）链路负载均衡性和节点负载均衡性都进行了考虑。但BACA算法假定节点映射是已知的，因而只从边映射的角度来分析虚拟网络映射问题；Cheng等［4］提出了一种拓扑感知的虚拟网络映射算法，提高了虚拟网络请求成功率，但是没有考虑中间节点的资源消耗；Lischka等［5］考虑了节点及链路的映射开销，但链路开销出现偏差时方法的成功率较低；蔡志平等［6］提出在满足虚拟网络资源需求的前提下，将虚拟网络植入到合适的底层物理节点和链路，但该方法的计算复杂度较高；陈晓华等［7］根据底层网络资源利用率的训练方法以及主动休眠底层节点和链路算法，提高休眠节点和链路数量，实现高效节能虚拟网络映射，但该方法没有考虑虚拟网络请求成功率的优化。上述方法均在不同程度上存在网络负载失衡问题，为此，本文提出了一种负载感知的虚拟网络映射算法（a workload-aware virtual network map⁃ping algorithm，WAVNM），同时考虑了基础网络的链路负载和节点负载，以均衡映射后的虚拟网络的流量。

2 虚拟网络映射分析

映射成本是虚拟网络映射需要解决的核心问题，因此通常以映射成本最小作为优化目标，即物理网络使用最少的带宽资源和计算资源来满足虚拟网络的需求。在分析虚拟网络映射问题时，物理网络可以被看作是一个无向图GS，其被定义为

其中，为物理网络的剩余计算资源；为物理网络的剩余带宽资源；NS为物理网络的节点集；LS为物理网络的链路集。

虚拟网络请求也可以被看作是一个无向图GV：

其中，为虚拟网络所需的计算资源；为虚拟网络所需的链路资源。

如果把虚拟网络映射过程看作是一个映射操作M，其是GV映射成GS的一个子集，并且该子集是GV在GS中的象，即该子集满足两个条件，一个是它的计算和链路资源不小于，另一个是它的计算和链路资源不大于。因此，可表示为

式（3）可以进一步分解成节点映射和链路映射：

其中，PS为一组物理链路LS的集合，即一条虚拟链路可由多条物理链路来实现。

3 问题建模

设物理网络为加权无向图GS(NS,ES)，其中（M为物理节点个数）是物理网络节点集合，ES是物理网络链路集合。和分别是总的CPU资源与可用CPU资源，之间的物理链路，而分别为的总带宽与可用带宽(i,j=1,2,…,M)。由于虚拟映射网络是物理网络的子图，因此，虚拟映射网络也可以用加权无向图GV(NV,EV)来表示，其中（N为虚拟映射网络中的节点个数）是虚拟映射网络节点集合，EV是虚拟映射网络链路集合。所需的计算资源，而表示虚拟链路所需的带宽。那么，虚拟网络映射到物理网络的数学模型为

在实际应用中，虚拟链路所对应的物理路径上的中间节点需要消耗部分CPU资源才能实现数据包的转发。在本章中，所对应物理路径上的每个中间节点消耗的CPU资源。令Γ=100CPUunits，Φ=100BWunits，数据包大小为Pn byte，中间节点转发该数据包需要花费的CPU周期为ω，那么的计算公式为

同时式（7）满足下列条件：

其中，表示虚拟链路所对应的物理路径上的最小剩余带宽。式（8）表明物理网络节点的处理能力能够满足自身需求和作为中间节点的需求。式（9）表明虚拟链路所对应的物理路径上的最小剩余带宽大于链路所需的带宽

为了衡量链路负载和节点负载的均衡性，下面对链路负载和节点负载进行数据建模。对于物理网络节点而言，其除了可以作为工作节点来进行计算以外，还可以作为中间节点来进行数据包的转发，因此，的负载为

那么，整个物理网络节点的平均负载Navg为

而整个物理网络节点的负载方差Nσ：

同理，物理链路的负载为

其中：所对应的物量链包括其它

那么，整个物理网络链路的平均负载Lavg为

而整个物理网络链路的负载方差Lσ为

为了实现链路负载和节点负载的双均衡，本文所定义的目标函数为

其中，α和β分别为节点负载调节因子和链路负载调节因子，并且0＜α，β＜1，α+β=1。α（或β）的取值根据Nσ（或Lσ）动态地进行调整。当Nσ（或Lσ）较大时，减少α（或β）的取值，改变虚拟网络映射，从而实现链路负载和节点负载的双均衡。

4 负载感知虚拟网络映射算法WAVNM

根据上述分析可知，虚拟网络映射问题是一个多目标优化问题，并且其已被证明是一个NP-hard问题［8］。对于多目标优化问题，粒子群优化算法是一种常用的求解方法［9］。针对标准粒子群优化算法存在过早收敛［10］和局部最优［11］的问题，因此本文使用改进的粒子群优化算法来进行虚拟网络映射问题的求解，算法包括初始化和迭代两个阶段。

4.1 初始化阶段

首先，我们引入能力衡量参数，该参数的定义为

在初始化阶段，WAVNM算法通过以下四个步骤生成初始种群。

1）为GV中的每个虚拟链路选择相对应的GS中的起始节点ns和结束节点ne；起始节点选择原则：（1）ns未被虚拟链路使用；（2）ns的值不小于所有未被虚拟链路所使用的节点的能力衡量参数；结束节点选择原则：（1）ne与ns的最小跳数不大于Nhop；（2）在Nhop范围内，ns的值最大，并且ns的可用CPU资源能够满足需求；（3）在ne与ns之间的所有最短路径中，选择一条链路负载最小并且满足式（8）和式（9）的路径。

2）如果根据步骤1）起始节点选择原则未找到ns，那么根据步骤1）结束节点选择原则来选取ns。

3）当ne和ns选择好后，在ne与ns之间的所有最短路径中，选择链路负载最小并且满足式（8）和式（9）的路径作为两者的通信路径。

4）重复步骤1～3），产生规模为Nscale的初始种群。

4.2 迭代求解阶段

由于在生成初始种群的时候，并未从整个物理网络的角度来考虑节点负载和链路负载的均衡度，因此需要在迭代阶段对映射方案进行调整，改善请求接收成功率、整体资源负载均衡度、长期运营收益［12］等。

在WAVNM算法，每个粒子分别根据式（17）～（18）来进行速度与位置的更新。

其中，Vi为粒子的速度向量；Xi为粒子的位置向量；为第次迭代时，粒子的局部负载均衡值；为第i次迭代时，粒子的局部最优负载均衡值；为第i次迭代时，粒子的全局最优负载均衡值。

4.3 WAVNM算法流程

结合4.1和4.2节，WAVNM算法的流程如下：

1）根据式（16），计算每个粒子的

2）根据式（19），计算c1、c2和c3；

3）根据式（17），计算每个粒子的Vi+1；

4）根据式（18），计算每个粒子的Xi+1，即随机选取的物理节点nt∈Ns以概率Vi+1替代原ne和nt，选取nt的原则为参照初始化阶段的步骤（3）；

5）调整α和β，更新

6）如果达到最大迭代次数，迭代结束，输出最优的VNM方案；否则，跳到步骤1）开始下一轮迭代。

5 评价指标

为了能够全面评估本文所提出的负载感知的虚拟网络映射算法性能，本文所使用的评价指标有：请求接收成功率、整体资源负载均衡度和长期运营收益。

请求接收成功率定义为

其中，Rqss为虚拟网络映射请求成功数；Rqtl为虚拟网络请求数。

在t时刻，物理网络的运营收益定义为虚拟网络占用的带宽资源和CPU资源，即

那么，长期运营收益为

6 实验与分析

为了验证WAVNM算法性能，本文所使用的部分仿真参数如表1所示。同时，假设物理网络两节点相连的概率为0.02，在100个单位时间内虚拟网络请求的到达率服从λ=5的泊松分布，虚拟网络的生存时间服从λ=400的负指数分布，虚拟网络两节点相连的概率为0.5。

图1给出了请求接收成功率随虚拟网络请求数的变化情况。图2给出了整体资源负载均衡度随虚拟网络请求数的变化情况。图3给出了长期运营收益随时间的变化情况。

从图1中可以看出，当虚拟网络请求数比较少时，两种算法的请求接收成功率都在90%以上。因为在虚拟网络请求数比较少的情况下，物理网络中节点的可用CPU资源和链路的可用带宽都比较多，所以两种算法的请求接收成功率都比较高。随着虚拟网络请求数的增加，两种算法的请求接收成功率逐渐减少，但是WAVNM算法的性能一直优于BACA，这是因为WAVNM算法对节点负载和链路负载的优化有效消除了中间节点资源不足所造成的网络瓶颈，实现了更高的求接收成功率。

图2 整体资源负载均衡度

从图2中可以看出，WAVNM算法的负载均衡度到要低于BACA。这是因为，每当收到虚拟网络映射请求后，WAVNM算法会根据当前物理网络的负载情况自适应地调整节点负载调节因子和链路负载调节因子，使得物理网络中节点负载和链路负载更加的均衡，从而提高了整体资源负载均衡度。

从图3中可以看出，WAVNM算法的长期运营收益远大于BACA，这是因为与BACA相比，WAVNM算法拥有更高的请求接收成功率，在相同的时间内，WAVNM算法能够成功地构建更多的虚拟网络，获得比BACA算法更高的长期运营收益。

图3 长期运营收益

7 结语

传统网络基础架构面对不断涌现的新应用需求越来越力不从心，针对当前虚拟网络映射算法的不足，本文提出来一种流量感知的虚拟网络映射算法，该算法同时考虑节点均衡和链路均衡两个问题，并基于多目标优化方法有效实现了问题的综合求解，仿真实验证明所提出的算法具备有效性。

参考文献

［1］王聪，王翠荣，王兴伟等.面向云计算的数据中心网络体系结构设计［J］. 计算机研究与发展，2012，49（2）：286-293.

［2］梅丹，王公宝，胡伟文，张建军.舰船通信网络结构复杂性实证分析［J］.舰船电子工程，2014，34（8）：53-55.

［3］Wang Z，WU J，Wang Y，et al.Survivable Virtual Net⁃work Mapping Using Optimal Backup Topology in Virtual⁃ized SDN［J］.Communications，China，2014，11（2）：26-37.

［4］Cheng X，Su S，Zhang Z，et al.Virtual Network Embed⁃ding through Topology-aware Node Ranking［J］.Acm Sig⁃comm Computer Communication Review，2011，41（2）：38-47.

［5］Lischka J，Karl H.A Virtual Network Mapping Algorithm Based on Subgraph Isomorphism Detection［C］//Proceed⁃ings of the 1st ACM workshop on Virtualized infrastruc⁃ture systems and architectures.ACM，2009：81-88.

［6］蔡志平，刘强，吕品等.虚拟网络映射模型及其优化算法［J］.软件学报，2012，23（4）：864-877.

［7］陈晓华，李春芝，陈良育等.主动休眠节点链路的高效节 能 虚 拟 网 络 映 射［J］.软 件 学 报 ，2014（7）：1416-1431.

［8］李伟东，李建平.具有数目约束的负载均衡问题［J］.计算机科学，2015，42（7）：74-77.

［9］申元霞，王国胤，曾传华.相关性粒子群优化模型［J］.软件学报，2011，22（4）：696-708.

［10］王皓，高立群，欧阳海滨.多种群随机差分粒子群优化算法及其应用［J］.哈尔滨工程大学学报，2017，38（4）：652-660.

［11］吕振肃，侯志荣.自适应变异的粒子群优化算法［J］.电子学报，2004，32（3）：416-420.

［12］张建勋，古志民，郑超.云计算研究进展综述［J］.电子学报，2010，27（2）：429-433.