软件定义网络(Software Defined Network，SDN)是一种分离控制平面与数据平面的新型网络架构，数据平面的交换机仅负责数据转发与信息收集，控制功能由控制平面的控制器负责。控制器监控和管理数据平面，以实现个性化的网络控制逻辑。

故障恢复是保证SDN网络可靠性的关键，目前有关SDN故障恢复方面的研究主要分为反应式恢复和主动式恢复^[1]。反应式恢复的时延较长，因为其恢复过程中，交换机需要与控制器通信以及更新流表项。而主动式恢复在故障发生之前安装备份流表项，故障发生后立即进行数据流的重路由，从而保证故障在电信级时间(50 ms)内恢复。因此，主动式恢复是当前故障恢复研究领域的主流恢复方案。

由于软件定义网络的特性，故障恢复主要发生在控制平面^[2-4]和数据平面^[5-14]。数据平面的组件故障会导致数据流无法到达目的交换机，影响用户的通信质量。在SDN的数据平面，为了更合理地分配网络资源，WANG等^[5]提出了一种反应式策略和主动式策略相协同的链路故障恢复机制，以保证网络连通性能够在故障发生后短时恢复，然后基于网络实时监控信息对备份路径进行动态调整，从而实现了恢复时间和带宽资源利用上的平衡；ZHANG等^[6]对网络中的链路进行重要性分级，针对不同等级链路提供不同的备份策略，减少了流表项数量；WANG等^[7]提出一种基于共享环的备份路径方案，使得连接核心交换机所形成的环路被所有备份路径共享，环中备份流表项复用率高，从而节省了备份资源；WANG^[8]提出了对数据流进行分类并分配不同的备份策略，减少了故障恢复时延和数据包丢失率；在计算备份路径时，ISYAKU等^[9]除了对数据流进行分类外，还考虑了交换机中的流表利用率，减少了备份路径的资源消耗；THORAT等^[10]提出使用VLAN标签的恢复策略，受故障影响的数据流被统一贴上标签形成聚合流，随即被转发到故障链路的另一端节点，从而减少了备份流表项；肖军弼等^[11]将网络进行划域，域内数据流使用MPLS标签进行匹配，同样节省了备份流表项；TRAM等^[12]借助机器学习方法学习流量的动态性，估算路径的优度后，自适应更新备份路径，其带宽利用率、恢复时间分别比基准模型提升了24%、50%；MOHAN等^[13]提出了2种实现主路径保护的主动式算法(FLR算法和BLR算法)，故障发生后，可根据当时的网络状态选择FLR算法或者BLR算法，2种算法都在一定程度上减少了备份路径的资源消耗，但是FLR算法仍然消耗了较多备份资源，BLR算法的故障恢复时延还有待提升。

现有主动式恢复方法的备份路径设计往往难以兼顾故障恢复的备份资源消耗和恢复时延，基于单链路故障，本文提出了一种基于链路故障位置的主动式故障恢复方案(LBR)，将主路径中的链路根据位置分成两部分，采用分而治之的方式，对不同故障位置的链路配置不同的备份路径，以实现快速故障恢复和对备份流表项资源的合理利用。并通过实验评估该方案性能，实验包括：(1)注重恢复时延和注重备份资源消耗的不同场景下，LBR方案与典型方案所展现的性能；(2)各方案在备份流表项消耗、恢复时延指标上的比较；(3)不同主路径长度对LBR方案性能的影响；(4)LBR方案在不同网络拓扑的适用性。

1.   问题描述

根据备份路径的起点与终点，可将现有备份路径的策略归纳为3类：

(1) 第1类为连接数据流源节点到目的节点的备份路径。这类策略主要有1+1方案^[14]和回溯方案^[14]。其中，1+1方案是指为主路径计算一条从源节点到目的节点且尽量不与主路径相交的备份路径，2条路径同时传输数据流，因此，主路径即使断开也能保持正常通信。但1+1方案需要占用2条路径的带宽资源，难以进行推广。回溯方案是指在故障发生后数据流沿着主路径回溯至源节点，然后沿着备份路径传输至目的节点。与1+1方案相比，回溯方案不需占用过多的带宽资源。如图 1所示，路径 < S₁—S₂—S₃—S₄—S₅—S₆>为数据流的主路径，当链路 < S₂—S₃>发生故障时，回溯方案的备份路径为 < S₂—S₁—S₇—S₈—S₉—S₁₀—S₆>。因为回溯方案为主路径配置了一条公共备份路径，所以备份路径的复用率高，需要的备份资源较少。然而，此方案在恢复过程中会造成额外的延迟，如出现最坏的情况，即当链路 < S₅—S₆>发生故障时，数据流必须沿着主路径回溯至源节点S₁，再沿着备份路径到达S₆，特别是在大型网络中，回溯方案会导致较大的恢复时延。

