傅妍芳，宋新美，张赵晨子，苏一昶

(1. 西安工业大学计算机科学与工程学院，陕西西安710021；2. 中国工商银行，陕西西安710021)

1 引言

网络是一种将控制层与数据转发平面分离的网络架构，其提供的可直接编程等特性为网络控制管理技术带来了革命性的改进。目前，SDN技术正在被广大科研、生产工作者广泛研究，并应用在数据中心、广域网等场景。然而构建一个完整的SDN网络至少需要控制器、OpenFlow 交换机、终端结点等设备，超出了大部分研究工作者具备的实验条件。为此，OpenNet、NS3、Mininet等仿真软件便应运而生，其中以Mininet最为流行。

Mininet 是由虚拟主机(Host)、交换机(Switch)、控制器(Controller)、链路(Link)组成的开源系统，其采用轻量级的虚拟技术，搭建的虚拟网络可以移植到真实网络中。Mininet 可以简单创建支持SDN的网络，其主要特性包括：①支持多个用户在同一个拓扑上进行并发操作；②方便可重复和可封装的回归测试；③无需物理网络；④提供用于网络测试的 CLI；⑤提供python API；⑥支持所有拓扑。总之，Mininet因其高灵活性、高可用性、可扩展性、可共享等优点目前被广泛使用。

基于Mininet仿真网络，本文主要关注网络QoS保障技术。针对在线直播、视频会议等多类型业务的QoS 保障需求，传统网络在早期提供的BE(Best Effort，尽力而为)服务之上提出了区分服务(DiffServ)模型，但受限于紧耦合的网络架构，DiffServ模型在传统网络中的实现不能快速适应网络状态并做出实时决策，因此无法严格保障端到端QoS。网络地址转换(Network Address Translation，NAT)、边界网关协议(Border Gateway Protocol，BGP)[1]、开放式最短路径优先(Open Shortest Path First，OSPF)[2]等协议功能也是为提高网络传输QoS而实施的保障措施，但它们在传统网络中的配置不灵活，功能迭代速度受限，因此依然存在业务QoS不能得到有效保障的问题。鉴于此，软件定义网络(Software-Defined Networking，SDN)[3]以其中心化的控制模式解决了传统网络保障QoS时的诸多问题[4]。在SDN中，控制器软件及实现控制功能的软件构成了控制平面，SDN交换机只需按照控制层面的转发流表执行转发动作。这种松耦合架构有效解决了传统网络中配置不便、路由不灵活等问题，从而实现了动态的路由策略、便捷的网络配置并降低了网络升级构建成本[5]。

目前，基于SDN的QoS保障技术研究已有不少成果。针对目前SDN架构中控制器上时序优先的流量调度算法的不足，Airton Ishimori等人提出了一种QoSFlow框架，引入HTB、SFQ、RED等队列调度算法降低数据包转发处理时延，有效提高了视频等数据流的PNSR[6]。Seyhan Civanlar等人通过以时延和网络丢包率的加权平均作为QoS约束代价，计算QoS视频业务和BE业务的路径，进而搜索满足约束的最优路径，一定程度上保障了时延、丢包率QoS需求[7]-[8]。这些路由算法[11]虽然实现了较好的流量分布策略，一定程度上保障了高优先级业务QoS，但对全局网络业务特性考虑不全，以一种QoS性能作为优化目标，因此无法满足多类型业务QoS需求，更不能达到动态自适应保障业务QoS的目标。

为有效保障多类型业务的QoS，本文基于Mininet仿真系统设计实现了一种基于SDN的拉格朗日松弛多约束(LRMC)QoS路由算法。在支持OpenFlow协议的交换机中，根据流表项中的TOS包头域对业务数据划分优先级，进而针对不同优先级业务流建立了多约束数学模型，采用拉格朗日松弛法和梯度迭代法对约束关系进行松弛并迭代求解链路权重，进而利用Dijkstra算法探索出最优路径解。最后借助Mininet 及其CLI对LRMC QoS路由算法进行网络仿真，对比其相较单约束QoS算法在网络连通收敛性和网络性能上的表现。

