SDN架构下的链路分离路径算法的研究

池亚平 高 聪 陈 颖 范晓红

1(北京电子科技学院通信工程系 北京 100070)2(西安电子科技大学通信工程学院 陕西 西安 710071)3(中国科学院信息工程研究所网络测评技术重点实验室 北京 100093)

0 引 言

近些年，随着互联网规模的不断扩大，互联网用户数量呈现巨大的增长。人们对互联网的需求越来越多，对网络的质量要求也日益增高，所以人们要求网络的传输能够更加可靠。传统网络具有非常分散的控制机制，特定的路由协议和算法在每个独立的节点上运行。在现如今网络设备多种多样的现实网络中，这种分布式网络架构，使得网络管理和监控成为一项艰巨的任务。SDN的出现给复杂的网络管理者们带来了曙光。SDN摆脱了硬件对于网络的限制，使网络可编程化，通过软件可以对网络进行管理和修改。

SDN是一个具有三层架构的新型网络架构(如图1所示)，包括数据层、控制层、应用层。其中控制层是SDN的一个核心层，在控制层实现路径的计算。在SDN架构中，控制层与数据层分离，对网络的控制集中在可编程控制器中。数据层与控制层分离的灵活架构，使QoS传输和流量工程可以集中式处理网络的拓扑信息，网络可以高效地运行。传统网络的体系结构是过于静态、不够灵活，无法获得网络全局拓扑信息。SDN中网络设备的流量可以由软件集中动态控制，可以确保网络资源的优化分配，避免拥塞。SDN的一个重要的特点是可以获取到网络拓扑的全局信息，SDN的出现使得流量工程有了更进一步的发展。该网络架构通过使用新型网络协议(如OpenFlow[1])降低传统网络设备获取网络资源信息的通信开销，降低对网络资源的占用。SDN另一个重要的特点是能够灵活地控制网络流量，使用不同的路由算法来改变网络的传输路径。路由算法仅运行在控制器中，SDN通过对路由设备的集中控制，提供更加精确的路径，获得更小的延迟、更加高质量的路径。

图1 SDN架构图

SDN网络的出现，使现有网络有了集中控制的思想，对传统网络中的路由算法有了较大的影响。由于SDN的创新特性的出现，不得不对传统的路由算法进行重新研究。本文对多路径算法进行了改进及应用，多路径算法对流量工程也具有很大帮助。流量工程用于优化网络流量的控制和监控，有助于满足特定的服务质量并提供高效的网络资源利用率。传统的流量工程增加网络的通信开销，并且复杂的算法对有限的计算资源来说是一个巨大的挑战，SDN的出现有效应对了流量工程的这一挑战。

多路径路由算法能够计算出网络中多条可行路径，可以应用到流量工程中，启用多路径，便于分流，从而利用现有利用率比较低的路径，有利于网络流量在不同链路上进行均衡。当前在多路径算法中，对于链路分离路径算法的应用研究很少。链路分离路径可以增加数据的可靠传递，为寻路失败提供弹性，缩减网络的拥堵，有助于在网络中提供高速率的数据传输和负载均衡。对于在QoS需求较高的网络中，SDN具有较高的优势。通过为不同的流量提供多个链路分离路径，从而有效地优化网络资源的利用，即实现接纳控制、流量分类和负载均衡等，还能够增强路径的可靠性。对于流量感知网络，解决接入控制和多路径的失败等问题需要耗费很多时间，这些工作的耗时不仅体现在网络的核心设备或路由器的接入时间，更体现在路径的计算上。

SDN通过使用OpenFlow协议能够细粒度地对流量进行调控，使得网络可以更加精确地对流量进行控制。现有的许多算法仅仅是增强链路的约束条件，或者是在SDN中应用十分复杂的算法来取得更优的链路。本文将SDN的灵活特性、细粒度控制特性与链路分离路径相结合，利用二者的特点，为网络提供多条可靠路径，从而提高网络的鲁棒性，并且可以使用多分离路径进行负载均衡。由于使用了分离路径算法，更能提高网络的利用率。

1 研究现状

