虚拟网络映射(VNE，virtual network embedding)实现了虚拟网络请求(VNR，virtual network request)到底层物理网络(SN，substrate network)的映射.生存性虚拟网络映射(SVNE，survivable virtual network embedding)是更加严格的VNE，保障被映射成功的VNR在SN发生故障时依然能够正常提供服务.

软件定义网络(SDN，software defined network)是一种新型网络架构，通过分离控制平面和数据平面实现对网络流量的灵活控制.流表是SDN交换机进行数据包转发处理的根本依据，直接影响SDN数据转发的效率.所以相较传统网络，SDN中的SVNE需要额外考虑物理节点的流表空间资源^[1].

现有针对SVNE的研究主要分为两类. Yu等^[2]提出了基于扩展虚拟网络请求(A-VNR，augmented VNR)的主动保护策略，即在映射前为VNR置备冗余的节点和链路. Hu等^[3]则进一步加入了节点的位置约束.但是这些主动保护策略增加了VNR资源需求，容易导致映射失败，且仅使用单一备份资源进行故障恢复，故障恢复成功率较低. Bo等^[4]提出的被动恢复策略则不需要预置备份资源，其基于当前网络剩余资源进行故障恢复. Xiao等^[5]将物理资源划分为主要和次要资源，分别用于VNR映射和故障恢复.这些被动保护策略虽然没有增加额外的资源消耗，但是增加了故障恢复阶段的耗时，效率较低.

为改善这两类策略会消耗更多底层网络资源以及故障恢复资源单一问题，针对SDN提出了一种基于网络剩余资源可伸缩备份虚拟资源的SVNE算法——SDN-ScaSVNE.当网络剩余资源充足时才对有需要的虚拟节点和链路提供备份，故障恢复阶段会优先使用备份资源，否则引入被动恢复策略重映射因故障而失效的虚拟节点和链路.

1 网络模型和问题描述 1.1 网络模型

图 1所示为SVNE的网络模型.其中SN被抽象为无向图G^S=(N^S, E^S, C^S), N^S和E^S分别为物理节点和链路集合，节点资源包括CPU计算资源c(s)和流表资源h(s)，节点的位置设为loc(s)，链路资源包括带宽资源b(l_mn). C^S为约束条件，包括节点位置约束、CPU和流表资源约束以及链路带宽资源约束.

VNR被抽象为无向图G^V=(N^V, E^V, C^V)，N^V和E^V分别为虚拟节点和链路集合. C^V为约束条件，包括节点位置loc(v)、请求的CPU资源c(v)和流表资源h(v)以及链路带宽资源b(e_i^V). A-VNR表示采用k冗余备份策略^[2]得到的扩展VNR，k为VNR中重要节点个数，每个重要节点及其关联链路都会预置备份.运行时间T内所有故障节点集合为

$ {F^N} = \bigcup\limits_{i = 0}^T {\{ {f_{\rm{s}}}\} } $

(1)

其中f_s表示某个时刻发生故障的物理节点.

1.2 问题描述

SVNE通过提高请求接受率和故障恢复成功率，最终提高SN的网络运营收益. SDN中节点资源模型不同于传统网络，因此单个VNR收益重定义为

$ R({G^{\rm{V}}}) = \zeta \sum\limits_{v \in {N^{\rm{V}}}} {c\left( v \right)} + \lambda \sum\limits_{v \in {N^{\rm{V}}}} {h\left( v \right)} + \pi \sum\limits_{e_{_i}^{\rm{V}} \in {E^{\rm{V}}}} {b(e_{^i}^{\rm{V}})} $

(2)

其中：ζ、λ和π分别为虚拟节点CPU、流表以及虚拟链路带宽的映射单价，SN运营商可根据实际情况调节.这里假定成本单价均为1个单位，映射单价均为10个单位，即每种资源可获得10倍利润.