图  1  SDN网络链路故障恢复示例

Figure  1.  Example of link failure recovery of SDN network

下载: 全尺寸图片 幻灯片

(2) 第2类为连接故障链路两端节点的备份路径。如图 1，当链路 < S₂—S₃>发生故障时，备份路径为 < S₂—S₁₁—S₁₂—S₃>。数据流重路由至故障链路另一端节点后，继续沿着主路径传输到目的节点，从而复用后序主路径的备份资源。但这种策略需要为主路径的每一条链路都计算一条备份路径，消耗较多的备份资源。

(3) 第3类为连接故障上游节点到数据流目的节点的备份路径。如图 1，当链路 < S₂—S₃>发生故障时，备份路径为 < S₂—S₁₃—S₁₄—S₆>。数据流直接重路由至目的节点，可以保证恢复时延，但需要的备份路径数量较多，且从检测节点直接连接至目的节点，需要消耗大量的备份资源。

综上所述，一般的故障恢复策略往往难以兼顾恢复时延和备份资源消耗。本文在综合考虑故障恢复时延和备份资源2个因素的前提下，将恢复问题建模为一个优化问题，然后基于该问题提出了一种恢复方案，从而选取最合适的备份路径，以在节省备份资源的基础上减少故障恢复时延。

2.   系统建模

本文将SDN网络记为一个无向图G=(V，E)，其中，V为所有交换机的集合，E为连接交换机的链路集合。本文所用其他主要符号见表 1。

表  1  主要符号及其含义

Table  1.  Mathematical notations and description

符号	含义
M	网络所有交换机的备份资源消耗之和
Trec	网络故障恢复时间
mi	交换机i的备份资源消耗
s, d	主路径的源节点、目的节点
k	故障恢复时在主路径中的一个绕行节点
Pi, jwork	主路径中节点i到节点j的路径
L1, L2	第1类链路、第2类链路的集合
Ps, dback1	第1类链路所有备份路径的公共路径
Pk, dback2	第2类链路所有备份路径的公共路径
Pi, jback1	路径Ps, dback1中节点i到节点j的路径
lin, lout	链路l的入口节点、出口节点
trlink	单个数据包在链路r的传输时延
tenode	单个数据包在节点e的处理时间
V(P)	路径P中交换机节点的集合
E(P)	路径P中链路的集合
C	备份路径的恢复成本
N	主路径的节点数

下载: 导出CSV 

| 显示表格

链路故障发生之前，控制器规划备份路径并将相应备份流表项部署于备份路径的交换机中。故障恢复过程中所有交换机的备份资源消耗之和M可以用下式表示：

其中，m_i为交换机i中备份流表项需要的内存空间，V(P^back)为用于恢复链路故障的备份路径P^back中交换机节点的集合。

故障恢复需要综合考虑恢复时间和备份资源消耗。本文用恢复成本C表示故障恢复过程中恢复时间和备份资源消耗的情况^{[5, 13]}：

其中：权重参数α、β分别为恢复时间、备份资源消耗在恢复过程中所占的比重；T_rec为网络的恢复时间，即原数据流的最后一个数据包到达目的交换机和重定向流的第一个数据包到达目的交换机的时间之差；f(·)为指标的标准化函数，取值范围为[0, 1]，本文采用最小最大归一化函数。可知，恢复成本C是一个综合考虑了恢复时间和备份资源消耗的指标，C较小，则意味着故障恢复方案的恢复时间和备份资源消耗会在一个较小的范围。因此，整个链路故障的恢复问题可以转化为一个优化模型：

Subject to:

其中，条件(4)是为了避免备份路径中的交换机发生流表溢出现象，即避免备份流表项的存储空间小于交换机中的存储空间上限m_max；条件(5)是为了整个恢复过程所需的时间小于电信级的恢复时间上限T_max(50 ms)。

3.   LBR方案