SDN使网络软件化、扁平化。在SDN中，关于路由算法的研究有很多。一方面，有些研究人员使用简单的路由算法，如最短路径优先算法和带宽最宽的路径算法来优化SDN网络中的路由问题。文献[2]使用带宽最宽的路径来查找数据中心的交换机和服务器之间路径，带宽最宽的路径搜索算法会对带宽资源造成过度的浪费，过度消耗网络带宽还能造成网络拥堵。文献[3]在Floodlight控制器中使用广度优先搜索算法代替了最短路径优先算法。在这些文献中，研究人员没有使用SDN的特性来对算法进行优化。另一方面，SDN中大部分的路由算法的研究主要集中在复杂的路由算法上，这些算法的主要目标就是满足服务需求的QoS约束，约束越多算法越复杂。文献[4-5]使用复杂的算法来优化多媒体和视频流量通信，从而提高网络服务的通信质量。同样的，文献[6]使用多约束最短路径来增强视频流的服务。SDN架构下的流量调度算法是当下研究的热点，文献[7-8]在混合SDN架构下对网络进行建模，研究使用贪婪策略对SDN交换机进行增量部署，计算出混合SDN网络中合理的SDN交换机配置数量比例。文献[9]研究了在SDN网络中，快速计算出带宽受限的路径。在传统的算法中，最小跳数算法MHA(Minimum-hopalgorithm)是使用比较广泛的算法，它可以在满足带宽需求的路径中选择链路跳数最少的一个路径。该算法维护每条链路上的可用带宽信息，只有那些有足够资源且满足用户需求的路由才会被考虑进路由中。MHA法非常简单，但是很快就会造成网络的瓶颈链路，导致资源利用率低下。文献[9]中提及的最短最宽路径SWP(Shortest Widest Path)和最宽最短路径WSP(Widest Shortest Path)算法都是MHA的增强的算法。其中WSP算法在最短可行路径集合中，选择具有最高可用带宽的路径即最宽路径，在负载均衡和资源消耗两个冲突的需求之间权衡。

上述算法最终都是考虑一条路径作为最佳传输路径，多路径算法在流量工程领域有很多优势。等价路由ECMP[10](Equal Cost Multipath Routing)就是多路径算法一个很好的应用，可以同时使用多条路径进行传输，增加了网络的传输带宽。Yen算法和MPS算法是都是多路径算法，属于K最短路径算法，可找出前K条最短路径。其中Yen算法在流量工程中有应用。以上的多路径算法在是寻找到多条发生重叠的路径，如果在公共链路上出现了故障，对两点之间的连通性有很大影响。文献[11]提出了最大K条不相交路径算法来实现路由。该算法未找到最短的一对不相交路径，并且没有使用SDN能够细粒度控制流量的特性来改进算法。

在通信的源节点和目的节点之间寻找多条分离路径，可以将多条路径互相当做主备路径，在一条路径失效时，将流量切换到其他路径上，以提高网络的可靠性，还有利于网络流量工程、负载均衡和拥塞避免的发生。关于分离路径算法，RF(Remove-Find)方法是在一对源节点和目的节点之间建立两条链路分离路径的一种简单方法。这种方法简单但是有以下缺点：1) 在网络中删除源节点和目的节点之间的链路，会导致剩余网络拓扑图不连通，从而导致求解不出更多的路径。2) 即使求出第二条路径，第二条路径过长，或者仅仅是问题的可行解而不是最优解。Suurballe提出通过路径增益方法，并使用最短路径方法构建以总长度最小为目标，寻找出两条节点分离路径。之后Suurballe和Tarjan对算法进行了改进。Bhandari通过在原始的Dijkstra算法基础上，提出在有向图中求取路径的链路分离路径算法。以上提到的多数算法都是对原有算法的条件进行改进和增强，没有利用到SDN能够细粒度控制流量的新特性。为了获得更好的路由性能，文献[12-13]已经开始尝试利用SDN架构的优势，但是没有考虑到分离路径算法的优势。

本文借鉴了Bhandari算法的优势，将其与SDN相结合，利用了SDN的灵活特性，为网络传输提供多个路径，增加数据的可靠传递，为寻路失败提供弹性，缩减网络的拥堵，有助于在新型网络中提供高速率的数据传输和负载均衡。