2 路由算法设计

面对多约束条件下的QoS路由问题时，一般采用启发式算法或近似算法保证策略的实时可靠性[13]。启发式算法具有时间复杂度低的优势，但策略质量无法保证；近似算法虽然时间复杂度相对较高，但能更好地保证策略可靠。本文主要针对拓扑节点数相对较少的网络环境，所以选择近似算法-拉格朗日松弛多约束算法求解。

2.1 QoS多约束建模

根据RFC2574标准对QoS路由的定义，QoS是基于网络可用资源和业务流QoS要求来选择路径的路由机制或包含各种QoS参数的动态路由协议[14]。作为一种路由机制，QoS路由的预设条件是满足一个或多个资源限制或业务流QoS要求，这些限制及要求被量化为丢包率、时延、带宽等参数[17]。本文研究的路由算法正是针对多约束条件参数展开，这些QoS指标被分为加法、乘法、凹性三种尺度[18]。定义如：在一个网络拓扑中，记路径P=(a，b，c，∧，e，f)，(i，j)为连接节点i和节点j的链路，c(i，j)为链路(i，j)上的某个QoS尺度值，c(p)为路径p的某个QoS尺度值。若满足c(p)=c(a，b)+c(b，c)+∧+c(e，f)，则这种c(i，j)尺度就属于加法尺度，例如网络时延等；若满足c(p)=c(a，b)×c(b，c)×∧×c(e，f)，则c(i，j)这种尺度就属于乘法尺度，例如丢包率等；若满足c(p)=min{c(a，b)，c(b，c)，∧，c(e，f)}，则c(i，j)这种尺度就属于凹性尺度，例如带宽等。

针对图G(V，E)表示的n个节点的网络，其中E代表网络中的链路集，V代表网络中的节点集，设路由源节点为s，目的节点为t，Pst表示由源节点到目的节点的所有路径集。则对于每一条路径p∈Pst，关于其中每条链路e(i，j)的延迟dij、丢包率lij、带宽bij，可根据QoS算法的性能尺度定义得到各尺度约束关系式，如式(1)、(2)、(3)所示

(1)

b(p)=min[bij，bij，…，bmn]

(2)

(3)

(4)

将式(1)(2)(3)代入上式，则上述多约束问题可简化为

(5)

该多约束最小代价路径问题是一个NP问题，通过拉格朗日松弛法可对式(5)进行松弛处理，求得多约束问题下界，随后在迭代探查过程中搜索满足约束条件的路径。

2.2 拉格朗日松弛处理

使用拉格朗日松弛法对多约束最小代价模型进行松弛时，首先需要对式(4)中丢包率约束不等式两边取对数，将多约束模型中的乘法约束转换为加法约束，即：

(6)

对式(5)进行拉格朗日松弛

(7-1)

min[bij]≥B

s.t.

(i，j)∈p

(7-2)

式(7)中μ1和μ2为两个常数级别拉格朗日乘子，因此μ1D+μ2logL也为常数，为简化计算，可将式(7)简化为式(8)。

(8)

根据上式，将链路权重Wij简化定义为式(9)所示。

Wij=wij+μ1dij+μ2loglij

(9)

2.3 梯度迭代

欲求解权重因子，可以考虑通过梯度迭代法求解，因为通过观察μ1、μ2与时延、丢包率的线性关系发现，μ1、μ2与dij、lij呈线性正相关，因此可以使用传统线性表达式的求解方式梯度迭代法来求解μ1、μ2最优解。

L(μ1，μ2)分别对μ1、μ2求偏导，如式(10)(11)所示

(10)

(11)

为保证Δd和Δl非负，Δd、Δl分别表示如下

(12)

(13)

令μ1←μ1+φΔd，μ2←μ2+ηΔl，保证权重因子单调递增。使用(μ1)t、(μ2)t表示第t次梯度迭代时的链路权重乘子，则t+1次迭代时的乘子如式(14)、(15)：

(μ1)t+1=(μ1)t+φtΔd

(14)

(μ2)t+1=(μ2)t+ηtΔl

(15)

