SDN路由器全配置下的网络流量工程仿真优化分析

吴菁晶，尹嘉麒

（1.东北大学 计算机科学与工程学院，辽宁 沈阳 110819；2.中北大学 电气与控制工程学院，山西 太原 030051）

0 引 言

随着网络业务多媒体化、物联网化的发展，网络中新业务需求量迅速增长[1]。但是，目前网络提供的流量并不足以应对这种增长，需要更好的路由方式对网络中的新业务进行更有效的规划。当前，网络中普遍使用两种常见的路由协议，内部网关协议（Interior Gateway Protocol, IGP）和多协议标签交换（Multi-Protocol Label Switching, MPLS）[2]。IGP协议在建立路由转发表时是由计算最短路径方式来建立的。因此，这样的路由方式对网络链路带宽和业务本身的特点并不关心，前者会造成链路拥塞，后者则不能满足业务的服务质量需求。MPLS协议在一定程度上能够随网络情况动态调整，但是该协议算法复杂度较高，路由器之间需要频繁的交互信息。在业务量较多的情况下，需要存储大量的网络状态信息和路由信息，而且这些信息都需要人工配置，因此配置过程十分繁琐而且配置成本高[3]。综上所述，目前这两种主要的路由协议，即IGP协议和MPLS协议都不能很好地适应目前的情况，因此急需设计一种成本低，并且能够随网络变化动态调整，同时避免网络拥塞的流量工程技术以解决上面提到的问题。

近年来，为了解决传统网络不能灵活操控网络流量的问题，软件定义网络（Software Defined Network, SDN）的网络架构被提出[4-6]。SDN技术可通过软件编程的形式定义和控制网络，形成独立的控制层，掌握全局网络信息，方便对业务转发路径进行集中计算，这样路由器只需要根据控制平面配置的路由表对数据进行转发，就可以大大降低链路堵塞的概率，提高数据包转发效率[7-8]。通过上述分析，SDN使得网络在垂直方向上变得开放化、标准化、可编程化，能够很好地解决当前网络面临的流量控制僵化问题。

1 问题描述

设在网络中所有路由器都是SDN路由器，并且网络中只有一个集中的SDN控制器。将网络抽象为一个有向图G（N，E），N代表网络中的路由器集合，E代表网络中的链路集合。假定流量矩阵对SDN控制中心来说是已知的，根据这些已知的流量信息，SDN控制器为每个业务计算转发路径，使得当前网络获得最好的性能指标，最优的流量工程优化效果。源节点s和目的节点d之间的业务矩阵用fsd来表示。

变量定义如下：

e：表示网络中的链路；

map(e)：表示链路e上的权重；

c(e)：表示链路e上的链路容量；

fsd：表示输入业务矩阵；

u(e)：表示链路e上的利用率；

INi：表示注入点i的数据流；

OUTi：表示流出点i的数据流；

x(P)：表示一条路径P上的流量大小；

W(P)：表示路径权重；

Pi：表示从s到d的路径集合。

约束条件的具体描述如下：

约束条件为：

式（1）表示优化目标为最小化网络中的链路最大利用率。式（2）表示整个网络中的流量需要守恒，即节点发出的总流量等于节点接收的总流量。式（3）表示链路利用率与链路容量和链路负载的关系。式（4）表示输入业务流不能为负数。式（5）表示单个节点的流量守恒。当一个节点既不是目的节点也不是源节点时，它的输入流量等于输出流量；当该节点是源节点时，它的输出流量减去输入流量等于该节点发出的流量；当该节点是目的节点时，它的输出流量减去输入流量等于该节点的接收流量。

2 基于贪婪算法的模型求解

贪婪算法（Greedy Algorithm, GA）是一种快速求解问题较优解的方法。贪婪算法的特点是一步一步进行问题求解，以某个因素评价当前解，寻找当前阶段的最优解，它通常以当前情况为基础根据某个优化标准做出最优选择，将所求问题简化成规模更小的子问题，省去了为寻找最优解而枚举所有可能情况所消耗的大量时间。这个最小化网络链路利用率问题可以转化为最小化数据传输代价问题。可以把链路权重定为传输当前数据流后链路的利用率即：

式中，f表示当前需要路由的数据流大小，由此可以看出，在寻路过程中选择权重较小的路径就能够达到减小网络中最大链路利用率的目的。

模型可以转化为：

约束条件为：

式（7）表示需要最小化网络的最大链路利用率。式（8）表示数据流选择的路径是源节点与目的节点之间权重最小的一条路径，其中Pi代表源节点和目的节点间所有存在路径。

式（9）是对链路上数据流大小的约束。式（10）表示路径上业务流为非负。

2.1 全SDN配置下的单跳转发算法

关于SDN单跳模式本节做如下假设：

（1）SDN控制中心能够正确并及时感知网络中的相关信息。

（2）网络中所有路由器均为SDN路由器。

（3）网络只有一个控制中心。

（4）同一个数据流在一个SDN路由器中只能在同一个转发口进行转发。

算法主要分为两部分，其一是配置链路权重，其二是择路。每个业务在转发之前都需要配置链路权重，所有链路的初始权重均为1，由链路权重公式（6）可知，链路权重随着业务转发过程的进行在不断改变。在择路部分，采用基于贪婪算法的Dijkstra算法，选择权重系数最小的路径。