2 OpenFlow

OpenFlow协议可以实现SDN，基于OpenFlow使得网络可编程，从而进一步推出了SDN的概念。OpenFlow支持基于流量的路由决策，OpenFlow交换机根据控制器发出的指令区分流量进行处理，一个流可以被广泛地定义为具有相似特征的一系列分组。控制器可以根据图2中的9个二层网络到四层网络之间的分组报文头字段以及该分组到达接口的标识符来定义一个网络流量。这种控制选项可以实现高精度控制的动态多路径路由，显著增加网络容量。

图2 OpenFlow报头字段

使用OpenFlow接口的统计特性来计算的最佳路径，可以使用基于OpenFlow协议的OpenMT[14]和OpenNetMon[15]等高效的开源软件提取路由算法所需要的信息。其中OpenMT是一种用于OpenFlow网络的流量矩阵估计系统，OpenMT使用OpenFlow交换机中提供的内置功能，既降低了开销，又准确地测量了流量矩阵。OpenMT使用从OpenFlow控制器中学到的路由来智能地获取流量统计信息。OpenNetMon也是一种开源的软件，用于监控OpenFlow网络中的每个流量指标，特别是吞吐量、延迟和数据包丢失。在OpenFlow提供接口来实现细粒度的流量工程的情况下，OpenNetMon提供必要的监视来确定是否实际满足端到端QoS参数，并为TE方法提供输入来计算适当的路径。

OpenFlow协议为数据层和控制层之间提供网络连接，为控制层提供全局的网络视图。当网络连接发生任何变化时，OpenFlow交换机会向控制层发送一个端口状态消息来更新这个变化。另外，OpenFlow交换机有各个端口、各个流和各个队列的流量计数器。这些计数器使用两种类型的消息来维护控制器数据库的网络状态。流量越大，消息越频繁。Read-State消息由控制器发送，用于手机交换机统计信息。消息包含每个交换机的流量持续时间和字节数，从而识别每个链路的网路吞吐量。

算法的实现需要从OpenFlow协议中提取出有效的QoS信息来进行计算。此外，还可以根据OpenFlow报头的不同识别流量的类型、源端口和目的端口等有效信息。

3 算法介绍

SDN控制层的一个主要功能是路径的计算，对于求解分离路径来说，就是找出从源点到目的节点之间一组链路利用率低的链路。在给定的源节点和目的节点之间计算出一对分离路径，将第一可用路径视为主路径，第二可用路径视为恢复路径，其他可用路径进行负载均衡。在主要路径故障发生时，将路径上的流量迅速切换至备用路径，这种方法可以有效地提高网络的可靠性和QoS保障。多路径算法能够更好地提供网络生存能力和恢复能力，非常有利于流量工程、负载均衡和拥塞避免等情况。

3.1 网络模型及假设

有关算法的实现，从关键的假设开始介绍，然后建立模型解决分离路径问题。假设网络的初始状态是具有非负性QoS链路权重的网络，其中QoS权重可以使用加性的，也可以是凸性或凹性的。加性约束有时延、抖动等；凸性或凹性的约束有如带宽、策略标志等。使用修改后的Dijkstra算法之后，网络中的链路将被置为相反方向或者QoS将被赋予负值。如图3所示，边AC在执行完一次算法之后将被置于反向，并将权QoS权重值设置为负值。

图3 修改的Dijkstra算法演示拓扑

将网络抽象为加权无向图，记为G(V,E)。网络中的路由设备和通信链路分别用图3中的节点和边表示。V表示节点的集合，E表示G(V,E)中边的集合。(u，v)表示从节点u到节点v的一条边。G中每条边(u，v)都具有特定的带宽。

用s和t分别代表通信的源和目的节点，P为从s到t的一条路径，用E(P)={(u,v)|(u,v)∈P}代表路径P上的边的集合，给出如下定义：

定义1假设路径P1和路径P2是网络G(V,E)中的两条路径，若E(P1)∩E(P2)=φ，则P1和P2为链路分离路径。

