基于流类型的SDN数据平面故障恢复算法

段 洁，高江明，程克非，赵国锋，韩 健

(1.重庆邮电大学 未来网络研究中心，重庆 400065；2.重庆邮电大学 网络技术研究所，重庆 400065)

0 引 言

云计算[1]、大数据[2]等互联网新技术的出现，导致网络流量迅速增加。尤其数据中心网络(data center networking，DCN)东西向流量急剧增加，对核心层链路负载提出了严峻考验[3]。因此，传统网络在流量管理、可扩展性、链路故障恢复等方面的局限性日益突出。

软件定义网络(software defined networking,SDN)是一种新型网络体系结构，被广泛部署于数据中心网络，其核心思想是将网络设备的控制平面和数据平面进行分离、实现逻辑上的集中式控制[4]。因此，SDN网络故障分为控制平面故障和数据平面故障：控制平面故障可以是组件故障、计算能力不足等；数据平面故障是网络中的交换机/链路出现故障，需要在所能容忍的故障恢复时延范围内实现故障的快速恢复，并尽量减少数据包的丢失等[5]。

目前对SDN网络故障的研究集中在数据平面，且处理故障的方法分为主动式和被动式：①主动式故障恢复：为网络中数据流计算一条备份路径，将备份路径转换为流表项并下发到对应交换机进行存储；②被动式故障恢复：当交换机/链路出现故障，故障交换机发送Packet_In数据包给控制器，控制器根据网络状态信息为故障流重新计算一条工作路径，并将工作路径转换为流表项下发给相应的交换机进行存储，交换机根据流表项对数据流进行传输。

文献[6]是在不考虑任何约束的情况下，为网络中每条数据流都计算备份路径，此方案可以保证故障的快速恢复，但可能会导致链路拥塞、数据包丢失、且消耗大量交换机流表项。文献[7]首先对数据流进行收集和分析，标识出大象流；然后只对大象流计算备份路径，除此以外的数据流将不再计算备份路径。此方案可以节约流表项，但还是没有考虑链路负载的问题。

为了更灵活地处理链路故障，SDN工作组提出了组表的概念，组表由唯一的组ID、组类型和行动存储段组成。组表类型设置为Fast Failover，行动存储段(action buckets)可以存储多个行动指令，为受影响的流存储主路径和备份路径，故障发生后，交换机自动将故障流转移到备份路径进行传输。文献[8]是利用组表的行动存储段来存储多个动作指令，当第1个指令失效后去执行第2个指令，此方案可以节约交换机存储资源，但没有负载调节能力，容易产生链路拥塞。文献[9-10]考虑了网络资源与用户请求之间的关系，根据用户请求数据流大小计算备份路径，从而实现网络的最大化吞吐量和满足用户带宽需求的限制。

本文为了满足用户的定制化需求和体现数据流的差异化特性，提出了基于流类型的SDN数据平面故障恢复算法。该方案是不同数据流在满足约束和实现用户的定制化需求情况下，对不同数据流采用不同故障恢复方法。

1 网络模型

本文用无向图G=(S,E)表示SDN网络，s是交换机集合S中的元素，e是链路集合E中的元素。其余符号及意义如表1所示。

表1 符号及意义Tab.1 Signs and meanings

流备份图如图1所示。图1中有7个交换机和9条链路，每条链路带宽是10个单位，数据流的大小见图1。图1a是数据流传输的初始状态，为了防止链路出现故障，已有研究工作是为每条流的工作路径上每条链路都作备份路径，且没有考虑备份路径是否会对链路产生拥塞，图1b是备份路径的一种情况。

已有研究工作是为每条数据流都计算备份路径，但由于网络数据流数量众多，将消耗巨大的流表项。因此，本文是对链路上数据流作备份路径，同时由于组表可以存储多个行动指令，所以，在计算备份路径时可以将行动指令存储在组表的行动存储段里面，以此来减少流表项的消耗；不同数据流对服务质量有不同要求，因此，需要设计具有差异化的故障恢复方法。通过仿真证明，本方法可以减少交换机流表项消耗、故障恢复时延、数据包丢失率。

图1 流备份图Fig.1 Flow backup diagram

2 SDN数据平面故障恢复算法

由于数据流具有差异化的服务质量要求，因此，在作备份路径时需要有所侧重；同时某些数据流在传输的时候也被加入了一些定制化的需求。本文提出了基于流类型的SDN数据平面故障恢复算法：首先将网络数据流按照服务质量要求进行分类；然后根据数据流定制化需求和约束条件为不同类型数据流制定相应的备份路径选择策略。

