一种基于混合SDN网络的单链路故障路由保护方法

摘要

本发明公开了一种基于混合SDN网络的单链路故障路由保护方法，属于互联网技术领域，解决了传统网络中LFC无法应对网络中所有可能出现的单链路故障情形的问题。本发明首先计算出所有未被LFC规则保护的源目的节点对；然后通过在网络中部署SDN节点，保护上述未被保护的所有源目的对，从而使得该方法可以应对网络中所有可能出现的单故障情形。本发明提出的方法不仅可以应对混合SDN网络中所有的单链路故障，并且具有较小的运行时间和路径拉伸度。因此本发明是一种可以在混合SDN网络中部署的高效的路由保护方法。

说明书

技术领域

本发明涉及路由保护技术领域，更具体地说，涉及一种基于混合 SDN网络的单链路故障路由保护方法。

背景技术

SDN是最近兴起的一种新型的网络体系架构，该架构最大的特 点是解耦了控制平面和转发平面的功能。控制平面由一个或者多个 SDN集中控制器组成，负责路径选择和路由决策。转发平面由SDN 交换机构成，负责转发网络中的数据流。控制平面和转发平面通过标 准化接口Openflow进行通信。SDN集中控制器拥有整个网络的逻辑 视图，控制网络中所有数据流的转发路径。控制器通过Openflow将 路由决策信息下发给SDN交换机，从而实现数据流的正确转发。SDN 网络相对于传统网络具有许多优点，例如，网络流量的灵活控制、易 于网络管理和安全策略的实施等。因此，如果在网络中部署SDN技 术将会大大提升网络的性能。但是如果将目前所有的网络设备升级为 SDN设备将是一件不可能的事情。这是因为一方面部署SDN面临巨 大的人力和物力等经济开销，另一方面部署SDN可能会导致网络中 断，影响用户体验。学术界和工业界普遍采用部分部署SDN技术来 升级传统网络，逐步替换网络中的传统设备。我们将传统设备和SDN 设备共存的网络称为混合SDN网络。一个混合SDN网络主要包括 SDN控制器、SDN交换机和传统路由器。SDN控制器通过Openflow 协议和SDN交换机交换信息。SDN交换机可以工作在两个模式中， 既可以和传统路由器通过路由协议交互信息，也可以通过SDN协议 和SDN交换机、SDN控制器交互信息。但是传统路由器只支持传统 的路由协议，无法和SDN控制器交互信息。

大量针对网络故障的研究已经表明，网络中70％的故障为单链路 故障，其余30％为单节点故障和并发故障。学术界和工业界普遍采用 路由保护方案来应对网络中频繁发生的故障。等价多路径路由 (ECMP，Equal-Cost Multipath Routing)是业界采用的最早的同时也 是最简单的一种路由保护方案，但是研究证实该方案无法提供较高的 故障保护率。针对ECMP存在的问题，IETF提出了快速重路由的框 架，在该框架的基础上提出了LFC、基于Not-Via的路由保护方案和 基于隧道的路由保护方案等。在所有的路由保护方案中，LFC以其简 单而受到业界的密切关注，并且得到了华为和华三等路由器厂商的部 署和支持。虽然LFC简单，容易部署，但是LFC有一个致命的缺点， 即LFC无法保护网络中所有可能出现的单链路故障情形。为了克服 LFC存在的问题，作者利用图论的理论知识分析了LFC故障覆盖率 的问题，通过调整网络中链路的权值(LFAOP，LFA Cost Optimization) 来增加LFC的故障保护率，但是该方法并不一定能保证应对所有单 链路故障情形。为此，作者从理论上详细分析了LFC的故障保护率 和网络拓扑之间的关系，通过增加链路来提高LFC的单故障保护情 形。然而，这些方案都是在传统网络体系结构和SDN网络体系结构 的基础上展开研究，无法直接应用在混合SDN网络中。

发明内容

本发明解决其技术问题所采用的技术方案是：构造一种基于混合 SDN网络的单链路故障路由保护方法，包括：

步骤1：计算出网络中所有未被LFC规则保护的源目的节点对的 集合L＝{(s,d),s,d∈V}，计算故障保护率，如果故障保护率小于1，则执 行步骤2，否则，则结束；

步骤2：对于集合(s,d)∈L中的任意源目的节点对，计算每个节点 对之间所有的SDN节点D(s,d)；

步骤3：对于网络中的任意节点i∈V，统计以该节点作为源目的 节点对L＝{(s,d),s,d∈V}的SDN节点的数量

