林川, 赵海, 毕远国, 蔡巍
东北大学计算机科学与工程学院 控制工程学院, 辽宁 沈阳 110169
收稿日期：2016-02-23
基金项目：国家自然科学基金资助项目(61671142, 61101121，61373159)。
作者简介：林川(1988 -)，男，辽宁凤城人，东北大学博士研究生;
赵海(1959 -)，男，辽宁沈阳人，东北大学教授，博士生导师。

摘要：采用OpenFlow技术, 设计并实现了一套基于软件定义网络的QoS测量与路由规划系统.利用控制器与OpenFlow交换机之间的消息交互, 实现SDN中链路时延、负载和丢包率的测量功能.针对QoS路由中存在的“多指标约束限制”问题, 根据本文考虑的QoS指标(链路时延、负载和丢包率), 改进并实现了一种自适应多指标限制路由算法.实验结果表明:该系统在准确测量链路QoS指标的同时, 可以根据测量结果切换符合条件的路由路径, 满足系统设计需求.
关键词：OpenFlow软件定义网络QoS测量路由规划多指标约束
Design and Implementation of a QoS-Enabled Measuring and Routing System Based on SDNs
LIN Chuan, ZHAO Hai, BI Yuan-guo, CAI Wei
School of Computer Science & Engineering, Northeastern University, Shenyang 110169, China
Corresponding author: BI Yuan-guo, E-mail: biyuanguo@ise.neu.edu.cn
Abstract: The QoS-enabled measuring and routing system is designed and realized by adopting the OpenFlow. The abilities of measuring link delay, load and packet loss are realized by utilizing the interactive messages between the controller and the OpenFlow-enabled switch. In order to solve the problem of multiple constraints during QoS routing, a multiple constraints routing algorithm is improved and realized with the QoS metrics (link delay, load and packet loss) considered. The experimental results show that the system proposed is able to measure the QoS metric and change the routing path based on QoS measurement, and it meets the needs of system design.
Key Words: OpenFlowSDN(software defined networking)QoS measurementrouting arrangementmultiple constraints
软件定义网络(software defined networking, SDN)是一种数据控制分离、软件可编程的新型网络体系架构^[1].SDN通过定义控制层和数据转发层的统一接口, 如OpenFlow, 实现集中式的控制平面和分布式的数据转发平面^[2].
SDN针对传统的以互联网为代表的通信网络中存在的数据处理独立、管理效率低下等问题, 通过提取通信网络中数据分组的共同特性, 提出“流”的数据封装与管理概念^[3], 实现逻辑上的集中管理.SDN这种逻辑上集中式管理的特点使粒度更细、效率更高的网络流量管理、规划、测量成为可能^[4].本文正是利用这一特点, 设计并实现了一套基于SDN的QoS(服务质量)测量与路由规划系统, 使用户可以实时感知网络全局QoS状态并根据实时测量结果切换满足条件的路由路径, 保证目标流量QoS^[5-6].
1 系统设计的原理分析如图 1所示, 本文设计与实现的基于SDN的QoS测量与路由规划系统共包括两个主要模块, 即QoS测量模块与路由规划模块.系统总体设计采用面向底层设备(数据层)的虚拟南向接口协议——OpenFlow协议^[7].QoS测量模块在利用LLDP协议发现网络拓扑之后, 利用OpenFlow控制器周期性地向OpenFlow交换机发送统计询问消息和探测数据包, 实时测量并统计网络链路负载、时延、丢包率.在此基础上, 路由规划模块根据QoS测量模块实时感知网络状态, 根据QoS路由规划算法, 实时计算满足目标流量QoS需求的路由路径, 并利用OpenFlow技术, 通过修改OpenFlow交换机的流表信息来切换目标流量的路由路径.此外, 在路由规划模块设计中, 为解决QoS多指标限制路由规划问题, 根据本文QoS模型, 改进并实现了一种多指标限制路由规划算法, 该算法可以计算同时满足QoS测量模块中的3种QoS指标要求的最优路径.
图 1(Fig. 1)