2.1 流的分类

实际网络中传输的数据流会有不同的要求，比如在线直播就需要传播速度快、播放流畅等要求；大文件传输需要提供足够带宽，减少数据包分步传输数量。因此，本文根据服务质量要求将数据流分为3类；①时延敏感业务(delay flow, FD)：对时间要求高、实时性强的业务，如语音业务、视频交互业务等；②吞吐量敏感业务(throughput flow, FT)：对网络带宽有较大要求，不重点关注时延的影响，如视频点播业务、海量数据文件传输业务等；③尽力而为业务：对时延和吞吐量都没有特殊要求的数据流业务可以归于此类。

由于运营商/用户对某些数据流有固定的定制化需求[11]，因此，在部分数据流上绑定了一些定制化需求，例如故障恢复时延要求小于50 ms，对数据流负载进行限制等。具体情况如表2所示。

2.2 基于流类型的故障恢复方法

本文算法总体流程图如图2所示。

首先在端主机处对数据流进行类型识别并标识和判断数据流类型；然后根据判断的不同类型数据流调用不同备份路径计算方法；最后将产生的备份路径转换为流表项并下发到相应的交换机上进行存储。以下分别对不同数据流的备份路径计算进行详细介绍。

表2 定制化需求介绍Tab.2 Customize requirement introduction

图2 流程图Fig.2 Flow chart

2.2.1 时延敏感业务

时延敏感业务是指运营商/客户对故障恢复时间要求非常短或对故障毫无察觉。对于此类数据流需要采用主动式策略进行备份路径计算，即在满足一定约束的情况下，以链路为主，为链路上的所有时延敏感业务作相同的备份路径，且不考虑备份流量对链路带宽的占用，即这条链路出现故障，时延敏感业务将沿着提前作好的备份路径进行传输。其中，{∀(e,f)|xf,e=1}表示在链路e上需要为流f作备份路径，反之，不需要作备份路径；对于那些不能通过的链路集合用{f.avoidV|∀e∈V,xf,e=0}表示。

此类型数据流考虑的目标及约束条件为

约束

(1)

由于时延敏感业务对故障恢复时延有严格要求，因此，对于重要链路上的备份路径可以计算第2条备份路径。如何选择重要链路及如何计算备份路径是后续研究工作中值得关注的方向。图3是链路故障后的备份路径执行过程。

图3 时延敏感业务备份路径Fig.3 Delayed sensitive service backup path

如果图3中的数据流F1是多条时延敏感业务组成的集合，此数据流的工作路径是，由于不考虑链路剩余带宽的限制，因此，为链路上所有时延敏感业务所作备份路径是链路，链路上所有时延敏感业务所作备份路径是链路，实际情况见图3。其中的转发规则存储在相应交换机的组表上，例如交换机A上为F1集合所作的备份路径转发规则见图3。数据包的正常传输是从端口3转发，当链路出现故障，将从端口4转发，实际转发规则存储如图所示，其余交换机组表的转发规则相同。

2.2.2 吞吐量敏感业务

吞吐量敏感业务是指数据流对带宽需求比较大，对此类数据流的要求是没有或很少有数据包的丢失，保证数据的传输质量。为此类数据流作备份路径时，需要考虑减少数据包多路分发传输,即让同一数据流在一条路径上传输完成，而不是在多条路径上按分割比例传输。所以计算备份路径时应考虑链路剩余带宽与流大小之间的关系，为此类数据流提前在备份路径上预留出足够的带宽，且此备份路径是与工作路径没有交集的路径，除了流f的源、目的节点外。

为此类数据流计算备份路径时，寻找的是一条全新的路径，且要考虑链路剩余带宽与数据流的大小。因此，在计算备份路径时，需要满足的约束条件为

(2)

约束1)是链路e上传输的流量加上备份流量之和小于等于设置的链路阈值，即需要考虑备份数据流占用带宽；约束2)是交换机s上原存储资源消耗加上备份数据流资源消耗之和小于等于交换机存储容量；约束3)保证工作路径与备份路径没有链路相交，除了数据流f的源、目的节点相同，即寻找一条全新的路径作为备份路径；约束4)是备份路径上传输数据流所用时间要小于等于数据流的定制化故障恢复时间限制。链路故障后的备份路径执行过程如图4所示。

