基于Ryu的SDN网络动态路由算法实现*

傅妍芳，李敬伟，马 静，赵世峰，田鹏辉

(西安工业大学 计算机科学与工程学院，西安 710021)

传统网络中，不容易对各交换设备的集中管理和配置，需要分别对其进行手动配置；对虚拟网络的管理应用不多，需要专门的虚拟网络管理系统；传统网络设备控制与数据平面的耦合，很难做到全局的网络拓扑的显示来实现监控功能；不同的厂商提供的网络设备都是闭源的，不同的设备需要不同的API来进行网络应用开发，不利于网络应用的创新.

SDN是对传统网络架构的重构[1]，从分布式网络架构转向集中式控制网络架构，将传统的各交换设备的控制层面[2]抽取出来，作为控制中枢来管理和控制各交换设备，与数据转发层面分离[3]；其网络配置也解决了传统的分布式框架，采用集中式的管理方式，对SDN设备进行统一管理和灵活部署[4]，并且可以对全网的拓扑进行监控，实现全局链路的显示，其控制层面可根据需要进行链路选择，如采用动态路由的方法对链路进行路径选择[5].

基于此，为了底层网络能更好的为上层业务和应用服务，使网络资源做到灵活调度，文中拟应用SDN架构，把协议的实现从硬件层剥离出来，把硬件用统一的模型描述，模型之外的部分变成控制器和流表，通过控制器和流表来实现各种网络协议.

1 SDN相关技术

作为SDN框架中的核心，SDN控制器获得下层的全局网络拓扑，做出控制报文的转发决策，可以解决在传统网络中路由不可控的问题.当需要调整网络行为时，不再需要修改网络设备本身，而是调整SDN控制器内部的软件.目前主流的SDN控制器采用的路由算法为Dijkstra算法，该算法只能计算出源节点和目的节点之间的最短路径.

Ryu控制器就作为一种基于组件的软件定义网络框架，提供了定义好的API使开发者更易创建新的网络管理和应用控制[6].Ryu支持不同的协议管理网络设备，如：OpenFlow、Netconf、OF-config等，且支持OpenFlow1.0到OpenFlow1.5.

mininet是一些虚拟的终端节点、交换机、路由器连接而成的网络仿真器，其基于Linux Container架构，采用轻量级的虚拟化技术，使得系统可以和真实网络媲美[7].利用mininet创建支持自定义的网络拓扑，缩短开发测试周期；支持OpenFlow、Open vSwitch等软件定义的网络组件[2，8]，在mininet上运行的代码可以无缝移植到支持OpenFlow的硬件设备；支持系统级的还原测试、支持复杂拓扑、自定义拓扑等.文献[9]对传统网络与SDN网络架构做了阐述(如图1所示)，SDN是把不同协议间的分布式系统集成到了网络操作系统中，各路由算法成为了另一种形态——APP.

图1 传统网络与新型SDN的架构变更

在Ryu控制器的架构中可以更加清晰的看到SDN的架构应用，整体结构如图2所示.

图2 Ryu控制器框架的层次结构

1.1 传统路由技术

在OSI模型中，网络数据传输主要在数据链路层和网络层.数据链路层主要负责数据帧的传输，网络层主要负责数据包在发送端和接收端的传输.路径选择、路由以及逻辑寻址也都是在网络层中实现.选路问题存在于网络的各个层之中，网络层中的路由选择和路由计算采用IP地址协议，其步骤如下：

① 当数据分组进入交换设备时，对分组的目的地址进行选路，确定下一跳的节点地址；

② 利用ARP确定下一跳节点物理地址；

③ 将数据分组封装在物理帧中，利用底层物理网络节点发送到下一跳节点.

当一个网络设备把数据包发给路由器时，路由器对收到的数据包进行解析，提取出目的地址，接下来路由器根据ARP协议确定下一跳的物理设备，路由器再把数据包转发出去，可以将数据包转发到最终的设备中.IP网络的路由是先选择路径，然后通过网络传输，每个设备只知道下一跳的地址，这样依次进行转发就可以到达目的地址.

1.2 SDN路由技术

与传统网络相比较，SDN网络中，SDN控制器集中拥有全局视图的网络拓扑[8].控制器通过链路层发现协议，获得网络设备的基本信息(包括网络拓扑和网络资源，网络资源包括节点连接关系，带宽、跳数、时延、误码率等信息)，形成网络拓扑视图和资源视图.基于网络拓扑，结合Dijkstra算法，并对其优化，找出网络中源节点到目的节点的最短路由.

传统网络中的路由只能实现基本的路由功能，不考虑整个网络中的流量分布情况，很容易造成局部链路的路由阻塞.而SDN控制器可以根据网络拓扑与网络资源进行路由的调度，选出最佳路径而不一定是最短路径.