图 1 系统示意图Fig.1 System architecture

本套系统的总体设计主要包括两部分:QoS多指标测量模块设计与路由规划模块设计.其中QoS多指标测量模块设计包括3部分:链路时延测量模块设计, 链路负载测量模块设计及链路丢包率测量模块设计; 路由规划模块设计包括:QoS模型设计及路由算法的选择与改进.
此外, 在实现过程中, 采用NTT公司主导研发的Ryu控制器构建SDN的逻辑控制层, 完成相关应用的开发.
2 QoS多指标测量模块设计OpenFlow协议由ONF组织负责维护, 项目发展至今已经有v1.0, v1.2, v1.3, v1.4等多个衍生版本.其中, OpenFlow v1.3作为一个支持长期维护的稳定版本而备受关注, 它提供了包括服务质量, IPv6扩展头等多个功能^[7].本系统正是利用OpenFlow 1.3向控制层提供的数据统计和管理消息命令来设计实现QoS多指标测量模块.
2.1 链路时延测量模块设计在本系统中，链路时延定义为数据流通过路由路径邻接交换机单向链路所需要的时间.链路时延测量包括两部分:测量探测数据流往返时延，测量控制器和交换机之间链路时延.如图 2a所示, t₁时刻, 控制器将时间t₁作为负载数据封装到探测数据流flow_pro中, 并利用PacketOut消息^[8]从S₁的端口1发出flow_pro.由于S₂并没有流表项与flow_pro匹配, 因此S₂利用PacketIn消息^[8]向控制器报告这一事件.t₂时刻, 控制器获取S₂的报告, 并从flow_pro获取负载数据时间t₁.那么, flow_pro的往返时延D_RTT为(t₂-t₁).D_RTT共由三部分组成, 分别为:控制器与S₁, S₂之间链路时延D_c-S1, D_c-S2; S₁与S₂之间链路时延D_S1-S2.如图 2b所示, D_c-S1, D_c-S2可以利用控制器分别向S₁, S₂发送数据请求消息(如下文FlowStatsRequest消息^[8]), 则从消息发出到控制器获取S₁, S₂的响应消息的时间差可以作为控制器与S₁, S₂之间的往返时延D_{rtt_S1}, D_{rtt_S2}.因此, D_c-S1, D_c-S2分别近似等于0.5D_{rtt_S1}, 0.5D_{rtt_S2}；D_S1-S2近似等于D_RTT- D_c-S1- D_c-S2.此外, 在实际计算交换机之间的单向链路时延时, 控制器与交换机之间的链路时延等于最近5个采样值的平均值.
图 2(Fig. 2)

图 2 链路时延测量示意图Fig.2 Link delay measurement (a)—往返时延测量；(b)—控制器与交换机时延测量.

2.2 链路负载测量模块设计链路负载测量模块的核心设计思想是:针对特定方向链路的下行交换机, 统计固定时间间隔内, 以链路关联端口为流量进入端口的流表项所匹配的数据流数量；则这条链路的负载即为匹配的数据流数量除以固定时间间隔.链路负载测量模块的示意图如图 3所示.在每个OpenFlow交换机中, 每一个和固定路由路径相关联的OpenFlow流表项的匹配域都会包含源IP地址、目的IP地址、进入端口、转发端口等信息.每隔固定时间间隔t_int，控制器利用OpenFlow技术向链路Link_S1-S2的下行交换机S₂发送FlowStatsRequest消息，并通过监听这一事件的反馈消息获取并统计所有以S₂的端口2为进入端口的相关流表项e₂₁, e₂₂, …, e_2n所匹配的数据流数量N_now.若在上一个时间间隔, 统计数据流数量为N_pre, 则在t_int内, 通过Link_S1-S2的所有数据流数量为(N_now-N_pre).Link_S1-S2的链路负载近似为(N_now-N_pre)/t_int.
图 3(Fig. 3)

图 3 链路负载测量示意图Fig.3 Schematic of link load measurement

