1. 清华大学 电子工程系, 北京 100084;
2. 清华大学 信息化技术中心, 北京 100084
收稿日期：2018-05-11
作者简介：赵俊(1989-), 男, 博士研究生
通信作者：李星, 教授, E-mail:xing@cernet.edu.cn
摘要：因为网络测量在软件定义网络中扮演着非常重要的角色，所以越来越多的测量算法相继被提出。根据测量方式，这些算法被分成两类：周期测量和自适应测量算法。无论何种算法，如果为每一个流量都发送数据采集请求会产生很大的通信开销，进而增加交换机的负载。为了降低采集流量数据的通信开销，该文首先提出一种基于非线性整数动态规划算法OpenCost，来决定每个流量的数据通过哪个交换机来采集。其次，为了降低算法的运行时间，提出一种贪心算法来近似求解上述最优化问题。最后，为了评估算法性能，搭建了仿真环境并进行了详细的仿真测试。测试结果表明：与其他流量数据请求算法相比，优化算法OpenCost可以降低系统采集流量数据通信开销的55%。
关键词：软件定义网络网络测量非线性整数动态规划OpenFlow协议
Low cost flow statistics collection in software defined networking
ZHAO Jun1, BAO Congxiao2, LI Xing1
1.Department of Electronic Engineering, Tsinghua University, Beijing 100084, China;
2.Information Technology Center, Tsinghua University, Beijing 100084, China
Abstract: Many monitoring methods have been proposed for network measurements that are essential in software defined networking. However, periodically or adaptively collecting statistics from software switches using per-flow queries incurs significant communication costs thus increase the loads on switches. This paper presents an approach called OpenCost that decides which switch us used to collect statistics in software defined networks based on a non-linear integer programming (NLIP) model. However, the NLIP problem is NP-hard; therefore, the problem is solved using an approximation algorithm based on a greedy algorithm. Extensive simulations were used to benchmark the algorithm with the results showing that OpenCost reduces the communication costs by 55% on average compared with other methods.
Key words: software defined networkingnetwork measurementnon-linear integer programmingOpenFlow
软件定义网络(software defined networking, SDN)是一种新提出的网络体系结构，通过使用OpenFlow协议将决定流量传输路径的系统控制平面(control plane)与底层负责转发流量的数据平面(data plane)解耦。由于网络测量在软件定义网络中扮演着非常重要的角色[1]，因此越来越多的测量算法相继被提出。根据测量方式，测量算法可以分成两类：被动测量和主动测量。
当流量第一次到达交换机时，交换机会向控制器发送Packet In消息；当流量空闲时间超过特定时间时，交换机会向控制器发送Flow Removed消息。被动式测量算法通过采集控制器接收到的Packet In和Flow Removed消息来估算流量数据。FlowSense[2]将特定周期时间内触发Packet In消息但没触发Flow Removed消息的流量定义为活跃流量，通过累加活跃流量在周期时间内的传输速率来估算当前链路的带宽利用率。
主动测量算法[3-6]通过周期地从相关交换机采集流量数据来估算链路资源利用率。SLAM[3]算法被用来测量软件定义网络中链路的传输延时。SLAM分别向传输链路上第一台和最后一台交换机发送探测报文，控制器利用收到响应报文的时间戳的差值来估算链路的传输延时。OpenNetMon[4]算法被用来细粒度的测量网络中每个流量的占用带宽、传输延时以及丢包率。为了降低网络测量产生的通信开销，同时兼顾测量精度，OpenNetMon会根据网络中的流量传输情况动态调整采集流量数据的周期：如果连续2次请求发现传输的报文字节数增加，则该算法会提高流量采集的频率；如果连续2次请求发现传输的报文字节数下降，则该算法会降低流量数据的采集频率。PayLess[5]算法采用了与OpenNetMon相同的流量数据采集频率的自适应算法，但PayLess对算法进行了封装并对外提供接口，用户可以很方便地选择采集哪些流量的数据。OpenTM[6]算法认为请求流量传输路径中任意一台交换机都可以获得该流量的数据，但众多采集请求同时请求同一台交换机会增加该交换机的负载。为了解决上述问题，OpenTM在所有交换机中均匀地分配流量数据采集请求，以此来降低交换机的负载。
上述主动测量算法具备以下共同点。首先，这些算法都是为每一个流量发送一个数据采集请求，如果要测量链路的带宽利用率，则需要对流经该条链路的流量数据进行聚合计算；其次，为了降低网络和交换机的负载，同时不影响测量的准确性，这些算法都动态地调整流量数据的采集频率；最后，如果活跃流量的数量非常大，为每一个流量都发送采集请求势必会在控制器与交换机之间产生巨大的通信成本。
根据OpenFlow协议标准，控制器可以从流量维度和交换机维度统计流量数据。流量维度指的是控制器为每一个流量都发送一个数据采集请求，交换机为每一个流量都返回一个应答报文。交换机维度指的是控制器只需要向每个交换机发送一个流量数据采集请求，而交换机一次性返回流经该交换机的全部流量数据。
最开始为每一个流量都发送一个数据采集请求，那么每一个流量会产生一个请求和一个应答消息。随着从交换机维度采集流量数据的交换机数量增加，通信成本会逐渐降低，因为控制器发送的流量采集请求在不断减少。但是如果从每台交换机中都采集流经该交换机的全部流量数据，由于每个流量可能流经多个交换机，因此控制器收到的应答消息中可能包含很多重复消息，进而导致通信成本不降反增。
受上述分析启发，本文提出OpenCost算法，其目标函数是最小化网络测量的通信成本，利用非线性整数动态规划算法，求解出哪些流量需要发送单独的采集请求报文，哪些流量的数据可以通过发送交换机维度的请求报文来采集。为了降低算法的运行时间，本文提出一种贪心算法OpenCost-Appro来近似求解上述最优化问题。为了评估算法性能，本文搭建了仿真环境并进行了详细的仿真测试。测试结果表明与其他流量数据请求算法相比，优化算法OpenCost可以降低系统采集流量数据通信开销的55%。
1 算法设计首先举一个例子来描述算法的工作原理，网络结构如图 1所示。基于OpenFlow协议的网络流量数据请求和应答报文的长度如表 1所示。用控制器与交换机之间发送的流量数据采集请求和应答报文的大小之和来衡量测量的通信成本。假设n为流经交换机的流量个数，则采用流量维度的测量通信开销为(104+64+56)×n，采用交换机维度的测量通信开销为104+64+56×n。
 |