在VNR运行时间内若有物理节点发生故障，则故障恢复失败所导致的赔偿金定义为

$ P\left( {{f_s}, {G^{\rm{V}}}} \right) = \left\{ \begin{array}{l} \rho R\left( {{G^{\rm{V}}}} \right), \;\;故障恢复失败\\ 0, \;\;\;未受f_s影响或故障恢复成功 \end{array} \right. $

(3)

其中ρ为赔偿金和收益的可调比例，设为0.2.

根据式(2)和式(3)得出网络运营总收益为

$ {\rm{Profit}}\left( T \right) = \sum\limits_{{G^{\rm{V}}} \in S\left( T \right)} {\{ R({G^{\rm{V}}}) - \sum\limits_{{f_s} \in {F^N}} {P({f_s}, {G^{\rm{V}}})} \} } $

(4)

其中S(T)和F^N表示在SN提供服务的总时间T内被成功映射的VNR集合以及故障节点集合.

网络开销定义为SN为VNR分配的资源总和

$ \begin{array}{l} C({G^{\rm{V}}}) = \left[ {\sum\limits_{e_i^{\rm{V}} \in {E^{\rm{V}}}} {\sum\limits_{{l_{mn}} \in {E^{\rm{S}}}} {b_{_{mn}}^{^i}} } + {b_b}} \right] + \left[ {\sum\limits_{v \in {N^{\rm{V}}}} {c\left( v \right)} + {c_b}} \right] + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left[ {\sum\limits_{v \in {N^{\rm{V}}}} {h\left( v \right)} + {h_b}} \right] \end{array} $

(5)

其中：b_mnⁱ为物理链路l_mn为第i条虚拟链路e_i^V分配的带宽资源，c_b和h_b分别为备份的CPU和流表资源，b_b为带宽备份资源.由式(5)得出SN总开销为

$ {\rm{Cost}}\left( T \right) = \sum\limits_{{G^{\rm{V}}} \in S\left( T \right)} {C({G^{\rm{V}}})} $

(6)

2 用于VNE求解的线性规划模型

Chowdhury等^[6]通过协同节点和链路的两阶段映射优化了VNE问题的求解.首先根据式(7)的位置约束得到每个虚拟节点的可映射物理节点集合：

$ \phi \left( v \right) = \{ s \in {N^{\rm{S}}}|{\rm{Dis}}({\rm{loc}}\left( v \right), {\rm{loc}}\left( s \right)) \le {r^v}\} $

(7)

其中：Dis(loc(v), loc(s))表示虚拟节点v的目标映射位置与物理节点s的实际位置之间的距离；r^v表示虚拟节点v能够接受的最大Dis值.

这样SN中的节点可以被看成划分在了多个簇中，为每个簇添加一个节点和多条链路，分别称之为元节点和元链路.每个元节点都代表了一个虚拟节点，它与相应簇ϕ(v)中的每个物理节点都通过一条带宽资源无穷大的元链路相连, 最终得到了扩展的SN抽象图G^S′=(N^S′, E^S′).因此VNE问题转化为了混合整数多商品流问题，VNR中的每条虚拟链路即为一条商品流，起点和终点是不同的元节点，它们各自只能选择一条元链路流入或流出.这一限制条件将确定每个虚拟节点最终被映射到哪个物理节点上.

但是该算法没有考虑到SN中节点之间的差异，笔者认为，如果在映射时对它们区别对待可以提高请求接受率以及SN的资源利用率，因此提出了用重要性因子来区分物理节点，计算方法将在3.2节详细介绍.

由于混合整数规划的求解是NP难问题，所以Chowdhury等可通过松弛整数条件将其转化为线性规划模型.笔者做了进一步改进，具体如下.

1) 变量设定

b_mnⁱ是物理链路l_mn为第i条虚拟链路分配的带宽资源. x_mn为二元值，若$ \mathop \sum \limits_i (b_{_{mn}}^{^i} + b_{_{nm}}^{^i}) > 0 $则为1；否则为0，整数条件松弛后为0~1之间的小数.

