SDN中基于蚁群优化的网络测量节点选择算法

doi:10.19678/j.issn.1000-3428.0062248

摘要/Abstract

摘要： 在软件定义网络（SDN）中，当流传输路径信息获取受限时，现有的测量节点选择算法只能基于网络拓扑的中心性指标进行测量节点选择，存在测量精度较低、测量负载不均衡、运行时间长等问题。将SDN网络中测量节点选择问题抽象为最小顶点覆盖模型，提出一种基于蚁群优化的测量节点选择算法ACO-NS。利用复杂网络的度分布理论缩减状态转移过程中的候选集规模，同时设计一种信息素局部增强-全局挥发机制，增大可行解的信息素浓度，提高算法的准确度和收敛度，并且缩短搜索时间。通过OpenFlow消息在线计算测量节点的负载，采用邻域搜索策略对过载节点进行筛选和替换，以降低过载处理的时间。实验结果表明，与ACO算法相比，该算法的准确度和收敛度分别提高56.7和28.2个百分点，且单位时间内的过载处理开销降低79.8个百分点，具有较高的测量精度。

关键词: 网络测量, 测量节点选择, 蚁群优化, 邻域搜索, 软件定义网络

Abstract: In Software Defined Network (SDN), when access to stream transmission path information is limited, existing measurement node selection algorithms can only select nodes based on the central index of the network topology, resulting in low measurement accuracy, an unbalanced measurement load, and a long run time.The measurement node selection problem in SDN network is abstracted as the minimum vertex coverage model, and a measurement node selection algorithm ACO-NS based on Ant Colony Optimization(ACO) is proposed.The degree distribution theory of complex networks is used to reduce the size of candidate sets in the state transition process.Simultaneously, a pheromone local enhancement global volatilization mechanism is designed to increase the pheromone concentration of feasible solutions, improve the accuracy and convergence of the algorithm, and shorten the search time.The load of the measurement node is calculated online through the OpenFlow message, and the Neighborhood Search(NS) strategy is used to filter and replace the overloaded nodes to further reduce the time overhead of overload processing.The experimental results show that compared to the ACO algorithm, the proposed algorithm improves the accuracy and convergence by 56.7 and 28.2 percentage points, respectively, and has high measurement accuracy, and the unit time overhead is reduced by 79.8 percentage points.

Key words: network measurement, measurement node selection, Ant Colony Optimization(ACO), Neighborhood Search(NS), Software Defined Network(SDN)

中图分类号:

TP393.07

叶和元, 韩俐, 孙士民. SDN中基于蚁群优化的网络测量节点选择算法[J]. 计算机工程, 2022, 48(5): 191-199.

YE Heyuan, HAN Li, SUN Shimin. Network Measurement Node Selection Algorithm Based on Ant Colony Optimization in SDN[J]. Computer Engineering, 2022, 48(5): 191-199.

http://www.ecice06.com/CN/Y2022/V48/I5/191

图/表 10

20220805181508

20220805181512

20220805181516

20220805181522

20220805181526

20220805181533

20220805181538

20220805181543

20220805181547

20220805181556

参考文献

