基于混合软件定义网络的路由保护算法

耿海军,张 伟,尹 霞

(1.山西大学 软件学院,太原 030006; 2.中国劳动关系学院 计算机应用教研室,北京 100048;3.清华大学 计算机科学与技术系,北京 100084)

0 概述

近年来,互联网得到了迅速的发展和广泛的部署。然而,大量的新型应用软件和应用场景层出不穷,这对互联网提出了更加严格的要求和更高的挑战。为了适应软件应用发展的需求,斯坦福大学的研究人员提出了一种网络体系结构,即软件定义网络(Software Defined Network,SDN)。该网络体系架构将控制平面和转发平面的功能进行了分离[1],控制平面主要关注如何根据优化目标制定最优的路由决策,而转发平面主要负责快速转发数据包[2]。由于研究人员对SDN架构的性能、健壮性等方面进行了优化,因此使得越来越多的互联网服务提供商开始在他们的骨干网中部署SDN技术[3-6]。然而,由于经济和技术等方面的原因,短期内不可能将目前骨干网中的所有传统网络设备替换为SDN节点,因此骨干网将会长期处在传统网络设备和SDN节点共存的状态,称该网络为混合SDN网络[7-8]。混合SDN网络主要由SDN控制器、SDN节点和传统网络设备构成,SDN节点既可以运行传统的路由协议,也可以和SDN控制器交互信息,但是传统网络设备只能运行传统的路由协议[9]。

随着互联网的发展,其支持的应用范围呈现出了显著的变化。最初,互联网主要支持一些非实时应用,如电子邮件、传输文件等。而如今大量的实时业务数据[10-11]在互联网上广泛传播,如IP语音(Voice over Internet Protocol,VoIP)、股票在线交易、远程手术、视频监控和即时通信等,这些新型应用对路由可用性[12]提出了更高的要求。由此可见,路由可用性将直接影响用户的财产安全甚至生命安全。

目前,提高域内路由可用性的算法可以分为两类,即被动恢复算法和路由保护算法[13]。其中被动恢复算法主要研究当网络出现故障时如何加快路由收敛速度,尽量缩短网络中断时间,但是当网络中的链路频繁断开时,该算法可能导致路由不稳定。路由保护算法则是根据相关规则事先计算备份路由,当网络中出现故障时,利用事先计算的备份路由转发数据包,从而最大化减少报文丢失,缩短网络服务中断时间。相比较而言,路由保护算法更受学术界青睐[14]。

比较典型的路由保护方案主要包括等价多路径路由[15]、多配置路由[16]、Failure Carrying Packet[17]、LFA[18]和Not-Via[19]等。文献[20]提出一种基于SDN的路由保护方案,其利用节点间的偏序关系为每个节点计算多个到达目的节点的下一跳,从而达到路由保护的目的。文献[21]提出一种基于段路由的单节点故障路由保护算法,该算法为网络中所有的节点对部署中转节点,从而提高路由可用性。

已有的路由保护算法多数针对单一网络体系结构,上述方案都可以直接应用在纯SDN网络体系结构中,但是无法直接应用于混合SDN网络。为此,本文提出一种基于混合SDN的路由保护算法。通过在网络中部署SDN节点,为网络中所有的链路计算一条保护路径,从而使算法可以应对网络中可能出现的单链路故障情形。

1 问题描述

目前互联网部署的域内链路状态路由协议为网络中所有的源-目的对计算一条最短路径。当有报文在网络中传输时,路由器根据报文头部字段中的目的地址将该报文正确地转发到目的地址。当网络出现故障时,受该故障影响的报文将会被丢弃,从而影响网络性能,降低用户体验满意度,影响了互联网服务提供商的声誉。学术界和工业界普遍采用路由保护方案来解决由于故障造成的网络性能下降问题。然而已有的路由保护方案都是基于单一网络体系结构展开研究,无法直接应用在混合SDN网络中。因此,可以将本文解决的问题具体表达为:给定网络G=(V,E),其中,V为该拓扑中节点的集合,E为该拓扑中边的集合。如何选择一组节点M⊂V部署SDN技术,从而使得该路由保护算法可以应对网络中所有可能出现的单链路故障情形。