2.3 链路丢包率测量模块设计链路丢包率测量模块设计原理与链路负载测量模块设计原理相似.以图 3所示链路Link_S1-S2为例, 在每个固定时间间隔t_int, 分别向S₁, S₂发送FlowStatsRequest消息.若在t_int内, 共有n种流flow₁(src₁, dst₁), flow₂(src₂, dst₂), …, flow_n(src_n, dst_n)经过Link_S1-S2, 针对每种流, 在S₁, S₂分别各有一个流表项与其相匹配；则Link_S1-S2在t_int内的丢包量可以通过计算S₁, S₂匹配相同种类数据流的流量差值来获得, 即可以通过计算每种流的丢包率来计算Link_S1-S2的丢包率.在本文, Link_S1-S2 的丢包率R_lin(Link_S1-S2)等于max(loss₁, loss₂, …, loss_n), loss_n为flow_n的丢包率.
3 路由规划模块设计如第2节所述, 在基于SDN的网络中, 可以实时测量获取网络中每一个链路的即时负载、丢包率和时延, 共3种QoS指标.在此基础上, 本文针对传统通信网络路由过程中存在的“QoS多指标约束限制”问题，根据本文QoS模型, 改进并实现了一款经典的自适应多指标限制路由算法——SAMCRA^[9].通过测量网络中非目标流量的3种QoS指标, 计算满足目标流量QoS指标限制的最优路径并实现源端到目的端的动态路由切换.
3.1 QoS模型若基于SDN的网络中存在一条经过n条链路的路由路径P, 那么路径P的可用带宽为

(1)

式中：X(p)为链路的最大可用带宽(链路能力)；l (p)为链路的即时测量负载.路径P的丢包率为

(2)

式中R_lin(p)为链路p的测量丢包率.路径P的时延为

(3)

式中D_lin(p)为链路p的链路时延.
3.2 算法改进SAMCRA算法核心共由3部分组成:基于Dijkstra算法的预处理(look ahead), 非线性距离(nolinear length), 支配路径(dominated path).其中, nolinear length作为该算法设计核心用来量化路由选择过程中的距离大小.在只考虑m种QoS指标的网络中, 路径P的非线性距离定义为

(4)

式中:w_i(P)为路径P的各链路p指标之和或乘积; L_i为指标限制.而在实际网络应用中, 以式(1) 为例, 路径P的可用带宽并不能通过各链路负载叠加和或乘积来获得.路径P的可用带宽是由这条路径可用带宽最小的链路决定的^[10].因此, 本系统在实际实现中, 只用丢包率和时延计算路径的非线性距离, 并通过非线性距离和当前子路径的可用带宽共同判断算法是否继续循环.针对本系统链路丢包率、负载和时延3种QoS指标, 具体改进如算法1所示.此外, 为避免流表下发和路由切换过程中存在的流表冲突并可能导致的非正常丢包现象, 本系统利用VLAN技术, 用ID 1和ID 2区分同一交换机针对同一目标流量的旧流表项和新流表项，先下发新流表项, 再删除旧流表项.
算法1?基于时延、链路带宽、丢包率的SAMCRA算法
1:用预处理初始化网络最大非线性距离maxlength(丢包率, 时延), 以及每个节点与目的节点的非线性距离, 将源节点插入Fibonacci堆Q
2:while(Q不为空)
3:从Q中提取距目的点非线性距离最小点u
4:if(u是目的节点)
5:停止查询, 返回最优QoS路由路径
6:else{
7:?for (v, v∈u的临界点集合Adj(u)){
8:??判断u到v的路径是否被其他路径支配
9:??计算从源点经过链路u, v到目的端的非线性距离nolinear length(u, v, 丢包率, 时延)及路由路径的可用带宽maxBw(u, v)
10:??if(nolinear length(u, v, 丢包率, 时延)≤maxlength(丢包率, 时延) AND maxBw(u, v)满足带宽需求AND路径没有被支配)
11:???更新Q
12:??if(v是目的节点AND nolinear length(u, v, 丢包率, 时延)＜maxlength(丢包率, 时延))
13:???maxlength(丢包率, 时延)=nolinear length(u, v, 丢包率, 时延)
15:?}
16:}
4 实验与测试实验平台选用mininet 2.2.1;OpenFlow版本为1.3.4;交换机为Open vSwitch(OVS) 2.3.2;控制器选用Ryu 3.30.实验拓扑如图 4所示:S₁, S₂, S₃, S₄为OVS交换机; Link_S1-S2, Link_S1-S3, Link_S2-S4, Link_S3-S4, Link_S1-S4为链路; h_x, x={1, 2, 3, 4, cli, ser}为产生网络流量的虚拟主机；eth i为端口i, i=1, …, 5.拓扑发现采用Ryu基于LLDP协议的topology.py模块.实验共包括两部分:QoS多指标测量模块测试和路由规划模块测试.
图 4(Fig. 4)

