或链路发生故障.文献[19]通过快速启用备用VNF和更新流量引导策略来恢复失效SFC，但未提出具体的VNF备份方法.文献[20]在与同一交换机相连的2个服务器上分别部署主备VNF，但无法应对交换机出现故障的情况.文献[21]针对单点故障、单链路故障和单点-单链路故障3种情况，分别提出了基于保护策略的SFC映射方法，并将面向单点-单链路故障的SFC映射建模为ILP问题，采用CPLEX求解，但在SFC数量多或网络规模大的情况下求解速度慢. 刘 艺 张红旗 杨英杰 常德显
(解放军信息工程大学 郑州 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的服务时延.
随着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)基于优化模型的映射方法的时间开销大.
本节首先给出了底层网络、VNF和SFC的定义，之后在介绍基本SFC映射过程的基础上引入可生存需求，对可生存SFC映射问题进行了描述.表1是主要符号列表.
Table 1 Key Symbols Lists
表1 主要符号列表
定义1 . 底层网络.底层网络 G =( V , E )，其中， v ∈ V 和( u , v )∈ E 分别是底层节点和底层链路.根据SFC参考架构 [24] ，底层节点分为3类：1)访问节点 v A ∈ V A ，表示流量进出网络的交换机；2)服务节点 v S ∈ V S ，表示服务功能转发器(service function forwarder, SFF)及与其相连的通用服务器(假设它们之间的链路可靠)，这些通用服务器上可运行VNF；3)转发节点 v R ∈ V R ，表示仅用于在访问节点和服务节点之间转发数据包的交换机.记服务节点 v S 具有属性{( id , ω ( id ))}，其中 id ∈ ID S 是与 v S 相连的服务器标识，具有全网唯一性， ID S 是所有与SFF相连的服务器的标识集合； ω ( id )表示服务器 id 的资源容量，本文以其可用的CPU核数衡量.为便于后文描述节点映射关系，假设每个访问节点上也有一个唯一性标识为 id ∈ ID - ID S 的服务器，且 ω ( id )=∞，其中 ID 是全网服务器标识集合.底层链路( u , v )的可用带宽和时延分别记为 λ ( u , v )和 η ( u , v ).
此外，底层节点 v 0和 v n 之间的路径记为 P S ( v 0, v n )={( v 0, v 1),( v 1, v 2),…,( v n -1 , v n )}，其中 v 0和 v n 是路径端点， v i (1≤ i ≤ n -1)是中间节点.若路径 P S ( v 0, v n )和 P S ( 
, 
)都经过节点 v ，且除 v 外无共用节点和链路，则称它们仅在 v 处相交.若它们无共用节点和链路，则称它们不相交.特别地，若它们除源和目的节点相同(即 v 0= ， v n = )外无共用节点和链路，则称它们节点不相交.
定义2 . VNF.假设网络中有 m 种VNF，构成VNF类型集合 T ={ f 1 , f 2 ,…, f m }.本文将类型为 f j 的VNF的服务能力定义为其实例最多可同时为 N ser ( f j )条SFC提供服务 [21] ，并且 f j 实例化所需的资源以CPU核数衡量，为避免非一致性内存访问带来的开销 [13] ，假定各类型VNF实例均需要1个CPU核.
定义3 . SFC.在本文中，一条SFC负责为一对访问节点之间的流提供服务，它被建模为有向图 
其中， 
和 
分别是虚拟节点和虚拟链路.虚拟节点分为2类：SFC端节点 
包括起点 
和终点 
它们与SFC所服务的流进出网络的访问节点相对应；VNF节点 
代表一个VNF，其类型 
表示 
是 
的直接后继节点，且除 
外每个虚拟节点有且仅有一个直接后继节点. 
是虚拟链路 
带宽需求.
基于上述网络模型，基本SFC映射过程分为节点映射和链路映射2部分.
1) 节点映射.将 
中的虚拟节点映射到底层网络 G 中的底层节点上，且满足CPU核数等约束条件.由于本文在底层网络模型中采用一个服务节点代表与同一SFF相连的多个通用服务器，仅凭借服务节点与VNF节点之间的映射关系无法确定VNF部署在哪个服务器上，因此，节点映射关系包括节点-节点映射和节点-服务器映射2种，分别记为 
和 
对SFC端节点 
有 
它们均唯一确定且提前已知.对VNF节点 
有 
2) 链路映射.将 中的虚拟链路映射到底层网络 G 中的路径上，且满足带宽约束等约束条件.本文将链路映射关系记为 
其中 P S 是底层网络任意节点对间的无环路径集合，且假定每条虚拟链路只映射到一条底层路径上.
由此，可得到与 
对应的 G 的子图 
其中 V R ′ ⊆ V R 是转发节点子集.通常将 G ′称作 
的服务路径.在本文中，SFC服务时延(或简称SFC时延)指的是SFC的服务路径的时延，即构成该路径的各底层链路的时延之和.
图1是示例底层网络和SFC，其中底层网络节点旁的方框中标明了相应的服务器标识及可用CPU核数，链路上标明了可用带宽 时延；SFC各虚拟链路的带宽需求均为5.由此，VNF1映射到节点 C ，VNF2和VNF3映射到节点 E ，示例SFC的服务路径是{( A , C ),( C , E ),( E , I ),( I , K ),( K , L )}，服务时延是14.
可生存SFC映射是指在满足SFC基本映射约束的前提下，通过在SFC映射时预分配备用资源，或在SFC失效后重映射失效节点和链路，降低底层网络故障对SFC提供服务的影响.而且，可生存SFC映射需要考虑最小化SFC服务时延，以提高服务质量.下面分别描述面向KSFC和面向NSFC的可生存映射问题.
Fig. 1 Substrate network and SFC
图1 底层网络和SFC
2.3.1 面向KSFC的可生存映射问题描述
给定底层网络 G 和KSFC集合 
将每条 
映射到 G 上，形成2条节点不相交的服务路径(分别称作 的主、备用服务路径)，并且使得 的时延尽可能小.此种映射需要满足4个约束条件：
1) 每个VNF节点 
被映射到2个不同的服务节点上，且它们都具有满足 的CPU核数需求的服务器，这2个节点分别称作 的主、备用服务节点，分别记为 
和 
这2个服务器分别称作 的主、备用服务器，分别记为 
和 
2) 由于SFF故障会导致与其相连的所有服务器不可达，即这些服务器上的VNF均失效，因此，对于同一KSFC的VNF节点来说，它们的主服务节点不能相同，但为减小链路带宽开销，它们的备用服务节点可以相同.此外，若 和 
是不同KSFC的VNF节点，则 的主服务节点和 的备用服务节点可以相同.
3) 每条虚拟链路 
被映射到2条不相交且满足带宽需求的底层路径上，分别称作 的主、备用服务子路径，分别记为 
和 
特别地，若 的某个端点是SFC端节点(假设 
则其主备服务子路径仅在 处相交.
4) 若 
是同一KSFC上的2个相邻VNF节点， 
则建立从 
到 
的桥接路径 
以便在 失效时快速将流切换至 且不影响 及其之前的服务节点继续提供服务，从而降低丢包率.此外，为避免 和 
同时失效，二者仅在 处相交.
依据上述映射规则，以图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的可生存映射问题描述
由于底层节点故障意味着以其为端点的底层链路也故障，要想恢复因该节点故障而失效的所有NSFC，就必须为映射到这些底层故障链路上的虚拟链路重分配资源，换言之，应对底层单点故障的NSFC恢复方法可以应对底层单链路故障.因此，本文从服务节点或转发节点出现单点故障这一情况入手，研究NSFC的可生存映射问题.假设底层节点 v ∈ V D (| V D |=1)发生故障，由它导致的底层故障服务器的标识集合为 ID D ，底层故障链路集合为 E D ,则失效VNF节点集合 
失效虚拟链路集合 
给定底层网络 G 、底层故障节点 v ∈ V D 和失效NSFC集合 
⊆ 
将失效VNF节点 
和失效虚拟链路 
重映射到 G 中，在尽可能多地恢复失效NSFC的基础上，使得已恢复NSFC的时延尽可能小.此种映射需要满足3个约束条件：
1) 每个失效VNF节点 被唯一地重映射到一个服务节点上，且它具有满足 
的CPU核数需求的服务器.同一NSFC的多个VNF节点不能映射到同一服务节点上，但不同NSFC的多个VNF节点可以映射到同一服务节点上.
2) 每条失效虚拟链路 被唯一地重映射到一条满足带宽需求的底层路径上.
3) 不重映射未失效虚拟节点和链路.
依据上述映射规则，对于图1中底层网络和SFC的映射关系，若节点 E 发生故障，则将VNF2和VNF3分别重映射至 D 和 G ，并将以VNF2或VNF3为端点的失效虚拟链路重映射至路径{( C , B ),( B , D )}，{( D , G )}和{( G , K ),( K , L )}.
基于上述问题描述，本节为面向KSFC的可生存映射建立了模型，提出了启发式算法进行求解，并分析了算法的时间复杂度.
以最小化最大的KSFC时延为优化目标，以节点约束、链路约束和可生存约束为约束条件，采用MILP为面向KSFC的可生存映射建立模型，记为Pro-KSFC.表2是该模型中的主要符号说明.
Table 2 Key Symbol Descriptions for Pro - KSFC
表2 Pro - KSFC的主要符号说明
① 由于SFC端节点和访问节点的映射关系已知，后文如无特别说明，仅讨论VNF和服务器之间的映射关系.
1) 决策变量
采用二元变量 
和 
来描述 
和服务器 id 之间的映射关系 ① .再结合参数 
可得到 与服务节点 v 的映射关系，即若 
则 v 是 的主(备用)服务节点，也称 被映射到主(备用)服务节点 v 上.由于多条SFC可以共享同一服务器上的VNF实例，故引入二元变量 
来表示服务器 id 上是否部署着类型为 f j 的VNF.
在Pro-KSFC中需要建立3种路径，主服务路径、备用服务路径和桥接路径.对于主备服务路径，采用二元变量 
和 
来描述虚拟链路和底层链路之间的映射关系.对于桥接路径，采用二元变量 
来描述.此外，引入实数变量 Q 表示所有KSFC时延的最大值，其中每条KSFC的时延是主、备用服务路径时延二者中的较大值.
2) 优化目标
min Q ,
(1)
式(1)表示最小化最大的KSFC时延.
3) 节点约束条件
(2)
(3)
(4)
∀ 
(5)
(6)
(7)
(8)
(9)
∀ id ∈ ID .
(10)
(11)
式(2)表示KSFC端节点的位置已唯一确定；式(3)表示虚拟节点被唯一地映射到一个主(备用)服务器上；式(4)表示VNF节点不能被映射到访问节点中的服务器上：式(5)表示同一KSFC的VNF节点不能被映射到同一主服务节点上；式(6)和式(7)不仅保证一个VNF节点被映射到不同的主备服务节点上，而且允许同一KSFC的VNF节点被映射到同一备用服务节点上；式(8)和式(9)保证VNF f j 在服务器 id 上部署，当且仅当存在类型为 f j 的VNF节点映射到 id 所在的主服务节点或备用服务节点上；式(10)和式(11)分别是服务器可用CPU核数约束和VNF服务能力约束.
4) 链路约束条件
∀ 
(12)
(13)
∀ 
u , v ∈ V ,( p , q )∈ E ： 
(14)
式(12)保证虚拟链路 被映射到以 和 
的主服务节点为端点的路径上，式(13)和式(14)的含义类似.
∀ 
(15)
(16)
(17)
(18)
∀ 
(19)
(20)
式(15)(16)分别保证虚拟链路 被映射到以 的主服务节点为起点和以 的主服务节点为终点的路径上，式(17)～(20)的含义类似，式(12)～(20)均可进行线性转换.
∀ 
(21)
(22)
∀
u , v , q ∈ V : u ≠ q , q ≠ v ： 
(23)
式(21)表示若存在一条以底层节点 q 为终点的底层链路属于主服务路径，则必有一条以 q 为起点的底层链路也属于该路径，式(22)和式(23)的含义类似.
∀ 
(24)
(25)
∀ 
(26)
(27)
式(24)保证虚拟链路 对应的底层路径不能包含以 的主或备用服务节点为终点的底层链路，式(25)～(27)的含义类似.
∀ 
(28)
∀ 
(29)
∀ 
( p , q ),( q , p )∈ E : p ≠ q ： 
(30)
(31)
∀ 
v ∈ V : u ≠ v ,( p , q ),( q , p )∈ E : p ≠ q 
(32)
∀ 
(33)
(34)
∀ 
(35)
∀ 
(36)
∀ 
η ( p , q )≤ Q .
(37)
η ( p , q )≤ Q .
(38)
式(28)～(32)用于避免不必要的拓展和环路；式(33)～(35)保证流在传输过程中不分割；式(36)是底层链路的带宽容量约束；式(37)和式(38)表示 Q 不小于任一 的主备服务路径的时延.
5) 可生存性约束条件
∀ 
(39)
(40)
(41)
(42)
(43)
∀ 
(44)
为便于叙述，引入二元变量 
和 
{0,1}，式(39)和式(40)表示 
当且仅当 的主服务路径经过服务节点或转发节点 p ∈ V S ∪ V R ，式(41)和式(42)的含义类似；由此，式(43)保证 的主备服务路径不能都经过 p ，即主备服务路径是节点不相交的；式(44)保证底层链路( p , p ′)不能同时属于 的主服务子路径和桥接路径.
由于Pro-KSFC模型求解复杂，本文设计了启发式算法——主备服务路径构建算法(算法1).为降低链路遍历规模，在算法运行前需要对底层链路的带宽进行离散化处理， λ ( u , v )= 
λ ( u , v ) μ i 
，其中 μ i 是 的带宽需求，并在每次底层链路带宽值更新后删除 λ ( u , v )<1的链路.
算法1 . 主备服务路径构建算法 
① 将与SFC端点对应的访问节点加入到主服务节点集合 V pr 和备用服务节点集合 V bk 中；
② 初始化主服务路径 E pr 、备用服务路径 E bk 、桥接节点集合 V br 和桥接路径集合 E br ；
③ 
④ tn ←0 *标识是否找到满足条件的候选主备服务节点* ；
⑤ id , id ′, CV pr , CV bk , CS pr , CS bk ←null
*临时变量* ；
⑥ l , CE pr , CE bk , CE br ←∅
*临时变量* ；
⑦ *搜索候选主服务节点*
⑧ for all r ∈ R do
⑨ x ←路径 r 的终点
* x 是候选主服务节点* ；
⑩ 
* id 是候选主服务器* ；
if id ≠null and Cnt_Check ( x ) then
*搜索候选备用服务节点*
V S -( V pr ∪{ x }), MaxHops ,
for all r ′∈ R ′ do
x ′←路径 r ′的终点 * x ′是候选备用服务节点* ；
* id ′是候选备用服务器* ；
if id ′≠null and Cnt_Check ( x ′)
then
tn ← tn +1；
∉ 
*搜索候选桥接路径*
* M 是较大的数* ；
l ← L [0]
* l 是候选桥接路径* ;
end if
if tn =1 or l ≠∅ then *为临时变量赋值*
CV pr ← x , CE pr ← r , CS pr ← id ,
CV bk ← x ′, CE bk ← r ′, CS bk ← id ′；
if l ≠∅ then
CE br ←{ l }；
break *结束备用服务节点搜索* ；
break *结束备用服务节点搜索* ；
end if
end if
end if
end for
end if
if l ≠∅ 
break *结束主服务节点搜索* ；
end if
end for
if l =∅ and tn =0 then
Back_Track ()；
else *为映射关系赋值*
V pr ← V pr ∪{ CV pr }, E pr ← E pr ∪ CE pr ；
V bk ← V bk ∪{ CV bk }, E bk ← E bk ∪ CE bk ；
E br ← E br ∪ CE br ；
end if
Update ( G ) *更新底层节点CPU核数和底层链路带宽* ；
end for
if 所有的 被成功映射 then
建立最后一个VNF节点与访问节点间的主备服务路径；
else return failed；
end if
return 
算法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 中搜索可部署VNF f 的服务器 id ， id 满足任一条件：1) id 上已部署 f 的实例，且它能再为至少一条SFC提供服务；2) id 能满足 f 的CPU核数需求.函数 Cnt_Check ( x )返回False，当且仅当将 x 置为主(备用)服务节点后剩余节点无法连通，即无法构建备用(主)服务路径.
本文以为一条SFC构建主备服务路径为例，分析算法1的时间复杂度.假设该SFC有 c 个VNF，底层网络的节点和链路数目分别为 d 和 l ，其中，访问节点、服务节点和转发节点的数目分别为 d a , d s 和 d r .算法1的主要操作是函数 Can_Path ( u , V , σ , Λ , τ )，在最坏情况下需要计算并遍历节点 u 和 v ∈ V 之间的所有 k 最短路径，时间复杂度为 O (| V |×( l + kd log d )) [25] .算法1在一次迭代过程中的操作主要包括3部分：1)对于每个VNF，确定其对应的候选主服务节点(及主服务路径)集合，在最坏情况下需要遍历每个服务节点，时间复杂度为 O ( d a ×( l + kd log d ))；2)确定每个候选主服务节点对应的候选备用服务节点集合，若候选主服务节点集合的大小为 b s ，则在最坏情况下的时间复杂度为 O ( b s × d s ×( l + kd log d ))；3)确定每个候选备用服务节点与前驱主服务节点之间的桥接路径，若候选备用服务节点集合的大小 
，则在最坏情况下的时间复杂度为 O ( b s ×( l + kd log d )).由此，算法1在最坏情况下的时间复杂度为 O ( c × d s × l + c × d s × d × k ×log d )).
基于上述问题描述，本节为面向NSFC的可生存映射建立了模型，提出了启发式算法进行求解，并分析了算法的时间复杂度.
以最大化成功恢复的失效NSFC数目和最小化最大的已恢复NSFC时延为优化目标，以节点约束和链路约束为约束条件，采用MILP为面向NSFC的可生存映射建立模型，记为Res-NSFC.表3是该模型中的主要符号说明.
1) 决策变量
采用二元变量 
描述虚拟节点 与服务器 id 之间的映射关系.再结合参数 可得到 与底层节点 v 之间的映射关系.与Pro-KSFC不同，在Res-NSFC中，服务器 id 上运行着的VNF类型(即 )是已知的，而失效NSFC可以利用 id 上已有的VNF实例或者在 id 上新增所需VNF实例，故采用二元变量 
指示是否在 id 上新增VNF f j .二元变量 
用于描述虚拟链路 与底层链路( u , v )的映射关系.
此外，由于优化目标需要计算成功恢复的NSFC的数目及其最大时延，故采用二元变量 
指示失效虚拟链路 是否重映射到某条底层路径上，二元变量 θ i 指示失效 
是否得到恢复，且实数变量 Q 表示已恢复NSFC时延的最大值.
2) 优化目标
(45)
式(45)分为2部分：①最小化未恢复的失效NSFC的数目；②最小化最大的已恢复NSFC时延.其中 α 用于调节这2部分的相对重要性.
3) 节点约束条件
∀ 
(46)
(47)
式(46)表示不重映射未失效的虚拟节点；式(47)表示失效VNF节点不映射到底层故障服务器或访问节点中的服务器上.
∀ id ∈ ID - ID D , f j ∈ T .
(48)
Table 3 Key Symbol Descriptions for Res - NSFC
表3 Res - NSFC的主要符号说明
∀ id ∈ ID - ID D , f j ∈ T .
(49)
+ 
≤1, ∀ id ∈ ID - ID D , f j ∈ T .
(50)
式(48)和式(49)表示VNF f j 在服务器 id 上部署，当且仅当存在类型为 f j 的VNF节点映射到 id 所在的服务节点上；式(50)表示VNF f j 至多有一个实例在 id 上运行.
∀ 
(51)
∀ id ∈ ID - ID D .
(52)
∀ f j ∈ T , id ∈ ID - ID D .
(53)
∀ 
(54)
式(51)保证虚拟节点被唯一地映射到一个服务器上；式(52)和式(53)分别是服务器可用CPU核数约束和VNF服务能力约束；式(54)表示若至少存在一条以失效VNF节点 为端点的失效虚拟链路成功重映射，则 必映射至某个无故障服务器，并且若 未成功重映射，则以 为端点的失效虚拟链路也重映射失败.
4) 链路约束条件
∀ 
(55)
∀ 
( u , v )∈ E D .
(56)
式(55)表示不重映射未失效的虚拟链路；式(56)表示失效虚拟链路不映射到底层故障链路上.
∀ 
(57)
∀ 
(58)
∀ 
(59)
∀ 
(60)
∀
(61)
∀( u , v )∈ E - E D .
(62)
式(57)是流守恒约束.式(58)和式(59)描述了失效虚拟链路 成功重映射的2种情况.其中，式(58)表示若端点 和 都映射至同一无故障底层节点，则 重映射成功，这是因为本文假设SFF与服务器之间的链路是可靠的；式(59)表示若端点 和 分别映射至不同的无故障底层节点 u 和 v ，且 映射至某条以 u 为起点的底层链路，则必有 重映射成功.式(60)表示只有 的所有失效虚拟链路成功重映射， 才成功恢复.式(58)～式(60)均可进行线性转换.式(61)保证 Q 不小于所有已恢复NSFC时延.式(62)是底层链路的带宽容量约束.
失效服务路径重建算法(算法2和算法3)用于求解Res-NSFC模型的可行解.算法2、算法3依据失效虚拟链路 的类型设计不同方法予以恢复：针对因VNF节点 
或 对应的服务器故障而失效的虚拟链路，即 
采用双重重映射子算法(算法2)重映射失效VNF节点和失效虚拟链路；针对因 
对应的底层路径经过故障节点而失效的虚拟链路，即 
∉ 
∉ 
采用替代路径选择子算法(算法3)在端点位置确定的条件下重映射失效虚拟链路.
4.2.1 双重重映射子算法
由于单个VNF实例可为多条NSFC提供服务，即它对应着多个VNF节点，因此，将失效VNF实例迁移至无故障服务器，等同于将与该实例对应的所有失效VNF节点重映射至该无故障服务器，并且失效VNF实例对应的失效VNF节点越多意味着，该实例的恢复可以提高更多失效NSFC的成功恢复概率.基于此，算法2将对应着同一失效VNF实例的失效VNF节点聚合为一个失效共享节点 
并将 
作为重映射单位，这样不仅保持了多条NSFC对VNF实例的共享关系，而且减少了需要重映射的节点数目.此外，算法2在成功重映射 后，优先映射与其直接相连的其他失效共享节点，从而避免出现部分恢复失效NSFC的情况.
具体地，首先，根据原始映射关系( g (), g ′(), h ())，得到 对应的失效NSFC集合 
对任一 
有失效虚拟链路 
和 
将 按照 
的大小降序排列(行①).然后，优先将 重映射至同一服务节点中的无故障服务器上(行③～⑤)，此种情况下无需重映射失效虚拟链路.之后，若不存在满足需求的服务器，则遍历 的候选服务节点集合 
确定最优服务节点 
最优服务器 
和最优重映射路径集合 BST (行⑥～ )，它们在保证| BST |最大(即成功重映射的失效虚拟链路最多)的前提下使得 BST 中的最大路径时延尽可能小，其中，候选服务节点 
满足： l 和 失效前所在服务节点 
之间的最短路径长度不超过阈值； l 中存在满足 的CPU核数需求的服务器 
最后，根据 
和 BST 的取值，重映射 和以 为端点的失效虚拟链路，并调整 
中待映射节点的顺序(行 ～ ).此外，完全重映射集合 RM 记录恢复失败的失效NSFC，可采用文献[26]中的算法重新构建服务路径.
算法2 . 双重重映射子算法 
① sort 
in decreasing order of 
② 
③ 
中存在无故障服务器 id ′满足 的CPU核数需求 then
④ 
∅；
⑤ else
⑥ H ←0；
⑦ 
⑧ 
⑨ if | Ω l |> H or (| Ω l |= H and
MDly ( Ω l )< MDly ( BST )) then
* MDly ()计算集合中的最大路径时延*
⑩ 
BST ← Ω l ；
end if
end for
end if
if BST ≠∅ then
将 和 
重映射至
中相应路径；
∅ then
或 优先映射；
end if
和 按 
和 
由大到小依次映射；
的唯一失效VNF节点重映射成功，但以它为端点的失效虚拟链路重映射失败* ；
end if
end for
end if
else
∉ 
∉ 
的某个失效VNF节点重映射失败，且该节点具有未失效的邻接VNF节点* ；
end if
end for
end if
end for
if RM ≠∅ then
return RM ;
end if
算法2的关键在于函数 MPaths ()，计算在 重映射至 l 条件下的重映射路径集合 Ω l ，该集合中的元素 
是与失效 
的失效虚拟链路 和 对应的底层路径.为最大化成功恢复的NSFC的数目， MPaths ()将计算重映射路径集合 Ω l 问题转化为最大流问题进行求解，其基本思想是：在链路容量有限的情况下，如果从源点出发每次选择一条不同的路径传输带宽值为1的流，那么在源点和汇点间传输最大流量的路径集合就是连接源点和汇点的最大路径集合. MPaths ()的基本过程是，首先，为底层网络添加伪源点 
伪汇点 
和伪链路，并设置带宽值(行①～ )；之后，函数 Mod_D ()利用Dinic算法 [27] ，计算当 重映射至候选服务节点 l 时，失效虚拟链路集合 
∉ 
对应的重映射路径集合 Ψ l ，以及 
∉ 对应的重映射路径集合 
(行 ～ )；最后，为 返回具有2个元素的集合 
它们分别对应着 和 的重映射路径(行 ～ ).特别地，若 和 均是失效共享节点，则 的重映射路径为空，但会在重映射 
已重映射)时再次计算.
① 
*添加伪源点 伪汇点 
；
② 
是以 为端点失效虚拟链路集合* ；
③ 
*添加伪链路*
④ 
∉
⑤ 
⑥ 
∉
⑦ 
⑧ end if
⑨ end for
⑩ for all ( u , v )∈ E do
if u 和 v 均不是伪节点 then
λ ( u , v )← 
λ ( u , v ) λ max 
；
else λ ( u , v )←1;
end if
end for
∉ 
∉
∅ 
∅ then
end if
∅ 
∅ then
end if
end for
return Ω l .
① 
*调用 Dinic 函数* ;
② for all P ∈ Φ do
③ 
④ 
⑤ 
⑥ else if P containing 
then
⑦ 
⑧ end if
⑨ end for
⑩ end for
return Ψ .
4.2.2 替代路径选择子算法
重映射失效虚拟链路 
是在 
和 
间找到一条不经过故障节点且满足带宽需求 
的替代路径.为尽可能多地恢复失效NSFC，算法3将 按其带宽需求升序排列，并依次计算替代路径.其中，函数 MDP ()在Dijkstra最短路径算法的基础上，将底层链路带宽容量和虚拟链路带宽需求作为链路选择依据，计算2点间时延最小的路径，这可以减小已恢复NSFC时延.
算法3 . 替代路径选择子算法 
① 
将 按 升序排列；
② 
③ 
④ 
∅ then
⑤ 将 重映射至 
⑥ else 采用文献[26]中算法重新为 所属NSFC构建服务路径;
⑦ end if
⑧ end for
在算法2的主函数中最耗时的操作是调用函数 MPaths ()，以获得重映射路径集合.由于 MPaths ()的关键步骤是利用Dinic算法，故时间复杂度为 O ( d 2 × l ).由此，若失效共享节点的数目是 p ，候选服务节点集合大小为 q ，则算法2在最坏情况下的时间复杂度为 O ( p × q × l × d 2 ).
假设失效虚拟链路集合 
的大小为 w ，算法3利用Dijkstra最短路径算法为每条 选择替代路径，时间复杂度为 O ( w × d ×log d + w × l ) [28] .
底层网络拓扑由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
表4 实验拓扑的节点个数信息
实验在配置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映射请求数目之间的比值.
3) KSFC 已恢复NSFC最大时延.
4) NSFC SFC故障恢复率.即成功恢复的NSFC SFC数目与因底层单点故障而失效的NSFC SFC数目的比值，其中，成功恢复的SFC既包括采用备用服务路径恢复的KSFC，也包括通过重映射而恢复的NSFC.
5) SFC成功运行率.即在SFC请求不断到来和底层网络间歇性出现单点故障的情况下，成功运行的SFC数目与SFC映射请求数目之间的比值，其中，成功运行的SFC既包括成功映射的新到的KSFC和NSFC映射请求，也包括成功恢复的已部署的KSFC和NSFC，该指标反映了SFC映射的有效性和对节点故障的SFC恢复能力.
6) 额外带宽消耗率.即SFC消耗的额外带宽与底层链路带宽总量之间的比值，其中，SFC消耗的额外带宽包括为KSFC的备用路径和桥接路径分配的带宽，以及为恢复NSFC分配的带宽.
实验分为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将它们映射到底层网络 T 3 中，测算KSFC映射成功率和算法运行时间.实验重复50次取均值，结果如图2所示.当 MaxHops ≤4时，KSFC映射成功率随 MaxHops 的增大而增大；当 MaxHops >4时，成功率几乎维持不变，而算法运行时间随着 MaxHops 的增大而增加.因此， MaxHops =4是相对最佳取值，后续实验中均采用该值.
实验在不同KSFC数目和不同底层网络规模条件下，分别采用PBSP-Bld和Opt-KSFC将随机生成的若干条KSFC映射至底层网络，测算KSFC最大时延、KSFC映射成功率和算法运行时间.实验重复50次取均值，结果如图3～5所示：
Fig. 3 Max latency of KSFC
图3 KSFC最大时延
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个节点( T 4 )且KSFC数目为10时，Opt-KSFC的KSFC最大时延比PBSP-Bld减小约16.4%，映射成功率提高1.85%，但算法运行时间增大了约84.4倍.
5.2.2 失效服务路径重建算法有效性评估实验
实验借鉴文献[9]中的方法，在网络 T 3 中随机部署若干条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可生存性映射方法有效性评估实验
为整体评估SFC可生存性映射方法的有效性，实验在网络 T 6 中应用SFC可生存性映射方案.当新的SFC映射请求到来时，采用PBSP-Bld映射KSFC，但因为本文只关注恢复已部署的失效NSFC，所以实验采用文献[26]中的方法映射NSFC；当底层网络发生单点故障时，利用桥接路径将KSFC迅速切换至备用服务路径，采用FSP-Res重映射NSFC中的失效VNF节点和虚拟链路.假设SFC映射请求的到达过程服从强度 λ r =4的泊松过程，SFC生存时间服从均值为10 ms的指数分布，底层单点故障发生过程服从强度为 λ n 的泊松过程，单点故障恢复时间服从均值为15 ms的指数分布.此外， 
= λ n λ r ， 
越大意味着底层单点故障发生越频繁，并将KSFC在所有SFC中占的比例记为 σ ，在每次实验期间保 
和 σ 不变，测算平均SFC故障恢复率、平均SFC成功运行率和平均额外带宽消耗率.实验重复50次取均值，结果如图8～10所示.
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 平均额外带宽消耗率
由图8可知， 
一定的条件下， σ 越大，平均SFC故障恢复率越大，且 σ 越接近1，平均SFC故障恢复率越接近100%，这是因为 σ 越大表示KSFC越多，而网络在底层单点故障之前就为KSFC分配了备用服务路径.在 σ 一定的条件下，平均SFC故障恢复率 
的增大而减小，但是 σ 越小，平均SFC故障恢复率的降幅越大，这是因为 σ 越小表示NSFC越多，而网络不为NSFC预留备用资源，当单点故障频繁发生时，有限的底层网络资源难以满足恢复失效NSFC的需要.
由图9可知， 
<0.45时，由于单点故障发生概率低，平均SFC成功运行率主要由SFC映射的有效性决定，因此 σ 越大，备用服务路径占用的底层网络资源越多，导致网络可接受的SFC映射请求减少，进而致使平均SFC成功运行率降低. >0.65时，平均SFC成功运行率受到SFC恢复的有效性影响，其值随 σ 的增大而增长，但单点故障频繁发生会加剧底层网络资源的匮乏程度，因此增长幅度不大， σ =0.8的SFC成功运行率仅比 σ =0.2的高3.47%～10.72%.此外，尽管平均SFC成功运行率会随 
的增大而下降，但其总能保持在59.2%以上.
由图10可知， 一定的条件下， σ 越大，平均额外带宽消耗率越大，这是因为底层网络需要为更多的KSFC备用服务路径和桥接路径分配带宽.在 σ 一定的条件下，随 的增大，由于底层链路失效现象愈加频繁，恢复NSFC所消耗的带宽增多，故平均额外带宽消耗率增大.
综上所述，PBSP-Bld算法和FSP-Res算法能够在较短的时间内获得接近最优的性能表现，并且随着底层网络规模的增大，二者在时间开销上的优势愈加显著.可生存SFC映射方法在底层单点故障频繁发生时能有效保证SFC的正常运行，但是其性能表现受KSFC和NSFC之间的数量比例的影响，并且在KSFC数量比例大时，该方法消耗的额外带宽资源也较大，需要从减小备用带宽资源开销方面对该方法进行改进.
针对已有可生存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[EB 
OL]. (2015-04) [2017-10-10]. https: www. rfc-editor. org info rfc7498
[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 IFIP IEEE 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[EB OL]. (2015-10) [2017-11-10]. https: www.rfc-editor.org info rfc7665
[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
Liu Yi , born in 1991. PhD candidate. Her main research interests include SDN security and SFC technology.
Zhang Hongqi , born in 1962. PhD, professor. His main research interests include network security and classification protection (zhq37922@126.com).
Yang Yingjie , born in 1971. PhD, professor. His main research interests include security management and situation awareness (yangyj-2010@qq.com).
Chang Dexian , born in 1977. PhD, associate professor. His main research interests include SDN security and trusted computing (changdexian@126.com).
Liu Yi, Zhang Hongqi, Yang Yingjie, and Chang Dexian
( PLA Information Engineering University , Zhengzhou 450001) ( Henan Key Laboratory of Information Security , Zhengzhou 450001)
Abstract Aiming at embedding the service function chain (SFC) in substrate network under the condition of single-node or single-link failure, this paper proposes a hierarchical method for survivable SFC embedding. The method takes into account both improving the survivability of SFC and reducing the resource consumption of substrate network. For the key service function chain (KSFC) delivering essential services, it pre-allocates backup resources for possible failures in the future. Meanwhile, for the normal service function chain (NSFC) delivering common services, it quickly re-embeds the failed nodes and links after a failure has occurred. Firstly, taking into account minimizing the service latency of SFC, we provide two mixed integer linear programming (MILP) formulations for the survivable embedding problem of KSFC and NSFC. Secondly, we propose two heuristic algorithms to solve the formulations quickly, namely, the primary-backup service path building algorithm (PBSP-Bld) for the KSFC and the failed service path restoring algorithm (FSP-Res) for the NSFC. The PBSP-Bld not only embeds nodes and links alternately based on greedy strategy to reduce the service latency of SFC, but also establishes bridging path between the primary and the backup service paths, which improves the speed of path switching and reduces the packet loss rate during path switching. Additionally, the FSP-Res finds the best re-embedding positions for failed nodes by means of the max-flow problem, which increases the number of recovered NSFCs. It also uses the modified version of Dijkstra’s shortest path algorithm to select re-embedding paths with low latency. Experimental results demonstrate the good performance of the heuristic algorithms under different network conditions. Moreover, the proposed method keeps the success ratio of running SFC above 59.2% under the simulated network environment.
Key words service function chain (SFC); survivable service function chain embedding; mixed integer linear programming; max-flow problem; service latency
摘 要 针对在底层网络可能发生单点和单链路故障情况下的服务功能链(service function chain, SFC)映射问题，提出一种区分等级的可生存SFC映射方法，为提供重要服务的关键SFC预先分配备用资源，为提供普通服务的普通SFC快速重映射失效部分，从而兼顾提高SFC可生存能力和降低底层网络资源开销的需求.首先，在考虑最小化SFC服务时延的条件下，分别为关键SFC和普通SFC的可生存映射问题建立混合整数线性规划模型.其次，提出2种启发式的模型求解算法，其中，面向关键SFC的主备服务路径构建算法采用贪心思想交替进行节点和链路映射，以减小SFC服务时延，并在主备服务路径之间建立桥接路径，以提高路径切换速度和降低路径切换过程的丢包率；面向普通SFC的失效服务路径重建算法引入最大流问题求解失效节点的最佳重映射位置，以提高成功恢复的失效普通SFC数目，并利用改进的Dijkstra最短路径算法选择时延低的重映射路径.最后，在不同网络条件下实验验证了启发式算法的性能，并且在模拟网络环境中所提可生存SFC映射方法能保证SFC的成功运行率在59.2%以上.
关键词 服务功能链；可生存服务功能链映射；混合整数线性规划；最大流问题；服务时延
中图法分类号 TP393.08
收稿日期： 2017-12-05；
修回日期： 2018-02-15
基金项目： 国家“八六三”高技术研究发展计划基金项目(2012AA012704)；郑州市科技领军人才项目(131PLJRC644)
This work was supported by the National High Technology Research and Development Program of China (863 Program) (2012AA012704) and Zhengzhou Science and Technology Talents Program (131PLJRC644).
通信作者： 刘艺(liuyi9582@126.com)