节点与链路协同映射的生存性虚拟光网络映射算法

朱国晖，梁申麟，李 庆

（西安邮电大学通信与信息工程学院，西安 710121）

0 概述

随着云计算、大数据、物联网等新型网络服务的迅猛发展，人们对网络服务的需求发生了巨大变化，并趋于向高带宽、高突发、低延迟的方向发展［1］。为更好地利用光资源来适应新的网络业务，新兴的弹性光网络（Elastic Optical Network，EON）因为具有灵活的频谱分配和可扩展的数据传输速率等特点，被作为下一代智能光网络［2］。与传统的WDM 网络相比，EON 采用粒度更小的频谱栅格，可以动态地根据用户对带宽的实际需求，采取不同的频谱资源分配方法，设置最佳的调制格式，因此极大地提高了频谱利用率［3-5］。

近年来，网络虚拟化技术克服了传统互联网的僵化问题，在共享公共物理基础设施方面展现了极大的灵活性和可扩展性，促进了广泛多样的云服务和应用的发展［6］。光网络是保证高带宽、低时延传输的基础部分，将网络虚拟化技术引入EON 被认为是解决网络刚性问题和资源利用率较低的有效方法［7-8］。而网络虚拟化技术的引入也会带来一些新的挑战，在进行虚拟网络映射时涉及到为虚拟光网络请求分配底层物理网络资源，还需满足多方面约束条件，如节点计算资源、链路频谱资源、映射位置、底层网络拓扑要求等［9］。而且，底层网络中故障难免发生，自然灾害或人为操作可能会导致节点或链路损坏，无法正常工作，影响映射至物理网络的虚拟网络，降低用户体验，给运营商带来不必要的经济损失［10-12］。

针对虚拟光网络的生存性映射问题，目前已有很多文献提出了相关的解决策略。文献［13］在保证VON 生存性的前提下综合考虑节点间距离和频谱碎片度，设计一种链路频谱资源消耗较小的节点与链路协同映射策略，提高了链路频谱资源利用率和VON 映射成功率。文献［14］采用共享保护方法将虚拟光网络映射到物理网络，在映射过程中考虑链路的频谱一致性，以增强虚拟节点和虚拟链路映射时的相关性，降低了频谱资源碎片度。文献［15］针对备份资源的冗余度相对较高的问题，考虑物理链路的故障概率，以链路安全性作为重要排序指标，并允许路径分割来提升虚拟光网络的映射成功率，但存在链路碎片度较高的问题。文献［16］提出一种基于自适应路径分裂的映射策略，利用部分备份资源提供针对单链路故障的完全保护，引入频谱窗选择机制以降低频谱碎片，降低了预留资源的冗余度，然而路径分裂增加了虚拟链路映射失败的发生率。

针对EON 中虚拟网络映射时出现的单链路故障问题，本文考虑链路映射开销，提出节点与链路协同映射的生存性虚拟光网络映射算法，并为虚拟光网络的部分重要链路提供保护。该算法在虚拟网络请求时依据虚拟节点的重要度将虚拟节点与链路分别划分为两种不同类型，并设计不同策略完成映射。在链路映射时将链路频谱碎片度作为映射开销的重要参数，利用匈牙利算法解出主动链路的最优映射方案，降低虚拟链路的映射总开销以节省频谱资源，提升后续虚拟网络请求的映射成功率。在此基础上，对虚拟网络部分重要的工作路径提供保护路径，并采用首端与末端联合的方式进行频谱资源分配，以在保证虚拟网络生存性的同时，减少物理链路频谱碎片的产生。

1 虚拟光网络映射问题

本节从底层物理网络和虚拟网络请求的角度描述网络模型，介绍可生存性虚拟光网络映射的目标和约束条件。

1.1 网络模型

弹性光网络表示为Gs=(Ns,Es,Cs,Bs)，其中：Ns表示物理节点集；Es表示物理链路集；Cs表示物理节点的可用计算资源；Bs表示物理链路中可用频谱资源。虚拟网络请求可以表示为Gv=(Nv,Ev,Cv,Bv)，其中：Nv表示虚拟节点集；Ev表示虚拟链路集；Cv表示对应虚拟节点所需计算资源；Bv表示对应虚拟链路所需频谱数。

1.2 目标函数与约束条件

本文以虚拟网络请求的平均资源消耗最小为目标，研究弹性光网络中可生存性虚拟网络映射问题，优化目标如式（1）所示，约束条件如式（2）～式（9）所示。