如果图4中的数据流F3是吞吐量敏感业务，需要为F3计算一条全新的路径作为备份路径。考虑到F3的大小与路径的剩余带宽关系，为此类数据流所作备份路径是，此备份路径除了源、目的节点相同，其余节点都不同。如果F3的工作路径上有任何一条链路出现故障，那么数据流将按照备份路径进行传输，实际情况见图4。其中的转发规则存储在相应交换机的组表上，只有交换机A上的组表存储了2个行动指令，交换机F，G上的组表分别只有一个行动指令。

图4 吞吐量敏感业务备份路径Fig.4 Throughput sensitive service backup path

2.2.3 尽力而为业务

尽力而为业务是除了时延和吞吐量敏感业务之外的没有特别要求的业务。对于此类业务，为了节约交换机的存储空间，将不会对此类数据流作任何的备份路径，采用的是被动式故障恢复策略。当交换机/链路出现故障后，由控制器根据网络拓扑信息进行重路由计算，并生成流表项下发到相应的交换机，然后根据此流表项传输数据流。在计算备份路径时，由于不存在备份流量的影响，因此，需要考虑的约束是(1)式中的约束1)和约束2)，即链路带宽和交换机存储资源的限制。

当网络中首次产生数据流时，交换机会向控制器请求计算工作路径，在计算工作路径时，同时判断此数据流属于什么类型，并根据不同类型分别计算备份路径，数据流的备份路径算法具体步骤如下。

Input:G=(S,E),f，α

Step1DF=0,TF=0 //DF：时延流为空，TF：吞吐量流为空

Step2 while (f.newFlow) //f是新的流

if (f∈FD)DF=f

return to Step3

if (f∈FT)TF=f

return to Step4

else while (f. linkFailure)

WPf=f. recomputeWPf

foreach (e∈WPf)

return WPf

Step3BPF=0

foreach (einG=(S,E))

Floyd (esrc,edst)

if (esatisfy (1)中约束)

BP. add (e) //e添加到BPf中

returnBPf

BPf.add(e)

returnBPf

当网络中产生了新的数据流，首先判断数据流类型并加入到对应的集合中；然后调用对应方法计算备份路径，对尽力而为业务是返回工作路径，其余2种数据流是返回备份路径。在确定了备份路径后，控制器会向相应的交换机下发流表项，并实时监控网络中交换机和链路状态信息，为控制器做出决策提供信息参考。

3 实验仿真

本部分通过实验对所提算法进行有效性验证。所选对比方法分别是为所有数据流作备份路径和根据链路等级不同设计备份路径策略，并对不同算法的性能指标进行对比。

3.1 仿真拓扑

实验采用的是Mininet仿真平台，Mininet是一款轻量级软件定义网络仿真及测试平台，利用此平台可以模拟出任意的网络拓扑图。实验采用的仿真拓扑图如图5所示，由9个交换机和14条链路组成，圈中的数字表示交换机序号，每条链路的带宽都是1 Gbit/s，链路上的数字表示交换机之间的距离。交换机7，8上分别连接了2个主机，交换机1，4上分别连接了4个主机，主机之间是可以相互连接和通信。

图5 仿真拓扑图Fig.5 Simulation topology

3.2 仿真结果与分析

为了对所提算法进行验证，本文选择了目前比较普遍的故障恢复方法[12](fast recovery approach, FRA)和基于备份资源的故障恢复方法[13](backup-resource based failure recovery, BR-FR)。本实验的链路阈值率根据带宽预留限制取值为0.8 (α=0.8)，即链路带宽利用率达到了0.8以上就认为链路出现了拥塞。

不同故障恢复方法的交换机流表项消耗数量如图6所示。从图6可以看出，在数据流较少的情况下，FR-FT和FRA几乎一样，BR-FR有一定优势。但随着数据流增多，FR-FT表现出了一定的优势。这是由于FRA是为每个数据流都作备份路径，BR-FR是为重要链路计算2条备份路径。本方案对于时延敏感业务是以链路为主来计算备份路径，对同一链路上所有时延敏感业务作的备份路径都是相同的，这是本方案节约交换机流表项消耗的重要原因。

图6 流条目消耗数量Fig.6 Consume number of entry

不同算法的链路故障恢复时延如图7所示。从图7可以看出，开始阶段故障恢复时间几乎一样，但是当网络中数据流增加时，链路负载率也随之增加，BR-FR和FRA的故障恢复时延比较久，这是由于BR-FR和FRA只是作备份路径，没有考虑网络链路负载的实时性变化。本文方法考虑到了吞吐量敏感业务的备份数据流对链路的影响。