2) 目标函数定义

扩展式(5)，以最小化每个VNR的映射开销

$ \begin{array}{l} {\rm{min\{ }}\sum\limits_{{l_{mn}} \in {E^{\rm{S}}}} {\frac{1}{{{R_{\rm{E}}}({l_{mn}}) + \delta }}} \sum\limits_i {b_{_{mn}}^{^i}} + \\ \sum\limits_{s \in {N^{\rm{S}}}} {\frac{{{\rm{Imp}}\left( s \right)}}{{{R_{{\rm{N, C}}}}\left( s \right) + \delta }}} \sum\limits_{z \in {N^{{\rm{S}}' }}\backslash {N^{\rm{S}}}} {{x_{zs}}c\left( z \right)} + \\ \sum\limits_{s \in {N^{\rm{S}}}} {\frac{{{\rm{Imp}}\left( s \right)}}{{{R_{{\rm{N, H}}}}\left( s \right) + \delta }}\sum\limits_{z \in {N^{{\rm{S}}' }}\backslash {N^{\rm{S}}}} {{x_{zs}}h\left( z \right)} } \} \end{array} $

(8)

其中R_E(l_mn)、R_{N, C}(s)和R_{N, H}(s)分别为物理链路l_mn的剩余带宽资源、物理节点s剩余的CPU和流表资源.各项分别除以对应的剩余资源值，以保证那些可用资源更多的物理节点和链路更容易被选中，从而达到负载均衡的效果.极小值δ用于防止分母为零. Imp(s)为物理节点s的重要性因子.

3) 约束条件

① 资源约束

对∀m, n∈N^S′, ∀z∈N^S′\N^S, ∀s∈N^S, 有

$ \sum\limits_i {(b_{_{mn}}^{^i} + b_{_{nm}}^{^i}) \le {R_{\rm{E}}}({l_{mn}}){x_{mn}}} $

(9)

$ {x_{zs}}c\left( z \right) \le {R_{{\rm{N, C}}}}\left( s \right) $

(10)

$ {x_{zs}}h\left( z \right) \le {R_{{\rm{N, H}}}}\left( s \right) $

(11)

以上3个式子包含了链路的带宽资源约束、节点的CPU和流表资源约束.其中式(9)确保物理链路l_mn所有方向上的流量总和不超过其可用带宽资源.

② 流量约束