2 路由算法设计

2.1 静态路由

静态路由的链路选择不是根据算法得到的，是网络管理员根据链路的实际需求，对各个网络设备进行手动配置得出，在规模比较小的网络中，可以满足应用，当网络规模较大，网络拓扑较复杂，且网络变化较频繁时，对网络的配置就显得不够灵活，非常低效.在SDN控制器中，可以显示他所控制和管理的域内全局的网络视图，而且Ryu控制器作为集中的控制层面，管理员只需在控制器中对各节点进行统一流表下发，使各OpenFlow交换设备根据流表项的规则进行数据转发，完成静态路由的功能.SDN网络中的交换机不再解析任何协议，只做流表匹配和转发，其控制方式采用集中式，所有协议解析都需在控制器内完成，流表下发也是统一从控制器下发.

在Ryu控制器中，将对各OpenFlow交换设备的MAC地址和输入输出端口进行规则定制，按照OpenFlow协议对各字段进行定义和封装，通过Ryu流表下发函数对各OpenFlow交换设备进行流表下发，从而完成链路的整个静态路由.

2.2 基于跳数的动态路由算法

基于SDN架构的静态路由可以集中的对各支持OpenFlow的交换设备进行表项下发，对于链路的状态也能做到更好的监测.但是，基于SDN的静态路由配置也存在一些缺陷，例如：需要预先对网络的状态进行获取，同时，对各交换设备的各个参数都要记录到控制器中，且以上过程都需要人工参与记录和流表项的规则制定，特别是当网络拓扑发生变化时，还需要对流表项进行更新，以适应新拓扑可以正常通信.

如果以上过程完全由程序来实现，如：对链路的自动发现，对网络状态的自动感知，对链路的自动选择，对各交换设备进行自动的流表下发，那么可以用动态的方式来完成以上过程.重点是对网络中进行动态的路径选择，利用Dijkstra算法[10]完成.结合Ryu控制器中的链路发现，对控制层面的可编程性，完成对链路的自动选择和对OpenFlow交换设备流表的自动下发[5].

Dijkstra采用贪心算法的原理，主要解决源节点到目的节点之间的最短路径问题，它的主要特点是每次迭代找到的点，除了已经找到的点之外离源点最近的点.Dijkstra算法思想如下：

一个有向图可以用G=(V,E)表示，V表示图中所有点的集合，E表示图中所有边的集合.V中点可以分成两组，一组用S表示，另一组用U表示.S中所包含的点是已经存在于已求最短路径中的点，开始时，S中只包含源点，之后每求出一条最短路径，就把其上的点加入S中，直到图中的所有点都包含在S中，算法结束.U中包含的点是尚在已求最短上出现的点，根据最短路径的长度，可以把U中的点依次加入到S中.在此过程中，必须保持源点到S中点的距离不大于源点到U中点的距离，另外，每个点都对应一个路径长度，S中点所对应的路径长度为该点到源点的最短路径长度，U中点所对应的距离，是该点到源点且路径只包含S中的点的路径长度.

在Ryu控制器中，通过链路发现协议来获取整个网络拓扑中的节点，包括各交换设备本身以及其对应的出入端口信息，将其存储到控制器中的MAC地址转发表中记录下来；根据动态路由算法，计算出源与目的主机之间经过的网络节点，并选择出源与目的之间的最短路径；将计算得到的路径经过的节点信息安装到各个节点的流表中，从而完成Ryu控制器中对动态路由的实现[11].

2.3 提高网络资源利用率的动态路由

在SDN网络中，基于跳数而实现的最短路径选择，在实际使用中远远不够，没有考虑到链路的实际资源情况，例如：各个链路的带宽、时延、丢包率等业务属性.

在Ryu控制器内部，利用网络特性和SDN控制器可以全局信息获取以及整体决策各交换节点的特点，开发感知网络资源的功能特性，获取到各个链路的实际带宽、时延、丢包率等属性，根据这些属性，将其设置为混合的权重机制，根据用户需求，进行权重优先切换，也可根据算法，将获取到的属性根据实际情况进行拟合，生成一个多权重融合的算法，一是为了使动态路由计算更加实际可用，二是为了提高网络资源的利用率.

3 最短路径转发实现

Ryu控制器与SDN交换机进行信息交换为：Hello握手信息，建立网络连接，保持链接状态；同时，Controller会向Switches发送状态请求，包括支持的OpenFlow版本，支持的Features等信息.

通过bserve-links指令自动下发LLDP，开启拓扑发现功能，Ryu控制器内部接收到链路发现事件后，触发控制器的事件处理模块进行交换设备、主机以及链路连接的信息获取.SDN控制器与SDN交换机的具体通信过程见表1.