若为主路径的每条链路都分配一条备份路径，则将产生较大的备份资源消耗。采用回溯方案为主路径配置一条公共备份路径，可以节省备份资源。然而，当接近目的节点的链路发生故障时，数据流需回溯至源节点并沿着备份路径重路由至目的节点，会产生较大恢复时延。若这部分链路发生故障，受到影响的数据流既不需要回溯至源节点，又能绕行至公共备份路径，则可在节省备份资源的基础上减少恢复时延。因此，本文提出对主路径中的前半部分和后半部分链路采取分而治之的方式，设计了一种基于链路故障位置的主动式故障恢复方案(LBR)。

LBR方案的具体流程(图 2)为：首先，在主路径中选取一个特殊的核心交换机作为绕行节点，记为节点k；然后，对主路径中在节点k之前的链路和在节点k之后的链路采用不同的故障恢复策略；最后，将备份路径对应的备份流表项存储于交换机中。

图  2  LBR方案流程图

Figure  2.  Flow chart of LBR scheme

下载: 全尺寸图片 幻灯片

3.1   快速修复组表

实现主动式故障恢复，需要在故障发生前下发备份流表项，并可以通过OpenFlow协议的快速修复组表(fast failover)实现链路故障的本地化修复^[15]：对于每个需要快速修复组表功能的流表项，在动作字段中指定相应的组表，然后在动作桶中部署所需的指令集，其中的组表类型设置fast failover。若动作桶中的首个指令可以执行，则跳出动作桶，后面的指令不再执行。若指令不可执行，则向下执行第一个可正常工作的指令，随后跳出动作桶。如图 3所示，图中的2个流表项成功匹配到数据包后，执行流表项动作字段中指向的组表的动作桶。若动作桶中第一个指令可以正常工作，即端口1正常，则将数据包发送到该端口。若端口1异常，则将数据包发送到端口2。利用组表，交换机可以在故障发生后自主地将中断流转移到备份路径。目前借助于组表实现主动式恢复是主流方式，因此，本文提出的LBR方案通过组表实现链路故障的主动式恢复。

图  3  快速恢复组表

Figure  3.  Fast failover failure group table

下载: 全尺寸图片 幻灯片

3.2   链路的备份策略

本文将主路径中节点k之前的链路l归为第1类链路，满足l∈E(P_{s, k}^work)；节点k之后的链路l归为第2类链路，满足l∈E(P_{k, d}^work)；为2类链路分别配置不同的备份路径。记第1类链路的集合为L₁，第2类链路的集合为L₂，具体的备份策略见算法1。

算法1   链路备份策略

输入：网络拓扑G，主路径P_{s, d}^work，绕行节点k

输出：第1类链路的备份路径集合P₁，第2类链路的备份路径集合P₂

//1~5行计算第1类链路的备份路径集合

1. P₁←{}

2. P_{s, d}^back1←ShortestPath(G, s, d)

3. for all l∈L₁ do

4.         $P_1 \leftarrow\left\{P_{l_{\text {in }}, s}^{\text {work }} \cup P_{s, d}^{\text {back1 }}\right\} \cup P_1$

5. end for

//6~29行计算第2类链路的备份路径集合

6. P₂←{}

7. P_{k, d}←P_{k, s}^work∪P_{s, d}^back1

8. P ← P_{s, d}^back1－{s, d}

9. C ← Inf

10. for all n∈ V(P) do

11.         if ShortestPath(G, k, n) exists then

12.             temp←ShortestPath(G, k, n)∪P_{n, d}^back1

13.                 C′← C(temp)

14.                 if C′ < C then

15.                     P_{k, d}=temp

16.                     C←C′

17.                 end if

18.             end if

19. end for

20. if ShortestPath(G, k, d) exists then

21.         P_{k, d}^′←ShortestPath(G, k, d)

22.         if $C\left(P_{k, d}^{\prime}\right)<C\left(P_{k, d}\right)$ then

23.             $P_{k, d}^{\text {back2 }} \leftarrow P_{k, d}^{\prime}$

24.         else

25.             $P_{k, d}^{\mathrm{back2}} \leftarrow P_{k, d}$

26.end if

27.for all l∈L₂ do

28.         $P_2 \leftarrow\left\{P_{l_{\mathrm{in}}, k}^{\text {work }} \cup P_{k, d}^{\text {back2 }}\right\} \cup P_2$

29.end for