$ \sum\limits_{n \in {N^{{\rm{S}}' }}} {b_{_{mn}}^{^i}} - \sum\limits_{n \in {N^{{\rm{S}}' }}} {b_{_{nm}}^{^i}} = 0, m \in {N^{{\rm{S}}' }}\backslash \{ {s_i}, {t_i}\} $

(12)

$ \sum\limits_{n \in {N^{{\rm{S}}'}}} {b_{_{{s_i}n}}^{^i}} - \sum\limits_{n \in {N^{{\rm{S}}' }}} {b_{n{s_i}}^{^i}} = b(e_i^{\rm{V}}) $

(13)

$ \sum\limits_{n \in {N^{{\rm{S}}' }}} {b_{{t_i}n}^{^i}} - \sum\limits_{n \in {N^{{\rm{S}}' }}} {b_{n{t_i}}^{^i}} = - b(e_i^{\rm{V}}) $

(14)

其中：b(e_i^V)表示虚拟网络G^V的第i条虚拟链路请求的带宽资源，它的起点和终点分别被映射到了物理节点s_i和t_i上.式(12)~(14)表明，除源节点s_i和宿节点t_i外，每个节点流入和流出的流量应该相等.

③ 其他约束

$ \sum\limits_{s \in \phi \left( z \right)} {{x_{zs}} = 1} , \forall z \in {N^{{\rm{S}}' }}\backslash {N^{\rm{S}}} $

(15)

$ \sum\limits_{z \in {N^{{\rm{S}}' }}\backslash {N^{\rm{S}}}} {{x_{zs}} \le 1} , \forall s \in {N^{\rm{S}}} $

(16)

式(15)和(16)分别表示确保每个元节点只选择一个物理节点及每个物理节点最多只被一个元节点选中^[6].

3 SDN-ScaSVNE算法 3.1 SDN-ScaSVNE算法框架

1) 度量物理节点重要性.计算节点的重要性因子，并将节点划分为重要节点和非重要节点两类.

2) 扩展VNR.使用k冗余备份策略^[2]得到A-VNR.

3) 使用SDN-BackupVNE算法映射A-VNR.

4) 使用SDN-ScaREC算法完成故障恢复.

3.2 物理节点重要性因子

现有针对SDN的VNE算法并未给出节点重要性计算方法，笔者从资源重要性和网络拓扑重要性两方面进行考虑.

参照文献[1]，对于每个物理节点，资源重要性的度量需要考虑节点自身资源以及邻居链路带宽和，而在SDN中节点自身资源包括CPU和流表资源.为了简化计算过程，网络拓扑重要性的度量则仅考虑邻居节点对该节点的贡献.对∀s∈N^S，计算方法如下：

1) 计算资源重要性

$ {I_{{\rm{cap}}}}\left( s \right) = \left[ {\lambda c\left( s \right) + \left( {1 - \lambda } \right)h\left( s \right)} \right]\sum\limits_{w \in {N_{{\rm{adj}}}}\left( s \right)} {b({l_{sw}})} $

(17)

其中：N_adj(s)为物理节点s的邻居节点集；l_sw为物理节点s和邻居节点w的相连链路；λ为可调参数，用于调节节点自身资源中CPU和流表的重要性比例，本方案取值0.6，即CPU比流表资源更重要.

2) 计算网络拓扑重要性

$ {I_{{\rm{top}}}}\left( s \right) = \sum\limits_{w \in {N_{{\rm{adj}}}}\left( s \right)} {\frac{{{I_{{\rm{cap}}}}\left( w \right)}}{{{\rm{deg}}\left( w \right)}}} $

(18)

其中deg(w)表示邻居节点w的度.

3) 根据式(17)和(18)得出节点重要性因子

$ {\rm{Imp}}\left( s \right) = {I_{{\rm{cap}}}}\left( s \right) + {I_{{\rm{top}}}}\left( s \right) $

(19)

4) 对于每个节点，若满足式(20), 则将节点加入重要节点集合N_Imp^S，否则加入N_Nimp^S

$ \begin{array}{l} {\rm{Imp}}\left( s \right) \ge \mathop {{\rm{min}}}\limits_{w \in {N^{\rm{S}}}} \{ {\rm{Imp}}\left( w \right)\} + \\ \eta (\mathop {{\rm{max}}}\limits_{w \in {N^{\rm{S}}}} \{ {\rm{Imp}}\left( w \right)\} - \mathop {{\rm{min}}}\limits_{w \in {N^{\rm{S}}}} \{ {\rm{Imp}}\left( w \right)\} ) \end{array} $

(20)

其中：η用于调节节点重要性因子的阈值，超过这个阈值则为重要节点；否则为非重要节点. η取值0.7.

5) 对节点的重要性因子进行归一化处理

$ {\rm{Imp}}\left( s \right) = \frac{{{\rm{Imp}}\left( s \right)}}{{\mathop {{\rm{max}}}\limits_{w \in {N^{\rm{S}}}} \{ {\rm{Imp}}\left( w \right)\} }} $

(21)

3.3 映射算法SDN-BackupVNE

改进了随机型映射算法R-ViNE^[6]，使其适用于A-VNR的映射.

1) 构造并求解第2节描述的线性规划模型.

2) 使用R-ViNE中的随机型方式映射虚拟节点.