从OpenFlow统计的信息中提取出网络中各链路的QoS信息，QoS信息可以从上文中介绍的开源软件中提取，该软件使用上文中所述的细粒度OpenFlow统计量。在多路径算法运行之前，先对网络拓扑进行处理。首先对QoS信息做处理，由于QoS权重可以是加性的也可是凸性或凹性的，对于凸性和凹性信息(如带宽和策略标志)使用OpenFlow统计的流量类型和数据，根据不同种类的流量给出QoS值。如果是对带宽需求较高的流量请求，我们可以将剩余带宽值较低的链路进行删除，保留合理的链路。对于加性QoS参数，例如延时和抖动，根据网络的特征来寻找更加合理的路径，而不是一味地寻求最短路径，容易造成网络拥堵，并产生资源的浪费。本文给出链路QoS信息的参考值，假设buv是流量的最低需求的带宽，duv表示链路延迟，puv表示丢包率，对低于有效带宽buv的链路进行删除，用Cuv来表示在(u,v)边上消耗的费用，将QoSuv定义为：

QoSuv=aduv+βpuv∀(u,v)∈E

3.2 改进的Dijkstra

Dijkstra算法适用于QoS路由，并在实际中网络中，具有可扩展性的优势，它被互联网路由的逐跳协议所使用。大型网络和SDN控制网络是可扩展的，使用改进的Dijkstra算法有助于减少源到目的路由的最坏计算时间。Dijkstra算法用一种贪婪的方法来计算源、目的地对之间或从源到任何其他目的地之间的最短路径。

对于传统的Dijkstra算法，不能直接应用到权值为负的拓扑中。Bhandari改进的算法之中，路径中存在负的边，必须保证已经标记的节点再次被评估，这就意味着任何已经被评估的节点在下一次计算中也要被再次评估。这对存在负弧的网络拓扑构造链路分离路径特别有效。

当拓扑存在权值为负的边时候，原始Dijkstra算法会失效，如图3所示。利用原始Dijkstra算法，求得的路径为P1=ABZ，权重大小为13，此路径并非最短路径，利用改进的Dijkstra算法之后，可以得到最短路径为P2=ADECBZ，权重大小为12，P2权重小于P1，是权重最小的链路。

3.3 链路分离路径算法

使用OpenFlow协议从网络中获取QoS信息作为算法的输入。最后输出需要的k条分离路径。链路分离路径算法的伪代码如下：

Input:(Graph G(V, E), QoS and Request R(s,d,k))

Output: kMDP

1 Run(MDA_Path_Pi);

2 E(Pir) <-E(Pi)

教师也可以根据学生回答问题的情况进行追问，追问的问题可以是学生以往的典型错误，可以是问题的进一步拓展，也可以是知识之间的联系和运用。在不断的设问和追问中，师生和生生不断产生思维碰撞。

3 K<-1,2,…,k;

4 Update Path;

5 while(negative_BMDA_Path_(Pi)=true) do

6 G<-G′;

7 Run(MDA_Path_Pi);

8 If (MDA_Path_Pi over) do

9 return kMDP;

10 else if(E(Pir)∩E(Pi)=∅) do

11 E(Pir)<-E(Pi)

12 Update Path;

13 else

14 E(Pir)<-{E(Pi)-E(Pir)∩E(Pi)}

15 Update Path;

16 end if

17 then if(Path < k) do

18 go to step 5;

19 else

20 Return kMDP;

21 end if

22 end if

在上述伪代码中，当第一次寻找路径时，在没有负边的情况下，算法第1行是按照最短路径算法来寻路的。第5～6行改变了原始的拓扑图，第7行在改变后的拓扑中寻找新的最短路径。第9～15行是将计算出的最短路径所在的边重新组合成最短路径。

3.4 算例分析