上述问题可以描述为一个0-1整数线性规划(Integer Linear Programming,ILP)模型,即:

(1)

Subject to:

y(i,j,k)∈{0,1},i,j,k∈V

(2)

y(i,j,k)=0,i∉SDN(j,k)

(3)

y(i,j,k)=1,i∈SDN(j,k)

(4)

(5)

x(i)∈{0,1},i∈V

(6)

(7)

(8)

f(i,j)∈{0,1},i,j∈V

(9)

f(i,j)=0, (i,j)∉E

(10)

f(i,j)=1, (i,j)∈E

(11)

z((i,j),i,d)∈{0,1},i,j,d∈V

(12)

z((i,j),i,d)=0, (i,j)∉sp(i,d)

(13)

z((i,j),i,d)=1, (i,j)∈sp(i,d)

(14)

(15)

y(i,j,k)≤x(i)

(16)

下文将阐述上述的0-1整数规划模型。式(1)是本文的优化目标,使得部署SDN节点的数量最小,并且能够实现保护网络中所有可能出现的单链路故障的目的。

在式(2)～式(4)中,变量y(i,j,k)的取值为0或者1,如果y(i,j,k)=1,则节点i是链路(j,k)的SDN节点,否则如果y(i,j,k)=0,则表示节点i不是链路(j,k)的SDN节点。如果节点i是链路(j,k)的SDN节点,则当链路(j,k)出现故障时,节点j可以先将报文发送给节点i,然后节点i再将报文发送给节点k。式(5)说明,如果某个节点i是链路(j,k)的SDN节点,则节点j到节点i的最短路径一定不包含链路(j,k),并且节点i至少有一个邻居节点到k的最短路径一定不包含链路(j,k),式(5)同时也给出了计算网络中所有链路SDN节点的方法。为了更好地理解式(5),本文通过实例来进行解释。图1表示节点i是链路(j,k)中SDN节点的情况,图中节点间的虚线表示这2个节点之间的最短路径,实线表示这2个节点是邻居节点。当链路(j,k)出现故障时,节点j可以先将报文发送给节点i,并且节点j到节点i的最短路径不能包含链路(j,k),然后如果节点i到节点k的最短路径不包含链路(j,k),则节点i通过最短路径将报文转发给节点k,否则如果节点i到节点k的最短路径包含链路(j,k),则节点i将报文转发给其邻居节点x,并且需要保证节点x到节点k的最短路径不包含链路(j,k)。

图1 节点i为链路(j,k)中SDN节点的情况

在式(6)～式(8)中,变量x(i)的取值为0或者1,如果x(i)=1,则该节点是SDN节点,否则如果x(i)=0,则该节点是传统网络设备。在式(9)～式(11)中,变量f(i,j)的取值为0或者1,如果f(i,j)=1,则表示链路(i,j)在网络拓扑结构中,否则如果f(i,j)=0,则表示链路(i,j)不在网络拓扑结构中。在式(12)～式(14)中,变量z((i,j),i,d)的取值为0或者1,如果z((i,j),i,d)=1,则表示链路(i,j)在节点i到节点j的最短路径上,否则如果z((i,j),i,d)=0,则表示链路(i,j)不在节点i到节点j的最短路径上。式(15)说明,对于网络中的任意一条链路,该链路对应唯一一个SDN节点。式(16)说明,如果有一条链路选择某个节点为其对应的SDN节点,则该节点必将被部署为SDN节点。

2 算法描述

2.1 SLFRPHSDN算法