表1 SDN控制器与SDN交换机信息交换

Tab.1 Information exchange between the SDN controller and the SDN switch

消 息类 型描 述HelloController→SwitchTCP握手,控制器请求交换机版本号HelloSwitch→Controller交换机回复它支持的版本Feature RequestController→Switch控制器询问可用端口SetConfigController→Switch控制器让交换机发送超时消息Feature ReplySwitch→Controller交换机回复端口速度、支持的表和行动

默认情况下，SDN控制器会对交换机下发table-miss流表，当交换设备的信息进入Controller时，及触发Packet-in事件供Ryu控制器进行处理.结合Dijkstra算法进行路径选择，其步骤如下：

① Ryu控制器获取整个网络的拓扑；

② 解析到网络拓扑中所有的交换机和端口信息，存储到邻接矩阵的字典中；

③ handler事件处理器处理接收到的Packet-in事件，进行MAC地址学习和端口映射存储；

④ 根据存储在mac地址表中信息进行链路计算，执行Dijkstra路由算法并选择出最短路径；

⑤ 对计算到的路径解析出其下一跳的交换机和出入端口信息；

⑥ 对各交换设备进行流表下发，使整个拓扑的所有数据平面按照计算结果进行数据包的正常转发.

在上述过程中，动态路由Dijkstra只是基于跳数计算出了最短路径，并没有考虑到实际的链路状态以及链路属性等信息.对此，增加了对链路的感知功能，通过感知Ryu控制器来获得链路的带宽、延迟、丢包率等链路属性，根据获得的链路属性来为其分配权重，将各种权重进行拟合，在路由算法中将权重加入到最短路径选择的邻接矩阵中，从而用户可以根据实际情况来切换权重，进而实现满足用户需求，同时又能提高网络利用率的网络路径选择.拓展的实现过程为：

① 获取拓扑信息之后进行链路感知；

② 获取链路的带宽、延迟、丢包率等属性；

③ 对获取的链路属性进行权重赋值；

④ 与MAC地址表中的源、目的交换设备进行参数传递；

⑤ 将链路属性参数作为Dijkstra的权重参数参与路径选择；

⑥ 根据最短路径结果绑定所有输入输出端口；

⑦ 匹配路径并为每个交换机下发流表.

4 实验仿真

实验采用All-in-one结构，将Ryu控制器、mininet安装在同一台虚拟主机里，其中Ryu负责对Openv Switch进行管理和控制，mininet负责对网络的仿真，模拟出虚拟交换设备与虚拟主机.针对OpenFlow交换机加入动态路由功能，其网络拓扑如图3所示.

图3 网络拓扑测试图

由图3可知，从h1到h2可以经过两条路径，分别是：h1→s1→s2→s4→h2；h1→s1→s3→s4→h2.链路发现程序执行之后，学习设备的端口和经过的链路.执行程序之后，得到如图4所示的详细端口信息.

图4 获取到链路后的详细信息

执行网络链路感知程序，图4中加入了h11、h22两个虚拟主机，目的是为了在程序中对各链路完成对带宽、延迟和丢包率等属性的获取.获取到信息后，根据用户需求对参数赋予权重，将其加入链路的动态路由算法，从而实现优化后的动态路由功能.

4.1 执行mininet网络仿真环境

为了控制SDN交换机，OpenFlow交换机采用Open vSwitch，执行环境采用mininet.通过自定义网络拓扑完成拓扑搭建，其中链路带宽、延迟、丢包率由Linux TC内核流量控制工具来模拟.脚本如图5所示.

图5 mininet网络拓扑仿真

由图5可知，通过mininet拓扑自定义脚本生成四个虚拟交换机，四个虚拟主机.四个主机分别与四个虚拟交换机相连，同时在mininet脚本中引入流量控制工具，对各链路的参数进行指定：带宽、丢包率以及延迟，以此来模拟实际网络环境中的情况.

4.2 执行Ryu应用

基于OVS的mininet仿真环境与Ryu控制器连接之后，控制器会自动进行链路发现和MAC地址学习等功能，从而控制器中会有虚拟交换机的全局拓扑，自动对链路中各网络节点进行获取，计算出各节点的出入端口，执行动态路由选择函数，计算出邻接的交换机信息，和从源到目的基于跳数的所有路径，而同时结合获取到的网络链路属性，对权重较低的链路进行剪枝，得出优化后的最短路径.SDN控制器对各交换机根据路由算法计算出的结果进行流表下发.

执行成功后，对h1到h4主机之间进行ping测试，然后对各交换机进行流表查看，结果如图6所示.