图4是使其运行改进后的Dijkstra算法演示。由于第一次运行，拓扑中没有负边缘的存在，严格按照Dijkstra算法来运行，计算出路径为P1=ABCZ。之后改变路径的方向为反向，将成本大小改变为负值，此时已经计算出的路径的链路成本改为-QoS，再次运行改进的Dijkstra算法，得到路径P2=ADCEZ。如果得到的路径与已知路径发生重叠，则删除两条链路的并集，剩余的链路组成分离路径。在计算出P2之后再次修改拓扑，将两条路径的方向取反，链路成本改为负值，得到图4中带有负权值的网络拓扑。在新的拓扑中使用改进的Dijkstra算法找到从A到Z的最短路径P3=AFECBHZ，再删除与之前求得的链路的并集，得到三条链路分离路径。重复上述步骤直到路径计算结束或已达到路径数量请求。

图4 相交路径算法演示

算法的主要流程就是在修改后的拓扑上求出最短路径，将计算出的最短路径和此前的最短分离路径作比较，删除重叠的边，将剩余的边组合成最短的链路分离路径。上述例子中路径P3=AFECBHZ遍历P2、P3的EC和BC两条边，删除EC和BC之后我们会得到三条链路分离的路径(AFEZ,ADCZ,ABHZ)，权重的总和为15，即三条链路权重之和。

如果FE权值变为5，在第二次转变后的拓扑中最短路径P3=AFDBHZ，三条分离路径即变成ABCZ、ADCEZ和AFDBHZ，他们的总长度为3+4+10=17。

4 仿 真

分别使用拥有20个节点的网络和40个节点的网络的拓扑，对于n个点之间我们建立n(n-1)条边的完全拓扑，并在拓扑中求解不同数量的路径个数，并统计算法的执行时间。如图5所示，算法在较短时间内可以求得所需要的路径数量。

图5 求解路径的平均计时间

仿真网络采用具有14个节点21条链路的NSFNET骨干网络进行实验仿真。如图6所示，使用延迟作为实验仿真的QoS值，对每个满足带宽需求的链路上设置不同的延时。在图中使用1节点为源节点，13节点为目的节点，使用SDN控制器获取分离链路。设置各个链路带宽1 Gbit/s，链路带宽满足网络链路的传输质量需求。当链路数量为1时，算法就是最短路径算法，所以求得的路径数目k须大于1，才能体现算法的特点，所以我们取k=2为例，实现仿真。

图6 NSFNET网络

使用Mininet[16]模拟骨干网络，使用Pox控制器进行控制。建立数据平面的方法有三种：1) Hop-by-Hop方式，即交换机之间的数据面直接进行物理连接的方式。2) 覆盖方式，即采用IP通道的等技术构建用于数面的覆盖网络。3) 混合方式，即上述两种方式的组合称为混合方式。本文采用Hop-by-Hop方式组建数据平面，其优点是OpenFlow交换机的数据平面直接互相连接，与其他覆盖方式相比，具有能够高速处理，判断何处出现故障时的考虑因素较少等优点。

利用网络中的延迟作为仿真的参考QoS，求出合适路径，计算出QoS最低的两条分离路径。在每条链路上取不同的延时参数，分别计算路径作对比。其中：MHA算法得到的延时较高；使用Yen算法得到两个链路的平均延时较高，求出的路径条数较多；Dijkstra算法得到最优路径；Path1和Path2是使用本文的算法求出的两条分离路径。由此可见，本文的算法比Yen算法更加有优势，在延时相对接近的情况下，本文的算法能够得到链路分离路径，而Yen算法得到的是一组发生重叠的路径。

如图7所示，多路径分离算法也可以取得良好的通信链路，但是路径分离算法使用到了更多的链路，计算出两条分离路径，可以提供更好的负载均衡，大大提高了链路的鲁棒性。

图7 不同算法之间延迟的比较

5 结 语

链路分离路径算法可以计算出多条没有共用链路的路径，将其与SDN的灵活性和细粒度控制特性相结合，可以为不同服务质量的流量请求提供不同的路径，也可以为同一类型的服务提供多条路径以供选择。根据网络的拥挤程度调整路径的使用，提供网络传输质量的同时，还能够提高网络利用率。链路分离路径能够提高网络的可靠性，为寻路失败提供韧性，缩减网络的拥堵，在网络中为高速率的数据传输提供很大的帮助，实现网络的负载均衡。