SDN网络中基于拓扑分域的故障恢复方法

肖军弼，孟祥泽+，田爱宝，陈 松

(1.中国石油大学(华东) 计算机与科学技术学院，山东 青岛 266580； 2.中国石油大学(华东) 信息化建设处，山东 青岛 266580)

0 引 言

近年来，互联网业务不断扩大，物联网、云计算等新兴领域快速发展，网络业务的繁杂和传统网络架构的短板为网络服务的运行和维护带来了巨大难题[1]。为解决传统网络中故障恢复时间过长的问题，探索新的网络架构及运行模式，给业务提供优质可靠的运行环境。研究重点利用SDN(software defined networking)[2]架构的强大管控优势，收集链路信息，快速定位链路故障，并改进故障恢复的方法，减少故障恢复所需时间并提高网络的服务质量[3]。相比于传统网络中生成树协议STP(spanning tree protocol)或快速生成树协议RSTP(rapid spanning tree protocol)[4]复杂、僵化的恢复方案，能够实时监控网络状态，并在第一时间对故障进行自愈操作，保障业务的正常运行，降低故障恢复时间，提高网络通信安全和服务质量。本文的主要内容包含如下两个方面：

(1)针对SDN网络中流表数量过多、冗余链路计算复杂的问题，本文研究UGLA算法，将拓扑中的环路划分成单独的环路域，环路域内部依靠MPLS标签匹配基础流表转发，实现故障恢复主备份路径策略，降低交换机中的流表数量。

(2)为保障业务的服务质量，在划分出环路域的基础之上，对环路域之间的逻辑链路进行链路评估，计算域间最优转发路径，结合环路域内部的基础转发流表，保证故障恢复通信的低丢包率、低延迟、高转发速率，保障业务正常运行。

1 相关工作

由于涉及整个网络的协调，传统的分布式网络难以捕获细粒度状态，而现代网络的动态特性又使得获取网络拓扑信息尤为困难。因此，科学有效管理网络的重要性日益凸显，获取准确的网络拓扑对于网络交换机、体系结构和协议的设计至关重要[5]。

Zhangchao W等[6]针对分布式网络结构难以捕获的问题，通过简单网络管理协议(simple network management protocol，SNMP)监控网络设备的性能，解决了由于不同厂商生产的底层设备产生的兼容性问题，实现设备的集中统一管理。赵伟等[7]采用LLDP协议(link layer discovery protocol，LLDP)为与其直接相邻的设备提供邻居信息，解决了利用MIB生成网络拓扑存在误差的问题，增强了拓扑链路状态获取的实时性。Huang H等[8]将BFD检测状态与OpenFlow组表相结合，一旦BFD协议检测到链路故障，OpenFlow协议就会根据故障状态执行相应的动作，但该方法缺乏对故障主动检测能力。

Zhao G等[9,10]在SDN架构中利用控制器的集中控制功能，可以准确发现故障点，根据故障节点所在位置，进行重路由，绕过故障节点，但该方法存在故障流量匹配项过多，不易处理的问题。针对网络规模扩大，故障标记不易区分的问题，黄睿等[11,12]将大规模网络根据接入、汇聚和核心划分出不同的区域，区域内采用不同的恢复策略，链路故障时通过重路由方式恢复，链路拥塞时通过QoS降低数据丢包率。为降低控制器重新计算转发路径的时间，居建涛等[13]在SDN网络中计算出数据流转发节点的备份路径，同时在链路故障时切换流表优先级，实现快速绕行转发。该方法提前计算好转发路径，以主备份形式存储于交换机中，降低了中断时间。为了进一步降低中断时间，Van Adrichem N.L.M等[14,15]制定传输策略，数据流在链路上正常传输时不做处理，当链路发生故障时，OpenFlow故障恢复组表自动切换到备份路径转发，此过程不需要控制器参与，解决了故障恢复过程中通信中断的问题，但主备份路径需要提前规划，需要一个最优的路径计算方法来制定转发策略。