图7 故障恢复时延时间Fig.7 Fault recovery latency time

网络链路出现故障后的数据包丢失率如图8所示。当网络重要链路数较少时，几乎没有数据包的丢失，其中，重要链路本文指的是链路利用率达到0.6的链路。随着重要链路数的增多，数据包的丢失率都有明显的增加。本文方法考虑到了部分备份数据流对链路负载的影响，因此，数据包的丢失量相对较少。尤其重要链路数越多，故障可能性越大，因此，FR-FT的优势就更加明显。

图8 数据包丢失率Fig.8 Packet loss rate

4 结束语

本文针对现有SDN网络的数据平面故障恢复算法在链路备份方面没有对数据流进行分类及考虑运营商定制化需求的缺陷，提出了基于流类型的SDN数据平面故障恢复算法，并对其进行仿真验证。该方法首先将数据流划分为3类不同服务要求的类型，并对不同类型的数据流分别建立相应的数学模型；然后根据运营商/客户定制化需求及不同数据流的约束条件提出不同的故障恢复策略，实现不同服务类型流之间的差异化。仿真结果表明，本方法可以减少故障恢复时延、数据包丢失率等。

[1] QI R, QI M. Research on Science and Technology Service Sharing Platform Based on Cloud Computing Technology[C]//IEEE.International Conference on Smart City and Systems Engineering. Hunan, China: IEEE Press, 2017:527-530.

[2] 宋杰,郭朝鹏,王智.大数据分析的分布式MOLAP技术[J].软件学报,2014,25(4):731-752.

SONG Jie, GUO Chaopeng, WANG Zhi. Distributed MOLAP Technique for Big Data Analysis[J]. Journal of Software, 2014, 25(4):731-752.

[3] MAO J, HAN B, LV G, et al. Topology-independent Software-Defined Edge Control for Scalable Ethernet DCN[C]//International Conference on High performance Computing and Communications. New York, USA: IEEE Press, 2015:1645-1650.

[4] MCKEOWN N. Software-defined networking [J]. INFOCOM keynote talk, 2009, 17(2):30-32.

[5] 张淑娟, 王颖, 邱雪松,等. 基于负载均衡的SDN数据平面故障恢复方法[C]// 全国通信软件学术会议程序册与交流.西安：IEEE，2016:71-76.

ZHANG Shujuan, WANG Ying, QIU Xuesong, et al. Failure Recovery Approach with Load-balancing in SDN Data Plane[C]// Proceedings and exchanges of the National Conference on communication software. Xi’an, China: IEEE Press，2016:71-76.

[6] PADMA V, YOGESH P. Proactive failure recovery in OpenFlow based Software Defined Networks[C]// International Conference on Signal Processing, Communication and Networking.Chennai,India: IEEE Press, 2015:1-6.

[7] 庄怀东,杜庆伟.一种基于 SDN 的数据中心网络动态流量调度方法[J].计算机与现代化, 2016(7):80-86.

ZHUANG H D, DU Q W. A Method of Data Center Networking Dynamic Traffic Scheduling Based on SDN[J].Computer and Modernization,2016 (7):80-86.

[8] LIN Y D, TENG H Y, HSU C R, et al. Fast failover and switchover for link failures and congestion in software defined networks[C]//International Conference on Communications. Kuala Lumpur, Malaysia: IEEE Press, 2016:1-6.

[9] CHU C Y, XI K, LUO M, et al. Congestion-aware single link failure recovery in hybrid SDN net- works[C]//ACM Conference on Computer Communications (INFOCOM).Hong Kong,China：IEEE Press, 2015:1086-1094.

[10] HUANG M, LIANG W, XU Z, et al. Dynamic routing for network throughput maximization in software defined networks[C]//International Conference on Computer Communications(INFOCOM).San Francisco,CA,USA:IEEE Press,2016:1-9.

[11] SHARMA S, STAESSENS D, COLLE D,et al. OpenFlow:Meeting carrier-grade recovery requirements[J].Computer Communications,2013, 36(6):656-665.

[12] ADRICHEM N L M V, ASTEN B J V, KUIPERS F A. Fast Recovery in Software-Defined Networks [C]//Third European Workshop on Software Defined Networks. London, UK: IEEE Press, 2014:61-66.

[13] ZHANG S, WANG Y, HE Q, et al. Backup-resource based failure recovery approach in SDN data plane[C]//Network Operations and Management Symposium. Kanazawa, Japan: IEEE Press, 2016:1-6.

(编辑：王敏琦)