一种区分等级的可生存服务功能链映射方法

刘 艺 张红旗 杨英杰 常德显

(解放军信息工程大学 郑州 450001) (河南省信息安全重点实验室 郑州 450001) (liuyi9582@126.com)

当前，网络中部署着大量的专用硬件设备(如防火墙和负载均衡器等)，为用户及业务提供了种类繁多的服务功能[1]，并且网络往往需要引导用户或业务流按序经过多个服务功能的处理，即以服务功能链[1](service function chain, SFC)的形式提供服务.但是，现有的SFC实现方式依赖于路由器等转发设备和防火墙等专用硬件设备[2]，不仅需要人工配置路由表项，过程繁琐且易出错[3]，而且专用硬件设备位置与网络拓扑紧耦合[4]，难以实现SFC的动态调整，如增加、移除服务功能或者改变服务功能的顺序.

软件定义网络[5](software defined networking, SDN)和网络功能虚拟化[6-7](network function virtualization, NFV)为灵活高效地实现SFC提供了新途径.在利用NFV技术将SFC中的服务功能软件化、并以虚拟网络功能(virtual network function, VNF)的形式部署在通用服务器的基础上，依照SFC的服务功能顺序要求，借助SDN的流量管控能力引导流量按序经过若干VNF，从而在网络中实例化SFC，为用户及业务提供服务.由此，基于“SDN+NFV”实现SFC的关键在于解决SFC映射问题，即规划服务功能的部署位置和服务功能间的流量路由路径.然而，在底层网络中，受软件错误、硬件失效和黑客攻击等事件的影响，节点和链路故障频现，这会导致VNF失效或VNF间的连接路径失效，进而造成SFC不可用、网络服务中断，而且由于SFC共享底层网络资源，即便是单点或单链路故障，也可能导致多个SFC无法正常提供服务.因此，如何在底层网络出现故障时保证SFC的正常运行成为亟待解决的问题，本文称之为可生存SFC映射问题.

目前，底层网络的单点和单链路故障出现频率较高[8]，预留备用资源成为解决可生存SFC映射问题的通用方法，但该方法在提高SFC可生存能力的同时会增大底层网络资源开销[9]，进而降低SFC映射的成功率.实际上，SFC的可生存能力需求与其所提供的服务的重要程度密切相关，比如为银行提供加密通信服务的SFC必须24 h正常运行，而为普通网站提供审计或备份服务的SFC即使在短时间内失效，也不会带来严重损失.因此，为应对底层网络的单点和单链路故障，本文提出一种区分等级的可生存SFC映射方法.该方法根据SFC提供服务的重要程度，将SFC划分为2个等级，即提供重要服务的关键SFC(key service function chain, KSFC)和提供普通服务的普通SFC(normal service function chain, NSFC)，分别采用保护和恢复策略解决可生存映射问题，从而兼顾提高SFC可生存能力和降低底层网络资源开销.此外，由于服务时延是评价服务质量的重要指标[10-11]，该方法将最小化服务时延作为映射SFC的重要考虑因素.本文的主要工作包括2个方面：

1) 采用混合整数线性规划(MILP)为基于保护策略的KSFC可生存映射建模，并提出了面向KSFC的主备服务路径构建算法(primary-backup service path building, PBSP-Bld)求解该模型，从而在KSFC映射时预分配备用VNF和备用链路，并最小化KSFC的服务时延；

2) 采用MILP为基于恢复策略的NSFC可生存映射建模，并提出了面向NSFC的失效服务路径重建算法(failed service path restoring, FSP-Res)求解该模型，从而在底层网络出现故障后为失效NSFC重新分配节点和链路资源，并在尽可能多地恢复失效NSFC的同时最小化已恢复NSFC的服务时延.

1 相关工作

随着SDN网络架构的逐步推广与NFV技术的日益成熟，SFC映射问题成为研究热点.已有研究大多将SFC映射建模为带资源约束的优化模型，并采用Gurobi优化器等现有工具[12]或设计启发式算法[13-14]进行求解，但它们未考虑底层网络发生故障的情况.