基于上述分析，目前的故障恢复研究尽管已经取得了诸多成就，但在检测精度、故障分类和故障恢复质量上仍存在问题。本文采用SDN架构实施对SDN网络的故障恢复，当链路出现故障时，采用OpenFlow协议的故障恢复组表功能，结合BFD和LLDP两种链路检测协议进行检测链路故障，实现对故障位置的精确定位。在故障类型分类部分采用分域治之的方式，将大规模网络分解成可实现故障恢复的环路，在环路内实施主备份策略，对故障流量精确分类。故障恢复部分采用OpenFlow组表和SDN控制器联合恢复的方法，将已发出的数据包做回溯转发，减少丢包率，然后利用控制器修改流表优先级，实现控制器和OpenFlow联合恢复流量转发，降低故障流量转发延时，提高网络健壮性。

2 基于拓扑分域的故障恢复方法

2.1 网络分域

作为SDN网络架构的特性，控制和数据平面分离解决了网络中弹性不足和可扩展性差等问题，交换机转发依赖于控制器正确和及时的配置。本文基于SDN的集中控制方法，研究并实现一种网络拓扑环路计算方法无向图环路算法(undirected graph loop algorithm，UGLA)，将网络中的环路融合，提前计算转发路径并下发到交换机中，转发策略分为环路内转发策略和环路间转发策略。通过将转发策略分为域内转发和域间转发，极大降低了匹配项的复杂度，减少流表数量，提高交换机处理速率。

在当前网络架构中，一般情况下网络链路中都存在链路冗余。UGLA分域算法将当前网络拓扑中的环路作为最小转发单元，称为环路域。通过计算域与域之间的转发路径，简化了复杂网络，提高了计算效率。本文引入了最短路径算法，计算一个拓扑中的所有环路，每个环路中包含的节点是组成最小环的必要节点。判断环路的基本思想如下，在一个图G中，若存在环路，则环路中的所有顶点的度大于或等于2。

步骤1 度为1的节点不能够产生环路，首先删除图中所有度为1的节点和该节点所连接的边，如果产生新的度为1的节点，则继续删除，删除的节点按连接关系加入到转发域中。

步骤2 选择一个度为2的节点作为起始节点开始计算最小环路，度为2的节点至多只有一个环路。

步骤3 检查剩余节点的度，若剩余图中的所有节点的度都大于2，则将剩余的节点融合至一个环路域内。

步骤4 若剩余图中的所有节点的度存在等于2的，则以选择的节点作为起始节点，断掉两条边中的一条，以该条边的对端顶点作为目的节点，计算最短路径。若最短路径存在，说明该最短路径能够形成一个最小环路，可以进行环路融合；若不存在最短路径，说明该节点只作为中间转发节点，只要邻居节点的度为2，就将该节点的邻居节点递归方式加入到同一转发域中。计算完成后删除该起始节点，并清除环路中的度为2的节点，重复步骤2到步骤4，直到所有节点都被访问。

步骤5 在环路域间建立连接，一个节点可以属于多个不同的域，而域与域之间是否能够建立连接，取决于域内节点所包含域的集合是否包含对端域。

基于以上步骤，我们设计了一种基于最小环路的UGLA融合算法，如算法1所示。

算法1: 拓扑分域算法 输入: 拓扑图信息G(V,E) 输出: 域集合Domain (1)function E(V) (2) ifV.length == 1 then (3) return[e1,…,en]; //与节点V相连的边 (4) else (5) return[e];//与节点v1,v2相连的边 (6) end if (7)end function (8)function D(V) (9) result ← 0 (10) result ← result +E(V) (11) returnresult;//节点的度 (12)end function (13)function PRE-TREATED(G(V,E)) (14) result ← G(V,E) (15) for allv ∈ result.V do (16) if D(v) == 1 then (17) result → V.delete(v) (18) result → E.delete(E(v)) (19) end if (20) end for (21) returnresult (22)end function (23)function UGLA(G(V,E)) (24) Domain ← {} (25) V’ ← [];//已访问节点 (26) whileV’.length < V.length do (27) v ← V.get(1) (28) if D(v) == 2 then (29) E.delete(E(v,v.dst)) (30) path=Dijkstra(v,v.dst) (31) end if (32) ifpath != 0 then (33) Domain.add(name,path.V) (34) V’.add(path.V) (35) end if (36) end while (37) returnDomain (38)end function