第1节分析了本文需要解决的关键问题,并且形式化地描述了该问题。从上文的描述可以看出,该问题中所有变量的取值均为0和1,因此需要解决的问题是一个0-1整数规划。因为0-1整数规划已经被证明是一个NP问题,所以不可能在有限的时间内获得最优解。在实际网络中,网络拓扑大小的变化范围较大,从十几个节点到上百个节点不等。在较小的网络中,可以使用已有的工具如CPLEX获得最优解,但是在较大的网络中,CPLEX将无法计算出最优解。因此,本文提出一种通用的解决方案SLFRPHSDN,该方案适用于各种类型的网络拓扑结构。

算法1SLFRPHSDN算法

输入G=(V,E)

输出M

1.计算网络中任意链路(j,k)∈E对应的SDN节点SDN(j,k)

3.M=Φ

4.While R(G,M)<1 and M≠V do

6.M←M∪m

7.For (j,k)∈E

8.If m∈SDN(j,k) then

9.清空SDN(j,k)

10.End If

11.End For

13.计算故障保护率R(G,M)

14.End While

15.Return M

2.2 算法实例

下文通过一个例子来详细解释算法SLFRPHSDN的执行过程。图2为一个包含8个节点和12条边的简单网络拓扑结构,边上标注的数值表示该边的权值。

图2 SLFRPHSDN算法执行过程

表1 算法初始化后链路对应的SDN节点

表2 算法执行完第一次循环链路对应的SDN节点

2.3 SLFRPHSDN算法的时间复杂度

上文详细介绍了SLFRPHSDN的执行过程,本节将从理论上分析该算法的时间复杂度。

定理1算法SLFRPHSDN的时间复杂度为O(|E||V-2|+|V|(|V|lg|V|+E))。

证明算法SLFRPHSDN的第1行对应的时间复杂度为O(|E||V-2|+|V|(|V|lg|V|+E)),这是因为该行需要为网络中的所有链路计算可能出现的SDN节点,每一条链路对应的SDN节点的数量最大为|V-2|。判断某个节点是否为链路的SDN节点需要计算节点对之间的最短路径,该部分的时间复杂度为O(|V|(|V|lg|V|+E))。算法第4行到第14行的功能是为所有的链路选择最终的SDN节点,时间复杂度为O(|E||V-2|)。综上所述,算法SLFRPHSDN的时间复杂度为O(|E||V-2|+|V|(|V|lg|V|+E))。

3 实验与结果分析

本节将利用模拟实验来验证算法的性能,并对实验的结果做出合理的说明。本文利用C+ +语言实现算法,编译器为CodeBlocks。该算法运行的平台为一台PC机,Intel(R) Core(TM) i7-7700 CPU@3.6 GHz处理器,16 GB内存,64位Windows10操作系统。算法的评价指标主要有SDN节点的数量、故障保护率和路径拉伸度。部署SDN节点需要一定的开销,如果只需要升级部分SDN节点就可以达到目的,则网络开销就越小,反之网络负担越大。如果故障保护率越接近100%,则该算法应对网络故障的能力越强,反之应对网络故障的能力较弱。如果路径拉伸度越接近于1,则该算法不会给网络增加较大的时延,否则该算法将会大大增加网络延迟,影响网络传输性能。本文首先详细介绍实验采用的网络拓扑,然后给出实验结果,并对结果给出详细的说明。

3.1 网络拓扑

为使实验的结果更具有说服力,本文将算法运行在3种不同类型的网络拓扑中,即真实网络拓扑、测量网络拓扑和利用模拟软件生成的网络拓扑。

1)真实网络拓扑结构[22-23]。在该类型的网络拓扑中选择了4个真实网络拓扑,Abilene包括11个节点和14条边,TORONTO包括25个节点和55条边,NJLATA、USLD包括28个节点和45条边。

2)Rocketfuel[24]测量的拓扑结构。在该类型的网络拓扑中选择了4个测量拓扑结构。AS1755包括87个节点和161条边,AS1239包括315个节点和972条边,AS3257包括161个节点和328条边,AS3967包括79个节点和147条边。

