一种基于SDN网络的QoS路由选择方案
2018-03-05孔祥彬沈苏彬
孔祥彬，沈苏彬，李 莉
(南京邮电大学 计算机学院、软件学院，江苏 南京 210003)
0 引 言
在IP网络中，网络设备变得越来越难以配置和安装，从IP网络中添加或移动一个设备需要耗费许多成本，信息技术(information technology，IT)人员也需要重新配置交换机、路由器并更新访问控制列表(access control list，ACL)、虚拟局域网(virtual local area network，VLAN)和其他一些机制[1]。IP网络最初设计的目标只是为了实现端到端数据传送，现在已经很难满足企业或用户日益增加的复杂网络需求。此外，在提供和管理包含多种技术的大型多供应商网络所涉及的运营成本也在不断增加，而运营的收入却在减少。
为了解决上述问题，工业界提出了软件定义联网(software defined networking，SDN)的概念[2]。SDN是一种分离网络控制与报文转发功能的、动态、可适配的体系结构[3]，这种逻辑集中式控制有助于网络资源的统一管理与分配，而转发层面只进行数据的转发。编程人员能够通过可编程接口实现对网络设备的管理和网络设备的报文转发控制，通过这种更加方便灵活的网络管理，从而达到简化网络运维、灵活管理调度的目标。因此，研究新型的网络架构软件定义联网具有重要意义。
IP网络报文在进行信息传递时会涉及到路由选择的问题，为业务流选择满足QoS度量参数约束的路由一直是学术界和工业界研究的重点问题。IP网络的路由协议(如RIP、OSPF)只针对跳数计算最短路由[4]，随着业务对服务质量(quality of service，QoS)[5]的要求越来越高，需要同时考虑多个QoS度量参数进行路由选择。当涉及到两个及以上互相独立的QoS度量参数的路由时，传统网络出现的问题主要有[6]：路由信息不准确、算法复杂度高且选路效率较低，在分布式路由中还会产生回路问题。在具有集中式路由特点的SDN网络中，控制器通过全局网络拓扑为业务流选择路由，与IP网络源路由不同的是，控制器能够实时收集链路信息，保证了链路信息的准确性，为设计高效、快速的启发式算法提供了有力保证。
文中通过SDN网络控制器实时收集网络资源，在此基础上设计并实现了基于SDN网络的QoS路由算法，并对算法的有效性进行了仿真测试。
1 相关技术分析
QoS路由[7]是指根据网络中的可用资源和业务流对QoS的请求来决定流的路由的机制。QoS可用丢包率、延迟、延迟抖动、瓶颈带宽等基本的性能指标来描述。随着IP网络的发展，视频会议、可视电话等多媒体业务不断增加，这类实时业务需要足够的带宽以保证其服务质量，因此，针对实时类业务流对带宽提出的约束问题进行QoS路由算法的设计。
在IP网络中，路由[8]一般由路由算法和路由协议构成，而路由协议用来收集网络状态信息，从而为QoS路由算法提供必要的状态信息。但是如果QoS路由算法[9]使用不准确的路由信息，会严重损害QoS路由算法的性能。因此，IP网络中期望在所有路由器维护最新的链路状态信息，随着网络规模的增大，频繁的链路状态更新需要消耗大量的信令开销。在SDN网络中，OpenFlow协议可以主动或被动地收集链路状态信息。文献[10]即是利用控制器与交换机之间的packet-in和Flow-Removed消息被动地收集链路信息，虽然控制器与交换机之间的通信开销较小，但是如果网络中存在持续时间较大的流量时，该方法则无法提供准确的链路信息。文献[11]中的OpenSample使用sFlow采样的方式收集基础设施层的链路信息，但数据的准确性受采样率的限制，如果为了提高准确率则同样会增加网络设备的CPU负载。为了能够提供准确的链路状态信息，文中选择OpenFlow协议以主动的方式采集链路状态信息，即使用StatisticsRequest消息以轮询的方式收集链路状态信息。
针对多个QoS度量参数提出约束要求称为多约束路径(multi-constrained path，MCP)路由问题。在MCP问题中，每条链路对应m个约束条件，一条满足m个约束条件的路径成为可行路径，网络拓扑中可能存在多条满足约束条件的路径，在多条可行路径中选择一条最小长度的路径称为多约束最优路径(multi-constrained optimal path，MCOP)问题。MCOP问题属于NP难度问题，MCOP问题中典型的一个子问题为延迟约束代价最小问题(delay constrained least cost，DCLC)。为了降低算法复杂度，根据求解问题类型和求解方法，QoS路由算法可分为[12]：多项式非启发类、伪多项式启发类、探测类、限定QoS度量类、花费函数和概率求解类。
文献[13]为了保证视频的服务质量，为业务流考虑了三个QoS度量参数，其中将延迟作为受限约束，将链路负载和延迟综合成链路代价，针对这个受限最短路径(restricted shortest path，RSP)问题采用拉格朗日松弛(Lagrangian relaxation)算法来为视频流选择QoS路由。文献[14]只考虑链路剩余带宽和延迟，将链路剩余带宽作为链路代价，延迟作为约束条件进行选路，当传输的业务流对延迟比较敏感时，采用拉格朗日算法计算路由。当传输的是数据类非实时业务流时，其只考虑链路剩余带宽，将链路剩余带宽作为链路代价并使用Dijkstra算法实现业务流的QoS路由选择。文献[15]基于SDN技术提出的HiQoS系统引入了多路径路由技术，其通过修改最短路径路由算法，使其能够计算满足QoS度量参数约束的多条路径并利用哈希表保存路径，控制器以一定的周期检查这些路径的链路状态，当需要为业务流选择路径时，控制器根据带宽使用情况和队列状态等选择一条最优的路径给相应的业务流。
2 问题分析与方案设计
(1)问题分析。
根据上一节对QoS度量参数收集、QoS路由算法的分析，可以看出IP网络信息收集需要耗费大量的信令开销来收集网络状态信息。当网络规模增大时，链路上的信令开销也会呈现指数级增大，并且由于信令延迟问题导致链路信息不准确，对QoS路由算法选路效率影响较大。因此，利用OpenFlow协议以主动的方式实时收集网络链路状态信息；此外，在IP网络中QoS路由算法实现起来相对困难，算法复杂度较高，很难为业务流选择端到端的QoS路由。而SDN网络可以聚集出基础设施层的网络拓扑且能够实时收集链路状态，控制器也可以提供集中式的路由服务。当前SDN网络中QoS路由方案是研究的热点问题，因此针对业务流对带宽提出的约束要求，设计了QoS路由算法以满足业务流的QoS需求。
(2)基于SDN网络的QoS路由方案。
基于SDN网络的QoS路由方案的总体框架如图1所示。
图1 方案总体设计框架
该方案的设计依赖于SDN控制器提供的网络基础功能，如链路发现、拓扑管理、流表下发等基础功能，其中链路发现使用链路层发现协议(link layer discovery protocol，LLDP)实现底层网络链路的发现与更新，拓扑管理用于构建SDN网络的拓扑并实时更新网络拓扑，流表下发用于将路由策略下发给OpenFlow交换机。在此基础上详细阐述了QoS数据监测方法、QoS路由算法，其中主要阐述了剩余带宽监测方法、基于Dijkstra的QoS路由算法，为业务流选择满足带宽约束要求的QoS路由。
(3)QoS数据监测设计。
QoS数据监测是对链路上流量信息的收集以为QoS路由算法提供实时、准确的链路状态信息。在SDN网络中能够以被动方式或主动方式进行流量信息的收集。SDN网络可以使用OpenFlow协议以主动的方式收集链路状态信息，保证流量收集的准确性。QoS数据监测则是基于SDN网络，主要用于剩余带宽的收集。控制器通过解析交换机发送的StatisticsReply消息获取并解析端口流量的统计信息，通过不同时间端口接收字节数和发送字节数的不同来计算链路当前流量占用的带宽，最终通过端口最大带宽减去端口当前流量占用的带宽得到链路剩余带宽。
(4)QoS路由算法设计。
文中将带宽作为QoS度量参数，主要考虑业务流对带宽提出的约束要求，因此，将带宽转换为链路代价并用cij表示，Bij剩余表示链路ij的剩余带宽，Bmin表示业务流提出的最小带宽要求。剩余带宽越大，越能满足业务流的带宽要求，如果剩余带宽小于最小带宽要求，则无法满足业务流提出的带宽约束要求。如果剩余带宽Bij剩余大于业务流提出的带宽约束Bmin，则此时链路代价cij的值为链路剩余带宽与业务流提出约束要求带宽的差值；如果剩余带宽小于业务流提出的带宽约束要求，此时链路代价为负无穷。通过以上链路代价的初始化，从而为业务流选路时满足业务流对带宽提出的约束要求。
网络拓扑图用G(N,A)来描述，其中N表示网络中的节点集合，A表示网络中的链路集合。Link(i,j)表示一条从节点i到节点j的有向链路。Pst表示从源节点s到目的节点t的所有满足带宽约束的可行路径，对于其中的路径P∈Pst，定义满足带宽约束的可行路径P的总代价fC，为路径P上每条链路代价的和。
基于以上的链路代价，使用Dijkstra算法为业务流选择满足带宽约束要求且代价最大的路径，算法的伪代码如下所示：
Dijkstra(G,s,t,c)//在图G中，s为源节点，t为目的节点，c为链路代价
任意的v属于节点集合N，dist[v]:=-∞,prev:=null;//初始化总代价为负无穷，前驱节点为空
dist[s]:=0;//设置源节点的总代价为0
S:=Ф//S表示保留了已知的所有d[v]的值已经是最大代价路径的值的顶点,集合S初始状态为空
Q:=N//Q保留了其他所有顶点，其初始状态为图G中所有的顶点集合N
while(Q:≠Ф)//当节点集Q不为空时进行循环操作
u:=Extract_Max(Q)//Q中dist[u]最大的顶点并将u从Q中删除
S.append(u)//将节点u加入到S集合中
if(u==t)end;//如果节点u为目的节点，算法结束
For each edge outgoing from u as (u,v)
alt=dist[u]+c(u,v);//遍历u的所有相邻节点v并计算总代价
if(alt>dist[v])//如果计算的总代价比原来代价大，则更新v的总代价
dist[v]=alt;//更新节点v的总代价
prev[v]=u;//更新v的前驱节点为u
end//算法结束
以上基于Dijkstra算法的QoS路由算法根据链路代价为业务流选择QoS路由，而链路代价cij考虑到了业务流对带宽的最小约束要求。此外，基于SDN网络的QoS算法较IP网络QoS路由算法的优势为数据平面交换机之间不需要信令开销。相较于IP网络QoS源路由，利用SDN控制器能够实现实时的链路状态更新，聚集出有效的链路状态信息而不会产生陈旧信息，选路效率较高；算法能够基于聚集的链路状态信息利用SDN控制器进行集中式路由。因此利用SDN网络实现QoS路由选择技术使算法具有易扩展、适应不同网络拓扑等特点。
3 方案实现
QoS路由选择的实现主要基于开源控制器Floodlight，其中依赖于Floodlight控制器实现了链路发现模块、拓扑管理模块、流规则下发模块。链路发现模块实现了底层网络链路的发现与更新，拓扑管理模块实现了网络拓扑的构建及更新，流规则下发模块实现了SDN网络控制器将路由策略下发给OpenFlow交换机。而QoS数据监测主要实现底层网络剩余带宽的收集。QoS路由算法主要实现业务流的QoS路由选择。
(1)QoS数据监测实现。
本节主要实现对剩余带宽的监测。基于Floodlight开源控制器设计了DataMonitor模块，该模块需要调用IFloodlightService、IFloodlightModule、IOFMessageListener提供的服务。其中IFloodlightService是Floodlight能够提供服务的模块的基本接口，IFloodlightModule定义了Floodlight能够加载的模块的接口。Floodlight控制器通过IOFMessageListener来监听OpenFlow消息。
DataMonitor模块中的主要类和接口如下：
IDataMonitor接口为DataMonitor中的一个服务，继承module模块即Floodlight能够提供服务的模块的基本接口IFloodlightService，主要方法为getLink，用于计算剩余带宽。通过IDataMonitorService接口向QoS路由模块提供剩余带宽信息。
DataMonitor类主要实现了剩余带宽的计算，实现了IFloodlightModule、IOFMessageListener两个接口中的getModuleServices、getServiceImpls等方法。IFloodlightModule标识了DataMonitor模块是Floodlight的一个模块，在Floodlight启动过程中，该类以模块形式加载。IOFMessageListener接口用于监听Floodlight控制器与OpenFlow交换机之间的消息，如Packet-in、Flow-Mod、Stat-Reply等。DataMonitor类除了实现getLink方法以外，还实现了receive方法，其主要是对Stat_Reply消息的处理。方法Precess_stat_reply功能是对OpenFlow消息Stat_Reply进行处理，创建一个Flow_Table_Entry，并将这个流表项作为getLink方法的一个参数。
计算剩余带宽的主要方法为getLink，在DataMonitor中实现。首先通过receive方法处理OpenFlow消息，然后通过Precess_stat_reply方法将统计的消息转化成一个流表项供getLink方法使用。getLink方法通过获取的当前端口的状态信息，计算出剩余带宽。
(2)QoS路由算法实现。
QoS路由选择的实现依赖于Floodlight控制器，首先在Eclipse中导入Floodlight源码和依赖包，然后在Eclipse中创建QoS路由选择模块，之后在resources META-INF/services/net.Floodlight.core.module.IFloodlightModule中指定新增模块名,添加模块配置信息。文中路由计算模块实现调用TopologyManager模块类以实现全局网络拓扑的维护，并且根据QoS数据监测模块提供的服务，为业务流选择QoS路由；然后调用Floodlight控制器的Forwarding模块给交换机安装流表项，最终实现业务流的转发。
下文对QoSRouting模块各个接口及类进行说明，并重点阐述了与QoS路由算法实现相关的方法。
其中QoSRouting模块主要的接口和类为：IFloodlightModule、MasterTopologyInstance类、TopologyManager类、IQoSRoutingService，各个类及接口之间的关系如图2所示。
图2 QoSRouting类及接口图
图中，DataMonitor类实现剩余带宽的监测，MasterTopologyInstance类实现QoS路由算法。其中IQoSRoutingService为Floodlight中其他模块提供服务的接口，其中主要方法为getRoutes，Forwarding模块可以通过该方法获取QoS路由路径。TopologyManager用于维护网络拓扑结构。MasterTopologyInstance类为QoS路由模块的核心类，完成路径计算，其中主要方法为Path Dijkstra(Cluster c,Map
4 实验环境搭建与结果分析
(1)测试环境。
采用Floodlight控制器与网络仿真工具Mininet对QoS路由方案的有效性进行测试。首先使用java-jar target/floodlight .jar命令开启改进后的Floodlight控制器，此时Floodlight根据其配置文件信息加载基本模块，拓扑模块、链路发现模块在Floodlight控制器启动即开始监听事件，但是此时Mininet并没有开启，Floodlight控制器的UI界面暂时没有网络设备。通过Mininet创建的自定义拓扑，连接Floodlight控制器，链路发现模块和拓扑管理模块处理packetin消息构建整个网络的拓扑。
实验中涉及两台物理主机，在其中一台物理主机(地址为192.168.1.110)上安装Floodlight控制器作为控制层设备。在另一台物理主机(地址为192.168.1.111)上安装Mininet网络仿真软件，用来构建网络拓扑。控制层和交换层物理主机上运行的环境为ubuntu12.04，在Mininet上使用iperf网络性能测试工具发送UDP数据包。实验拓扑图如图3所示。使用Mininet自定义拓扑功能，将链路
图3 实验拓扑图
(2)测试步骤与结果分析。
根据实验拓扑图，设置业务流最小带宽约束为6 Mbits，利用iperf网络性能测试工具进行发送UDP报文的测试，以验证算法的有效性。步骤如下：
①Mininet连接最短路算法的Floodlight控制器，通过Mininet的xterm命令打开h1和h3虚拟终端，以h1为iperf客户端，h3为iperf服务端，h1通过如下命令向h3发送UDP报文：
iperf-c10.0.0.3-S0x10-u-i5-t30-b6M
通过Floodlight控制器的UI界面查看交换机的流表项可知，业务流的传输路径为
②启动添加了QoS路由方案的Floodlight控制器，首先需要在floodlight.modules配置参数后添加QoSRouting模块名，以让模块在Floodlight启动时必须加载，然后再次运行Ant命令重新编译版本，最后执行floodlight.sh启动Floodlight控制器。通过Mininet的xterm命令开启h1和h3的虚拟终端，以h1为iperf客户端，h3为iperf服务端，h1通过如下命令向h3发送UDP报文：
iperf-c10.0.0.3-S0x10-u-i5-t30-b6M
通过查看Floodlight控制器的UI界面中的交换机流表项，分析UDP报文的转发路径为
图4 s5交换机部分流表项
由自定义拓扑中链路的带宽状态可知，最短路路径
5 结束语
基于SDN网络设计了QoS路由选择方案，利用OpenFlow协议收集网络状态信息，根据SDN控制器的集中控制优势，设计并实现了QoS路由算法，为有QoS要求的业务流选择QoS路由，最后对该方案进行了测试。结果验证了QoS路由算法的有效性。接下来的工作将对算法满足带宽约束进行更深入的测试，并且利用SDN网络控制器的集中控制优势，通过合理的资源分配满足业务流服务质量要求。
[1] 左青云,陈 鸣,赵广松,等.基于OpenFlow的SDN技术研究[J].软件学报,2013,24(5):1078-1097.
[2] Open Networking Foundation.Software-defined networking:the new norm for networks[EB/OL].2012-04-01.https://www.opennetworking.org/sdn-resources/sdn-library/whitepapers.
[3] 沈苏彬.软件定义联网的建模与分析[J].南京邮电大学学报:自然科学版,2014,34(3):1-9.
[4] 林玉侠,朱慧玲,马正新,等.QoS路由度量参数的选择问
题研究[J].电信科学,2003,19(7):22-27.
[5] 杨胜文,史美林.一种支持QoS约束的Web服务发现模型[J].计算机学报,2005,28(4):589-594.
[6] KUIPERS F A.Quality of service routing in the internet:theory,complexity and algorithms[M].[s.l.]:IOS Publisher,2004.
[7] 朱慧玲,杭大明,马正新,等.QoS路由选择:问题与解决方法综述[J].电子学报,2003,31(1):109-116.
[8] 闵应骅.计算机网络路由研究综述[J].计算机学报,2003,26(6):641-649.
[9] MASIP-BRUIN X,YANNUZZI M,DOMINGO-PASCUAL J,et al.Research challenges in QoS routing[J].Computer Communications,2006,29(5):563-581.
[10] YU C,LUMEZANU C,ZHANG Y,et al.FlowSense:monitoring network utilization with zero measurement cost[C]//International conference on passive and active network measurement.Berlin:Springer,2013:31-41.
[11] SUH J,KWON T T,DIXON C,et al.OpenSample:a low-latency,sampling-based measurement platform for commodity SDN[C]//International conference on distributed computing systems.Madrid,Spain:IEEE,2014:228-237.
[12] 崔 勇,吴建平,徐 恪,等.互联网络服务质量路由算法研究综述[J].软件学报,2002,13(11):2065-2075.
[13] EGILMEZ H E,DANE S T,BAGCI K T,et al.OpenQoS:An OpenFlow controller design for multimedia delivery with end-to-end quality of service over software-defined networks[C]//Signal & information processing association summit and conference.Hollywood,California,USA:IEEE,2012.
[14] CUI H Y,ZHU Y,YAO Y,et al.Design of intelligent capabilities in SDN[C]//International conference on wireless communications,vehicular technology,information theory and aerospace & electronic systems.Aalborg,Denmark:[s.n.],2014:1-5.
[15] YAN Jinyao,ZHANG Hailong,SHUAI Qianjun.HiQoS:an SDN-based multipath QoS solution[J].China Communications,2015,12(5):123-133.