为了更直观展示算法工作流程，下面将使用一个简单的示例对上述过程加以详细的说明。在图1所示的拓扑中，总共有14台交换机设备，根据图中的连接关系可以得出该拓扑图具有环路，进行环路融合。该拓扑图大致可以分为5个域，分别是{S1,S2}组成的转发域Group1;{S3,S4,S5}组成的环路域Loop1;{S4,S5,S6,S7}组成的环路域Loop2;{S8,S9,S10}组成的转发域Group2;{S11,S12,S13,S14}组成的环路域Loop3。下面按照5个域生成的计算步骤进行详细的说明。

图1 初始拓扑结构

首先根据步骤1，先检查图中所有度为1的节点，当前拓扑图中度为1的节点为S1，删除掉该节点和边，新产生了一个度为1的节点S2，继续删除S2节点和其直连的边，并将S1和S2加入到一个转发域Group1中，形成转发域Group1，拓扑图如图2所示。

图2 融合转发域Group1

在删除掉度为1的节点和边后，拓扑图中不存在度为1的节点，下面将开始计算环路。选择度为2的节点作为起始节点开始计算包含该节点的最小环路，当前选择节点S3作为起始节点。根据步骤2～步骤4删除S3-S5的连接，通过最短路径算法求取S3-S5的最短路径，最终求得路径S3-S4-S5为最小路径，因此将{S3,S4,S5}加入到一个环路域中，生成环路域Loop1，拓扑图如图3所示。

图3 融合环路域Loop1

删除节点S3和环路域中度为2的节点，进行循环步骤2～步骤4的处理。选择S4初始节点，经过计算将{S4,S5,S6,S7}加入同一环路域，生成环路域Loop2，拓扑图如图4所示。

图4 融合环路域Loop2

删除初始节点S4，清理掉该环路域中度为2的节点{S5,56}，由于清除完成后S7度为1，将S7清除并保留与S7直连节点S8的度进行下面的计算。以S9为初始节点，断掉S9-S8的邻边，计算S9-S8的最短路径。经过计算，S9到S8不存在最短路径，说明未形成环路，将S9删除，并同步删除新产生度为1的节点{S8,S10}，至此{S8,S9,S10}加入到转发域中，产生转发域Group2，生成的拓扑图如图5所示。

图5 融合转发域Group2

前面的步骤已访问了S1-S10，剩下的{S11,S12,S13,S14}所有节点的度都大于2，因此将这些节点加入到同一个环路域中，生成环路域Loop3。通过各个域之间建立连接关系，转发域Group1通过S2与环路域Loop1中的S3直连，Loop1中的{S4,S5}与Loop2中的{S4,S5}相交，转发域Group2通过S8与环路域Loop2的S7直连，通过S10与环路域Loop3的S11直连。通过以上关系建立网络链路连接，最终拓扑图如图6所示。

图6 最终域间逻辑拓扑

通过融合的环路域和转发域可以简化拓扑结构，方便流量调度，其最重要的一个优势是简化了流表数量。对于转发域来说，转发域中的节点只能组成一条链路，域间转发时，在域中传输每台设备只需要两条流表，用来控制发送和接收数据的转发；域内转发时，每台设备需要一条流表匹配目的节点，实现域内转发。对于环路域来说，每个环路域至少包含两条转发路径，可以将这两条路径作为主备份路径安装进交换机，在链路故障时进行故障恢复，域间转发时，设备中的匹配方式通过域名匹配，需要两条流表控制转发出口。

综上所述，交换机流表数量与交换机设备所属于的域成正比，单域设备只有一种转发方式，总共两条流表；多域设备需要按域转发，一条发送一条接收，因此流表数量是域数量的两倍。在用到所有设备的情况下，流表数量与设备数量之间的关系如下

普通流表数量=N*2*流数量 分域流表数量=N*2+域数量*2*流数量