其中：式（2）确保一个虚拟网络的虚拟节点只能被映射到一个物理节点；式（3）确保虚拟节点所映射物理节点的节点度大于等于其自身节点度；式（4）和式（5）确保有足够的计算资源和频谱资源来满足虚拟节点和虚拟链路的需求；式（6）确保对于给定的虚拟链路其工作路径和保护路径不相交；式（7）和式（8）指定所映射的物理链路必须使用连续的频谱隙；式（9）确保给定的频隙最多只能由一个虚拟请求使用。

本文符号说明如表1 所示。

表1 符号说明Table 1 Symbol description

2 生存性虚拟光网络算法设计

2.1 虚拟节点重要度

在虚拟光网络映射过程中，因为不同虚拟节点的节点度与计算资源需求不同，其邻接链路对频谱资源的需求也不同，所以采用文献［17］定义虚拟节点的综合评价：

其中：e表示节点nV的邻接链路；为虚拟节点的节点度。由于本文采用节点与链路交替进行的方法完成虚拟网络映射，因此虚拟节点所映射的顺序和位置在一定程度上也影响着链路映射情况。

2.2 虚拟网络节点与链路分类策略

根据式（10）计算其虚拟节点重要度，将重要度最大的虚拟节点选取为主动节点放入主动节点集合NVZ中，而其邻接节点则选取为被动节点放入被动节点集合NVB中。剔除已分类节点，将剩余未分类节点再次按照上述过程排序并分类，重复上述过程，直至所有虚拟节点均完成分类并放入对应的节点集合中。如图1 所示，经计算可得出节点B重要度最大，选取为主动节点，因此与节点B邻接的节点均为被动节点。而节点E和节点D还未分类，需再次对其排序，最后将重要度较大的节点E放入主动节点集合NVZ中，与其相连的节点D放入被动集合NVB中，此时虚拟分类已完成。

图1 虚拟网络模型Fig.1 Virtual network model

虚拟节点分类完成后再继续进行虚拟链路的分类，划分依据是判断链路两端的虚拟节点已映射个数，若该链路仅有一个虚拟节点被映射，则该虚拟链路被划分为主动链路，若该链路两端的虚拟节点均已被映射，则该虚拟链路被划为被动链路。如主动节点B映射成功后，其邻接链路B-A、B-F、B-C即作为主动链路被划分至集合EVZ中，当主动链路均完成映射时，虚拟节点A、F、C的位置随之确定，链路C-D、C-E、A-F、E-F两端节点映射均已完成，则作为被动链路被划分至被动链路集合EVZ中，完成后续链路映射。

2.3 物理节点重要度

物理节点的选取决定着主动节点映射能否成功映射，也对后续主动链路能否在较小跳数内映射成功有着重要影响。因此，当选择物理节点映射时，在考虑该节点计算资源和节点度是否满足需求的前提下，应将其邻接链路的频谱资源和邻接节点的计算资源使用情况作为重要参考指标，如式（11）所示：

2.4 基于匈牙利算法的虚拟链路映射策略

在虚拟链路映射时，综合考虑其映射至物理链路所需频谱资源与映射后物理链路的频谱碎片程度［18］，构建映射路径映射开销计算公式：

图2 所示为虚拟网络请求的节点计算资源需求与链路频谱需求。图3 所示为底层物理节点B及其邻接链路的频谱使用状态。若虚拟网络请求中主动节点a成功映射至物理网络中节点B时，则开始映射与其相连的主动链路，虚拟链路a-b、a-c、a-d可分别映射至物理链路B-C、B-D、B-E、B-F等4 条链路方向。若所选映射物理链路的频谱资源和下一跳节点计算资源均满足需求，则可成功映射并确定被动节点的映射位置，若所选链路频谱资源满足需求而下一跳节点计算资源不足，则将该节点加入路径集合，并继续计算该节点的下一跳节点及路径频谱资源是否满足映射需求，直至找到满足映射需求的物理路径和被动节点映射位置；否则，说明该链路方向无法成功映射。

图2 虚拟网络请求Fig.2 Virtual network request

图3 底层光网络模型Fig.3 The underlying optical network model