| 图 1 一个简单的例子 |
| 图选项 |
表 1 OpenFlow协议的报文长度
| 报文字段 | 长度/B |
| 流量请求报文的头部和负载 | 104 |
| 流量请求应答报文的头部 | 64 |
| 流量请求应答报文的负载 | 56 |
表选项
如果使用文[3-6]中的算法，为每一个流量都发送一个采集请求，那么通信开销为3×(104+64+56)B=672 B。如果为每一个交换机仅发送一条请求该交换机上全部活跃流量数据，那么通信开销为2×(104+64+56×2)B=560 B。为了进一步降低通信开销，可以从交换机维度向交换机A发送一条采集全部流量(流量1和2)数据的请求，并从交换机B采集流量3的数据，此时通信开销为(104+64+56×2)B+(104+64+56)B=504 B。通过上述简单的例子，可以看出混合使用流量维度和交换机维度采集流量数据，能够有效地降低网络的通信开销。
1.1 OpenCost算法设计上述例子表明混合使用流量维度和交换机维度采集流量数据能够有效地降低网络的通信开销。所以本文提出基于非线性整数动态规划算法OpenCost，来计算流量维度和交换机维度采集流量数据的最优组合。表 2列举了OpenCost算法用到的数学表达式的含义。
表 2 OpenCost算法用到的数学表达式含义
| 表达式 | 长度 |
| N | 活跃流量的数量 |
| M | 交换机的数量 |
| Aij | 二值变量，表示第i个流量是否流经第j个交换机 |
| Cj | 从交换机维度采集流经第j个交换机的流量数据所产生的通信开销 |
| Cf | 请求单一流量(流量维度)数据所产生的通信开销 |
| Xj | 输出二值变量，表示是否从交换机维度采集流经第j个交换机的流量数据 |
表选项
假设网络中有N个活跃流量和M个交换机，那么采集流量数据所产生的通信开销可通过下式计算：
| $C = \sum\limits_{j = 1}^M {{C_j}{X_j} + {C_{\rm{f}}}\sum\limits_{i = 1}^N {\left( {\prod\limits_{j = 1}^M {\left( {1-{A_{ij}}{X_j}} \right)} } \right).} } $ | (1) |
| ${C_j} = 104 + 64 + 56\sum\limits_{i = 1}^N {{A_{ij}}.} $ | (2) |
| ${\rm{min}}\sum\limits_{j = 1}^M {{C_j}{X_j} + {C_f}\sum\limits_{i = 1}^N {\left( {\prod\limits_{j = 1}^M {1-{A_{ij}}{X_j}} } \right);} } $ |
| ${\rm{s}}{\rm{.t}}{\rm{.}}\;{C_j} = 104 + 64 + 56\sum\limits_{i = 1}^N {{A_{ij}}, } $ |
| ${X_j} \in \left\{ {0, 1} \right\}, \forall j \in \left[{1, M} \right].$ |
上述非线性整数动态规划(NLIP)算法是典型的NP难问题。随着网络中活跃流量和交换机数量的增加，求解上述最优化问题所耗费的时间也会显著增加。
1.2 近似算法OpenCost-Appro如图 2所示，本文用贪心算法来近似求解上述非线性整数动态规划问题，该算法可以在多项式时间求解。
 |
