动态路径分裂的虚拟网络重构算法*

谢 枫，孟相如，孟庆微，于兴超

（1.空军工程大学信息与导航学院，西安 710077；2.山东省济南市章丘区第七中学，济南 250206）

0 引言

网络虚拟化是解决网络“僵化”的有效方法［1-3］，该方法支持多个虚拟网络（VN，Virtual Network）在同一个底层物理网络上运行。虚拟网络映射［4］是网络虚拟化研究中的关键，主要是根据虚拟网络的需求为其合理地分配资源。然而，受到人为或自然因素的影响，底层物理网络经常发生节点或链路故障，导致承载的虚拟网络故障［5］。若故障虚拟网络没有及时恢复，不仅影响正常的网络服务，还会产生相应的赔偿金，因此，降低底层物理网络故障带来的影响，对于保证虚拟网络的成功运行具有重要意义。

针对底层物理网络故障引起的虚拟网络故障，目前主要的解决策略为资源备份与即时迁移策略。文献［6］根据不同服务的保护质量，为每条虚拟链路预留一条或多条不相交的物理路径作为保护路径。文献［7-8］在为虚拟链路进行资源备份时，引入备份资源共享的方法，提高物理资源的使用率。文献［9］将整个底层物理网络资源的一部分直接划归为备份资源，发生故障时，将故障虚拟网络迁移到备份资源上，保证虚拟网络的正常运行。但资源备份策略必然降低物理网络资源的利用率，因此，文献［10-11］采用即时迁移策略，当故障发生后，将故障虚拟网络迁移到剩余的物理网络资源上，充分利用物理网络资源，但是在选择待迁移的目标节点时，并没有考虑其位置与所在区域的负载情况，同时，目标物理路径的选取都局限于单物理路径，从而影响了算法的性能。

针对已有算法存在的问题，本文提出一种动态路径分裂的虚拟网络重构算法（DPS-VNRA）。该算法首先根据故障虚拟网络可能产生的赔偿金、剩余的生存时间，以及故障虚拟链路与节点个数确定重构顺序；同时，考虑到在后期为故障虚拟链路寻找一条满足其资源需求的独立物理路径较为困难，本文借鉴文献［12-14］中路径分裂的思想，引入一种动态路径分裂的方法，该方法可以对每条故障虚拟链路进行合理的分裂，分别迁移到独立的物理路径上，以提高故障虚拟链路的恢复率；对于故障虚拟节点，在为其选取待迁移的目标物理节点时，结合就近原则与底层物理网络的负载情况，在故障虚拟节点恢复的基础上，进一步优化映射的结果。仿真结果表明，该算法降低了底层物理网络故障的影响，提高了虚拟网络的请求接受率与成功运行率。

1 问题建模

1.1 物理网络与虚拟网络

1.2 故障描述与重构模型

1.2.1 物理节点故障与重构模型

图1 故障虚拟网络重构示意图

1.2.2 物理链路故障与重构模型

1.3 评价指标

1.3.1 虚拟网络的请求接受率

虚拟网络的请求接受率为在时间T 内，映射成功的虚拟网络数目与虚拟网络总数目之比

式中，VNmaps（T）为映射成功的虚拟网络数目，VNmapt（T）为虚拟网络的总数目，δ 为趋近于0 的正数。

1.3.2 虚拟网络的成功运行率

虚拟网络的成功运行率为在时间T 内，成功运行的虚拟网络数目与虚拟网络总数目之比

1.3.3 虚拟网络的收益开销比

在t 时刻，每成功映射一个虚拟网络所产生的收益定义为

在t 时刻，每接受一个虚拟网络，底层物理网络的开销定义为

式中，参数β 用于调整节点开销和链路开销的权重，本文取值为1。h（ev）是虚拟链路映射到物理链路上经过的跳数。

假设在ts时刻，虚拟网络Gv发生故障，若Gv重构成功，则收益不变，开销可能发生变化，若失败，则定义为，同时释放占用的物理网络资源，产生赔偿金，且赔偿金存在的时间区间为为正常情况下Gv的结束时间。赔偿金定义为