以示例拓扑为例，总共有14台设备，分成了5个环路域，流表数量变化如图7所示。

图7 流表数量对比

随着流数量的增加，分域流表数量增加的速度远远低于普通流表数量，当前拓扑环境下，当流数量达到8条时，流表数量较普通SDN下发流表数量减少了50%以上，达到了减少交换机流表数量的目的。

2.2 分域调度

随着用户数量的不断增加，网络业务类型和业务流量不断增长，导致当前网络呈现高冗余性。物理网络上端到端具有多条可达路径，如何在该网络上制定合理的调度策略，以实现网络业务的正常运行并保证服务质量，是当前网络管理工作中的一项重大挑战。本文在进行环路融合后，引入路径评估方法，在下发转发配置前评估所有转发路径，选择最优转发路径进行转发流量，保障网络业务的服务质量。

在环路融合后，每个环路域或转发域融合成一个节点，域与域之间通过逻辑链路连接，每段链路具有两个权值，包含域中节点的数量和域中链路转发的链路带宽。通过计算一条转发路径，使链路带宽满足业务需求并且经过的域节点数量最少，提高业务的服务质量。

我们假定一条流从源设备到目的设备经过了多个域，设这条路径为p，该路径包含了多个域节点，每个域流向下一个域所经过的节点数量为hi；域与域之间通过链路连接，每条链路具有两个带宽值，带宽总容量为ci，链路已使用带宽为bi，存储方式如式(1)～式(3)

H=[h1,h2,…,hi,…,hn]

(1)

C=[c1,c2,…,ci,…,cn]

(2)

B=[b1,b2,…,bi,…,bn]

(3)

其中，下标n表示域的总数，h1表示流经过的融合域1流向融合域2所经过的设备节点数量，即转发跳数。ci、bi分别表示域链路上的带宽总容量和已使用的带宽。根据转发策略的不同，每条流可能经过的域数量不同，因此该数组为可变长数组。

通过参数f(src,dst,band)表示一条流的需求，从源端交换机src转发到目的交换机dst，业务所需带宽是band。算法先用深度优先探索(depth-first-search，DFS)进行全路径计算，提取出所有可达路径。遍历路径上的每条链路，检查链路剩余带宽是否满足业务需求，剩余带宽的计算方式见式(4)。满足带宽需求的转发路径将会保留下来，进行之后的筛选，不满足需求的路径会被排除

R=[r1,r2,…,ri,…,rn]=C-B

(4)

全路径算法选出所有可达路径，经过计算带宽余量后，会留下符合标准的一条或多条转发路径。每条转发路径都包含以下数组，H数组记录了路径经过每个域的跳数，C数组记录了转发路径上链路带宽的总量，B数组记录了转发路径上已使用的链路带宽，数组长度与路径长度相等。首先计算路径的所有跳数，使用式(5)。选择满足需求路径中Hop最小的链路作为转发链路，然后挑选一条域相交数量较少的链路作为备份链路

(5)

经过计算Hop值后，有可能会产生Hop值相同的链路，需要计算链路的容纳度和平滑度，选择最优的链路作为转发路径。链路容纳度是一条转发路径中链路剩余带宽的最小值，计算方法如式(6)

Contain=min{ri} (ri∈R)

(6)

选择容纳度最大的链路，使该转发路径具有更多的带宽资源来容纳数据，防止突发流量对链路的影响。最后如果链路的容纳度也相同就需要进行最终的链路平滑度计算，保证转发路径中链路的带宽均匀分布，减少来自不同节点转发数据产生的拥塞。具体步骤如下。

步骤1 当前链路已经计算出了链路的容纳度，首先需要计算转发路径的各个链路剩余带宽与容纳度的差值，获取与路径对应的一组链路差值对比数据。对于路径p上的一条链路，其容纳度为Contain，每段链路的差值公式为di，计算方式如式(7)

di=ri-Contain

(7)

步骤2 根据计算出的链路差值数据，计算差值的平滑度，可根据式(8)计算一个评估值Smooth，评估参数Smooth值越小说明该链路的带宽分布更加均匀，不会因某一个节点出现拥塞而影响所有链路的转发，能够为业务提供更加稳定的服务