图6 各交换机的流表项查看结果

4.3 链路连通测试

通过OVS指令，对mininet仿真出的虚拟交换机进行流表查看，图6中可以看到，数据从s1的1端口进入，2端口流出，从s2的1端口进入，2端口流出，从s4的1端口进入，3端口流出，此时的路径为h1→s1→s2→s4→h2，而端口从交换机的流入流出情况为s1(1,2)→s2(1,2)→s4(1,3),验证输出结果如图7所示.

图7 路由学习后的链路验证结果

从图7可知，学习所有交换机MAC地址与端口后，需对源主机与目的主机进行ping测试，测试结果表明，Ryu控制器完成了所有交换机和端口信息以及链路信息的发现.根据Dijkstra算法计算出所经过的数据传输路径，结合对链路属性的获取，在算法中增赋予链路权重，从而对不满足需求链路进行剪枝，实现了动态路由的路径计算，而ping测试也验证了从源到目的主机之间的链路连通.

5 结 论

文中通过Ryu控制器、mininet网络仿真工具对SDN网络架构以及网络动态路由进行研究，通过SDN控制器收集到整个网络的拓扑和资源，形成拓扑视图和资源视图，实现了对OpenFlow交换机的管控功能.基于Ryu控制器分析和设计了静态路由算法，通过控制器对各个交换设备进行统一静态路由进行配置，分析了存在的缺陷；在SDN架构中引入基于跳数的动态路由方法，根据SDN全局获取到的拓扑信息，将网络节点以及交换设备的端口映射信息保存汇总，根据Dijkstra算法算出基于跳数的最短路径；增加链路感知功能，获取到网络链路的带宽、延迟、丢包率等属性，将其加入动态路由算法，并通过mininet对网络节点进行仿真.仿真结果表明，结合Ryu控制器内部应用来对Ryu控制器应用的开发可以实现动态路由选择功能，并完成了自动的流表规则下发.SDN架构中应用层面对网络协议等功能的设计方法具有可行性，并且SDN控制器能够根据优化的路由算法实现对虚拟网络设备进行集中的管理和自动化配置.

参考文献：

[1] 张卫峰.深度解析SDN—— 利益、战略、技术、实践 [M].北京:电子工业出版社,2014.

ZHANG Weifeng.In-depth Analysis of SDN—Benefits,Strategy,Technology,Practice [M].Beijing:Electronic Industry Press,2014.(in Chinese)

[2] 左青云,陈鸣,赵广松,等.基于OpenFlow的SDN技术研究[J].软件学报,2013(5):1078.

ZUO Qingyun,CHEN Ming,ZHAO Guangsong.Research on SDN Technology Based on OpenFlow[J].Journal of Software,2013(5):1078.(in Chinese)

[3] 张顺淼,邹复民.软件定义网络研究综述[J].计算机应用研究,2013,30(8):2246.

ZHANG Shunmiao,ZOU Fumin.A Review of Software Defined Network.Application Research of Computers[J].2013,30(8):2246.(in Chinese)

[4] 李朝辉.SDN路由算法设计与实现[D].北京：北京邮电大学,2016.

LI Chaohui.Design and Implement of SDN Routing Algorithm[D].Beijing:Beijing University of Post and Telecommunication,2016.(in Chinese)

[5] 李勇，刘学军.基于OpenFlow的SDN网络中路由机制研究[J].移动通信,2015(7):51.

LI Yong,LIU Xuejun.Research on Routing Mechanism in SDN Network Based on OpenFlow[J].Mobile Communication,2015(7):51.(in Chinese)

[6] RYU SDN Framework [EB/OL].[2017-10-05].http://osrg.github.io/ryu/.

[7] Mininet Team[EB/OL].[2018-01-01].http://Mininet.org/.

[8] A Linux Foundation Collaborative Project.Open vSwitch[EB/OL].[2018-01-01].http://www.openswitch.net /.

[9] MCKEOWN N,ANDERSON T,BALAKRISHNAN H,et al.OpenFlow:Enabling Innovation in Campus Networks[J].Acm Sigcomm Computer Communication Review,2008,38(2):69.

[10] 王树西,李安渝.Dijkstra算法中的多邻接点与多条最短路径问题[J].计算机科学,2014,41(6):217.

WANG Shuxi,LI Anyu.Multiple Adjacency Points and Multiple Shortest Paths in Dijkstra’s Algorithm[J].Computer Science,2014,41(6):217.

(in Chinese)

[11] YU Y S,KE C H.Genetic Algorithm Based Routing Method for Enhanced Video Delivery over Software Defined Networks[J].International Journal of Communication Systems,2018,31(1):e3391.