可生存SFC映射问题与可生存虚拟网络映射问题(survivable virtual network embedding, SVNE)[9]类似，均是在不可靠的、共享的底层网络中为带有资源约束的逻辑拓扑分配相应资源，保证在网络故障发生时能有效恢复受影响的逻辑拓扑.但二者存在诸多不同，如SFC中各服务功能有严格的顺序约束，而虚拟网络(virtual network, VN)只要求虚拟节点之间连通；在SFC映射时需要考虑服务功能类型和底层节点类型，而VN映射只涉及一种物理设备[15](即路由器)；只有全部服务功能正常运行，且服务功能间的流量路由路径完整，SFC才能正常提供服务[16]，而只要VN是一个连通图，虚拟网络服务就可以保持连续性[17].由此可见，解决可生存SFC映射问题可借鉴SVNE研究成果，如SVNE主要采用保护和恢复2种策略[18].保护指事先预留备用资源以应对可能的故障；恢复指在故障发生后实时地为失效部分重分配资源，但是仍需要根据SFC的特性提出针对性的解决方法.

目前，关于可生存SFC映射问题的研究刚刚起步，根据底层故障类型大致分为2类：

1) 面向单故障的可生存SFC映射.单故障指在一个时刻至多只有一个底层节点和或链路发生故障.文献[19]通过快速启用备用VNF和更新流量引导策略来恢复失效SFC，但未提出具体的VNF备份方法.文献[20]在与同一交换机相连的2个服务器上分别部署主备VNF，但无法应对交换机出现故障的情况.文献[21]针对单点故障、单链路故障和单点-单链路故障3种情况，分别提出了基于保护策略的SFC映射方法，并将面向单点-单链路故障的SFC映射建模为ILP问题，采用CPLEX求解，但在SFC数量多或网络规模大的情况下求解速度慢.

2) 面向多故障的可生存SFC映射.多故障指在一个时刻可能有多个底层节点和链路发生故障.文献[22]提出了基于回溯机制的SFC备用资源分配方法，但回溯机制耗时长，且未考虑降低底层网络资源开销.文献[16]以服务器失效时SFC中所有VNF仍正常运行的概率衡量SFC的可靠性，提出了基于联合备份的SFC映射算法，但未考虑多条SFC共享备用资源.文献[23]利用负载均衡器实现SFC备份，但它假设底层链路绝对可靠.

综上，已有研究主要存在3点不足：1)大多通过大量预分配备用资源来增强SFC的可生存能力，导致底层网络资源开销大；2)大多关注如何在底层网络资源有限的情况下为SFC分配足够的运行资源，而对其自身的运行性能(如服务时延)缺乏考虑；3)基于优化模型的映射方法的时间开销大.

2 问题描述

本节首先给出了底层网络、VNF和SFC的定义，之后在介绍基本SFC映射过程的基础上引入可生存需求，对可生存SFC映射问题进行了描述.表1是主要符号列表.

Table 1 Key Symbols Lists表1 主要符号列表

2.1 基本定义

定义1. 底层网络.底层网络G=(V,E)，其中，v∈V和(u,v)∈E分别是底层节点和底层链路.根据SFC参考架构[24]，底层节点分为3类：1)访问节点vA∈VA，表示流量进出网络的交换机；2)服务节点vS∈VS，表示服务功能转发器(service function forwarder, SFF)及与其相连的通用服务器(假设它们之间的链路可靠)，这些通用服务器上可运行VNF；3)转发节点vR∈VR，表示仅用于在访问节点和服务节点之间转发数据包的交换机.记服务节点vS具有属性{(id,ω(id))}，其中id∈IDS是与vS相连的服务器标识，具有全网唯一性，IDS是所有与SFF相连的服务器的标识集合；ω(id)表示服务器id的资源容量，本文以其可用的CPU核数衡量.为便于后文描述节点映射关系，假设每个访问节点上也有一个唯一性标识为id∈ID-IDS的服务器，且ω(id)=∞，其中ID是全网服务器标识集合.底层链路(u,v)的可用带宽和时延分别记为λ(u,v)和η(u,v).

定义2. VNF.假设网络中有m种VNF，构成VNF类型集合T={f1,f2,…,fm}.本文将类型为fj的VNF的服务能力定义为其实例最多可同时为Nser(fj)条SFC提供服务[21]，并且fj实例化所需的资源以CPU核数衡量，为避免非一致性内存访问带来的开销[13]，假定各类型VNF实例均需要1个CPU核.

