姜厚海，庄 毅，曹子宁

（南京航空航天大学计算机科学与技术学院，江苏 南京 211106）

0 引 言

软件定义网络（Software Defined Network，SDN）是一种新的网络架构［1］，它将传统交换机的控制逻辑与数据转发操作分离，运营商可以通过控制平面的集中控制器轻松部署网络应用。在SDN 中，逻辑集中的控制器直接决定交换机的转发行为，并通过一些标准化协议（如OpenFlow［2］等）监控网络状态。这种架构通过对网络的集中控制，降低了网络管理的复杂度，实现了更灵活的网络控制并有利于网络创新［3-5］。

尽管SDN 控制与转发分离的思想在当下取得了迅速的发展，但由于关键链路拥塞、链路带宽利用不均衡、链路或节点故障等原因，SDN 提供的可靠数据传输受到了巨大挑战。其中，单链路故障是一个必须解决的主要问题，因为单链路故障是网络中最常见的问题［6］，其发生概率高于其他故障几个数量级。

针对单链路故障，目前的故障恢复方案可以分为2 类：反应式故障恢复方案和主动式故障恢复方案［7-8］。这2 种策略的主要区别在于是否提前设置了受保护的路径以及故障恢复过程是否需要控制器参与。反应式故障恢复方案中，在链路发生故障之后，集中控制器会收到链路中断的通知，然后根据当前拓扑信息对备份路径进行动态计算，并将计算得到的备份路径流表规则下发到相关的交换机上，以转移中断的流量［9-10］。主动式故障恢复方案中，集中控制器会在出现任何故障链路之前，预先将备份路径的转发规则下发到相应交换机上。当交换机之间的链路发生故障而无法传输数据时，数据平面的交换机可以自动将中断的流量转发到备份路径，无需控制器参与［11-12］。

这2 种故障恢复方案各有优缺点。对于主动式恢复方案来讲，提前安装备份路径转发规则可以在发现故障后快速恢复，但是会消耗珍贵的三态内容寻址存储器（Ternary Content Addressable Memory，TCAM）资源，大大增加了网络成本［13］。TCAM是一种昂贵且存储受限的高能耗硬件［14］，根据文献［15］显示TCAM 比基于ARM的存储硬件贵400倍。另外，提前安装备份路径难以保证故障发生后备份路径的性能，可能会在故障恢复后发生链路拥塞，造成网络服务质量（QoS）的下降［16］。而反应式故障恢复方案需要在发生故障后重新计算中断流量的备份路径，会增加集中控制器的负载，并且有较高的恢复时延，难以在电信级别要求的50 ms［17］内完成整个链路故障的恢复过程。

从2 种故障恢复方案的优缺点来看，有必要去设计一种新的故障恢复方案来平衡SDN 中的故障恢复时间和存储成本。针对主动式恢复方案中流表规则消耗太多存储资源的缺陷，人们提出了一种基于流聚合的方案来解决这个问题。该方案将所有受到故障影响的流量聚合为一个带有新标签的大流量，控制器只需要为聚合流提前计算备份路径并安装流表规则即可。然而，一个包含所有中断流的聚合流在重路由的过程中，很可能会导致恢复后网络中的潜在拥塞。因此，本文提出一种基于流聚合与拥塞避免的SDN快速故障恢复方案FACAR。该方案支持从单链路故障中进行本地故障转移，并且可以将流经同一链路的流量备份到不同的备份链路，从而避免故障恢复后网络中的潜在拥塞。

本文主要工作如下：

1）为SDN提供一种有效的快速故障恢复方案，可以在SDN 交换机上以低存储开销实现本地快速故障恢复，同时，可以避免故障恢复后网络中的潜在拥塞。

2）将故障恢复方案表示为一个整数线性规划问题，并提出一种基于贪心的启发式算法去选择最合适的备份路径。

3）进行广泛的仿真来评估性能，结果表明，与现有的SDN 故障恢复方法相比，可以在满足快速故障恢复的基础上实现低TCAM 存储开销和故障恢复后的负载均衡。

1 相关工作

在主动式故障恢复和反应式故障恢复方案方面，国内外学者已经有了许多的研究成果。