对于第1类链路l，算法1根据主路径的源节点s与目的节点d，计算一条与主路径的各条链路都不相交的最短路径，记为P_{s, d}^back1，作为第1类链路的所有备份路径的公共路径，又称为第1类链路的共享备份路径。路径P_{lin, s}^work与路径P_{s, d}^back1组成第1类链路l的备份路径。当故障发生时，数据流回溯到源节点后沿着P_{s, d}^back1重路由至目的节点。如图 4所示，假设节点S₃作为绕行节点k，则链路 < S₁—S₂>及 < S₂—S₃>为第1类链路，第1类链路的共享备份路径为 < S₁—S₇—S₈—S₉—S₁₀—S₆>。当链路 < S₂—S₃>发生故障时，数据流的备份路径为 < S₂—S₁—S₇—S₈—S₉—S₁₀—S₆>。其中节点S₁、S₂中的流表项和组表项的情况如图 5所示。

图  4  第1类链路故障恢复示例

Figure  4.  Example of failure recovery of the first type of link

下载: 全尺寸图片 幻灯片

图  5  交换机S₁、S₂中的流表项和组表项的情况

Figure  5.  The flow table enrtys and group table entrys on S₁, S₂

下载: 全尺寸图片 幻灯片

对于第2类链路l，首先以节点k为绕行节点，计算一条连接至P_{s, d}^back1且复用P_{s, d}^back1后半部分的路径，记为P_{k, d}。连接点的选取基于最小恢复成本原则。其次，根据节点k与主路径的目的节点，计算一条与主路径和P_{s, d}^back1的各条链路都不相交的最短路径，记为P_{k, d}^′。比较路径P_{k, d}和路径P_{k, d}^′，从中选择使得恢复成本C最小的路径，作为第2类链路所有备份路径的公共路径，即第2类链路的共享备份路径，记为P_{k, d}^back2。可知，若选择前者则无需再为复用P_{s, d}^back1部分的路径下发备份流表项。路径P_{lin, k}^work与路径P_{k, d}^back2组成第2类链路l的备份路径。如图 6所示，假设节点S₃作为绕行节点k，则链路 < S₃—S₄>、 < S₄—S₅>和 < S₅—S₆>为第2类链路。比较路径 < S₃—S₉—S₁₀—S₆>和路径 < S₃—S₁₁—S₆>用于共享备份路径的恢复成本C，若路径 < S₃—S₉—S₁₀—S₆>用于共享备份路径的恢复成本C更小，则第2类链路的共享备份路径为 < S₃—S₉—S₁₀—S₆>。即当链路 < S₄—S₅>发生故障时，数据流的备份路径为 < S₄—S₃—S₉—S₁₀—S₆>。否则，第2类链路的共享备份路径为 < S₃—S₁₁—S₆>。当链路 < S₄—S₅>发生故障时，数据流的备份路径为 < S₄—S₃—S₁₁—S₆>。其中，节点S₃中的流表项组表项情况如图 7所示。由于第2类链路只需要回溯至节点k即可重路由至目的节点，大大减少了目的节点近端链路故障发生时网络的恢复时延。

图  6  第2类链路故障恢复示例

Figure  6.  Example of failure recovery of the second type of link

下载: 全尺寸图片 幻灯片

图  7  交换机S₃中的流表项和组表项的情况

Figure  7.  The flow table entrys and group table entrys on S₃

下载: 全尺寸图片 幻灯片

3.3   绕行节点k的选取

当第1类链路l发生故障时，数据流立即回溯至源节点，然后流经路径P_{s, d}^back1到达目的节点。同时，链路故障点之后的数据流继续沿着主路径到达目的节点。网络的恢复时间为原数据流的最后一个数据包到达目的交换机和重定向流的第一个数据包到达目的交换机的时间之差。数据流到达目的节点的时间由所经过路径上的全部链路的传输时延和在全部节点上的处理时间组成。记数据流中的一个数据包在链路r的传输时延为t_r^link，数据包在节点r的处理时间为t_r^node。当第1类链路l发生故障时，原数据流尾数据包与重定向流首数据包所经过路径的全部链路传输时延之差ΔT₁^link(l)为：

其中，E(P)表示路径P上所有链路的集合，P_{i, j}^work表示主路径中节点i到节点j的路径，P_{s, d}^back1表示第1类链路的所有备份路径的公共路径。所经过的全部节点处理时间之差ΔT₁^node(l)为：

