基于软件定义网络的多路径路由选择算法

魏波

（郑州工业应用技术学院信息工程学院,河南郑州451100）

树形结构的以太网交换机构成了传统的分层结构网络,是一种静态体系结构.这种网络虽然在一定程度上可以满足数据交换以及信息传递的需求,但是在面对日益增大的网络规模和人们对高效便捷生活的需求时,其网络架构的可扩展性不足、网络的动态计算性能弱以及可管理性差等缺点便暴露出来,增加了网络优化的难度及网络管理人员的工作量[1].2006 年斯坦福大学的研究团队提出了软件定义网络（SDN）的概念,SDN 是一种新型的网络体系结构,为了实现网络控制器逻辑层面的集中,采用转发层面分离的路由决策,通过解耦控制层与数据传输层,实现控制器决定路由选择,进而实现网络控制的集中化,从而得到简单方便的网络管理,在减少企业运营成本的同时,使得路由技术更加灵活精确[2].本文在传统路由选择算法的基础上,提出基于软件定义网络的多路径路由选择算法,通过定义权重变量,对控制器进行多方面均衡考虑,最终实现多路径路由选择.

1 SDN 简介及分析

1.1 SDN 概念及架构

传统的网络是一种静态、封闭的体系结构,系统的更新发展严重依赖于厂商硬件设备的更新,导致了维护费用高、网络刷新速度慢等问题[3].SDN 是一种新型网络,以OpenFlow 为基础,具有灵活的网络可编程性,能够实现应用与创新网络协议之间的融合,具体讲只要满足可编程化、集中式软件管理以及分开管理的控制转发层就属于软件定义网络[4].而在广义上也在不断对SDN 的定义进行扩充,涉及到软件驱动、软件定义安全等深层次的概念[5].

SDN 架构作为一种新型的网络架构,设计理念主要分为3 层：基础设施层、控制层和应用层.简化的网络设备构成了基础设施层即数据平面；SDN 控制软件构成了控制层可以自动对网络状态进行反应,保证上层控制逻辑的准确性；应用层则由应用APP 构成[6].SDN 架构体系通过将数据转发层和控制层分离,改变了以往控制层和数据层集中的特点,实现了网络编程的集中控制,进而使得网络配置变得更加简单和精确[7].SDN 体系架构如图1 所示.

图1 SDN 架构Fig.1 SDN network architecture

1.2 SDN 关键技术

SDN 关键技术主要涉及OpenFlow 协议、工作机制以及控制层关键技术[8].SDN 是一种新型的网络架构,本身不具有技术实现功能.OpenFlow 是网络标准协议,是一种技术,由ONF 标准化组织进行维护和宣传,主要负责实现控制器和交换机之间的数据交流以及交换机操作,运行在传输控制协议或安全传输协议连接之上,通过定义控制器对交换机的管理方式以及消息格式和类型来实现交换机转发层的功能.SDN 的工作机制主要有流量统计机制、数据流处理机制以及网络拓扑学习机制,通过不同的机制实现网络资源的合理配置,进而为网络带宽优化提供数据支撑,实现网络服务质量的提升.SDN 的控制层技术主要由两部分组成：（1）SDN 控制器及北向接口技术.控制器作为软件定义网络的计算单位,提供对路由进行计算以及对网络交换设备进行管理、网络状态监测来实现其功能；南向接口技术实现了对网络设备的标准化对接,北向接口技术在提供标准化管理接口的同时提供了可扩展服务接口,对资源进行统一调度进而实现网络系统的灵活性、开放性和便利性.（2）网络虚拟化及多控制器架构.网络虚拟化作为云计算和数据中心技术焦点,满足了流量隔离、多租户以及网络自由控制进而实现多用户数据共享等需求；多控制器架构可以减少控制器与交换机之间的通信延时,减轻单个控制器的负载,进而提高网络服务质量[9].

1.3 软件定义网络路由管理技术

由于传统的网络是一种静态、封闭的体系结构, 因此路由的选择只考虑了数据包的交换和网络拓扑,但是这种方法收敛速度慢、程序复杂,不能灵活适应数据的变化[10].SDN 路由管理技术,根据流量实时性和安全性需求提出一种多路径路由优化模型,进而减少网络拥塞实现多路径优化机制,路由选择方案主要有基于SDN 的多径路由选择、基于SDN 的通用路由选择以及基于SDN 的分段路由选择[11].

2 路由选择策略

路由规则管理主要有数据层面的路由规则放置以及更新和控制层面的数据传递.SDN 路由选择策略主要是利用中间节点以及节点与节点之间的链路, 在网络体系结构中选择一条最优的目的节点和源节点之间的路径,进而提高数据传输效率和负载均衡[12].常用的基于SDN 的路由选择策略主要有基于负载均衡、基于交换等级、基于权重的路由选择算法.SDN 路由选择算法分类如图2 所示.

图2 SDN 路由选择算法分类Fig.2 Classification of SDN routing algorithms

2.1 基于SDN 的路由选择