[1] WU X B, LI P L, RAN Y Y, et al.Network measurement for 100 GbE network links using multicore processors[J].Future Generation Computer Systems, 2018, 79(1):180-189.
[2] 戴冕, 程光, 周余阳.软件定义网络的测量方法研究[J].软件学报, 2019, 30(6):1853-1874. DAI M, CHENG G, ZHOU Y Y.Survey on measurement methods in software-defined networking[J].Journal of Software, 2019, 30(6):1853-1874.(in Chinese)
[3] 张恒, 蔡志平, 李阳.SDN网络测量技术综述[J].中国科学:信息科学, 2018, 48(3):293-314. ZHANG H, CAI Z P, LI Y.An overview of software-defined network measurement technologies[J].Chinese Science:Information Science, 2018, 48(3):293-314.(in Chinese)
[4] TOOTOONCHIAN A, GHOBADI M, GANJALI Y.OpenTM:traffic matrix estimator for OpenFlow networks[C]//Proceedings of International Conference on Passive and Active Network Measurement.Berlin, Germany:Springer, 2010:201-210.
[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 IEEE Network Operations and Management Symposium.Washington D.C., USA:IEEE Press, 2014:1-9.
[6] DENG J, CAI H, CHEN S, et al.Improved flow awareness among edge nodes by learning-based sampling in software defined networks[J].Mobile Networks and Applications, 2019, 29:1-10.
[7] ZHANG Y, TAN Y, JIE T, et al.TOHIP:a topology-hiding multipath routing protocol in mobile Ad Hoc network[J].Ad Hoc Networks, 2014, 21(5):109-122.
[8] YOON S, HA T, KIM S, et al.Scalable traffic sampling using centrality measure on software-defined networks[J].IEEE Communications Magazine, 2017, 55(7):43-49.
[9] PERDICES D, MUELAS D, PEDRO L D, et al.Network performance monitoring with flexible models of multi-point passive measurements[C]//Proceedings of the 14th International Conference on Network and Service Management.Washington D.C., USA:IEEE Press, 2018:1-9.
[10] COCIGLIO M, FIOCCOLA G, MARCHETTO G, et al.Multipoint passive monitoring in packet networks[J].IEEE Transactions on Networking, 2019, 27(6):2377-2390.
[11] LI R Z, HU S L, ZHANG H C, et al.An efficient local search framework for the minimum weighted vertex cover problem[J].Information Sciences, 2016, 372(1):428-445.
[12] WANG L Z, HU S L, LI M Y, et al.An exact algorithm for minimum vertex cover problem[J].Mathematics, 2019, 7(7):1-8.
[13] GAO W R, FRIEDRICH T, NEUMANN F, et al.Randomized greedy algorithms for covering problems[C]//Proceedings of the Genetic and Evolutionary Computation Conference.New York, USA:ACM Press, 2018:309-315.
[14] GUAN B X, ZHAO Y H, LI Y.An improved ant colony optimization with an automatic updating mechanism for constraint satisfaction problems[J].Expert Systems with Applications, 2021, 164:1-7.
[15] HU S L, WU X L, LIU H, et al.Multi-objective neighborhood search algorithm based on decomposition for multi-objective minimum weighted vertex cover problem[J].Sustainability, 2019, 11(13):1-21.
[16] YU C, LUMEZANU C, SHARMA A, et al.Software-defined latency monitoring in data center networks[C]//Proceedings of International Conference on Passive and Active Network Measurement.Berlin, Germany:Springer, 2015:360-372.
[17] VAN ADRICHEM N L M, DOERR C, KUIPERS F A.OpenNetMon:network monitoring in OpenFlow software-defined networks[C]//Proceedings of IEEE Network Operations and Management Symposium.Washington D.C., USA:IEEE Press, 2014:1-8.
[18] 张荣, 杨谈, 金跃辉, 等.分布式网络测量中测量节点的智能选择算法[J].计算机科学, 2015, 42(9):70-77. ZHANG R, YANG T, JIN Y H, et al.Intelligent selection algorithm of measurement nodes in distributed network measurement[J].Computer Science, 2015, 42(9):70-77.(in Chinese)
[19] DIEGO K, PAULO E V, SIAMAK A.Software-defined networking:a comprehensive survey[J].Proceedings of the IEEE, 2015, 103(1):14-76.
[20] 覃远年, 梁仲华.蚁群算法研究与应用的新进展[J].计算机工程与科学, 2019, 41(1):173-184. QIN Y N, LIANG Z H.New progress of the ant colony algorithm in research and applications[J].Computer Engineering and Science, 2019, 41(1):173-184.(in Chinese)
[21] EBADINEZHAD S.DEACO:adopting dynamic evaporation strategy to enhance ACO algorithm for the traveling salesman problem[J].Engineering Applications of Artificial Intelligence, 2020, 92:1-10.
[22] MIAO C W, CHEN G Z, YAN C L, et al.Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm[J].Computers and Industrial Engineering, 2021, 156:1-10.
[23] QU W, WEN D L, FENG X S.A dynamic energy-saving routing strategy based on ant colony optimization[C]//Proceedings of the 29th Chinese Control and Decision Conference.Chongqing, China:[s.n.], 2018:2079-2084.
[24] JOVANOVIC R, TUBA M.An ant colony optimization algorithm with improved pheromone correction strategy for the minimum weight vertex cover problem[J].Applied Soft Computing, 2011, 11(8):5360-5366.
[25] LI X L, WANG Y.Scheduling batch processing machine using max-min ant system algorithm improved by a local search method[EB/OL].[2021-07-01].https://downloads.hindawi.com/journals/mpe/2018/3124182.pdf.
[26] SUN M, WANG L, HE Y.An optimization algorithm for multiple measurement points placement in SDN[C]//Proceedings of IEEE International Conference on Computer and Communication Systems.Washington D.C., USA:IEEE Press, 2019:203-207.
[27] HARK R, GHANMI M, KAR S, et al.Representative measurement point selection to monitor software-defined networks[C]//Proceedings of the 43rd Conference on Local Computer Networks.Washington D.C., USA:IEEE Press, 2018:511-518.
[28] MA F, LUO X D, WANG P.Random growth networks with exponential degree distribution[J].Chaos, 2020, 30:1-11.

选择文件类型/文献管理软件名称

选择包含的内容