| 图 2 OpenCost算法的近似算法 |
| 图选项 |
OpenCost-Appro算法中的中间变量Fcover表示数据已经被采集的流量的集合，而Fremain则表示数据还未被采集的流量的集合。
OpenCost-Appro算法的主要目的是寻找哪些交换机适合通过交换机维度来采集流量数据，亦即控制器只发送一个请求报文，交换机返回全部流量的数据。OpenCost-Appro算法需要按照以下2个原则对交换机进行排序：1)交换机应该包含足够多的没有被采集数据的流量; 2)使用交换机维度采集流量数据所产生的通信开销足够小。OpenCost-Appro算法优先选择满足上述2个条件的交换机(第5行)。
中间变量C1(第6行)表示对尚未被采集数据的流量使用流量维度的方法采集数据所产生的通信成本；而中间变量C2(第7行)表示采用交换机维度方法采集第j个交换机的流量数据，其余流量仍然使用流量维度的方法采集数据所产生的通信成本。
如果对尚未被采集数据的流量采用交换机维度和流量维度采集相结合的方法能够降低通信成本(第8行)，就更新中间变量Fcover(第9行)和Fremain(第10行)，同时置输出变量Xj为1 (第11行)；否则认为使用交换机维度的方法采集数据对降低通信成本没有帮助，OpenCost-Appro算法会结束循环并返回最终结果。
由于OpenCost-Appro算法中第5行的计算复杂度最多为O(M)，并且网络中一共有N个活跃流量，那么其计算复杂度最多为O(MN)。OpenCost-Appro算法的处理流程与OpenCost算法相同，只不过利用贪心算法取代NLIP近似求解二值输出变量Xj。
1.3 算法对比传统的流量数据采集算法(如OpenNetMon[4]、PayLess[5]、OpenTM[6])均属于流量维度的采集算法，其需要为网络中每一个流量都发送一条流量数据采集请求。而OpenCost及OpenCost-Appro算法则根据流量的分布情况，采用流量维度和交换机维度相结合的方式采集流量数据，能够有效地降低数据采集的通信开销，这也是OpenCost和OpenCost-Appro相比传统算法的最大优势。
OpenNetMon算法会根据网络中流量的传输情况动态调整数据采集的频率，以此来降低通信的成本。同理也可以根据网络中的流量传输情况动态调整中心控制器利用OpenCost算法采集流量数据的频率，这是OpenCost及OpenCost-Appro算法的另一优势。
虽然OpenCost利用交换机维度和流量维度相结合的方式采集流量数据，但交换机维度会一次请求该交换机上的全部流量数据，里面有很多重复数据，这是OpenCost算法的缺点。如何仅仅采集交换机中一部分流量的数据(比如目的IP相同的流量的数据)是未来可能的优化方向。
2 实验测试通过仿真环境来对OpenCost及OpenCost-Appro算法的性能进行测试。仿真测试的硬件环境为一台装有Ubuntu 16.04 LTS操作系统的服务器，该服务器具备四核2.3 GHz的处理器和8 GB内存。本文使用Python 3.5实现上述OpenCost算法并利用NAG[7]软件包求解上述NLIP最优化问题。
2.1 仿真环境搭建为了提供高效的数据传输服务，越来越多的应用构建在数据中心网络之上，它们通过构建覆盖网络来优化数据的传输路径。受文[8]启发，本文模拟一个在线扑克游戏。在这个游戏中，来自世界各地的玩家两两以视频的形式进行对弈。假设这些视频流量通过分布于世界各地的数据中心的软件交换机进行转发，以提供更好的游戏体验。
全世界一共有超过4 000个数据中心，软件交换机就部署在这些数据中心的服务器中，大多数数据中心都位于北美和欧洲。
假设流量的到达模型遵循Poisson分布，并设到达速率为λ=0.1 s-1。文[9]对在线扑克游戏做了详尽的调查分析，并提供了玩家在各个城市的分布情况。在生成流量时，流量传输的源地址和目的地址都从上述城市中选取，并使得流量的分布满足文[9]的统计结果。由于玩家玩游戏的行为具备一定的昼夜变化，因此将一天分割成24个区间，并为每个区间分配一个系数，使得某一个城市的玩家个数在白天时增加，在黑夜时减少。
流量的持续时间分布如图 3所示，其遵循均值μ=3 600 s，标准差σ=1 800 s的正态分布。流量传输速率分布遵循文[10]的测量结果，如图 4所示。
 |