基于Qos 指标的路由选择算法,通过感知Qos 指标为不同优先级用户和应用进行分流和路径选择,对最大化链路的剩余宽带进行建模得到目标函数进而实现最优路径选择,Qos 指标主要包括网络吞吐量、误码率和传输时延等.基于负载均衡的路由选择算法则是通过目的节点和源节点之间路径,找到空闲链路然后将网络数据分配到上面,进而实现链路的优化,提高网络利用效率,实现负载均衡.基于权重的路由选择算法将路由和调度结合起来,以时延和链路带宽作为选择权重参数,建立模型将路由选择转化为求解最优化问题,降低系统复杂的同时减少流量延迟.

2.2 路径选择机制

网络系统结构的优化受多方面因素制约,为了使得节点配合网络进行数据传输,保障数据交换以及通信的实时性和有效性,进而满足不同服务对系统的需求,需要对路径选择机制参数、性能和安全进行综合考虑,从而保证路径选择的最优化,进而实现数据交换时链路能够满足需求.路径选择机制主要由3个方面构成：

（1）网络性能参数.主要包括吞吐量和丢包率,吞吐量的数学定义为单位时间内在网络链路（i,j）上通过的数据量Tij即为此链路的吞吐量,单位时间为秒.丢包率则为数据传输过程中由于内在或外在因素的影响造成的数据损失,丢包率的范围为[0,1].

（2）网络安全参数.为了保证数据传输的安全性,需要考虑网络体系架构的可靠性,而可靠性主要通过Switch 转换次数、路径通过次数来决定.

（3）路径的评价与选择.在对源节点和目标节点进行路径选择时,需要考虑系统的多个约束条件并对链路进行评价,因此需要建立多路径路由问题优化模型,进而对优化问题进行求解,得到路径选择机制.

3 基于SDN 的多路径路由选择算法

3.1 基于多路径路由选择模型

基于SDN 的多路径路由选择,应通过对节点流量进行描述,同时需要考虑链路容量对网络吞吐量的限制以及节点容量有限,进而选择最优路径.节点流量的数学定义为：源节点和目标节点路径上任一节点（s,d）,流出该节点和流入该节点的数据量相等,即

式（1）中：s 为源节点,d 为路径节点,u、v 为节点集合,E 为节点间的连接,D 为源节点到目标节点的所需流量的集.则代表经过链路（u、v）从源节点s 达到目的节点d 的流量.链路容量是多路径选择的另一个重要因素,在链路（u、v）上链路容量能够承受通过的最大值数学公式表示为

式（2）中：Cuv为链路容量能够承受的最大值.

3.2 基于SDN 的多路径路由选择算法

在已知网络架构模型上建立基于SDN 的多路径路由选择算法,通过对传统路由优化算法进行梳理和优化,进而实现多路径路由选择,算法流程如图3 所示.具体算法步骤为：

（1）对整个网络架构,计算源节点和目标节点路径上任一节点（s,d）可能产生的路径,以及每一条路径的流量,同时需要考虑流出该节点和流入该节点的数据量相等即链路容量对网络的限制,保存所有数据,路径数量和路径上的流量在约束条件下取最大值；

（2）逐个的对每条路径上的所有节点进行验证,以检验是否在流表容量范围内,只有当一条链路上的所有节点都满足条件时（目标节点和源节点不在验证范围）,才说明此链路具有路由选择性；

（3）通过步骤（2）选择到满足所有限制条件合适的路径,并对不符合条件的路径进行重新规划计算看是否可以规划到其他路径,如果经过规划仍不能满足系统的所有条件,则说明该路径是不可行的,最终得到路由选择的多条路径目标值.

图3 基于SDN 多路径路由选择算法流程Fig.3 Multi-path routing algorithm flow based on SDN

3.3 仿真实验

为了测试算法的有效性需要通过模拟环境来实现,实验采用的硬件环境为：主计算机16 G 内存,CPU 3.2 G 内存.利用Mininet 网络仿真器为仿真平台创建虚拟拓扑网络模型,Mininet 可以方便地创建一个支持SDN 的网络,同时设置实验网络拓扑结构：20 个源节点,2 000 个节点,链路容量根据实验环境进行设置,实验参数见表1.

表1 实验参数配置Tab.1 Experimental parameter configuration

为了验证本文算法的有效性, 将基于SDN 的多路径路由选择算法和最优解Optimal 算法以及SPR算法在不同缓存容量下运行速度进行比较,具体见表2.

表2 不同缓存容量（S）下算法的运行速度Tab.2 Algorithm speed under different cache sizes

由表2 可知,在不同缓存容量下,基于SDN 的多路径路由选择算法的运行速度明显优于其他算法,运行时间虽然包含了仿真器本身的运行开销,但算法仍具有优势,同时解决了多路径路由选择策略以及网络链路的拥堵,节省了运行时间,从而能够保证整体网络架构的总体时延在可接受范围内.

4 小结

本文针对SDN 网络架构分别从定义、关键技术以及路径选择机制进行了分析,同时介绍了SDN 路由选择算法分类.由于控制器可以对全局信息进行分析,进而能够为多路径路由选择作出判断,因此对SDN 中关键技术控制器进行了着重介绍.在建立多路径路由选择模型的基础上提出了基于SDN 的多路径路由选择算法,并通过实验仿真验证了算法的运行速度和有效性,具有一定的应用价值.如何对网络中的延迟情况进行优化,并且在减少丢包率的同时提高网络运行效率及准确性是下一步研究的重点.