3) 虚拟节点备份映射.在虚拟节点的可映射节点集ϕ(v)中，若存在一个或多个物理节点已为其他虚拟节点提供了备份映射，则从这些节点中选择提供备份资源最多的作为当前虚拟节点的备份映射节点(这种共享策略可以有效降低资源消耗)；否则使用随机型方式完成节点的备份映射.若ϕ(v)为空，则不备份该虚拟节点，实现了虚拟节点的可伸缩备份.

4) 虚拟链路映射.若VNR支持路径分裂，使用多商品流(MFC，multi-commodity flow)算法完成链路映射；否则使用K最短路径(KSP，K shortest paths)算法完成链路映射.

5) 虚拟链路备份映射.对存在备份节点的虚拟节点，使用KSP算法为它的每条关联虚拟链路提供备份路径.如果某些关联链路无可映射的备份路径，则不进行备份，实现了虚拟链路的可伸缩备份.

3.4 故障恢复算法SDN-ScaREC

不同于文献[2-3]中仅使用备份资源的主动保护策略，笔者通过引入文献[4]中的被动恢复策略，利用备份资源和SN中的剩余资源共同完成故障恢复，改善了主动保护策略恢复资源单一的问题，有效提高了故障恢复成功率.具体步骤如下.

1) 在物理节点发生故障后，如果受到影响的虚拟节点和链路存在足够的备份资源，则直接将它们迁移至备份资源上，完成故障恢复.

2) 若备份资源不够，则利用SN中的剩余资源，并采取重映射的方式，完成故障恢复.

3) 对于失效虚拟节点，根据式(22)获得可重映射的物理节点集合，这些物理节点满足位置约束且尚未映射该VNR内的其他虚拟节点.

$ \begin{array}{c} \phi '\left( v \right) = s \in {N^{\rm{S}}}\backslash \\ \{ \sum\limits_{v \in {N^{\rm{V}}}} {{N_{\rm{M}}}\left( v \right)} \} |{\rm{Dis}}({\rm{loc}}\left( v \right), {\rm{loc}}\left( s \right)) \le {r^v}\} \end{array} $

(22)

其中N_M(v)表示被虚拟节点v映射的物理节点.

4) 使用上述SDN-BackupVNE算法中的步骤3完成失效虚拟节点的重映射.

5) 为了减少故障恢复的消耗时间, 使用复杂度较低的KSP算法重映射失效的虚拟链路.

4 实验仿真 4.1 仿真环境配置

物理SDN拓扑是系数为8的fat-tree类型，包含80个物理节点和256条物理链路.参照文献[6]设定，物理节点的CPU、流表和链路的带宽资源大小均服从50~100之间的均匀分布. VNR到达规律服从系数为4的泊松分布，仿真持续时间为5万个时间单元，平均每100个时间单元内有4个VNR到达，在5万个时间单元内共计到达2 000个VNR.每个VNR的虚拟节点个数服从2~10之间的均匀分布，虚拟节点的连通性为0.5，虚拟节点的CPU、流表和链路的带宽资源大小均服从1~10之间的均匀分布.

仿真过程模拟了300个物理节点故障，物理节点故障的产生规律服从系数为0.6的泊松分布.

4.2 对比方案和性能选取

选取了主动保护策略LC-SVNE算法^[3]和被动恢复策略NB-SVNE算法^[4]作为对比方案，请求接受率、收益/成本(R/C)比、故障恢复成功率和故障恢复平均耗时作为性能评价指标.其中，R/C比值为

$ R/C = \frac{{{\rm{Profit}}(T)}}{{{\rm{Cost}}(T)}} $

(23)

4.3 仿真结果和分析

图 2所示为SDN-ScaSVNE和两组对比算法的请求接受率对比. NB-SVNE仅使用被动恢复策略，不需要扩展虚拟网络，映射单个VNR的消耗最低，所以请求接受率最高. LC-SVNE仅使用主动保护策略，增加了单个VNR的映射消耗，请求接受率最低.而SDN-ScaSVNE基于剩余网络资源实现了VNR的可伸缩备份，提高了映射成功率.

