雷田颖林子薇何荣希刘家怿

SDN中多链路状态路由算法∗

雷田颖林子薇何荣希刘家怿

（大连海事大学信息科学技术学院大连116026）

针对软件定义网络（SDN）易于获取链路状态信息的特点，综合考虑链路的时延和可用带宽两种因素的影响，提出一种多链路状态路由算法（MLSR），并通过Mininet和Floodlight进行仿真。仿真结果表明：与文献中已有算法相比，ML⁃SR具有更低的传输时延和丢包率。

软件定义网络；链路状态；路由；Floodlight；Mininet

Class NumberTP393

1引言

软件定义网络（Software Defined Network，SDN）具有松耦合的控制平面与数据平面，支持集中化的网络状态控制，能实现底层网络设施对上层应用的透明［1～2］，与传统网络相比，具有灵活、开放、简单等特点，已得到业界的广泛认可。SDN网络架构分为应用层、控制层和数据层，层与层之间通过南、北向接口相应的协议实现通信［3］。OpenFlow是目前最流行的南向接口协议，其最小数据交换单位为流。交换机根据控制器生成并统一下发的流表来转发数据流［4］。

如何设计和实现高效的路由策略是SDN中一个关键问题，目前已有不少文献［5～8］对此进行讨论。最小跳数路由［5］（Minimum Hop Routing，MHR）、轮询路由［6］（Round-Robin Routing，RRR）、等价多径路由［7］（Equal-Cost Multi-Path，ECMP）和基于链路关键动态路由［8］（Dynamic Routing Algo⁃rithm based on Link Critical Degree，DraLCD）是目前控制器中使用较多的四种路由策略。MHR算法［5］总是选择源和目的交换机之间跳数最少路径，路径一旦选择则始终使用该路径。当两个交换机节点之间存在多条可达路由时，可能导致剩余路径空闲而产生资源浪费。RRR［6］和随机ECMP［7］算法虽然避免了资源浪费的问题，但是与MHR［5］一样，均未能利用网络的实时链路状态信息。DraLCD算法［8］基于剩余链路带宽来选路，有利于根据实时链路情况进行路径选择，但是该算法在拓扑管理时获取链路的带宽信息，而在路由选择时的实时数据可能会与已获取的数据存在一定偏差。更重要的是，该算法没有考虑链路的时延，仅利用局部信息选择下一跳链路，并没有充分利用SDN可以获取全网信息的优势，从全局考虑来选择最佳路由。实际上，网络中各个链路的时延和带宽是动态变化的，而且各不相同，因此，很有必要综合考虑时延及可用带宽等链路状态信息的影响，设计一种更高效的路由算法。

为此，本文针对SDN设计并实现了一种根据网络中多种实时链路状态信息进行路由选择的多链路状态路由算法（Multiple Link-state Routing，ML⁃SR），该算法通过改写Floodlight控制器［9］的源码，利用SDN控制器可以掌控全网信息的优势，从全局考虑，综合分析源交换机到目的交换机的每一条路径所经链路的平均时延和平均剩余带宽等状态信息，进而选出一条综合代价最小的最佳路径。最后利用Mininet［10］对所设计算法进行仿真评测，仿真结果验证了算法的有效性。

2 MLSR算法描述

SDN的系统架构如图1所示，主要分成数据转发层和Floodlight控制层两部分。其中，数据转发层主要是由转发设备和SFlow代理两部分构成；Floodlight控制器主要包括全网感知模块、链路发现决策模块、流表下发模块和SFlow控制器。

图1 系统架构

在Floodlight控制器中，首先通过全网感知模块获得各设备的连接方式，进而获取全网拓扑结构。然后通过链路发现决策模块实现MLSR算法，完成最佳路径选择。SFlow控制器通过Restlet框架和JSON数据以及正则表达式技术，为链路发现决策模块提供链路选择所需实时流量信息。最后流表下发模块根据所获取的最佳路径，通知该路径途经交换机进行流表更新。

MLSR算法通过链路发现决策模块实现，可分成链路发现子模块和链路选择子模块两部分。

链路发现子模块的主要工作过程为：

1）获取全网节点的邻接矩阵relations［total］［total］，其中total为全网交换机的个数。

2）分别获取源和目的交换机节点的标号src和dst。

3）初始化存放路径的堆栈stack，将src放入stack。

4）调用findRoute（src，dst，relations，stack）方法获取路径。其中，findRoute方法的伪代码为

链路发现子模块完成上述步骤后可获取源、目的交换机节点之间的所有路径，并存放到路由集合R中。链路选择子模块通过Java的IO流技术从配置文件中获取链路的时延和初始可用带宽信息，然后从SFlow控制器获取链路的实时流量信息，从而调用MLSR算法进行最佳路径选择。