步骤4：创建一个队列Q，该队列的结构为

步骤5：设置部署SDN节点集合的初始值为空集M＝φ；

步骤6：判断故障保护率是否等于1，如果不成立，则执行步骤 8，否则，则结束；

步骤7：如果队列Q为空，则结束，否则选择一个

步骤8：如果从M＝V成立，则结束，否则将上述节点加入到集 合M中，此时M＝{m}∪M；

步骤9：对于集合(s,d)∈L中的任意源目的节点对，如果m∈D(s,d)， 则该源目的对之间的SDN节点就确定了，不必要再为其计算SDN节 点，将

步骤10：更新

步骤11：计算故障保护率，循环执行步骤6-11，直至故障保护 率为1。

其中，步骤1所述的计算故障保护率的方法为：

其中V为该拓扑中节点的集合，

其中，步骤2所述的计算节点对(s,d)之间所有的SDN节点的方 法为：节点i是源目的节点对(s,d)的SDN节点必须满足的条件，即链 路(s,dn(s,d))不在节点s到节点i的最短路径上，并且节点i至少有一个邻 居节点到节点d的最短路径不包括链路(s,dn(s,d))。可以形式化表示为：

x((s,dn(s,d)),s,i)＝0表示链路(s,dn(s,d))不在节点s到节点i的最短路径上，

与现有技术相比，本发明具有如下优点：针对已有路由保护方法 都是在传统网络体系结构或者SDN网络体系结构的基础上展开研究， 这些方法无法直接解决混合SDN网络中的单链路故障问题。本发明 提出了一种基于混合SDN网络的单故障路由保护方法，该方法不仅 可以应对混合SDN网络中所有可能出现的单故障情形，并且具有较 小的开销和路径拉伸度。本发明的其它特征和优点将在随后的说明书 中阐述，并且，部分地从说明书中变得显而易见，或者通过实施本发 明而了解。本发明的目的和其他优点可通过在说明书、权利要求书以 及附图中所特别指出的结构来实现和获得。

附图说明

下面将结合附图及实施例对本发明作进一步说明，附图中：

图1是本发明提供的一种基于混合SDN网络的单故障路由保护 方法的流程示意图。

图2是本发明提供的一种基于混合SDN网络的单故障路由保护 方法的网络拓扑结构示意图。

具体实施方式

为了对本发明的技术特征、目的和效果有更加清楚的理解，现对 照附图详细说明本发明的具体实施方式。

参阅图1，本发明提供了一种基于混合SDN网络的单故障路由 保护方法，包括：

步骤1：计算出网络中所有未被LFC规则保护的源目的节点对的 集合L＝{(s,d),s,d∈V}，计算故障保护率，如果故障保护率小于1，则执 行步骤2，否则，则结束；计算故障保护率的方法如下

步骤2：根据步骤1计算出来的集合L＝{(s,d),s,d∈V}，对于集合(s,d)∈L 中的任意源目的节点对，计算每个节点对之间所有的SDN节点D(s,d)， 计算节点对(s,d)之间所有的SDN节点的方法如下：节点i是源目的节 点对(s,d)的SDN节点必须满足的条件，即链路(s,dn(s,d))不在节点s到节 点i的最短路径上，并且节点i至少有一个邻居节点到节点d的最短路 径不包括链路(s,dn(s,d))。可以形式化表示为：

x((s,dn(s,d)),s,i)＝0表示链路(s,dn(s,d))不在节点s到节点i的最短路径上，

步骤3：对于网络中的任意节点i∈V，统计该节点可以做为源目 的节点对L＝{(s,d),s,d∈V}的SDN节点的次数

步骤4：创建一个队列Q，该队列的结构为

步骤5：设置部署SDN节点集合的初始值为空集M＝φ；

步骤6：判断故障保护率是否等于1，如果不成立，则执行步骤 8，否则，则结束；

步骤7：如果Q为空，则结束，否则选择一个

步骤8：如果M＝V成立，则结束，否则将上述节点加入到集合M 中，此时M＝{m}∪M；

步骤9：对于集合(s,d)∈L中的任意源目的节点对，如果m∈D(s,d)， 则该源目的对之间的SDN节点就确定了，不必要再为其计算SDN节 点，将

步骤10：更新

步骤11：计算故障保护率，循环执行步骤6-11，直至故障保护 率为1。