设不受约束时的路径最小权重为Cmin，则步长φt和ηt如式(16)、(17)所示。

(16)

(17)

每次迭代时的标量ωt、ρt取非负常数，即

(18)

(19)

利用梯度迭代法即可求解满足原线性规划问题的权重乘子μ1和μ2，即式(8)问题的权重乘子。如果所选路由上性能参数不满足约束阈值，则调整相应的权重乘子改变该参数在链路权重计算中的权重比，进而通过迭代探寻满足式(4)约束模型的最优可行路径。

3 路由算法实现

基于对实时业务数据流的优先级分类和多约束QoS路由算法的建模分析，本文实现了SDN网络中实时业务多约束QoS路由算法。

图1 LRMC多约束QoS算法流程图

算法流程如图1所示，主要步骤如下：

1)以拓扑中链路e(i，j)的延迟dij为链路权重，通过Dijkstra算法求得最短路径Pd。若该最短路径的带宽和延迟指标满足预设的阈值需求，则Pd为满足约束的最短路径，返回Pd，算法结束。否则执行步骤2)。

2)以拓扑中链路e(i，j)的带宽bij为链路权重，通过Dijkstra算法求得最短路径Pd。若该最短路径的带宽和延迟指标满足预设的阈值需求，则Pd为满足约束的最短路径，返回Pd，算法结束。否则执行步骤3)。

3)通过步长φt和ηt迭代计算μ1和μ2，并将μ1和μ2代入式(9)得到链路多约束权重wij。Dijkstra算法以wij为代价求得最短路径Pt+1，如果Pt+1满足约束模型式(5)则选择Pt+1为(s，t)传输路径。

分析算法流程可得，本文实现的基于SDN的LRMC多约束QoS路由算法的时间消耗主要包含两部分：Dijkstra算法和调整权重因子迭代探寻最优多约束路由。LRMC多约束QoS路由算法在搜索最优路径时，首先采用经典单源最短路径Dijkstra算法求解带权有向网络拓扑中的最短路径，而Dijkstra算法总的时间复杂度为O(n2)[20]；当Dijkstra算法所得路径无法满足业务多约束需求时，使用LRMC算法迭代调整权重乘子并重新计算链路权重，因此设t次迭代得到最优路径，则算法时间复杂度为O(t·n2)。综上，针对n个节点的稀疏网络拓扑，逐步迭代t次搜索最优路径，LRMC多约束路由算法在最坏情况下的时间复杂度为O(t·n2)，最好情况下时间复杂度为O(n2)。

4 仿真及性能评价

为评价基于SDN的LRMC多约束QoS路由算法(以下简称LRMC算法)的性能，本文采用mininet仿真工具分别对LRMC算法和一种SC(Single Constraint)算法对比，该算法是与LRMC算法同等算法条件下对QoS时延指标单约束(Single Constraint)的路由算法。仿真性能包括连通时延收敛性及带宽、传输速率、丢包率、时延性能的表现。

4.1 仿真环境设置

本文采用Ubuntu14.04操作系统虚拟机与mininet仿真工具模拟网络环境。LRMC算法选用Python2.7开发语言和PyCharm编译器进行开发编译，并部署运行在虚拟机上安装的Ryu控制器中。仿真在Mininet仿真环境下进行，为模拟真实网络环境中的链路负载情况，实验中为每条链路Hi→Hj设定固定带宽值(bw)，网络拓扑脚本如图2所示。

图2 拓扑构建脚本

4.2 仿真及分析

1)实验一：算法收敛性实验

建设全域旅游示范区，首要的是抓好高等级的优质景区[13]，这些景区是引领区域旅游发展的增长极，可以依托这些景区打造沿黄精品旅游线路。目前山西沿黄县市还没有5A级景区，未来仍需加紧二次深度开发沿黄核心景区，提升景区质量等级与接待服务水平，创新旅游项目，延伸景区景观以扩大景区规模。同时，要摸清沿黄旅游资源家底，对尚未开发到位的旅游资源，尤其是特色旅游资源，要按照国际旅游标准开发规划，争取一次到位，避免破坏性建设。