Sharma 等人［9］详细介绍了反应式故障恢复的过程，在检测到故障后，控制器更新拓扑并为每个受到故障影响的流计算工作路径，通过删除旧的流表规则和下发新的流表规则来完成流的重定向。他们还比较了主动式恢复和反应式恢复方法的恢复延迟性能［10］，实验结果表明反应式故障恢复策略恢复延迟在75～130 ms 左右，难以满足电信级别要求，而主动式故障恢复策略恢复延迟可以控制在45 ms 以内。Kim 等人［18］提出了一种采用反应式策略从多链路故障中恢复的系统，其中控制器使用全局网络的拓扑信息来计算多条路由路径以处理多链路故障。在文献［19］中，作者提出一种称为本地快速重路由的方法，该方法通过将所有受到故障影响的流聚合为一个流，并在链路故障之后通过控制器计算路径，使得聚合流可以转发到故障链路的下游交换机，完成流的重定向。显然，由于反应式故障恢复策略在发生故障之后，需要控制器重新计算工作路径，使得反应式故障恢复策略在恢复时延方面表现不佳，不适用于运营商级网络。但是，它可以处理多组件故障的情况，并且不需要存储额外的转发规则，节省了存储空间。

主动式故障恢复方案采用故障保护策略，控制器可以预先将受保护的路径转发规则配置到数据平面的交换机中，以便上游邻居交换机可以将受故障影响的流从工作路径切换到受保护路径。在这种情况下，故障恢复时延几乎等同于故障检测时间。在文献［20］中，工作路径和备份路径的流表规则被分配了不同的优先级，如果没有发生故障，则优先级较高的工作路径流表规则将发挥作用，否则，工作路径的流表规则会被删除，优先级较低的备份路径流表规则将用于流的重定向。文献［11］提出一种1:1 保护机制，控制器为工作路径计算一条不相交的备份路径，并结合使用Fast Failover 故障切换功能，如果链路发生故障，交换机将进行切换操作，将受影响的数据流重定向到备份路径，而不需要控制器的参与。上述研究通过预先配置流的备份路径实现快速转移，当流的数量增加时，无疑会加大交换机内部存储空间的消耗。针对该问题，Zhang 等人［12］提出了一种以更少的备份资源实现故障恢复的方法，根据链路重要性将链路分为3个级别，为最高级别的链路配置2条备份路径，为中等级别的链路配置1 条备份路径，最低级别的链路采用反应式故障恢复策略。这种方法虽然减少了备份资源的消耗，但是其覆盖的保护范围并不全面，仅可以满足重要链路上数据流的恢复时延和传输质量。Chen等人［21］提出了一种使用流标记机制的主动恢复方案，以较少的备份资源恢复单链路故障。如果发生链路故障，受故障影响的数据包将被标记VLAN 标签并重定向到故障链路的另一端。然而，包含所有中断数据流量的聚合流的重定向可能会导致恢复后网络中的链路拥塞问题。

通过对已有工作内容的总结与分析，可以发现之前的链路故障恢复方案的侧重点都有所不同，整体包含3 个方面：1）链路发生故障后网络恢复需要的时间长短；2）对TCAM 存储资源消耗的多少；3）链路故障恢复后网络是否会发生链路拥塞。综合考虑这3 个方面，本文提出一种基于流聚合与拥塞避免的快速故障恢复方案（Flow Aggregation and Congestion Avoidance for Fast Failure Recovery in SDN，FACAR），其主要特性如下：

1）快速恢复：FACAR 预先安装备份路径，并在故障链路的邻居交换机上结合使用Fast Failover 故障切换功能进行流的重定向，缩短故障恢复时间。

2）低存储开销：FACAR通过将同一链路上的所有流视为一个或几个聚合流，然后仅为聚合流构造受保护的路径，大大减少备份流表规则对存储资源的占用。

3）拥塞避免：对于重路由可能会导致的网络拥塞问题，FACAR 通过综合考虑网络拓扑、故障状态以及链路负载来进行不同保护路径的安装，以确保重路由后不会出现网络拥塞问题。

2 SDN网络模型和故障恢复策略

2.1 网络模型