其中，V(P)表示路径P上所有节点的集合。则对于第1类链路，发生故障时平均恢复时延为：

其中，L₁表示第1类链路的集合。

对于第2类链路，链路l发生故障时，原数据流尾数据包与重定向流首数据包所经过路径的全部链路传输时延之差ΔT₂^link(l)、所经过的全部节点处理时间之差ΔT₂^node(l)分别为：

其中，P_{k, d}^back2表示第2类链路的所有备份路径的公共路径。则发生故障时平均恢复时延为：

其中，L₂表示第2类链路的集合。

由3.2可知，若P_{k, d}^back2复用了P_{s, d}^back1的一部分路径，记P_{k, d}^back2与P_{s, d}^back1的第1个交点为节点n，则网络所有交换机的备份资源消耗之和为：

其中，m_i表示交换机i的备份资源消耗。

若P_{k, d}^back2是一条与P_{s, d}^back1的各条链路都不相交的路径，则网络所有交换机的备份资源消耗之和为：

由式(2)、(7)~(12)，有

由以上分析可知，绕行节点k的选取直接决定了用于故障恢复所需要的恢复成本，即网络的恢复时延和备份资源消耗。为了尽可能减小恢复成本，首先评估主路径中所有节点作为绕行节点k的恢复成本，然后选取使得恢复成本最小的节点作为绕行节点k，如算法2。

算法2   节点k的选取

输入：网络拓扑结构G，主路径P_{s, d}^work

输出：节点k

1.P ← P_{s, d}^work-{s, d}

2.C(k)← Inf

3.for all i∈V(P) do

4.     if C(i) < C(k) then

5.         k←i

6.     end if

7.end for

本文的LBR方案借鉴回溯方案的思想配置备份路径，以使备份方案具有备份路径复用率高的特性，因此所需的备份资源较少。针对主路径后半部分链路故障造成恢复时延过长的问题，在主路径中间节点采用“搭桥”方式，使得后半链路发生故障时，不必重新回溯到远端的源节点再重路由到目的节点，而是回溯到中间节点k即可重路由至目的节点，有效保障了故障发生时网络的恢复时延。

4.   实验评估

将LBR方案与DT方案^[14]、ST方案^[5]、FLR方案^[13]进行对比实验，其中，DT方案为与LBR方案的研究思路比较相近的回溯方案，ST方案为基于最短路径的故障恢复方案，FLR方案为根据最少跳数原则将数据流从故障点前向路由到主路径上的另一个下行交换机的方案。将数据流在每条链路的传输时延和在每个节点的处理时间设置为定值，则故障恢复时间用故障发生后原数据流所经过路径和重定向流所经过路径的跳数之差来近似表示。本文依次选取网络拓扑所有的节点作为主路径的源节点来进行多组实验，每组实验中的目的节点为网络中除源节点外的所有节点。对相同主路径长度产生的实验数据取平均值，并将此平均值作为该主路径长度的最终实验数据。

4.1   实验环境

本文采用的实验环境为Intel(R)Core(TM)i5-5200U CPU@2.20 GHz, 4.00 GB内存，操作系统Windows10版本(64位)，利用PyCharm软件进行实验，使用NetworkX工具建模。

4.2   实验拓扑

实验采用的拓扑结构选自于SNDLib^[16]的3种骨干网拓扑：JANOS-US-CA、Cost266、NOBEL-EU(图 8)。

图  8  3种骨干网拓扑

Figure  8.  Three backbone topologies

下载: 全尺寸图片 幻灯片

4.3   结果与分析

4.3.1   不同权重系数β对恢复成本的影响

本实验中交换机流表项消耗数量的权重系数β的取值范围为[0.1, 0.9]。当主路径的节点数N=11时，拓扑JANOS-US-CA中不同故障恢复方法的恢复成本(图 9)表明：(1)在β的取值范围为[0.1, 0.4]时，即较为注重网络恢复时延的情况下，FLR方案的恢复成本最小，DT方案的恢复成本最大，LBR方案的恢复成本较接近于FLR、ST方案。这是由于FLR方案和ST方案都是基于最短路径原则配置备份路径，网络能在故障后进行快速恢复，DT方案需要数据流重新回溯到源节点，恢复时间并不理想。(2)在β的取值范围为[0.5, 0.9]时，即较为注重备份资源消耗的情况下，ST方案的恢复成本逐渐变得最大，LBR方案的恢复成本最小。这是由于ST方案需要为每条链路都分配备份路径，消耗较多的备份流表项。LBR方案只需要在DT方案的基础上增加少量备份流表项，便可明显减少恢复时延。所以，LBR方案的恢复成本是最小的。