2.2 基本SFC映射过程

基于上述网络模型，基本SFC映射过程分为节点映射和链路映射2部分.

图1是示例底层网络和SFC，其中底层网络节点旁的方框中标明了相应的服务器标识及可用CPU核数，链路上标明了可用带宽时延；SFC各虚拟链路的带宽需求均为5.由此，VNF1映射到节点C，VNF2和VNF3映射到节点E，示例SFC的服务路径是{(A,C),(C,E),(E,I),(I,K),(K,L)}，服务时延是14.

2.3 可生存SFC映射问题描述

可生存SFC映射是指在满足SFC基本映射约束的前提下，通过在SFC映射时预分配备用资源，或在SFC失效后重映射失效节点和链路，降低底层网络故障对SFC提供服务的影响.而且，可生存SFC映射需要考虑最小化SFC服务时延，以提高服务质量.下面分别描述面向KSFC和面向NSFC的可生存映射问题.

Fig. 1 Substrate network and SFC图1 底层网络和SFC

2.3.1 面向KSFC的可生存映射问题描述

依据上述映射规则，以图1中的底层网络和SFC为例，主服务路径是{(A,C),(C,E),(E,I),(I,K),(K,L)}，其中C、E和K分别是VNF1，VNF2和VNF3的主服务节点.备用服务路径是{(A,B),(B,D),(D,G),(G,J),(J,L)}，其中D是VNF1和VNF2的备用服务节点，G是VNF3的备用服务节点.桥接路径是{(C,B),(B,D)}和{(E,H),(H,G)}.

2.3.2 面向NSFC的可生存映射问题描述

3) 不重映射未失效虚拟节点和链路.

依据上述映射规则，对于图1中底层网络和SFC的映射关系，若节点E发生故障，则将VNF2和VNF3分别重映射至D和G，并将以VNF2或VNF3为端点的失效虚拟链路重映射至路径{(C,B),(B,D)}，{(D,G)}和{(G,K),(K,L)}.

3 面向KSFC的可生存映射建模与求解

基于上述问题描述，本节为面向KSFC的可生存映射建立了模型，提出了启发式算法进行求解，并分析了算法的时间复杂度.

3.1 面向KSFC的可生存映射模型

以最小化最大的KSFC时延为优化目标，以节点约束、链路约束和可生存约束为约束条件，采用MILP为面向KSFC的可生存映射建立模型，记为Pro-KSFC.表2是该模型中的主要符号说明.

Table 2 Key Symbol Descriptions for Pro-KSFC表2 Pro-KSFC的主要符号说明

① 由于SFC端节点和访问节点的映射关系已知，后文如无特别说明，仅讨论VNF和服务器之间的映射关系.

1) 决策变量

2) 优化目标

minQ,

(1)

式(1)表示最小化最大的KSFC时延.

3) 节点约束条件

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

式(2)表示KSFC端节点的位置已唯一确定；式(3)表示虚拟节点被唯一地映射到一个主(备用)服务器上；式(4)表示VNF节点不能被映射到访问节点中的服务器上：式(5)表示同一KSFC的VNF节点不能被映射到同一主服务节点上；式(6)和式(7)不仅保证一个VNF节点被映射到不同的主备服务节点上，而且允许同一KSFC的VNF节点被映射到同一备用服务节点上；式(8)和式(9)保证VNFfj在服务器id上部署，当且仅当存在类型为fj的VNF节点映射到id所在的主服务节点或备用服务节点上；式(10)和式(11)分别是服务器可用CPU核数约束和VNF服务能力约束.

4) 链路约束条件

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

式(21)表示若存在一条以底层节点q为终点的底层链路属于主服务路径，则必有一条以q为起点的底层链路也属于该路径，式(22)和式(23)的含义类似.

(24)

(25)

(26)

(27)

(28)

(29)

(30)

(31)

(32)

(33)

(34)

(35)

(36)

(37)

(38)

5) 可生存性约束条件

(39)

(40)

(41)

(42)

(43)

(44)

3.2 主备服务路径构建算法