2.2 全SDN配置下的多跳全传算法

在移动化、物联网和多媒体化的趋势下，网络流量增长迅速，业务类型也越来越多样化。前文介绍了SDN不同业务类型对于服务质量要求的不同。有些业务对丢包的容忍度很低，例如，交互类业务；有些业务允许少量数据包被重传或丢弃，例如语音、视频业务等。因此，根据业务类型的不同设计了不同的SDN转发算法。

本小节介绍的是适合对丢包容忍度很低的业务的全SDN配置下的多跳全传算法，关于此算法本节做如下假设：

（1）SDN控制中心能够正确并及时感知网络相关信息。

（2）网络中所有路由器均为SDN路由器。

（3）网络只有一个控制中心。

（4）同一个数据流在网络中能够在不同路径上转发。

（5）所有业务在网络中都必须传输。

情况一：路径P上所有链路均未饱和；分别计算路径P上所有链路的剩余容量，根据“木桶短板原理”，路径P的容量即路径P中剩余容量最小链路的剩余容量，记为F(P)。

若F(P)小于fsd，则在该路径上传输大小为F(P)的数据流，fsd=fsd-F(P)，进入下一次迭代；若F(P)大于fsd，则fsd全在该路径上传输。

情况二：若路径P上有过载链路，剩余容量全部都在链路P上传输。

2.3 全SDN配置下的多跳丢弃算法

本算法考虑的是适合允许数据包被稍后转发或丢弃的业务的全SDN配置下的多跳丢弃算法，该算法首要考虑网络中的链路不能过载，网络一直处于畅通状态。当转发该业务会造成链路拥堵时SDN控制中心将搁置该业务，稍后转发或丢弃。

全SDN配置下的多跳丢弃算法适用于允许部分数据流被搁置或丢弃的业务，做如下假设：

（1）SDN控制中心能够正确并及时感知网络相关信息。

（2）网络中所有路由器均为SDN路由器。

（3）网络只有一个控制中心。

马铃薯早疫病的症状通常在植株处于逆境时期易发生，而这些逆境经常来自于缺肥（如缺氮及其他营养）、气温偏高、植株缺水、生长衰弱。

（4）同一个数据流在网络中能够在不同的路径上转发。

（5）网络中所有链路都不得超载。

根据公式（6）配置每条链路权重，借助Dijkstra算法计算权重最小的路径P，找到的路径P有两种情况：

情况一：路径P上所有链路均未饱和；分别计算路径P上所有链路的剩余容量，根据“木桶短板原理”，路径P的容量即路径P中剩余容量最小链路的剩余容量，记为F(P)。

若F(P)小于fsd，则在该路径上传输大小为F(P)的数据流，fsd=fsd-F(P)，进入下一次迭代；若F(P)大于fsd，则fsd全在该路径上传输。

情况二：若路径P上有过载链路，表示如果传输该业务会造成网络链路的拥堵。将该业务完全丢弃，网络链路状态恢复到上一个业务传输完成状态。

丢弃算法与全传算法的主要区别就在于发现传输当前业务会造成链路拥堵时将当前业务搁置或丢弃，直接传输下一个业务。

3 仿真结果对比与分析

为验证算法性能，本章在不同条件下对OSPF（Open Shortest Path Firs, OSPF）算法、全SDN单跳算法、全SDN多跳不丢弃算法进行了比较。

从图1可以看出，在业务矩阵较小，业务大小远小于链路容量，路由完成所有业务矩阵后未出现链路过载的情况下，SDN单跳模式与SDN多跳模式优化效果相同且远优于OSPF转发模式。这说明，在业务矩阵较小时SDN单跳模式与SDN多跳模式均可行。接下来讨论业务矩阵较大的情况下，哪种转发模式优化效果更好。

图1 小业务矩阵下三种方案最大链路利用率对比

从图2可看出，在业务矩阵较大时，SDN单跳与多跳模式均远远优于OSPF转发模式。且SDN单跳模式的表现差于SDN多跳模式，可以假设SDN多跳转发模式更适合业务矩阵较大的情况，为验证假设的正确性制定了3个指标比较SDN单跳与多跳模式。这3个指标分别是：链路最大利用率、网络中过载链路数、经过拥堵链路的业务数目。下面用另外的指标对2种SDN转发模式的仿真结果进行评价。

图2 大业务矩阵下三种方案链路最大利用率

图3中参数全SDN单跳方式链路最大利用率、全SDN多跳方式链路最大利用率使用的是右侧y轴；参数全SDN单跳方式过载链路数、全SDN多跳方式的过载链路数目使用的是左侧y轴。图4中参数全SDN单跳方式链路最大利用率、全SDN多跳方式链路最大利用率使用的是右侧y轴；参数全SDN单跳方式经过拥堵链路的业务数、全SDN多跳方式经过拥堵链路的业务数目使用的是左侧y轴。

图3 大业务矩阵SDN单跳与多跳模式下过载链路

图4 大业务矩阵SDN单跳与多跳模式下拥堵业务数

4 结 语

通过仿真分析将传统算法、单跳SDN转发算法和多跳SDN转发算法进行了比较，对比了这些路由策略后指出了它们各自的优缺点和适用情况。