图  9  拓扑JANOS-US-CA中不同权重系数β下的恢复成本(N=11)

Figure  9.  The recovery cost of different weight coefficients β at JANOS-US-CA(N=11)

下载: 全尺寸图片 幻灯片

4.3.2   LBR方案的有效性分析

设交换机流表项消耗数量的权重参数β=0.7，相应地，α=0.3，主路径的节点数N为4~11，研究拓扑JANOS-US-CA中不同故障恢复方法的备份流表项消耗数和恢复时间。

由结果(表 2)可知：(1)随着主路径节点数的增加，FLR、ST方案的恢复时间较为稳定，LBR方案的恢复时间逐渐增大，这是因为FLR、ST方案的中断流总是沿着最短路径回到主路径，其恢复时间较少且稳定，而LBR方案的中断流所经过的路径长于最短路径。LBR、FLR、ST方案的备份流表项消耗数都逐渐增加，但LBR方案消耗的备份流表项数量少于FLR、ST方案，这是因为LBR方案的备份路径复用率高于FLR、ST方案。因此，对于时延较不敏感的数据流采用LBR方案进行故障恢复可以有效节省备份流表项。(2)FLR方案使用故障链路上游节点到主路径下行节点的最短路径作为链路的备份路径，ST方案使用故障链路两端的最短路径作为链路的备份路径，所以FLR方案为链路分配的备份路径长度比ST方案的短，更能节省备份流表项，恢复时间也更少。而故障链路两端的最短路径经常是故障链路上游节点到主路径下行节点的最短路径，因此FLR方案与ST方案的性能较相近。(3)与DT方案相比，LBR方案在大约增加了1条备份流表项的情况下，恢复时间减少了34%~44%，显示LBR方案具有一定的实用性。这是由于LBR方案并不需要回溯到源节点，只需要回溯到中间的绕行节点就能进行重路由。主路径与第1类链路的共享备份路径在网络拓扑中的位置往往较为接近，因此数据流从中间节点绕行至该共享备份路径所需的流表项较少。综上可知，LBR方案的优势为：与FLR、ST方案相比，LBR方案节省了备份流表项，主路径的节点数N=11时的备份流表项分别比FLR、ST方案减少23%、27%, 随着主路径长度的增加，节省效果更明显；LBR方案的恢复时间虽多于FLR方案，但其增幅较为平缓；LBR方案仅比DT方案增加了0.3~1.3条备份流表项，但恢复时间减少了34%~44%，在只付出极小存储资源的代价下大幅减少了恢复时间。

表  2  4种方案在不同主路径长度的备份流表项和恢复时间

Table  2.  Backup flow entries and recovery time of ST、FLR、DT and LBR at different lengths of work path

主路径节点数	ST方案			FLR方案			DT方案			LBR方案
	备份流表项/条	恢复时间/跳		备份流表项/条	恢复时间/跳		备份流表项/条	恢复时间/跳		备份流表项/条	恢复时间/跳
4	8.589	1.937		8.507	1.896		6.736	3.736		8.062	2.354
5	11.601	1.949		11.350	1.879		8.658	4.658		9.674	2.759
6	14.318	1.916		14.026	1.860		10.698	5.698		11.603	3.296
7	17.333	1.973		17.086	1.934		12.729	6.729		13.621	3.907
8	20.634	1.986		20.291	1.938		14.901	7.901		15.745	4.820
9	23.428	2.025		23.306	2.007		16.750	8.750		17.416	5.270
10	25.333	2.007		25.062	1.951		18.187	9.187		18.562	5.340
11	27.500	1.850		26.000	1.633		19.666	9.666		19.967	5.433

下载: 导出CSV 

| 显示表格

4.3.3   不同主路径长度对恢复成本的影响