为对比SC算法与LRMC算法在路由发现时间上的收敛性，本次实验拟在实验拓扑中分别运行SC和LRMC算法，利用ICMP协议中的icmp＿seq字段测试连通性，执行操作如下： H1、H3、H5分别向H4、H6、H8发送30次ICMP请求报文，监测ICMP＿seq发送次数与连通响应时间。

图3、图4、图5分别为H1→H4、H3→H6、H5→H8节点之间链路的30次连通时间折线图，图中剔除了SC算法的超时数据。由图可知，SC算法在ICMP＿seq次数少于21次时均连接超时，无法收敛，在21至25次之间时才不超时，但是连通时延均大于等于0.28ms，H1→H4连接过程中当ICMP＿seq次数为25、26时，H1和H4的时延测试结果甚至达到2046ms和1047ms，此后时延才急剧下降，实现收敛。而LRMC算法在ICMP＿seq次数仅为1时就达到连通目标，且除第一次连通外，连通时延均小于0.1ms。

图3 H1、H4连通收敛图

图4 H3、H6连通收敛图

图5 H5、H8连通收敛图

因此由该算法收敛性实验可见，LRMC算法的连通速度明显快于SC算法，快速实现收敛性。

2)实验二：算法性能实验

为验证LRMC算法在网络传输性能上的表现，本次实验分别计算SC算法与LRMC多约束路由算法运行时的链路带宽、传输速率、延迟及丢包率性能，并统计分析其方差。实验中，将H1-H7共7 台主机作为客户端，H8作为服务端，当SC算法与LRMC算法运行时，客户端分别向服务端发送6M的TCP数据包，计算每条链路在两种算法运行时的传输性能。

表1 LRMC算法与SC算法运行时网络性能

LRMC算法与SC算法运行时网络性能统计如表1所示，由表可知，LRMC算法运行时，链路带宽、传输速率、丢包率性能与SC算法运行时基本一致，部分链路略高于SC；而对于传输速率，除路径H1→H8、H6→H8、H7→H8在两种算法运行时的差值小于0.1%之外，LRMC路由算法在其余H2→H8、H3→H8、H4→H8、H5→H8路径上运行时的传输速率比SC算法运行时高39～99.3倍。

为进一步对比LRMC算法、SC算法在链路带宽、传输速率、链路时延、丢包率性能上的稳定性，本实验计算并统计了表2对应各性能数据方差值，性能方差数据直方如图6所示。

图6 算法传输性能方差对比

如图7所示，对于链路带宽性能，SC算法与LRMC算法运行时性能方差基本一致，LRMC算法比SC算法带宽方差小9.27%，而其它传输速率、时延、丢包率3个性能指标在两种算法运行时的性能方差差距较明显，LRMC算法方差比SC算法分别小38.2%、45.2%、11.9%。由此可知，相较于SC算法，LRMC算法运行时的网络性能稳定性更优。

综上实验结果及分析可得，本文设计实现的LRMC多约束路由算法在链路带宽、传输速率、时延、丢包率性能上的表现优于SC算法，并且相较于SC算法运行时对业务QoS的保障，LRMC算法在QoS保障方面性能更稳定。

5 总结

本文借助Mininet仿真系统，搭建、运行仿真SDN网络，最后基于对传统网络QoS保障算法的研究，针对多类型业务QoS无法得到有效保障的问题，设计实现了一种基于SDN的LRMC多约束QoS路由算法。根据业务QoS需求建立了关于带宽、延时、丢包率性能指标的多约束数学模型，在Dijkstra算法基础上结合拉格朗日松弛法和梯度迭代法迭代求解得到满足约束条件的最优路径解。最后将LRMC多约束QoS路由算法算法实现部署运行在Mininet仿真网络控制器中，在仿真网络中对比其与单约束算法在连通时间收敛性和网络性能上的表现。Mininet仿真结果表明，本LRMC路由算法运行时的连通时间较同等条件下的时延单约束算法连通时间更短、性能更优更稳定，结合SDN网络架构的可直接编程特性和集中控制特性可有效保障多类型业务QoS。