本文中的SDN网络拓扑模型化表示为G=（V，E），其中V表示交换机集合，E表示链路集合。在本文提出的方案中，采用了OpenFlow 协议提供的虚拟局域网（VLAN）标记功能，将网络中的每条链路用一个唯一的标识符标记，当链路出现故障后，为所有流经故障链路的数据流打上唯一链路标识符，然后利用Fast Failover 组表功能将流量传输切换到备份路径，为了避免故障恢复后潜在的拥塞问题，可能会提前配置多条备份路径，在备份路径上，通过唯一链路标识符对流进行聚合，可以大大减少备份路径对流表存储资源的消耗。本文所用完整的符号列表如表1所示。

表1 符号列表

2.2 基于流聚合与拥塞避免的故障恢复策略

在SDN 网络架构中，控制器会利用链路层发现协议（Link Layer Discovery Protocol，LLDP）获取网络整体的拓扑结构并维护可用的备份路径信息。基于这些信息，控制器可以在流的工作路径上预先配置备份路径，以预防可能发生的单链路故障。当数据流的首个数据包进入网络后，源交换机会向控制器发送Packet_in 消息，控制器收到请求后，利用全局的拓扑视图为源、目的主机计算工作路径以及每条工作链路的备份路径，将对应链路的VLAN ID 作为故障上游交换机备份路径的匹配规则，最后下发流表安装指令到所有相关的交换机中。在数据流正常传输过程中，交换机将数据包转发到Fast Failover 组表中，之后将数据包转发到工作路径的下一跳交换机。当链路出现故障之后，故障上游交换机会将原来通过故障链路的数据包都打上唯一VLAN ID 标签，然后转发到备份路径的下一跳交换机，备份路径通过匹配VLAN ID 进行数据包的转发，最后在数据包转发到故障下游交换机之前去除VLAN ID 标签，由故障下游交换机继续完成正常工作路径的数据包转发。

下面通过一个例子来说明本文的故障恢复策略。在网络拓扑中包含5 台交换机（S1、S2、S3、S4、S5）以及6 台主机（H1、H2、H3、H4、H5、H6），网络中部署了3 个数据流，分别为H1→H4、H2→H5、H3→H6，每条链路附近的2 个数据表示流量负载和链路总带宽。各链路对应的VLAN ID如表2所示。

表2 链路对应的VLAN ID表

图1显示了链路故障前的3个流量的路由情况。

图1 正常路由

图2 显示了典型的主动故障恢复策略，链路S1-S5 的备份路径为S1-S2-S5。当S1-S5 链路发生故障之后，3 条流量会同时经过备份路径S1-S2-S5，使链路S1-S2 和S2-S5 出现链路拥塞问题，承载的流量带宽超过了链路的带宽。

图2 典型主动故障恢复

图3 显示了本文提出的故障恢复策略，对于链路S1-S5，部署了2 条备份路径，其中S1-S2-S5 作为流H1→H4 的备份路径，S1-S3-S4-S5 作为流H2→H5和H3→H6的备份路径。通过使用2条备份路径将故障链路S1-S5 上的3 个流进行重路由，并利用流聚合的特性减少了S3、S4 交换机中的备份转发规则的数目，即只需要为流H2→H5 和流H3→H6 形成的聚合流配置2 个VLAN ID=3 的匹配转发规则。在这种情况下，与为每个流的链路都进行备份转发规则的典型主动故障恢复方法相比，大大减少了预置备份转发规则的数目，同时，避免了故障恢复后网络中的潜在拥塞问题。

图3 基于流聚合与拥塞避免的故障恢复

2.3 问题定义

FACAR 方案使用提前安装备份路径的方式来实现链路故障快速恢复，为了避免恢复后链路拥塞，FACAR 允许将故障链路的恢复流量分流到多个预置的备份路径。在预先配置备份路径时，本文的目标是在链路故障前最小化配置备份转发规则的数量。对该问题的正式描述如式（1）所示：

其中，P表示链路l上游交换机sl到链路l下游交换机dl的k条最短的路径集合，hi表示路径pi是否被选为备份路径，m表示链路l上流的数量，xij表示流fj的备份路径是否为pi，ni表示路径pi上的交换机数量，需要满足约束条件如下：