式中，μ 为赔偿系数，本文取0.5。

虚拟网络的收益开销比定义为

2 算法设计

当底层物理网络在t 时刻发生故障之后，首先统计发生故障的虚拟网络，根据排序算法确定重构顺序。对每个故障虚拟网络，先进行故障情况2 和3的恢复，再进行故障情况1 的恢复。若失败，则释放占用的物理网络资源，产生赔偿金。

2.1 故障虚拟网络重构排序设计

本文从3 个方面来考虑虚拟网络的重构顺序：一是故障虚拟网络可能产生的赔偿金大小；二是赔偿金存在的时间长短；三是故障虚拟网络的重构难度，采用虚拟网络中故障节点与链路数目之和nf表示。综上所述，定义虚拟网络的重构排序函数（RSF，Sort Function of Reconfiguration）

2.3 酒糟有机肥不同用量对烤后烟叶化学成分的影响 从表3可以看出，各处理中部烤后烟叶主要化学成分指标除钾外均无显著差异，含有酒糟有机肥2 250 kg/hm2配施20%化肥的处理钾含量显著低于其他处理，其糖和淀粉含量均高于其他2个处理；3个处理的氯含量较低，均低于对照，其他化学成分含量各处理间以及各处理与对照间均无显著差异。

2.2 故障虚拟链路迁移算法

1）对故障虚拟链路按照带宽需求从高到底进行排列，依次选取进行迁移。

2）针对所选的故障虚拟链路，先将物理链路中不满足其带宽资源需求的物理链路删除，再使用最短路径算法寻找其两端节点所对应的目标物理节点之间的物理路径，若存在，进行迁移，否则进行路径分裂迁移。

3）对于进行路径分裂迁移的故障虚拟链路，使用最短路径算法找出两端物理节点之间所有的m条独立的物理路径l，按路径中最小的可用带宽bwmin（l）从大到小排列，再定义满足路径可分裂的条件为

表明如果序列中前k 条物理路径的bwmin（li）之和大于等于bw（），则可以分裂成k 条虚拟链路，每条虚拟链路的带宽需求分别为，将其按顺序分别映射到前k 条物理路径上。同时，k≤3 表明最多分裂成3 条虚拟链路进行迁移，避免因分裂过多而导致虚拟链路故障频发。若无法满足上述条件，则虚拟链路迁移失败。

故障虚拟链路迁移算法如表1 所示。

2.3 故障虚拟节点迁移算法

2）因为节点的迁移会引发邻接链路的迁移，所以在选取目标物理节点时必须兼顾邻接链路的资源负载情况，定义物理节点的区域负载（RL，Regional Load）为：

进一步定义物理节点的适应值函数（NFF，Node Fitness Function）为：表示物理节点上承载的虚拟网络个数，NM（）为与相邻的虚拟节点对应的目标物理节点集合，

3）按2 中的排序对每个物理节点进行尝试，直到邻接虚拟链路迁移成功，否则虚拟节点迁移失败。邻接虚拟链路的迁移方法与2.2 节的方法一致

故障虚拟节点迁移算法如下页表2 所示。

3 算法性能评估

本文主要通过仿真实验，以文献［15］中的映射算法为基础，分别在故障发生次数较少和较多的情况下，对表3 中4 种算法的性能进行比较。比较的指标为虚拟网络的请求接受率、成功运行率和收益开销比。

表2 故障虚拟节点迁移算法

表3 算法介绍

3.1 仿真环境设置

本文在仿真平台MATLAB 下进行实验评估。用于仿真的底层物理网络、虚拟网络拓扑以及故障发生模型的参数设置如下：

底层物理网络拓扑：节点个数为100，均匀分布在1 000×1 000 的底层网络平面上，节点间相连的可能性为50%。节点的可用计算资源和链路可用带宽服从［50，100］的均匀分布。

虚拟网络拓扑：每个虚拟网络的节点个数服从［2，10］的均匀分布，节点间相连的可能性为50 %，节点的计算资源需求与链路带宽需求服从［15，30］的均匀分布。虚拟网络到达时间服从参数为0.1 的Poisson 分布，平均100 时间单位内有10 个请求到达。虚拟网络的生存时间服从参数为300 个时间单位的指数分布。

