因为网络测量在软件定义网络中扮演着非常重要的角色，所以越来越多的测量算法相继被提出。根据测量方式，这些算法被分成两类：周期测量和自适应测量算法。无论何种算法，如果为每一个流量都发送数据采集请求会产生很大的通信开销，进而增加交换机的负载。为了降低采集流量数据的通信开销，该文首先提出一种基于非线性整数动态规划算法OpenCost，来决定每个流量的数据通过哪个交换机来采集。其次，为了降低算法的运行时间，提出一种贪心算法来近似求解上述最优化问题。最后，为了评估算法性能，搭建了仿真环境并进行了详细的仿真测试。测试结果表明：与其他流量数据请求算法相比，优化算法OpenCost可以降低系统采集流量数据通信开销的55%。
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.
[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.
[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.