(8)

通过最终的平滑度公式可以计算出一条波动性较小的转发路径，业务在该路径上传输流量时能够避免一些因突发流量造成的链路拥塞问题，达到了业务保障的效果，提高了业务的服务质量。

3 实验与结果

为了直观展示该流程，本文在模拟网络环境下，将UGLA算法和链路评估引入到故障恢复技术中，并与传统的SDN故障恢复技术和基于OpenFlow组表恢复方法进行对比，以此对本文提出的策略进行测试评估。

本综合实验以Floodlight开源控制器[16]作为控制核心，用于检测链路故障和计算下发故障恢复策略。网络拓扑如图8所示，整体网络由13台设备组成，为了更好地展现故障恢复性能，拓扑结构设计成多环路链接，提高链路冗余度。

图8 实验测试拓扑

通过Mininet[17]构建了一个13台交换机组成的网络，链路上具有2 ms延迟效果，用于模拟物理设备间的通信延迟，每段链路都有不同的带宽值，用于验证带宽在路径选择中的作用。

首先通过网络分域计算当前拓扑中的环路，并计算出每个域的最小带宽和总节点数量，这两个数值将作为链路评估所使用的参数。根据UGLA计算方法所得的环路域如图9所示，经过计算精简了当前拓扑结构。

图9 环域融合逻辑拓扑

根据当前的环路域拓扑结构，生成域内转发流表，保证每个域内的流量能够正常通行。例如，在Loop1域中下发基础流表后，交换机{S1,S2,S3,S4,S5}能够处理带有Loop1标签的MPLS流量，使该流量在当前环路域中沿顺时针或逆时针转发。

经过基础流表的配置，最后只缺少匹配具体数据流的流表，用于流量的流入和流出，链路评估算法正是用来生成该数据流的流表。假定一条数据流为S1发送至S12，带宽需求是10 M。算法为了选择一条转发路径，首先要确定该数据流的基本属性，其源地址是S1，属于环路域Loop1，目的地址是S12，属于环路域Loop7。根据环路域拓扑上的参数，计算出满足当前需求的路径总共有4条，分别是{Loop1,Loop2,Loop6,Loop7}、{Loop1,Loop3,Loop6,Loop7}、{Loop1,Loop2,Loop4,Loop6,Loop7}、{Loop1,Loop3,Loop5,Loop6,Loop7}。

经过筛选，最终决策出{Loop1,Loop2,Loop6,Loop7}作为该数据流的主要转发路径，{Loop1,Loop3,Loop6,Loop7}作为备份转发路径，最终生成流表下发至交换机中。

本文设计了两个应用场景，利用基于SDN的故障恢复来处理域内故障和域间故障。计算出主要转发路径为{Loop1,Loop2,Loop6,Loop7}，确定物理拓扑中数据流的正常传输路径为{S1,S4,S7,S6,S11,S12}。

当发生域内故障时，例如域Loop1内的{S1,S4}和Loop2内的{S5,S6}都发生断路，系统启动域内故障恢复功能，此时不需要控制器参与调控，交换机会自动切换到域内备份路径，并告知控制器故障点位置。经过域内故障恢复策略，此时的数据流转发路径变更为{S1,SS,S3,S5,S9,S10,S13,S12}，故障恢复转发路径如图10所示。

图10 域内故障恢复

由于环路域Loop1中的{S1,S4}出现故障，数据流从备份路径{S1,S2,S3,S5}转发到环路域Loop2的S5，S5同时属于环路域1、2、3、6，S5将标签剥离至Loop6。由于Loop6中的{S5,S6}发生了断路，因此环路域Loop6的转发路径由{S5,S6}切换至{S5,S9,S10}。

通过域内故障恢复处理，能够完成对域内故障的数据流量转发，在增加少量延迟的代价上，实现故障反应快、转发丢包率低的效果。