3)利用模拟软件Brite生成的拓扑结构。Brite使用的模型为Waxman,拓扑中节点的数量在100和500之间,alpha的参数设置为0.15,beta的参数设置为0.2,网络的平均度参数设置为2到4,网络中节点的分布服从重尾分布,链路的带宽参数设置为10到1 024,链路的代价和链路带宽互为倒数。

3.2 SDN节点的数量

为了保护网络中所有的链路,本文将网络中部分传统设备升级为SDN设备。但是升级SDN设备需要一定的经济开销,因此如果升级的SDN节点数量越少,则带来的经济开销越小,否则,该方案很难在实际网络中部署。因此,本节主要研究为保护网络中所有的链路,不同网络拓扑中需要部署SDN节点的数量。表3说明了不同类型的网络拓扑中对应部署SDN节点的数量。在表3中,Brite(m,n)表示利用Brite软件生成的拓扑结构,节点数量为m,网络平均度为n。

表3 SDN节点的数量

从表3可知,在真实网络拓扑中Abilene需要升级1/3左右的节点,其余网络拓扑仅仅需要升级1/8左右的节点。在测量拓扑中,AS1755和AS3967需要升级1/7左右的节点,AS3257需要升级1/16左右的节点,而AS1239仅仅需要升级1/26的节点。在Brite生成的拓扑结构中,当网络的平均度为2时,需要升级大约1/20～1/30左右的节点,当网络的平均度为4时,仅仅需要升级1/50～1/100左右的节点。从上面的实验结果可知,在稀疏图中需要升级大量的SDN节点,然而在稠密图中仅仅需要升级少量的SDN节点。这是因为在稀疏图每条链路对应的SDN节点数量较少,并且SDN节点重复的可能性较小。在稠密图中,每条链路对应的SDN节点数量较多,不同链路之间公共SDN节点较多。因此,在稀疏图中,最终选择的SDN数量较多,在稠密图中,最终选择的SDN数量较少。

3.3 故障保护率

本节利用故障保护率来衡量算法应对故障的能力,故障保护率的数值越大,该算法应对故障的能力越强。如果算法的故障保护率为100%,则表明该算法可以应对网络中所有可能出现的单链路故障情形。表4列出了算法在3种拓扑中的故障保护率结果。

表4 故障保护率

由表4可知,在所有网络拓扑结构中,算法对应的故障保护率为100%。这是因为本文的算法可以为所有的链路找到SDN节点,从而达到保护链路的目的。

3.4 路径拉伸度

本节利用路径拉伸度来度量算法带来的路径开销。在本文实验中,将路径拉伸度定义为当网络出现故障时,利用算法SLFRPHSDN计算出的路径的代价和利用OSPF计算的最短路径的代价的比值。表5列出了算法SLFRPHSDN在不同网络拓扑中对应的路径拉伸度。

表5 路径拉伸度

从表5可以看出,在实验的所有网络拓扑中,AS1239对应的路径拉伸度最大为1.267,其余网络拓扑对应的路径拉伸度均小于该数值,因此该算法不会带来较大的路径开销。尤其是在真实拓扑Abilene中,算法对应的路径拉伸度仅为1.075,该数值和利用OSPF协议收敛后计算出的最短路径的代价基本一致。

4 结束语

本文研究在传统网络中将传统设备升级为SDN设备,从而使得路由保护算法可以应对网络中可能出现的单链路故障情形。通过将传统网络中部署SDN节点的问题描述为0-1整数规划问题,并提出一种启发式的算法SLFRPHSDN进行求解。实验结果表明,该算法只需在传统网络中将少部分节点升级为SDN节点,故障保护率即可达到100%,并且不会带来过多的路径开销。本文仅讨论了混合SDN网络中的单链路故障路由保护算法,下一步将针对多链路故障和单节点故障情形设计路由保护算法。