① 将与SFC端点对应的访问节点加入到主服务节点集合Vpr和备用服务节点集合Vbk中；

② 初始化主服务路径Epr、备用服务路径Ebk、桥接节点集合Vbr和桥接路径集合Ebr；

④tn←0*标识是否找到满足条件的候选主备服务节点*；

⑤id,id′,CVpr,CVbk,CSpr,CSbk←null

⑥l,CEpr,CEbk,CEbr←∅

⑧ for allr∈Rdo

⑨x←路径r的终点

VS-(Vpr∪{x}),MaxHops,

then

算法1按序迭代映射VNF节点及相关虚拟链路，在每次迭代过程中，首先，确定候选主服务节点x(行⑦～)，具体是以访问节点或前驱VNF节点的主服务节点为起点，搜索与备用服务路径仅可能在访问节点处相交，且路径跳数不大于跳数阈值MaxHops的候选路径，并将它们按时延大小升序排列(行⑦)，依次对各候选路径的终点进行可用资源容量检验(行⑩)和连通性检验(行)；之后，按照前述类似过程确定候选备用服务节点x′(行～)；最后，确定从前驱VNF节点的主服务节点到x′的桥接路径(行～)，它和最新建立的主服务子路径仅在x处相交.此外，为提高主备服务路径构建成功率，只有在搜索候选主备服务节点和构建桥接路径均失败的情况下，才重新映射前驱VNF节点(行～).

在算法1中，函数Can_Path(u,V,σ,Λ,τ)用于搜索候选路径集合，并按时延大小升序排列，每条候选路径满足：1)以节点u为起点，以V中的某个节点为终点；2)路径跳数不大于σ；3)与路径集合Λ中的路径仅可能在τ处相交.函数Res_Check(x,f)用于在底层节点x中搜索可部署VNFf的服务器id，id满足任一条件：1)id上已部署f的实例，且它能再为至少一条SFC提供服务；2)id能满足f的CPU核数需求.函数Cnt_Check(x)返回False，当且仅当将x置为主(备用)服务节点后剩余节点无法连通，即无法构建备用(主)服务路径.

3.3 算法的时间复杂度分析

4 面向NSFC的可生存映射建模与求解

基于上述问题描述，本节为面向NSFC的可生存映射建立了模型，提出了启发式算法进行求解，并分析了算法的时间复杂度.

4.1 面向NSFC的可生存映射模型

以最大化成功恢复的失效NSFC数目和最小化最大的已恢复NSFC时延为优化目标，以节点约束和链路约束为约束条件，采用MILP为面向NSFC的可生存映射建立模型，记为Res-NSFC.表3是该模型中的主要符号说明.

1) 决策变量

2) 优化目标

(45)

式(45)分为2部分：①最小化未恢复的失效NSFC的数目；②最小化最大的已恢复NSFC时延.其中α用于调节这2部分的相对重要性.

3) 节点约束条件

(46)

(47)

式(46)表示不重映射未失效的虚拟节点；式(47)表示失效VNF节点不映射到底层故障服务器或访问节点中的服务器上.

(48)

Table 3 Key Symbol Descriptions for Res-NSFC表3 Res-NSFC的主要符号说明

(49)

(50)

式(48)和式(49)表示VNFfj在服务器id上部署，当且仅当存在类型为fj的VNF节点映射到id所在的服务节点上；式(50)表示VNFfj至多有一个实例在id上运行.

(51)

(52)

(53)

(54)

4) 链路约束条件

(55)

(56)

式(55)表示不重映射未失效的虚拟链路；式(56)表示失效虚拟链路不映射到底层故障链路上.

(57)

(58)

(59)

(60)

(61)

(62)

4.2 失效服务路径重建算法

4.2.1 双重重映射子算法

⑤ else

⑥H←0；