以图2 中虚拟链路a-c为例，将其分别映射至候选映射路径上时，利用式（13）计算其映射开销，若物理节点B的邻接节点（C，D，E，F）计算资源充足可满足主动节点a的邻接节点（b，c，d）的计算资源需求，则可计算其映射开销分别为：8、N（虚拟链路B-D无法满足其频谱资源需求），20、8。再分别计算其他主动链路映射至候选物理链路不同方向时的映射开销。如表2 所示，可将链路映射问题转为指派问题，若候选可映射物理链路数大于待映射虚拟链路时，则可对其补0 使其构成标准指派问题［19］。使用匈牙利算法求解最优映射方案，得出最小虚拟链路映射总开销为23，即应将虚拟链路a-b映射至物理链路B-C，a-c映射至B-F，a-d映射至B-D，该链路映射方案不仅节约了频谱资源消耗，而且也降低了物理链路的频谱碎片度。

表2 虚拟链路映射方案Table 2 Virtual link mapping scheme

2.5 首末端联合频谱分配方法

如图4 所示，若按照FF（First-Fit）频谱分配法为保护路径分配频谱块6 与7，而频谱块8 则将作为频谱碎片被浪费，不利于为后续的业务进行频谱资源分配。当使用FLF（First-Last-Fit）频谱分配方法时，将链路频谱资源分为工作和保护2 个频谱区，此分区方法要求工作和保护路径在进行频谱分配时尽量使用自己分区的资源，而频谱资源不足时依然可以跨区使用［20］。为保护路径分配频谱时，采用LF（Last-Fit）频谱分配法为其分配频谱块15 与16，避免了频谱碎片的产生，提高了频谱资源的利用率。

图4 FLF 频谱分配示意图Fig.4 Schematic diagram of FLF spectrum allocation

生存性虚拟光网络算法如下：

输入物理网络GS，虚拟网络请求GV

输出映射结果

步骤1根据式（10）计算虚拟节点重要度，并将其降序排列。

步骤2将首个节点放入主动节点集合内，其他与之连接的节点放入被动节点集合内。

步骤3将剩余节点按照步骤1、步骤2 重复执行直至所有节点分类完毕。

步骤4求出满足主动节点计算资源和节点度需求的物理节点候选集，按式（11）计算其物理节点重要度并降序排列。

步骤5将主动节点映射至物理节点重要度最大的节点上。

步骤6将主动链路根据频谱资源需求降序排列，确定其映射顺序。

步骤7使用式（13）计算将主动链路分别映射至候选不同物理链路上的映射开销。

步骤8使用匈牙利算法求解出映射开销最小的方案。

步骤9将主动链路依照所求方案按序映射并分配频谱资源同时确定与之相连的被动节点的映射位置。

步骤10重复步骤4～步骤9 直至所有的节点和主动链路映射成功。

步骤11用KSP 算法为被动链路分配映射开销较小的工作路径，并分配频谱资源。

步骤12再以首个主动节点为根节点用prim 算法计算虚拟网络请求的最小生成树。

步骤13用KSP 算法为该最小生成树链路分配映射开销较小的保护路径。

步骤14返回映射结果。

CMST-HA 算法的虚拟节点和物理节点排序时间复杂度分别为O（Nv×lbNv）与O(Ns×F)，工作路径与的选择和频谱分配复杂度为O(K2×F2×(|Ls|+Ns×lbNs))，保护路径的选择和频谱分配时间复杂度为O(|Ls|+Ns×lbNs)，其中：F为链路可用频谱数；|Ls|为物理链路数。因此，CMST-HA 算法的算法复杂度为O（Nv×lbNv+Ns×F+K2×F2×（|Ls|+Ns×lbNs)+|Ls|+Ns×lbNs)。

3 仿真与性能分析

3.1 实验环境配置

本文所提算法在MATLAB R2018a 中编程实现，在拓扑图为24 个节点与43 条链路的USNET 网络中进行仿真，且虚拟网络请求拓扑均为连通图，具体参数如表3 所示。为保证仿真结果的相对准确性，每组仿真运行5 000 组虚拟网络，并取3 次仿真的平均值作为最终结果。

表3 实验配置参数Table 3 Experimental configuration parameters

3.2 结果分析

将本文所提CMST-HA 算法与文献［21］RVNM算法、文献［22］CMST 算法进行对比，在不同网络负载下，从虚拟网络的请求阻塞率、虚拟网络映射平均频谱资源消耗、链路映射平均跳数和物理网络收益这4 个方面来所验证提方法性能。3 种算法的简要描述如表4 所示。