式（2）表示集合P中所有备份路径都必须不包含待保护链路l，其中表示路径pi是否包含链路（sl，dl）。

式（3）表示流量守恒定律，即流入交换机u的流量会从u完全流出，以确保流在路径中的连续性。

式（4）表示循环避免约束，即备份路径pi不包含环路，以确保流在传输路径中的性能。

式（5）表示分配给备份路径pi的流的带宽总和不能超过pi的可用带宽，以确保链路故障恢复后没有潜在的拥塞问题，其中bj表示流fj的带宽，λ表示链路利用率上限表示链路的带宽，表示链路的负载。

式（6）表示每个被中断的流都会被分配到一个唯一的备份路径上，以确保被中断的流可以正常恢复。

通过求解这个整数线性优化问题ILP，可以获得所有备份路径以及备份流表规则的数量。然而，从整数多商品流问题［22］的推导中可知，这个优化问题是NP完全的，对于大型网络，计算可能无法在多项式时间内完成。因此，为了在多项式时间内解决该优化问题，本文设计一个多项式时间复杂度为O(kv(n+vlog2v) +k(n+m+v))的启发式算法，如下文的算法1所示。

3 ILP-FACAR算法设计

3.1 备份路径计算

为了解决上文提出的优化问题，本文提出一种基于贪心的启发式算法，该算法计算待保护链路的上下游交换机节点之间的前k条最短路径，然后再计算每条路径的可用带宽并按照可用带宽对路径进行降序排序，最后选择满足条件的路径对流进行备份。

在FACAR 中，为了实现故障快速恢复，利用OpenFlow 协议的组表功能实现快速故障转移功能，在检测到故障发生后，故障上游交换机可以自动将中断的数据流绕开故障链路转发到预先配置的备份路径上，无需控制器参与，从而可减少故障恢复时间。同时，为了避免故障恢复后的拥塞，控制器给每个中断的流预先配置备份路径，并且将分配给相同备份路径的流汇聚成具有唯一VLAN ID 标签的聚合流。FACAR 采用灵活的流聚合策略，实现SDN 单链路故障的快速恢复和拥塞避免。

算法1 的输入为网络拓扑、待保护链路和待保护链路上的流集合，输出为待保护链路提前配置的备份转发规则的数量。

算法1ILP-FACAR算法。

输入：网络拓扑G=（V，E），待保护链路l，l上的流集合F。

输出：链路l的备份转发规则的数量。

算法1流程描述如下：

1）流排序和拓扑更新。对待保护链路上的流按照带宽大小进行降序排序，并将待保护链路从拓扑中去除，然后更新网络拓扑。

2）最短K 路径计算。采用Yen［23］提出的KShortestPaths算法计算待保护链路上下游交换机节点之间的前k条最短路径，将它们作为备份路径的候选路径，最后按照路径的跳数对这些候选路径进行升序排序。

3）路径可用带宽计算。为每条候选路径创建一个空集合，用于存储当候选路径被选为备份路径时被路径备份的流，并计算路径的可用带宽。

4）备份路径选择。迭代每条待保护链路上的流，选择最短的候选路径，如果候选路径可用带宽满足流的需求，就选择当前候选路径作为流的备份路径，然后将流添加到候选路径的备份流集合中，并更新该路径的可用带宽，否则，选择下一条最短的候选路径。

5）配置备份路径转发规则。迭代每条候选路径，如果候选路径的备份流集合不为空，表明该候选路径被选为一条或几条流的备份路径，采用下文的算法2进行备份路径上转发规则的配置，最后输出提前配置的备份转发规则的数量。

3.2 备份路径流规则安装

当控制器完成待保护路径的备份路径计算后，采用算法2进行备份路径流规则的安装。

算法2备份路径流规则配置算法。

输入：备份路径pi，pi备份的流集合Ui。

输出：对应交换机的流规则配置。

算法2主要操作描述如下：