⑨ if |Ωl|>Hor (|Ωl|=Hand

MDly(Ωl)

BST←Ωl；

⑧ end if

⑨ end for

⑩ for all (u,v)∈Edo

② for allP∈Φdo

⑧ end if

⑨ end for

⑩ end for

4.2.2 替代路径选择子算法

⑦ end if

⑧ end for

4.3 算法的时间复杂度分析

在算法2的主函数中最耗时的操作是调用函数MPaths()，以获得重映射路径集合.由于MPaths()的关键步骤是利用Dinic算法，故时间复杂度为O(d2×l).由此，若失效共享节点的数目是p，候选服务节点集合大小为q，则算法2在最坏情况下的时间复杂度为O(p×q×l×d2).

5 实验与结果分析

5.1 实验环境

底层网络拓扑由GT-ITM工具随机产生，每对节点以0.5的概率互连，各类型节点的个数如表4所示.在底层网络中，每个服务节点具有2个服务器，每个服务器具有2个CPU核，底层链路时延服从取值区间为[5,20](单位：ms)的均匀分布，带宽值均为1 Gbps.假设网络中有6种VNF，每种VNF至多可被4条SFC共享.SFC由随机选取的访问节点对和3种VNF构成，其带宽需求服从取值区间为[50,150](单位：Mbps)的均匀分布.

Table 4 Number of Nodes in the Experimental Topology

实验在配置2个Intel Xeon E5-2650 8 x 2 GHz处理器和128 GB RAM的服务器上进行，2种对比算法采用CPLEX 12.6.0.1分别对Pro-KSFC和Res-NSFC进行求解，记为Opt-KSFC和Opt-NSFC.评估指标包括：

1) 算法运行时间.

2) KSFC映射成功率.即成功映射的KSFC数目与KSFC映射请求数目之间的比值.

5) SFC成功运行率.即在SFC请求不断到来和底层网络间歇性出现单点故障的情况下，成功运行的SFC数目与SFC映射请求数目之间的比值，其中，成功运行的SFC既包括成功映射的新到的KSFC和NSFC映射请求，也包括成功恢复的已部署的KSFC和NSFC，该指标反映了SFC映射的有效性和对节点故障的SFC恢复能力.

6) 额外带宽消耗率.即SFC消耗的额外带宽与底层链路带宽总量之间的比值，其中，SFC消耗的额外带宽包括为KSFC的备用路径和桥接路径分配的带宽，以及为恢复NSFC分配的带宽.

5.2 实验结果与分析

实验分为3部分：1)针对PBSP-Bld算法，研究参数MaxHops对KSFC映射成功率和算法运行时间的影响，并从KSFC最大时延、KSFC映射成功率和算法运行时间3方面评估算法有效性；2)针对FSP-Res算法，从NSFC故障恢复率、已恢复NSFC最大时延和算法运行时间3方面评估算法有效性；3)模拟实际网络环境，从SFC故障恢复率、SFC成功运行率和工作链路资源利用率3方面评估所提SFC可生存性映射方法的有效性.

Fig. 2 Influence of the value of MaxHops图2 MaxHops取值的影响

5.2.1 主备服务路径构建算法有效性评估实验

实验随机生成10条KSFC，采用具有不同Max-Hops值的PBSP-Bld将它们映射到底层网络T3中，测算KSFC映射成功率和算法运行时间.实验重复50次取均值，结果如图2所示.当MaxHops≤4时，KSFC映射成功率随MaxHops的增大而增大；当MaxHops>4时，成功率几乎维持不变，而算法运行时间随着MaxHops的增大而增加.因此，MaxHops=4是相对最佳取值，后续实验中均采用该值.

实验在不同KSFC数目和不同底层网络规模条件下，分别采用PBSP-Bld和Opt-KSFC将随机生成的若干条KSFC映射至底层网络，测算KSFC最大时延、KSFC映射成功率和算法运行时间.实验重复50次取均值，结果如图3～5所示：

Fig. 4 Success ratio of KSFC mapping图4 KSFC映射成功率

Fig. 5 Running time图5 算法运行时间

由图3和4可知，Opt-KSFC在KSFC最大时延和映射成功率方面的表现优于PBSP-Bld，这是因为前者搜索了更多种映射方案以寻求最优解.在KSFC数目一定的情况下，随着底层网络规模的增大，可利用的网络资源增多，二者的映射成功率增大，然而它们的KSFC最大时延未明显降低，这是因为虽然网络规模越大意味着KSFC映射的优化空间越大，但是KSFC时延会受到访问节点和服务节点位置的影响.此外，在底层网络规模一定的情况下，由于底层网络资源有限，随着KSFC数目的增大，二者的映射成功率下降，KSFC最大时延增大.