故障发生模型：物理网络在故障较少和较多的情况下，发生故障的时间分别服从参数为0.05 和0.15 的Poisson 分布，持续时间均服从参数为150 个时间单位的指数分布。其节点故障和链路故障发生的概率分别为0.2 与0.8。仿真时间为3 000 个时间单位，在两种情况下分别进行10 次实验，取平均值作为最终结果。

3.2 仿真结果分析

3.2.1 请求接受率

图2 请求接受率

如图2 所示，在底层物理网络故障较多的情况下，4 种算法的请求接受率都低于故障较少的情况。其中，DPS-VNRA 与IP-DR 不采用资源备份策略，在映射阶段就可以充分利用底层物理网络资源，接受更多的虚拟网络，故请求接受率更高。同时，DPS-VNRA 由于在故障恢复的同时进行底层物理网络的负载均衡，所以，该算法的请求接受率优于IP-DR。而DPS-VNRA-B 与IP-DR-B 都将一部分底层物理网络资源划归为备份资源，在映射阶段无法使用，所以请求接受率较低。

3.2.2 成功运行率

图3 成功运行率

如图3 所示，虚拟网的成功运行率随故障的增多而下降，都低于相同情况下的请求接受率。DPS-VNRA 在故障虚拟网络重构时采用了动态路径分裂的方法，提高了故障虚拟链路的恢复率，同时考虑就近原则，将故障虚拟节点迁移到区域负载轻且承载虚拟网络少的物理节点上，一方面增加邻接虚拟链路迁移成功的概率，另一方面也减少了因某个物理节点故障而引发大量虚拟网络故障的情况，提高了虚拟网络成功运行的概率。IP-DR 只采用就近原则策略，容易加剧底层物理网络负载与分布不均的情况，导致大量虚拟网络发生故障，所以IP-DR 的成功运行率低于DPS-VNRA。随着故障发生次数的增多，剩余物理网络资源无法满足故障虚拟网络的重构需求，所以，DPS-VNRA 与IP-DR 的成功运行率与请求接受率之间的差距加大。而DPS-VNRA-B 与IP-DR-B 由于采用备份资源策略，有充足的物理网络资源进行故障虚拟网络的重构，所以在两种故障情况下，二者的运行成功率都相近且与请求接受率无明显差距，甚至优于IP-DR，但受限于较低的请求接受率，一直低于DPS-VNRA。同时，当故障发生次数的增多，DPS-VNRA-B 与 IP-DR-B 的成功运行率与DPS-VNRA 之间的差距减小。

3.2.3 收益开销比

如图4 所示，在两种故障情况下，DPS-VNRA-B 与IP-DR-B 的收益开销比都是最优的。而DPS-VNRA 由于采用了动态路径分裂的方法，使分裂的虚拟链路映射到较长的物理路径上，导致链路映射开销增大，所以收益开销比与DPS-VNRA-B与IP-DR-B 相比有所降低。IP-DR 因为存在较多故障虚拟网络无法恢复，产生了大量的赔偿金，所以收益开销比较低。

图4 收益开销比

4 结论

本文着重研究了由底层物理网络故障导致的故障虚拟网络的恢复问题，提出了一种动态路径分裂的虚拟网络重构算法。该算法首先确定故障虚拟网络的重构顺序，其次采用动态路径分裂方法以提高故障虚拟链路的恢复率，同时在确保故障虚拟节点恢复的情况下，结合负载均衡与就近原则，一方面优化底层物理网络的负载情况，减小了大量虚拟网络出现故障的情况，也保证了较小的资源开销。仿真结果表明，该算法与之前所提算法相比，提高了虚拟网络的请求接受率与成功运行率，但由于采用了动态路径分裂的方法，导致链路映射的开销增大，收益开销比有所下降，略低于备份算法。所以在下一步的研究中，将进一步考虑如何减小重构过程中的资源开销，同时设计合理的备份算法与之结合，进一步提高算法的性能。