表4 对比算法描述Table 4 Comparison algorithm description

表5 所示为3 个算法的时间复杂度对比，均在多项式时间内可解。3 个算法的虚拟节点和物理节点排序时间复杂度相同，主要区别在于工作路径和保护路径的选择与频谱分配时间复杂度不同。

表5 算法复杂度对比Table 5 Comparison of algorithm complexity

RVNM 算法需在确定工作路径或保护路径后，不断更新链路映射方案以降低频谱消耗，因而复杂度较高，CMST 算法只需在确定工作路径后为虚拟网络的最小生成树链路提供保护路径，复杂度较低，而CMST-HA 算法为降低工作路径的频谱资源消耗与链路频谱碎片度，引入匈牙利算法进行映射方案的求解，故复杂度位于两者之间。

图5所示为3种算法在不同网络负载下的阻塞率。CMST 算法和CMST-HA 算法均采用节点与链路协同映射的方式，选择跳数较小的物理路径进行映射，并通过为虚拟网络的最小生成树链路提供保护路径，降低了频谱资源消耗。但RVNM 算法和CMST 算法在频谱分配时没有考虑频谱碎片的因素，增加了VON 请求被阻塞的概率，而CMST-HA 算法采用匈牙利算法求解主动类型的虚拟链路最优映射方案进一步降低了频谱资源的消耗与链路频谱碎片度，另外采用工作路径和保护路径分离的首端末端联合频谱分配方法，提升了频谱资源的利用率，进而增加了后续虚拟网络请求映射成功的机率，因此CMST-HA 算法的阻塞率最低。

图5 3 种算法在不同网络负载下的阻塞率Fig.5 The blocking rate of three algorithms under different network loads

图6 所示为3 种算法在不同网络负载下链路映射平均跳数。

图6 3 种算法在不同网络负载下链路映射平均跳数Fig.6 The average number of link mapping hops for the three algorithms under different network loads

RVNM 算法在VON 映射时采用两阶段映射方法，将虚拟节点映射至可靠性较高的物理节点上，但未考虑节点间的映射距离，导致虚拟链路的映射跳数较大。CMST 算法在链路映射时忽视了主动节点间的位置约束，导致虚拟网络各部分分布较远，增加了被动链路的映射资源消耗。CMST-HA 算法将主动节点映射至邻接链路与邻接节点资源丰富物理节点上，提高了主动链路在较小跳数内映射成功的机率，链路映射时采用匈牙利算法求解最优映射方案降低了物理链路的频谱碎片度与频谱资源的消耗，提升了后续虚拟链路映射成功的机率。因此，其链路映射平均跳数最短。

图7 分析了不同虚拟网络请求数量下的虚拟网络映射频谱资源消耗。CMST 算法和CMST-HA 算法都是为虚拟网络请求的最小生成树提供保护路径，相较RVNM 算法为每条虚拟链路都提供保护路径节省了频谱资源。由图6 可知，CMST-HA 算法的链路映射平均跳数是三者中最小的，且虚拟链路的频谱需求为定值，因此跳数越小虚拟网络映射所占用频谱资源越少。

图7 不同虚拟网络请求数量下虚拟网络映射频谱资源消耗Fig.7 Spectral resource consumption of virtual network mapping under different virtual network requests

图8 所示为3 种算法的物理网络收益均随着虚拟网络数量的增加而增加，但CMST-HA 算法的收益比其他2 个对比算法更高，因为该算法具有较低的虚拟网络请求阻塞率和平均频谱资源消耗，能使更多的虚拟网络成功映射至底层物理网络，所以物理网络收益也更高。

图8 物理网络收益Fig.8 Physical network benefits

4 结束语

本文针对EON 中可生存性虚拟网络映射问题，提出一种针对单链路故障的专用保护算法。采用节点和链路协同映射的方法完成虚拟网络映射并对其最小生成树链路进行专有保护，在链路映射时选择映射开销较低的映射方案减少频谱消耗，在频谱分配时采用首末端联合分配的方法提升频谱资源利用率。仿真结果表明，CMST-HA 算法可以提高虚拟网络请求的阻塞率，降低平均频谱资源消耗。本文研究的是单域VONE，当涉及到多域VONE 时会产生域内和域间的链路故障问题，因此探索多域链路的生存性虚拟光网络映射算法将是下一步的研究方向。