此外，由图5可知，PBSP-Bld的运行时间小于Opt-KSFC，这是因为后者的搜索空间更大.而且，结合图3～5可知，随着底层网络规模的增大和KSFC数目的增多，PBSP-Bld和Opt-KSFC在映射成功率和KSFC最大时延方面间的差距未显著增加，但前者的算法运行时间愈发优于后者，比如当底层网络具有45个节点(T4)且KSFC数目为10时，Opt-KSFC的KSFC最大时延比PBSP-Bld减小约16.4%，映射成功率提高1.85%，但算法运行时间增大了约84.4倍.

5.2.2 失效服务路径重建算法有效性评估实验

实验借鉴文献[9]中的方法，在网络T3中随机部署若干条NSFC，并保证底层链路负载均衡，由此，通过改变已部署的NSFC数目可以改变网络的底层链路利用率.在不同底层链路利用率情况下，从网络中随机选取一个转发节点或服务节点或服务器作为故障节点，并将相关链路和服务器置为失效，分别采用FSP-Res和Opt-NSFC(权重α=1 000，即以最大化成功恢复的NSFC数目为主要目标)恢复失效NSFC，测算NSFC故障恢复率，已恢复NSFC最大时延和算法运行时间，实验重复50次取均值，结果如图6所示.此外，实验采用不同规模的底层网络，在保证它们的链路利用率相同的情况下重复上述实验，结果如图7所示.

Fig. 6 Performance comparison under different substrate link utilization图6 在不同底层链路利用率下有效性的对比

Fig. 7 Performance comparison under different substrate network size图7 在不同底层网络规模下有效性的对比

由图6(a)和7(a)可知，Opt-NSFC的故障恢复率均高于FSP-Res，这是因为前者在更大的节点和链路空间中进行搜索以重映射失效VNF节点和虚拟链路.由图6(a)可知，它们随底层链路利用率的增大而降低，这是因为底层链路利用率越大意味着单点故障可能导致更多的NSFC失效，而且可用于恢复失效虚拟链路的带宽也越少.进一步地，当底层链路利用率大于60%时，2种算法的故障恢复率显著下降，原因在于:为达到较高的底层链路利用率，文献[9]的NSFC映射方法降低了对链路负载均衡的要求，使得部分链路的剩余带宽难以满足NSFC需求，进而导致失效虚拟链路无法重映射到所有经过这些“拥塞”链路的底层路径上，并且底层链路利用率越高，“拥塞”链路越多.此外，由图7(a)可知，2种算法的故障恢复率随底层网络规模的增大而增加，这是因为底层链路越多意味着有更多条不同的底层路径可作为重映射失效虚拟链路的选择.

由图6(b)和7(b)可知，Opt-NSFC的已恢复NSFC最大时延均小于FSP-Res.由图6(b)可知，它们随底层链路利用率的增大而增大，这是因为更多的底层链路难以为NSFC提供足够的带宽，致使失效虚拟链路不得不重映射到更长的路径上.此外，由图7(b)可知，随着底层网络规模增大，2种算法的已恢复NSFC最大时延小幅增大，原因在于：在规模较大的网络中访问节点可能相距较远，导致NSFC对应的服务路径较长.

由图6(c)和7(c)可知，FSP-Res比Opt-NSFC至少约快384倍.此外，随着底层链路利用率和底层网络规模的增大，由于失效NSFC增多和待搜索的节点、链路空间扩大，2种算法的运行时间均增大，但是单点故障恢复算法的运行时间增幅小于Opt-NSFC.

5.2.3 SFC可生存性映射方法有效性评估实验

Fig. 8 Average recovery ratio of SFC图8 平均SFC故障恢复率

Fig. 9 Average successful running ratio of SFC图9 平均SFC成功运行率

Fig. 10 Average additional bandwidth consumption ratio图10 平均额外带宽消耗率

综上所述，PBSP-Bld算法和FSP-Res算法能够在较短的时间内获得接近最优的性能表现，并且随着底层网络规模的增大，二者在时间开销上的优势愈加显著.可生存SFC映射方法在底层单点故障频繁发生时能有效保证SFC的正常运行，但是其性能表现受KSFC和NSFC之间的数量比例的影响，并且在KSFC数量比例大时，该方法消耗的额外带宽资源也较大，需要从减小备用带宽资源开销方面对该方法进行改进.

