基于SDN 的多级多域路由算法研究

田家翼，黄 韬，杨 帆

(北京邮电大学信息与通信工程学院，北京 100876)

0 引言

企业网络中通常利用MPLS 等技术提供专线业务，维护成本昂贵，配置复杂并且难以管理，在这样的架构下进行路由方案调整，优化用户业务质量异常困难[1]。针对此类问题，现有的路由策略[2]无法提供合适的解决方案。传统路由方案通常按照尽力而为的策略选择单一路径，不能有效的结合网络当前的负载情况，没有考虑网络中的流量特征和链路状态，如等价多路径算法（ECMP）[3]，可能会将多个流量分配到同一条链路上，当链路间差异很明显的时候，很难达到满意的效果。

将软件定义网络[4]与广域网结合，利用软件定义网络数据平面和控制平面分离的架构进行路由规划和路径选择，能够灵活的控制和调度网络流量，可以使网络服务敏捷性大大增加。SDN-WAN[5]提供了基于SDN 架构的企业分支在广域网中的解决方案。通过部署SDN 和SDN-WAN，可以提供更好的性能并且改善可用性，利用灵活的路由算法，保障用户业务，让链路处于轻载状态。结合SDN-WAN通常连接不同的服务网络，规模巨大的特点，本文采用一种分级路由的方案，将整个网络划分多个子域，路由计算分为域内路由和域间路由两个部分[6]，实施不同的路由策略，并且将网络拓扑进行抽象简化，如下图所示，域间由只需要获取跨域链路的负载状态，接收到简化到全局视图之后进行路由计算和流量调度，不仅减少了信息交互，而且降低了路由计算的复杂度。

图1 多个域路由拓扑 Fig.1 Muti-domain routing topology

本文主要研究一种结合软件定义网络，采用多级多域的路由方案的动态流量调度方法。该方法可以提高整个网络的链路利用率，调节网络拓扑的流量分布和吞吐量，并且能够达到更优负载均衡，有效的调整网络拥塞，最后算法拥有较低的时间复杂度，可以较快进行计算和响应。

1 相关研究

在已有的基于软件定义网络架构的路由方案中，文献[7]中提出了一种级连路由的多路径算法，通过不同节点之间交换路径信息构建多条路径来保障用户服务。文献[8]提出了一种网络最坏适应多路径路由算法（AWMR），该算法根据网络中可用的网络资源和新加入节点的带宽需求来选择多条路径和确定新加入节点的转发路径，而不是对每个流使用固定数量的转发路径。文献[9]提出了一种基于网络性能的路由算法（PBR），该算法通过测量往返时延作为路径权重，利用bellman-ford 算法结合SPFA 进行优化，利用计算的路径矢量图进行快速路由。

以上几种算法都有着不可避免的一些问题，级连路由的多路径算法对于如何构建满足多个约束条件的级连路径，没有提出一种通用有效的方案。最坏适应多路径算法通过计算源节点与目的节点的最短路径集，根据流量的带宽需求选择最坏匹配路径，但是其收敛速度可能很慢，并不能适应响应速度要求很高的网络环境。基于网络性能的路由算法通过时延探测网络性能，并没有考虑整个网络的流量状态。

综上所述，上述算法不能根据当前网络的全局负载情况，保证高效快速的路由转发。本文的算法采用域间和域内相结合的路由策略，当链路负载过高时，根据域间流量分布和域内链路状态进行重新路由。

2 基于软件定义网络的路由算法

本节将提出一个基于软件定义网络的多级多域的路由算法。对链路负载进行监测，域内和域间基于不同的选路策略。

2.1 设计思路

本文设计了一种域间域内相结合的路由策略，可以使得全局流量得到最大化的合理均匀分配。为域的集合，每个域 di∈ G为有向图的一个子集。

1）域内采用基于时延的路由算法：