图 4 实验场景Fig.4 Experimental scenario

4.1 QoS多指标测量模块测试实验过程如下:首先, 利用mininet将实验网络中的交换机链路设定为TC Link链路，这样就可以对实验网络中的每条交换机链路设定链路最大带宽, 链路丢包率和链路时延, 具体设定如表 1所示；然后, 利用iperf命令和虚拟主机h₁, h₂, h₃, h₄在链路Link_S1-S2, Link_S1-S3, Link_S2-S4, Link_S3-S4, Link_S1-S4产生带宽为2Mbit/s, 持续时间为10s的UDP数据流量.图 5是采样周期为1s的实验结果.
表 1(Table 1)

表 1 QoS测量模块实际设定Table 1 Setting of the experiments for testing the QoS measuring module 链路 时延/ms 最大带宽/(Mbit·s-1) 丢包率/% LinkS1-S2 5 1 1.5 LinkS1-S3 15 1.5 2.0 LinkS2-S4 20 0.5 3.0 LinkS3-S4 25 0.7 2.5 LinkS1-S4 30 0.9 4.0

表 1 QoS测量模块实际设定 Table 1 Setting of the experiments for testing the QoS measuring module

图 5(Fig. 5)

图 5 链路时延、链路负载和链路丢包率的测量结果Fig.5 Measurement of link delay, load and packet loss

由图 5可知, 虽然本实验在各交换机链路之间产生的是2 Mbit/s的测试流量, 但由于TC Link的限制, 使各链路的实际负载限制为链路的最大带宽.此外, 链路时延、链路负载与链路丢包率的测量值与标准值(链路设定值)的平均测量误差分别为3.3%, 3.9%和1.8%.综上, 本系统在一定误差范围内, 可以测量基于SDN网络中的链路时延、链路负载和链路丢包率.
4.2 路由规划模块测试在该模块测试中, 由于现有实验条件限制(mininet并不允许动态切换链路时延与丢包率), 本文在构建动态QoS网络环境时, 只利用h₁, h₂, h₃, h₄在交换机链路产生网络流量，并为每一条链路设定一个虚拟链路时延与丢包率权值.链路最大带宽统一设定为1 Mbit/s.实验以保证h_cli到h_ser的网络流量traffic_cli-ser为目标.实验网络动态QoS设定的时延、负载、丢包率及周期如表 2所示.traffic_cli-ser的QoS具体要求如下:带宽≥500 kbit/s, 路径总时延≤50 ms, 路径丢包率≤3%.此外, 在得到QoS最优路径后, 利用交换机端口队列技术为h_cli在S₁的流量输出端口设定最大可用带宽, 以保证目标流量的带宽需求.实验开始后, 目标流量推迟2 s, 路由重新计算间隔也为2 s, QoS数据选用最近一次的采样样本(实际应以网络管理需求设定时间间隔).
表 2(Table 2)

表 2 路由规划模块实验设定Table 2 Setting of the experiments for testing the routing-planning module 链路 (时延/ms, 最大带宽/(kbit·s-1), 丢包率/%) 0s~10s 10s~20s LinkS1-S2 (15, 500, 0.5) (21, 300, 0.3) LinkS1-S3 (17, 300, 2.0) (16, 300, 2.0) LinkS2-S4 (15, 700 1.7) (12, 200, 1.5) LinkS3-S4 (20, 600, 1.0) (17, 400, 1.7) LinkS1-S4 (40, 400, 1.5) (60, 500, 2.5)