1）待保护链路的上游交换机。针对待保护链路的上游交换机，配置一个组表规则和一个流表规则。设置一个唯一的组表ID，并在组表规则第1个动作桶中配置转发端口为正常的工作转发端口，发生故障之前，数据都从该端口转发；在第2 个动作桶中配置转发端口为备份路径的转发端口，故障发生之后，交换机进行端口切换，为流经故障链路的数据包进行VLAN ID 标记，然后数据从备用端口转发。另外，对于流表规则的配置，其匹配域为流的源和目的主机的IP地址，转发动作为转发到提前配置的组表中。

2）备份路径上的交换机。针对备份路径上的交换机，除了2 个首尾交换机以外，只需要给其他的交换机下发一条流表规则即可，匹配域为待保护路径的VLAN ID以及输入端口号，转发动作为备份路径的下一跳交换机。另外，对于备份路径上的最后一个交换机（不包括目的交换机），需要在数据转发之前剥除数据包中的VLAN ID，最后将数据转发到目的交换机。

3.3 算法时间复杂度分析

本文用变量k表示需要计算的最短路径数量，m表示被中断的流的数量，v表示网络拓扑中交换机节点的数量，n表示网络拓扑中边的数量。在算法1中，KShortestPaths算法的时间复杂度为O(kv(n+vlog2v))［24］，路径可用带宽计算时间复杂度为O（kn），备份路径选择时间复杂度为O（km），配置备份路径转发规则时间复杂度为O（kv）。综上所述，ILP-FACAR 算法时间复杂度为O(kv(n+vlog2v) +k(n+m+v))。

4 实验与分析

4.1 实验环境设置

为了评估所提出的FACAR 方案，本文使用支持OpenFlow1.3 的RYU［25］控制器，并使用Mininet［26］来仿真测试网络的拓扑结构，通过使用3 种不同的拓扑来评估所提出的基于拥塞感知的方案FACAR：图4中的例子拓扑、真实的网络拓扑USNET［27］和挪威骨干网拓扑Norway［28］。

图4 例子拓扑

网络拓扑中直连主机的交换机称为边缘交换机，在仿真实验中，每个边缘交换机连接2～3 台主机，链路的带宽统一设置为50 Mbit/s，利用Iperf 在主机之间随机产生流量，流量带宽在［4，6］Mbit/s 范围内均匀分布。实验运行环境为Ubuntu 18.04.6 LTS，Intel Core i7-10700 CPU，2.90 GHz，8 GB内存。

4.2 实验与结果分析

本节通过实验对本文提出的FACAR 方案进行有效性验证，主要包括以下3 个方面：故障恢复时间、负载平衡性能、备份流表TCAM 资源消耗，并将FACAR与已有的故障恢复方法进行分析对比。

1）故障恢复时间。

首先，评估FACAR 方案的故障恢复时间，将FACAR与目前流行的反应式恢复方案（RRM）［10］和基于路径保护的主动式恢复方案（PRM）［11］进行比较。为了获得故障恢复时间，随机选择一条链路，使用Iperf随机生成流经该链路的流量，然后断开该链路的连接，在目的主机使用Wireshark［29］工具来进行数据包的监控。故障恢复时间使用在链路故障之前接收到最后一个数据分组和链路故障之后接收到第一个数据分组之间的时间差。通过改变选择的链路和流的数量，进行20次实验模拟，最后结果如图5所示。

图5 3个拓扑中的平均故障恢复时间

可以看到，随着网络规模的增大，3 种方法的平均故障恢复时间均有所增加，其中，RRM 消耗的时间最多，是因为它是反应式故障恢复方案，在发生故障之后，控制器需要重新计算流的工作路径，并且网络规模越大，平均故障恢复时间就越长。而2 种主动式故障恢复方案FACAR 和PRM 受到网络规模的影响较小，并且故障恢复时间远远小于反应式恢复方案，因为它们在发生故障之后，不需要控制器参与备份路径的计算，故障上游交换机可以直接将受到故障影响的数据流切换到备份路径上。本文提出的FACAR 方案相比PRM 方案平均故障恢复时间增加了11.5%、14.3%和13.8%，这是因为FACAR 方案采用拥塞感知的流聚合方法，将故障链路上的流量配置到了不同的备份路径上，因此在交换机进行端口切换时，所需时间略微增加，但仍满足50 ms 内的故障恢复时间，可以实现单链路故障的快速恢复。