根据子域流量数目多，对时延敏感[10]等特点，每个子域内 di计算链路平均时延作为路径的权重，采用基于时延进行权重选路的策略。设源节点s，目的节点d，链路为 ek，权重参数，代价计算：

每次当前节点选择权重最优的链路进行构建，直到到达目的节点。其中时延计算方法为当前节点发送探测数据包，通过接收回传的探测包，使用当前时间戳减去发送探测包的时间戳，得到路径的往返时延，记为RTTSiSj， si,sj表示路径。

2）域间采用基于流量[11]的动态路由算法：

由于域间流量具有动态性的特点，采用周期性检测以更新网络状态， 根据当前链路状态判断负载情况，基于可选路径统计域内平均链路利用率，计算当前流量带宽情况，将较大的流量根据最大—最小公平原则进行路由。

步骤1 行链路负载检测，当超过阈值则将负载过重的链路上的流量进行路径转换或者重新路由。链路负载参数为：

l 为某一时刻链路i 的负载率，N 为所有链路，当δ ＞ δ*时，需要进行流量调度重新路由。

步骤2 设网络中有n 条数据流F={ f1, f2, f3,…, fn}，表示所有流的集合，一条流 fi定义为一个三元组( sk, dk, bk)，表示每条跨域流量的起始域 sk和目的域 dk和流量需要的带宽 bk；每个子域 di周期性的下发统计消息，向交换机进行数据采集，流量的带宽速率可以由以下公示计算：

式中，ψt是根据时间对流量大小进行的估计， bt是交换机在时刻t 接收到的该流的所有字节数，bs是时刻s 接收到该流的所有字节数，t - s是统计的时间间隔。

步骤3 将链路上S 条流量F={ f1, f2, f3,…, fs}进行重新路由，以各个子域内 di内的平均链路利用率作为权重，每个子域平均链路利用率为：

其中， bmi表示第m 条路径第i 条链路在某时刻的已占用带宽，可通过信息统计计算出，N 为链路的总条数，B 为链路的最大带宽。在此基础上，计算可选n 条路径，路径集合为P={ p1, p2, p3, …,pn}，每条路径有k 条链路，将流量离散化以最大—最小公平原则[12]进行路由，对于F={ f1, f2, f3, … ,fs}，带宽需求满足 b1＜ b2＜ …＜bs，链路总带宽为B，将 B /s 分配给带宽需求最小的流量，超出部分回收，再次将(B -b1)/( s- 1)的带宽分配给其他流量，对于所有路径重复上述过程。

2.2 算法实现

将全局网络抽象成一个有向图G =(V, E)，V 是网络节点（各个子域抽象成独立节点）的集合，E是链路的集合，一条链路 eij定义为一个三元( vi, vj, c) 组， vi,vj∈ V为网络节点，每一条链路 eij都有一个非负数值0c ＞ 表示链路带宽。

算法1 getIntraDomainRounting

输入：源节点s，目的节点d，节点V 和链路E 的集合

输出：域内最优转发路径

Begin

delay[s] = 0;

for (int i = 0; i < vertices.length - 1; i++);

for(int j = 1; j < vertices.length; j++)

edgeDelay(i,j) = detectDelay(edge(i,j));

end for

end for

while(true)

if (s == d)

break

else

int minVertex =minCost()

for (V v： minVertex.adjcent())

int cost =delay[minVertex] + edgeDelay(v, minVertex);

delay[v] = delay[v] < cost? delay[v] ： cost;

updateVertex(v, delay[v]);

end for

return buildPath();

End

算法2 getInterDomainRounting

输入：源节点s，目的节点d，节点V 和链路E 的集合，子域的集合D

输出：流量重新优化路由结果

Begin

if (countLinkLoad() > loadMax)

for (flow f ： F)

for(Domain d ： D)

averageLoad[d] = Sum(V.links().load()) / Sum(V.links.size);

end for

paths = getOptimizedPath(f, D, averageLoad, k);