当发生域间故障时，例如Loop2中的{S4,S5}和{S7,S8}出现断路，导致环路域Loop2与Loop6的连接中断，出现这种情况时，需要控制器参与故障的恢复，以实现降低延迟的效果，故障恢复转发路径如图11所示。

图11 域间故障恢复

根据数据流主要转发路径，当数据流转发到交换机S7时，交换机S7发现链路{S7,S6}出现故障，启用故障恢复组表切换备份路径回传到S4并标记该流量为域Loop2故障流量。交换机S4发现链路{S4,S5}出现故障，且该数据流为故障流量，启动域间故障恢复功能，将该数据流发回域Loop1内并打上域间故障的标记。链路评估计算所得的备份路径开始工作，切换域转发路径为{Loop1,Loop3,Loop6,Loop7}，此时转发路径为{S1,S4,S7,S4,S1,S2,S3,S5,S6,S11,S12}。

仅通过OpenFlow协议恢复会使当前转发路径每次都需要转发到S4和S7交换机然后回溯，浪费网络带宽资源。本设计引入控制器协同工作，在S4上报故障的同时，控制器给S4的上游设备下发配置，匹配故障流量修改转发路径，引导流量不再经过S4和S7，减少网络资源浪费。

当发生域内故障时，本文设计与其它故障恢复方法进行性能对比，链路传输速率如图12所示。

图12 域内故障恢复转发速率对比

传输延迟对比如图13所示。

图13 域内故障恢复延迟对比

该数据表明，控制器恢复方式虽然会选择最优转发路径，但是在故障时需要等待流表失效，才能进行路径切换。OpenFlow方法恢复故障只在本地有效，所有流量必须转发到故障点才能触发故障恢复组表功能，延迟时间过长，且流表数量比控制器调度路径更多。本文提出的恢复方式采取分域转发，减少了流表数量，同时故障也只在域内处理。

当发生域间故障时，链路传输速率如图14所示。

图14 域间故障恢复转发速率对比

传输延迟如图15所示。

图15 域间故障恢复传输延迟对比

该数据表明，OpenFlow组表恢复方式和本文提出的恢复策略均能很好恢复故障，并且加入了控制器的引导，在故障后降低了传输延迟。

综上所述，相比于基于SDN控制器恢复的技术，故障反应时间更快，降低了故障恢复过程中的丢包率，流表数量更少，实现了故障即时恢复的需求；相比于基于OpenFlow协议恢复技术，降低了流表数量，通过交换机上报故障点使控制器能够感知故障位置，控制器及时选择最优路径进行转发流量，降低了传输延迟。本文提出的基于SDN的故障检测及恢复技术实现了SDN网络中故障流量的快速恢复，通过OpenFlow组表和控制器的协同工作以更低的延迟和丢包率传输故障流量，链路评估算法提升了故障流量的传输速率，整网的可靠性和可用性大大增强。

4 结束语

近年来，计算机技术蓬勃发展，互联网业务不断扩大，物联网、云计算等新兴领域逐步成长为大型行业。业务的增多导致网络结构日趋复杂，为网络管理人员带来了繁琐的维护工作。为实现控制器自动恢复网络中出现的故障，减少网络管理人员的维护工作，本文研究和设计的基于SDN的故障恢复方法，依靠控制器强大的管控优势和可编程的开放性，针对链路故障实施故障恢复策略，保证冗余链路故障时，通信能够正常进行。同时还加入了链路带宽评估方法，计算最佳的域间转发路径，满足链路故障时业务的带宽需求，降低传输延迟，提高业务服务质量。

本文的方法优势如下：

(1)保持传输通畅：本文充分利用了OpenFlow协议的特性，实现故障恢复的自动化切换机制，在恢复过程中确保通信不中断。

(2)提高传输质量：本文充分利用了控制器在SDN架构中的核心控制功能，当链路出现故障时，控制器会介入恢复过程，提前将故障数据流引导至正常转发路径上，节约网络资源、降低传输延迟。

(3)降低流表数量：本文使用UGLA对当前拓扑进行分域，流量的匹配仅通过MPLS标签标识，极大降低了交换机中的流表数量，节约了交换机存储资源和流表的匹配效率。