| 图 3 流量的持续时间分布情况 |
| 图选项 |
 |
| 图 4 流量传输速率的分布情况 |
| 图选项 |
利用文[11]提出的算法来计算2个交换机之间是否有直连链路，进而创建覆盖网络。同时利用文[12]提出的算法来估算链路的传输延时。最后参考多协议标签交换(MPLS)算法，为每一个流量选择延时最短的路径进行传输。
2.2 仿真结果尽管仿真测试持续了10 d，但是由于天与天之间的测试结果相似，因此只展示一天24 h内的测量结果。
在仿真实验中，随机选取相应数量的交换机使用交换机维度算法采集流量数据，其通信成本的变化趋势如图 5所示。通信成本随着使用交换机维度算法采集流量数据的交换机数量的增加呈现先下降后上升的趋势。本文提出的OpenCost算法的目的就是要寻找究竟哪些交换机适合用交换机维度算法来采集流量数据，以获得最小的测量通信开销。
 |
| 图 5 通信成本随着使用交换机维度采集流量数据的交换机数量增加的变化情况 |
| 图选项 |
每秒钟大约有380个活跃的流量，同时进行流量转发的交换机数量约为2 400个，使得OpenCost算法需要求解的未知变量个数达到2 400个。由于NLIP问题是NP难问题，当需要尽快完成流量数据采集时，求解含有2 400个未知变量的NLIP问题所耗费的时间无法忽略不计。
图 6所示为OpenCost及OpenCost-Appro算法求解上述动态规划问题所耗费的时间。绝大多数情况下，OpenCost算法需要花费超过20 s来计算最优解。而OpenCost-Appro算法只需要耗费0.015 s就可以计算出次优解。图 6表明OpenCost-Appro算法与OpenCost算法相比，即使网络中活跃流量和交换机数量巨大时依然能够高效地计算出次优解，因此具备一定的高效性和可扩展性。
 |
| 图 6 OpenCost及OpenCost-Appro算法的计算效率对比 |
| 图选项 |
图 7所示为不同算法在进行网络测量时所产生的通信开销。这些算法包括常用的流量维度测量算法，也包括交换机维度测量算法。
 |