设β=0.7，主路径的节点数N为4~11，研究拓扑JANOS-US-CA中不同故障恢复方法的恢复成本。由结果(图 10)可知：主路径节点数越多，不同故障恢复方法用于恢复故障的恢复成本均越大。其中，LBR方案的恢复成本基本上都是最小的，并且随着节点数增加，这种优势越来越明显。主要原因为：(1)随着主路径长度的增加，FLR、ST方案都需要为每条链路都分配备份路径，因此，备份流表项的消耗越来越大，导致恢复成本明显增大。(2)DT方案中接近目的节点的链路故障造成的恢复时延随着主路径长度的增加愈发增大，导致恢复成本也明显增大。(3)LBR方案能一定程度地缓解上述2种问题，因此恢复成本上升趋势较为缓和，主路径长度越大，数据流从中间节点重路由至目的节点的作用也越大。

图  10  拓扑JANOS-US-CA中不同主路径长度下的恢复成本(β=0.7)

Figure  10.  The recovery cost of different lengths of work path at JANOS-US-CA(β=0.7)

下载: 全尺寸图片 幻灯片

4.3.4   在不同网路拓扑下各算法的恢复成本

由4.3.1至4.3.3节的实验结果可知，在拓扑JANOS-US-CA中，LBR方案较好地兼顾了故障恢复时的恢复时间和资源消耗。本节在拓扑Cost266、NOBEL-EU中进行实验，实验结果表明LBR方案同样具备快速恢复和节约备份资源的性能。具体为：(1)当主路径的节点数N=8、交换机流表项消耗数量的权重系数β的取值范围为[0.1, 0.9]时，拓扑Cost266中不同故障恢复方法的恢复成本(图 11)表明：在β的取值范围为[0.1, 0.3]时，FLR方案的恢复成本最小，LBR方案与FLR、ST方案的恢复成本相差很少；当β>0.3时，LBR方案的恢复成本在β=0.9时略低于DT方案，在β的取值范围为[0.4, 0.8]时是最小的。(2)当主路径的节点数N=8、交换机流表项消耗数量的权重参数β的取值范围为[0.1, 0.9]时，拓扑NOBEL-EU中不同故障恢复方法的恢复成本(图 12)表明：在β的取值范围为[0.1, 0.6]时，LBR方案的恢复成本接近FLR、ST方案；β的取值范围为[0.7, 0.9]时，LBR方案的恢复成本最小。(3)当β=0.6、主路径的节点数N的取值范围为^{[4, 8]}时，拓扑Cost266中不同故障恢复方法的恢复成本如图 13所示；当β=0.8、主路径的节点数N的取值范围为^{[4, 8]}时，拓扑NOBEL-EU中不同故障恢复方法的恢复成本如图 14所示。可以看出，随着主路径节点数的增加，LBR方案的恢复成本都是最小的，并且随着节点数增加，这种优势越来越明显。综上可知，LBR方案在3种拓扑下的性能表现相似，显示该算法具有一定的适用性。

图  11  拓扑Cost266中不同权重系数β下的恢复成本(N=8)

Figure  11.  The recovery cost of different weight coefficients β at Cost266(N=8)

下载: 全尺寸图片 幻灯片

图  12  拓扑NOBEL-EU中不同权重系数β下的恢复成本(N=8)

Figure  12.  The recovery cost of different weight coefficients β at NOBEL-EU(N=8)

下载: 全尺寸图片 幻灯片

图  13  拓扑Cost266中不同主路径长度下的恢复成本(β=0.6)

Figure  13.  The recovery cost of different lengths of work path at Cost266(β=0.6)

下载: 全尺寸图片 幻灯片

图  14  拓扑NOBEL-EU中不同主路径长度下的恢复成本(β=0.8)

Figure  14.  The recovery cost of different lengths of work path at NOBEL-EU(β=0.8)

下载: 全尺寸图片 幻灯片

5.   结束语

本文讨论了SDN数据平面的故障恢复问题，针对现有主动式恢复方法的备份路径设计难以兼顾故障恢复的备份资源消耗和恢复时延的不足，提出了一种基于链路位置的SDN数据平面故障恢复方案(LBR)。该方案采用分而治之的思想，根据主路径链路的位置进行分类，不同类型的链路采用不同的恢复策略，以实现恢复时间和备份资源消耗的有效平衡。实验结果表明：LBR方案有效利用了备份资源，与回溯方案相比，在增加了0.3条流表项的条件下，LBR方案的恢复时延减小了34%~44%；在保证了恢复时延的前提下，与FLR、ST方案相比，LBR方案分别减少了23%、27%的备份流表项。