2）负载平衡性能。

进一步，本文对FACAR 方案故障恢复后的负载平衡性能进行评估。通过2 种主动式故障恢复方案PRM 和Van Adrichem 等人［30］提出的方案（命名为BG）与本文提出的FACAR 进行对比，在网络拓扑中部署流量，并选择负载最大的链路断开，然后通过比较3 种方案恢复后的最大链路带宽利用率来评估负载平衡性能。

图6 ～图8 分别显示了例子拓扑、USNET 和Norway 这3 个网络拓扑中故障恢复后的最大链路利用率。可以看出，随着流的数量增加，PRM 和BG 方法的最大链路利用率随之增加，当达到一定数量后，恢复后的网络出现了网络拥塞。本文中最大链路利用率阈值λ设置为0.8，当链路利用率大于0.8 时，就认为该链路是拥塞的。整体来看，BG 方法的负载均衡性能优于PRM 方法，这是因为BG 方法的备份路径是从故障节点上游交换机到目的交换机，而PRM 方法的备份路径是一条与原工作路径不相交的路径，后者在故障恢复时，通常会影响更多链路上的链路利用率，而本文提出的FACAR 方案始终保持一个更优的负载均衡效果。这是因为PRM 和BG 只关心在故障后进行中断流的快速恢复，而没有考虑恢复后网络中的潜在拥塞问题，而FACAR 在安装备份路径时，会将不同的流备份到不同的路径上，以避免链路故障后，通过故障链路的流仅能在一条备份路径上进行恢复。

图6 例子拓扑中最大链路利用率

图7 USNET中最大链路利用率

图8 Norway中最大链路利用率

3）TCAM存储开销。

最后，对FACAR 方案的备份流表TCAM 资源消耗进行评估。在网络拓扑中部署流量，并利用3 种主动式故障恢复方法PRM、BG和FACAR 提前为链路配置备份路径，然后计算备份流规则的数量。

图9～图11 分别显示了例子拓扑、USNET 和Norway 这3 个网络拓扑中提前配置的备份流规则的数量。可以看出，随着流的数量增加，3 种方法所需要配置的流规则的数量都在增加，其中增长最快的为BG 方法，因为其备份路径考虑的是从每个工作节点到目的节点，因此相比于PRM 的不相交备份路径和FACAR 的链路保护，BG 方法所需流规则数量是最多的。在流的数量比较少时，PRM 和FACAR 拥有十分相近的备份流规则数量，这是因为此时网络拓扑中受到FACAR 保护的链路数量比较少，需要配置的备份流规则比较多。当FACAR 为更多的链路配置了备份路径之后，只需要给新的流量配置很少的备份流规则，而PRM 还是需要为每个流去配置备份路径，因此随着流的数量增加，FACAR 方案可以更好地节省TCAM 资源消耗。在流的数量达到20 时，相比于PRM 和BG方案，FACAR 的备份流规则数量平均减少了46.7%和75%。

图9 例子拓扑中备份流规则数量

图10 USNET中备份流规则数量

图11 Norway中备份流规则数量

5 结束语

针对链路故障恢复后可能发生的拥塞问题和备份路径TCAM 资源消耗高的问题，本文提出了一种基于流聚合与拥塞避免的SDN 快速故障恢复方案FACAR。FACAR 方案基于VLAN ID 的流聚合，通过将同一链路上的所有流视为一个或几个聚合流，然后为聚合流构造受保护的路径，这大大减少了备份流表规则对存储资源的占用并确保网络链路在故障恢复后不会发生拥塞。本文将FACAR 方案形式化表述为一个整数线性规划问题，以求解最少配置备份转发规则的数量。为此，本文提出了一种基于贪心的启发式算法来配置备份转发规则。实验结果表明，本文提出的FACAR 方案可以实现电信级别要求50 ms 内的快速恢复，而且相比于PRM 和BG 方法，FACAR 方法可以始终保持很好的负载均衡。在备份流表TCAM 资源消耗上，FACAR 方法相比于PRM 和BG 方法，备份流规则数量平均减少了46.7%和75%。综上所述，FACAR 是一种负载均衡、低存储开销的快速故障恢复方案。