| 图 7 不同算法产生的通信开销成本 |
| 图选项 |
流量维度测量算法[3-6]和交换机维度测量算法平均产生每秒60 kB的通信开销。由于交换机维度测量算法只需要为每一个交换机发送一个采集请求报文，因此一般情况下交换机维度的测量算法产生的通信开销要小于流量维度的测量算法。由于很多流量流经多个交换机，因此交换机维度的测量算法可能接收到很多重复的流量数据信息，致使某些时刻流量维度的测量算法产生的通信开销要低于交换机维度的测量算法。
OpenCost算法平均产生27 kB的通信开销，与流量维度的测量算法相比，通信成本降低了55%。计算效率更高的OpenCost-Appro算法也仅仅产生29 kB的通信开销，远小于流量维度的测量算法。图 7表明，本文提出的OpenCost及OpenCost-Appro算法能够有效地降低网络测量时的通信成本。
3 结论为了降低SDN网络中网络测量产生的通信成本，本文提出了OpenCost算法，该算法利用非线性整数规划算法来决定通过哪些交换机采集哪些流量的数据。为了克服OpenCost算法计算效率低的问题，本文进一步提出了基于贪心算法的OpenCost-Appro算法。仿真结果表明：OpenCost算法能够极大地降低网络测量所产生的通信成本，同时OpenCost-Appro算法能够在不显著影响算法性能的前提下极大地降低算法的求解时间。
参考文献
| [1] | 赵俊, 包丛笑, 李星. 基于OpenFlow协议的覆盖网络路由器设计[J]. 清华大学学报(自然科学版), 2018, 58(2): 164-169. ZHAO J, BAO C X, LI X. OpenFlow based software overlay router[J]. Journal of Tsinghua University (Science and Technology), 2018, 58(2): 164-169. (in Chinese) |
| [2] | YU C, LUMEZANU C, ZHANG Y P, et al. Flowsense: Monitoring network utilization with zero measurement cost[C]//Proceedings of the 14th International Conference on Passive and Active Network Measurement. Hong Kong, China: Springer, 2013: 31-41. |
| [3] | YU C, LUMEZANU C, SHARMA A, et al. Software-defined latency monitoring in data center networks[C]//Proceedings of the 16th International Conference on Passive and Active Network Measurement. New York, NY, USA: Springer, 2015: 360-372. |
| [4] | VAN ADRICHEM N L M, DOERR C, KUIPERS F A. OpenNetMon: Network monitoring in OpenFlow software-defined networks[C]//Proceedings of 2014 IEEE Network Operations and Management Symposium (NOMS). Krakow, Poland: IEEE, 2014: 1-8. |
| [5] | CHOWDHURY S R, BARI M F, AHMED R, et al. PayLess: A low cost network monitoring framework for software defined networks[C]//Proceedings of 2014 IEEE Network Operations and Management Symposium (NOMS). Krakow, Poland: IEEE, 2014: 1-9. |
| [6] | TOOTOONCHIAN A, GHOBADI M, GANJALI Y. OpenTM: Traffic matrix estimator for OpenFlow networks[C]//Proceedings of the 11th International Conference on Passive and Active Measurement. Zurich, Switzerland: Springer, 2010: 201-210. |
| [7] | The Numerical Algorithms Group. The NAG library for Python. (2018-05-09). https://www.nag.com/. |
| [8] | CLEGG R, LANDA R, GRIFFIN D, et al. Faces in the clouds:Long-duration, multi-user, cloud-assisted video conferencing[J]. IEEE Transactions on Cloud Computing, 2017. DOI:10.1109/TCC.2017.2680440 |
| [9] | FIEDLER I, WILCKE A C. The market for online poker[R]. Rochester, NY, USA: SSNR, 2014: 7-19. |
| [10] | AMEIGEIRAS P, RAMOS-MUNOZ J J, NAVARRO-ORTIZ J, et al. Analysis and modelling of youtube traffic[J]. Transactions on Emerging Telecommunications Technologies, 2012, 23(4): 360-377. DOI:10.1002/ett.v23.4 |
| [11] | GIOTSAS V, LUCKIE M, HUFFAKER B, et al. Inferring complex AS relationships[C]//Proceedings of the 2014 Conference on Internet Measurement Conference. Vancouver, BC, Canada: ACM, 2014. |
| [12] | LANDA R, ARAú JO J T, CLEGG R G, et al. The large-scale geography of internet round trip times[C]//Proceedings of 2013 IFIP Networking Conference. Brooklyn, NY, USA: IEEE, 2013: 1-9. |