6 总 结

针对已有可生存SFC映射研究存在底层网络资源开销大、SFC服务时延长和映射时间开销大等问题，本文提出了一种区分等级的可生存SFC映射方法.通过综合保护和恢复策略，减少了备用资源消耗，从而降低了底层网络资源开销.通过将可生存SFC映射问题建模为以最小化服务时延为目标的优化模型，并提出启发式算法进行求解，降低了服务时延，减小了直接求解模型的时间开销.仿真实验表明，在不同KSFC数目和不同底层网络规模条件下，PBSP-Bld算法的KSFC映射成功率和KSFC最大时延分别比Opt-KSFC低0.99%～7.14%和高3.48%～58.31%，但前者的时间开销比后者低95.31%～99.99%.在不同底层网络规模和不同底层链路利用率条件下，FSP-Res算法的NSFC故障恢复率和已恢复NSFC最大时延分别比Opt-NSFC低1.05%～7.34%和高2.01%～18.44%，但前者的时间开销比后者低99.74%～99.97%.此外，实验模拟实际网络环境，通过改变KSFC比例和底层单点故障发生频率，从SFC故障恢复率、SFC成功运行率和额外带宽消耗率3方面验证了区分等级的可生存SFC映射方法的有效性.在未来研究中，需要在各类真实网络中进一步评估和验证所提方法，从优化网络资源利用方面对其进行改进，并研究针对底层网络多点、多链路和区域故障问题的可生存SFC映射方法.

[1]Quinn P, Nadeau T, Yadav N. Problem statement for service function chaining, RFC 7498[EBOL]. (2015-04) [2017-10-10]. https:www. rfc-editor. orginforfc7498

[2]Ding Wanfu, Qi Wen, Wang Jianping, et al. OpenSCaaS: An open service chain as a service platform toward the integration of SDN and NFV[J]. IEEE Network, 2015, 29(3): 30-35

[3]Bari M F, Chowdhury S R, Ahmed R, et al. On orchestrating virtual network functions[C]Proc of the 11th Int Conf on Network and Service Management. Piscataway, NJ: IEEE, 2015: 50-56

[4]Gupta A, Habib M F, Mandal U, et al. On service-chaining strategies using virtual network functions in operator networks[J]. Computer Network, 2018, 133: 1-16

[5]McKeown N. Software-defined networking[C]Proc of the 28th IEEE Conf on Computer Communications. Piscataway, NJ: IEEE, 2009: 30-32

[6]Chiosi M, Clarke D, Willis P, et al. Network functions virtualisation-introductory white paper[R]. Darmstadt, Germany: AT&T, 2012

[7]European Telecommunications Standards Institute. Network functions virtualization (NFV): Architectural framework[R]. Nice, France: ETSI, 2014

[8]Guo Tao, Wang Ning, Moessner K, et al. Shared backup network provision for virtual network embedding[C]Proc of the 2011 IEEE Int Conf on Communications. Piscataway, NJ: IEEE, 2011: 1-5

[9]Rahman M R, Boutaba R. SVNE: Survivable virtual network embedding algorithms for network virtualization[J]. IEEE Trans on Network & Service Management, 2013, 10(2): 105-118

[10]Nagarajan R, Kurose J F. On defining, computing and guaranteeing quality-of-service in high-speed networks[C]Proc of the 11th Annual Joint Conf of the IEEE Computer and Communications Societies. Piscataway, NJ: IEEE, 1992: 2016-2025

[11]Aurrecoechea C, Campbell A T, Hauw L. A survey of QoS architectures[J]. Multimedia Systems, 1998, 6(3): 138-151

[12]Mehraghdam S, Keller M, Karl H. Specifying and placing chains of virtual network functions[C]Proc of the 3rd IEEE Int Conf on Cloud Networking. Piscataway, NJ: IEEE, 2014: 7-13