MLSR算法综合考虑链路的时延和带宽使用情况来选择代价最小的路径。将源、目的交换机中第i条路径ri的代价定义为

其中，di和bi表示ri所经过链路平均时延和平均可用带宽，其值由式（2）和（3）决定；α为小于1的常量，表示di和bi所占权重，α越大则di在ci中起的作用越大。

其中，dij表示ri中第j段链路lij的时延，而bij表示lij的可用带宽；tij表示lij的初始带宽；uij表示lij的已用带宽，N表示路径中的链路条数。

MLSR算法流程图如图2所示。当新的数据流被发送到控制器后，路由引擎会首先触发路径发现模块，通过该模块获取源和目的交换机之间的所有路径并存放到路由集合中。然后通过路径选择模块根据网络的链路状态信息从路由集合中进行最佳路径的选择。路径选择模块由式（2）和式（3）计算出di和bi，然后再由式（1）计算出路径发现模块中获得的所有路径的代价ci，最后获得其中最小的代价MinCost，进而利用MinCost获取最佳路径，并将此路径告知给流表下发模块。

图2 MLSR算法流程图

3仿真实验及结果分析

本节将通过Floodlight远程控制器［9］和Mininet网络仿真工具［10］对MLSR算法进行仿真测试，并与MHR［5］、RRR［6］、ECMP［7］和DraLCD［8］四种算法进行对比。Mininet是由Stanford大学开发的虚拟化平台，可以在PC机上测试SDN，或者对基于OpenFlow协议进行开发验证，Mininet还提供了可编程的接口，通过编写Python语言脚本，即可实现更为复杂的自定义的网络拓扑结构［10］。

仿真网络拓扑如图3所示，链路初始状态按表1设置。通过ping命令和Iperf技术，对上述5种算法的传输时延和丢包率进行仿真测试，仿真中α= 0.5。针对每种情况分别进行10次随机实验，然后对各次实验结果取平均，所得结果如图4和5所示。

表1 链路的初始状态信息

图3 仿真网络拓扑图

首先，通过ping命令在主机h1上向主机h4发送不同字节大小的数据流来测试不同算法的传输时延，仿真结果如图4所示。

图4 不同算法的传输时延比较

从图4可以看出：随着数据流大小的增大，各个算法的传输时延逐渐增大。其中MHR算法传输时延最大，MLSR算法最小，RRR、ECMP和DraLCD居中，而且DraLCD的传输时延低于其他两种算法。另外，当数据流大小不超过30k字节时，RRR算法、ECMP算法和DraLCD算法的时延表现相当。而当数据流大于30k字节后，RRR和ECMP传输时延大幅度增加。这是由于此时传输路径上开始出现拥塞链路，而RRR和ECMP没有考虑网络链路状态，因此，会导致传输时延的快速增长。与之对应的是，DraLCD和MLSR考虑了链路状态，可以根据实时情况选择最佳路径，因此传输时延增长趋势平稳。另外，与其他四种算法相比，MLSR算法考虑的因素更为全面，因此传输时延始终最小。

其次，通过在主机h1上安装Iperf的客户端，在主机h4上安装Iperf的服务器端，来测量两主机之间不同算法的丢包率，仿真结果如图5所示。

图5 不同算法的丢包率比较

从图5可以看出：数据发送速率在20Mbps以内时，各个算法的丢包率差别不大，但MLSR算法的丢包率更小。当数据发送速率大于20Mbps后，MHR算法的丢包率急剧增加，RRR算法和随机ECMP算法的丢包率也明显增加，DraLCD算法的丢包率有所增加，但是MLSR算法的丢包率变化不明显，仍然低于其他四种算法。主要原因在于：MHR算法选择的路径始终为s1-s4，其带宽与发送速率匹配程度严重失衡，导致链路负荷过重，所以随着发送速率的增加，丢包率越来越大。而RRR算法和ECMP算法所选路径也存在负荷不均衡问题，所以其丢包率也较大。由于MLSR算法实时根据网络的负载情况动态调整路径，可以最大限度地从当前网络中选择最优链路进行数据传输，因此，丢包率最小。

从以上实验结果可以看出：当网络链路负载较低时，五种路由算法表现相当，传输时延和丢包率均较低；但是，随着负载的增加，网络中逐渐出现拥塞，此时由于MLSR算法能根据链路的时延和带宽状态动态调整路径的权值，有利于更合理地选择路径，因此具有更好的性能。

4结语