minMaxFireAllocatePath(f, paths);

end for

return

End

2.3 算法复杂度

假设全局网络节点数为N，而每个Domain 网络的节点数是 /N n。在传统网络或者SDN 架构中路径计算的复杂度是{ 2}N∧。在本文中，跨域路径计算被划分为域内路径计算和域间路径计算两部分，其中域内路径复杂度为，而域间复杂度为{ 2}n∧。因此，跨域路径计算复杂度为当1N ＞ 且n N＜ 时，且较大时，所以本文提出的算法可降低网络路径计算[13]的复杂度。而当时，可以最大程度降低全局路径计算复杂度。

2.4 仿真结果

为了验证本文的设计，利用Mininet 仿真软件和ONOS 控制器[14]进行实验验证。算法由域间控制模块和域内控制模块实现，各个子域与域间控制模块之间进行周期性的信息交互，域内控制模块从交换机[15]采集端口的统计信息，包括端口号，收发的包数和字节数，信息接收时间，链路状态等统计信息，将当前域内路由状态，域的标识和域间链路信息返回给域间控制模块，根据这些信息计算流量速率和链路负载参数等。

本文构建了5 个域来模拟SDN-WAN 中多个域的网络场景。每个域包括8 台交换机，和80 台主机，网络中所有节点之间的链路均设置为全双工链路，并将链路带宽设定为100 Mbp/s，使用iperf 工具产生模拟的网络流量，随机的选择源主机向目的主机发送报文，每个流的速率服从于均匀分布，平均为10 Mbp/s，每个流持续时间80 s。在本实验中，逐步增加注入网络的流量速率，变化范围是链路总带宽的1%～90%。

本文对多级多域负载均衡路由算法（标记为LBMD）和ECMP 以及针对SDN-WAN 提出的基于网络性能（标记为PBR）的路由算法进行比较，结果如下图所示。可以看到，图5 分别采用不同算法进行路由的平均链路利用率仿真对比。仿真结果表明由于ECMP 在路由时没有将网络的链路状态和流量分布情况考虑在内，只是将数据流均匀分配到各条等价路径上，导致链路带宽分配不均匀，增加了链路拥塞的可能性，因此它的平均链路利用率要低于PBR 和LBM。此外，从图中可以看出PBR 算法中没有考虑传输后路径上的实时负载情况，这容易造成某条路径上的负载过重，降低网络链路利用率，而LBMD 算法对链路状态进行实时检测，采用动态的路由策略进行调整，因此性能要高于其他两个算法。

下图为网络吞吐量性能的对比。从图中可以看出，当流量速率超过一定大小之后，ECMP 的吞吐量要比LBMD 低的多，这是因为ECMP 按照地址散列的方式可能将多个流映射到同一条路径上，造成网络拥塞，导致数据包的丢失。PBR 的吞吐量也要比LBMD 低，是因为PBR 将时延作为参数进行路由计算，在网络规模比较大的情况下不能够及时的做出调整，而LBMD 针对域间路径采用实时监测进行分流的策略，减少了开销并且优化了流量分布。

图2 平均链路利用率对比 Fig.2 Comparison of average link utilization

图3 网络吞吐量对比 Fig.3 Comparison of network throughput

3 结论

本文针对SDN-WAN 网络中的路由问题，提出了一种多级多域的动态流量调度算法。该算法将网络划分为多个域，针对域间和域内不同的链路特点采用不同的路由计算方案。首先介绍了算法的总体流程，给出算法设计思想和实现步骤，最后在仿真平台上对算法进行了验证，结果表明，与其他算法相比，LDMD 算法可以提高多个域网络对平均链路利用率和网络吞吐量，并且有较低的时间复杂度。 下一个阶段计划进行更多的验证实验，算法没有对其他性能进行仿真测试，比如时延等参数，以及与其他基于SDN 架构的路由算法的分析和比较。