R/C能够较好地反映算法的总体性能. 图 3中给出了3组算法的R/C比值. SDN-ScaSVNE和NB-SVNE的R/C比值接近，且明显高于LC-SVNE.这是因为SDN-ScaSVNE虽然请求接受率低于NB-SVNE，但是其故障恢复性能更佳. LC-SVNE因为收益较低，且增加了映射消耗，所以最终的R/C比值最低.

图 4所示为3组算法的故障恢复成功率，其中SDN-ScaSVNE最高，而LC-SVNE最低.这是因为SDN-ScaSVNE算法能够结合已有的备份资源和网络剩余资源共同完成故障恢复，所以相对于仅使用备份资源的LC-SVNE算法和仅使用网络剩余资源的NB-SVNE算法，故障恢复策略更灵活，恢复成功率更高.

此外，SDN-ScaSVNE、LC-SVNE和NB-SVNE算法单个故障恢复的平均耗时分别为2.56、2.02和3.18 min.可见，SDN-ScaSVNE耗时介于仅使用备份资源进行恢复的LC-SVNE和仅使用网络剩余资源进行恢复的NB-SVNE之间.这是因为SDN-ScaSVNE在备份资源充足时直接使用备份资源进行恢复，备份资源不足时又通过被动恢复策略寻找网络剩余资源进行恢复.

综上，SDN-ScaSVNE具有最高的故障恢复成功率和R/C比值.但由于需要预留备份资源，所以请求接受率偏低，因此如何确定备份资源的比例，以获得较高的请求接受率还有待进一步研究.

笔者还针对故障物理节点中重要节点的比例不同，对故障恢复成功率和VNR请求接受率的影响进行了仿真和分析，如图 5和图 6所示.

当故障节点中重要节点比例较低时，SDN-ScaSVNE的故障恢复成功率较低，而请求接受率较高.由于VNR中重要的虚拟节点往往是所需资源比较多或者处在网络关键位置的节点，它们大多会被映射到重要的物理节点上，所以如果重要节点出现故障的比例较低，受影响的虚拟节点也大多是非重要的.由于本文方案只对虚拟网络中的重要节点提供备份资源，对非重要节点故障只能通过重映射进行故障恢复，导致故障恢复成功率较低.但失效的虚拟网络因为无法恢复会释放原来占用的物理资源，有利于后续VNR的映射，所以请求接受率得到了提升.

随着故障节点中重要节点比例的提高，故障恢复成功率会有很大提升，请求接受率却相应下降.由上述分析可知，如果产生故障的物理节点大多是重要节点，那么受到影响的虚拟节点也大多是重要的.笔者提出的方案利用SN中的备份资源和可用资源共同完成故障恢复，提高了故障恢复成功率.但故障节点和成功恢复的虚拟网络会进一步压缩物理网络的可用资源，不利于后续VNR的映射，导致请求接受率较低.

上述结果说明，当物理网络中的重要节点发生故障时，SDN-ScaSVNE能够更加有效地为虚拟网络提供生存性保障，当然由于需要一定的备份资源，会牺牲一定的请求接受率.

5 结束语

结合主动保护策略和基于网络剩余资源的被动保护策略提出了可伸缩备份的SVNE算法，改善了现有算法映射僵化和恢复资源单一等问题，能够为虚拟网络提供较好的生存性保障.后续工作可以从以下2个方面进行改进.首先，VNR映射收益和故障赔偿金中的参数是人为定义的，需要参考网络运营商的实际数据进行调整；其次，虚拟网络映射和故障恢复阶段的重映射仅采用了静态映射方式，如果在物理网络资源不足的情况下通过动态调整资源分配即动态映射方式可以进一步提高VNR请求接受率和故障恢复成功率.