利用SDN易于获取全网链路状态信息的优点，综合考虑链路的平均时延和平均剩余带宽，提出一种多链路状态路由算法（MLSR），并通过Mininet和Floodlight进行仿真评测。仿真结果表明：MLSR算法可以改善网络的传输时延，具有更低的丢包率。但是MLSR算法只是选择了影响数据传输的诸多因素中最重要的两个因素，在下一步研究中可考虑其他因素的影响，例如交换机中流表的处理能力等，设计更有效的综合路由策略。

［1］Nunes B A A，Mendonca M，Nguyen X N，et al.A survey of software-defined networking：Past，present，and future of programmable networks［J］.IEEE Communications Sur⁃veys&Tutorials，2014，16（3）：1617-1634.

［2］蔡岳平，王昌平.软件定义数据中心网络混合路由机制［J］.通信学报，2016，37（4）：44-52.

CAI Yueping，WANG Cangping.Software defined data center network with hybrid routing［J］.Journal on Commu⁃nications，2016，37（4）：44-52.

［3］张朝昆，崔勇，唐翯祎，等.软件定义网络（SDN）研究进展［J］.软件学报，2015，26（1）：62-81.

ZHANG Chaokun，CUI Yong，TANG Heyi，et al. State-of-the-Art survey on software-defined networking（SDN）［J］.Journalof Software，2015，26（1）：62-81.

［4］左青云，陈鸣，赵广松，等.基于OpenFlow的SDN技术［J］.软件学报，2013，24（5）：1078-1097.

ZUO Qingyun，CHEN Ming，ZHAO Guangsong，et al.Re⁃search on Open Flow-based SDN technologies［J］.Journal of Software，2013，24（5）：1078-1097.

［5］Cormen T H，Leiserson C E，Rivest R L，etal.Introduction to Algorithms.An introduction to element theory［M］.Ed⁃inburgh：Edinburgh University Press，2011：14-24.

［6］魏凯.基于蚁群算法SDN负载均衡的研究［D］.吉林：吉林大学硕士学位论文，2015：32-38.

WEI Kai.The Load Balancing Research of SDN Based on Ant Colony Algorithm［D］.Jilin：Jilin University，2015：32-38.

［7］Ho T V，Yves D，Oliver B，et al.Traffic engineering for multiple spanning tree protocol in large data centers［C］// Proceedings ofthe 2011 23rd International Teletraffic Con⁃gress（ITC），2011：23-30.

［8］杨洋，杨家海，秦董洪.一种新的数据中心多路径路由方案研究［J］.中国科技论文在线，2015，8（16）：1688-1695.http：//www.paper.edu.cn/

YANG Yang，YANG Jiahai，QIN Donghong.A Novelmul⁃tipath routing scheme for Data Center Network［J］.Scien⁃cepaper Online，2015，8（16）：1688-1695.http：//www.pa⁃per.edu.cn/

［9］SONG Haoyu.Protocol-oblivious forwarding：Unleash the power of SDN through a future-proof forwarding plane［C］//Proceedings of the second ACM SIGCOMM work⁃shop on Hot topics in software defined networking.ACM，2013：127-132.

［10］De Oliveira R L S，Schweitzer C M，Shinoda A A，etal. Using mininetfor emulation and prototyping software-de⁃fined networks［C］//IEEE Colombian Conference on Com⁃munications and Computing（COLCOM），IEEE，2014：1-6.

Multiple Link-state Routing Algorithm in Software Defined Networks

LEI Tianying LIN Ziwei HE Rongxi LIU Jiayi
（College of Information Science and Technology，Dalian Maritime University，Dalian 116026）

Based on the feature that Software Defined Networks（SDN）that can easily obtain the link-state information，this paper proposes a Multiple Link-state Routing Algorithm（MLSR），with an integrated consideration of the influence of link delay and available bandwidth.And then the performance ofproposed algorithm is evaluated based on Mininetand Floodlight.The simula⁃tion results show that MLSR has lower transmission delay and packetloss rate than other existing algorithms presented in literature.

software defined network（SDN），link state，floodlight，mininet，routing

TP393

10.3969/j.issn.1672-9722.2017.08.026

2017年2月10日，

2017年3月24日

国家自然科学基金项目（编号：61371091）；大连海事大学“十三五”重点科研项目（编号：3132016318）资助。

雷田颖，男，硕士研究生，研究方向：SDN与数据中心网络的路由策略。林子薇，女，硕士研究生，研究方向：SDN与数据中心网络的路由策略。何荣希，男，博士，教授，研究方向：通信网络及其相关技术。刘家怿，男，研究方向：机器学习/数据分析。