[13]Mohammadkhan A, Ghapani S, Liu Guyue, et al. Virtual function placement and traffic steering in fiexible and dynamic software defined networks[C]Proc of the 21st IEEE Int Workshop on Local and Metropolitan Area Networks. Piscataway, NJ: IEEE, 2015: 1-6

[14]Ghaznavi M, Shahriar N, Kamali S, et al. Distributed service function chaining[J]. IEEE Journal on Selected Areas in Communications, 2017, 35(11): 2479-2489

[15]Luizelli M C, Bays L R, Buriol L S, et al. Piecing together the NFV provisioning puzzle: Efficient placement and chaining of virtual network functions[C]Proc of the 14th IFIPIEEE Int Symp on Integrated Network Management. Piscataway, NJ: IEEE, 2015: 98-106

[16]Fan Jingyuan, Ye Zilong, Guan Chaowen, et al. GREP: Guaranteeing reliability with enhanced protection in NFV[C]Proc of the 2015 ACM SIGCOMM Workshop on Hot Topics in Middleboxes and Network Function Virtualization. New York: ACM, 2015: 13-18

[17]Cheng Xiang, Zhang Zhongbao, Su Sen, et al. Survey of virtual network embedding problem[J]. Journal on Communications, 2011, 32(10): 143-151 (in Chinese)(程祥, 张忠宝, 苏森, 等. 虚拟网络映射问题研究综述[J]. 通信学报, 2011, 32(10): 143-151)

[18]Sun Gang. Research on virtual network mapping technologiesp[D]. Chengdu: University of Electronic Science and Technology of China, 2012(in Chinese)(孙罡. 虚拟网络的映射技术研究[D]. 成都: 电子科技大学, 2012)

[19]Medhat A M, Carella G A, Pauls M, et al. Resilient orchestration of service functions chains in a NFV environment[C]Proc of the 3rd IEEE Conf on Network Function Virtualization and Software Defined Networks. Piscataway, NJ: IEEE, 2017: 7-12

[20]Suh D, Baek H, Jang S, et al. Distributed service function failover mechanism in service function chaining[C]Proc of the 2017 Int Conf on Information Networking. Piscataway, NJ: IEEE, 2017: 148-150

[21]Hmaity A, Savi M, Musumeci F, et al. Virtual network function placement for resilient service chain provisioning[C]Proc of the 8th Int Workshop on Resilient Networks Design and Modeling. Piscataway, NJ: IEEE, 2016: 245-252

[22]Beck M T, Botero J F, Kai S. Resilient allocation of service function chains[C]Proc of the 3rd IEEE Conf on Network Function Virtualization and Software Defined Networks. Piscataway, NJ: IEEE, 2017: 128-133

[23]Herker S, An X, Kiess W, et al. Data-center architecture impacts on virtualized network functions service chain embedding with high availability requirements[C]Proc of the 2015 IEEE GLOBECOM Workshops. Piscataway, NJ: IEEE, 2015: 1-7

[24]Halpern J, Pignataro C. Service function chaining (SFC) architecture, RFC 7665[EBOL]. (2015-10) [2017-11-10]. https:www.rfc-editor.orginforfc7665

[25]Martins E Q V. An algorithm for ranking paths that may contain cycles[J]. European Journal of Operational Research, 1984, 18(1): 123-130

[26]Beck M T, Botero J F. Scalable and coordinated allocation of service function chains[J]. Computer Communications, 2017, 102: 78-88

[27]Dinitz E A. Algorithm for solution of a problem of maximum flow in networks with power estimation[J]. Soviet Mathematics-Doklady, 1970, 11: 1277-1280

[28]Fredman M L, Tarjan R E. Fibonacci heaps and their uses in improved network optimization algorithms[C]Proc of the 25th Annual Symp on Foundations of Computer Science. Piscataway, NJ: IEEE, 1987: 338-346

LiuYi, born in 1991. PhD candidate. Her main research interests include SDN security and SFC technology.

ZhangHongqi, born in 1962. PhD, professor. His main research interests include network security and classification protection (zhq37922@126.com).

YangYingjie, born in 1971. PhD, professor. His main research interests include security management and situation awareness (yangyj-2010@qq.com).

ChangDexian, born in 1977. PhD, associate professor. His main research interests include SDN security and trusted computing (changdexian@126.com).