表 2 路由规划模块实验设定 Table 2 Setting of the experiments for testing the routing-planning module

图 6为各时间段内traffic_cli-ser的QoS路由路径所对应的OpenFlow流表.在2 s至10 s, 所选路由路径为S₁-S₄, 路径丢包率为1.5%, 路径时延为40 ms; 在10 s至20 s, 切换路由路径为S₁-S₂-S₄, 路径丢包率为1.8%, 路径时延为33 ms.实验过程中traffic_cli-ser的实际带宽如图 7所示, 均能保证在500 kbit/s左右.综上, 本系统的路由规划模块可以实现动态路由切换, 满足目标流量的路径时延、带宽和丢包率限制要求.
图 6(Fig. 6)

图 6 路由路径所对应的OpenFlow流表Fig.6 OpenFlow flow table of the routing path (a)—2 s~10 s；(b)—10 s~20 s.

图 7(Fig. 7)

图 7 trafficcli-ser带宽Fig.7 Bandwidth of trafficcli-ser

5 结语本文利用OpenFlow技术, 设计并实现一套基于SDN的QoS测量与路由规划系统.在QoS测量模块中, 利用控制器与OpenFlow交换机之间的消息交互机制, 实现链路时延、负载与丢包率的测量功能.在路由规划模块的设计中, 针对网络路由中存在的“QoS多指标约束限制”问题, 根据本文实际QoS模型, 改进实现了SAMCRA算法.实验结果表明, 该套系统集QoS测量与路由规划于一体, 可以根据QoS实时测量结果, 切换满足目标路由条件的路由路径.本系统设计思想旨在为未来通信网络的流量工程与路由规划提供参考.
参考文献

[1]	张朝昆, 崔勇. 软件定义网络(SDN)研究进展[J].软件学报, 2015, 26(1): 62–81. ( Zhang Chao-kun, Cui Yong. State-of-the-art survey on software defined networking (SDN)[J].Journal of Software, 2015, 26(1): 62–81.)
[2]	Kreutz D, Ramos F M V, Verissimo P E. Software-defined networking:a comprehensive survey[J].Proceedings of the IEEE, 2015, 103(1): 14–76.DOI:10.1109/JPROC.2014.2371999
[3]	Jain S, Kumar A, Mandal S.B4:experience with a globally-deployed software defined WAN[C/OL]// ACM SIGCOMM 2013 Computer Communication Review.[2016-01-08].https://users.ece.cmu.edu/~vsekar/Teaching/Fall14/18859K/papers/b4.pdf.
[4]	Tootoonchian A, Ghobadi M, Ganjali Y.OpenTM:traffic matrix estimator for OpenFlow networks[C]//International Conference on Passive and Active Network Measurement.Berlin:Springer Berlin Heidelberg, 2010:201-210.
[5]	Adami D, Donatini L, Giordano S.A network control application enabling software-defined quality of service[C]//IEEE International Conference on Communications.New York:IEEE, 2015:6074-6079.
[6]	Tomovic S, Prasad N, Radusinovic I.SDN control framework for QoS provisioning[C]//Telecommunications Forum.New York:IEEE, 2014:111-114.
[7]	Openflow consortium[EB/OL].[2015-12-20].http://www.openflow.org/.
[8]	Openflow switch specification[EB/OL].[2015-12-20].https://www.opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/openflow/openflow-switch-v1.3.5.pdf.
[9]	van Mieghem P, de Neve H, Kuipers F. Hop-by-hop quality of service routing[J].Computer Networks, 2001, 37(3): 407–423.
[10]	Tomovic S, Radusinovic I.Fast and efficient bandwidth-delay constrained routing algorithm for SDN networks[C]//IEEE NetSoft Conference and Workshops.New York:IEEE, 2016:303-311.