现在互联网部署的域内路由协议主要是链路状态路由协议，如 IS-IS和OSPF等。在这两种路由协议中，网络中所有的路由器都拥 有本自治域内的完整拓扑结构。当网络处于稳定状态的时候，所有路 由器中存储的拓扑结构是一致的。网络中的每个路由器根据该网络拓 扑结构利用最短路径优先算法(SPF，Shortest Path First)计算一棵以 自己为根的最短路径树(SPT，Shortest Path Tree)，然后利用该树构 造出路由表。根据上述描述可知，目前域内路由协议采用最短路径转 发报文，但是当源节点到目的节点的默认下一跳出现故障时，传输到 该节点的报文将会丢失，将会造成网络中断，大大降低了用户体验。

从上述的描述可知，目前互联网采用最短路径转发报文，当网络 出现故障时将会导致网络中断，严重影响网络性能。因此，为了提升 网络可用性，提高用户体验，国际互联网工程任务组(The Internet Engineering Task Force，IETF)提出利用LFC规则应对网络中的频繁 发生的单链路故障。下面将介绍LFC规则：

LFC：对于任意目的地址d，节点c可以将报文发送给其邻居节 点x，当且仅当满足cost(x,d)＜cost(x,c)+cost(c,d)。该规则可以理解为当节点c 到目的地址d的最优下一跳之间的链路出现故障时，节点c可以将报 文送给其邻居节点x，因为节点c不在节点x到目的地址d的最短路径 上，其中cost(x,d)表示在网络中节点x到节点d的最小代价。

本发明方法在具体实施过程中，

步骤1，根据LFC规则，计算出网络中所有未被LFC规则保护 的源目的节点对的集合L＝{(0,1),(0,2),(1,0),(1,3)}，故障保护率为8/12＝66.67％， 因为故障保护率小于1，所以执行步骤2；

步骤2：根据步骤1计算出来的集合L＝{(0,1),(0,2),(1,0),(1,3)}，对于集 合(s,d)∈L中的任意源目的节点对，计算每个节点对之间所有的SDN 节点D(s,d)，D(0,1)＝{2}，D(0,2)＝{1}，D(1,0)＝{3}，D(1,3)＝{0,2}；

步骤3：对于网络中的任意节点i∈V，统计该节点可以作为源目 的节点对L＝{(0,1),(0,2),(1,0),(1,3)}的SDN节点的次数

步骤4：创建一个队列Q，该队列的结构为

步骤5：设置部署SDN节点集合的初始值为空集M＝φ；

步骤6：因为故障保护率小于1，所以执行步骤7；

步骤7：因为节点2和节点3可以作为源目的节点对 L＝{(0,1),(0,2),(1,0),(1,3)}的SDN节点的次数数值都为2，2的编号小于3的 编号，所以m＝2，此时Q中的元素为((0,1),(1,1),(3,2))；

步骤8：将节点2加入到集合M中，此时M＝{2}；

步骤9：因为2∈D(0,1)，所以源目的对(0,1)之间的SDN节点就确定 了，将∑y(i,0,1),i∈V的数值设置为0，同理，因为2∈D(1,3)，所以源目的 对(1,3)之间的SDN节点就确定了，将∑y(i,1,3),i∈V；

步骤10：更新

步骤11：因为源目的对(0,1)和(1,3)之间的SDN节点就确定了，此 时的故障保护率为10/12＝83.33％，执行步骤6；

步骤6：因为故障保护率小于1，所以执行步骤7；

步骤7：因为节点3可以作为源目的节点对L＝{(0,1),(0,2),(1,0),(1,3)}的 SDN节点的次数数值为2，所以m＝3，此时Q中的元素为((0,0),(1,1))；

步骤8：将节点3加入到集合M中，此时M＝{2,3}；

步骤9：因为3∈D(0,2)，所以源目的对(0,2)之间的SDN节点就确定 了，将∑y(i,0,2),i∈V的数值设置为0，同理，因为2∈D(1,0)，所以源目的 对(1,0)之间的SDN节点就确定了，将∑y(i,1,0),i∈V；

步骤10：更新

步骤11：因为源目的对(0,2)和(1,0)之间的SDN节点就确定了，此 时的故障保护率为12/12＝1，执行步骤6；

步骤6：因为故障保护率等于1，所以结束。

上面结合附图对本发明的实施例进行了描述，但是本发明并不局 限于上述的具体实施方式，上述的具体实施方式仅仅是示意性的，而 不是限制性的，本领域的普通技术人员在本发明的启示下，在不脱离 本发明宗旨和权利要求所保护的范围情况下，还可做出很多形式，这 些均属于本发明的保护之内。