微信服务号

微信订阅号

2025年5月31日 23:37 星期六
首页 > 过刊浏览>2024年第35卷第2期 >852-871. DOI:10.13328/j.cnki.jos.006938
PDF HTML阅读 XML下载 导出引用 引用提醒
网络重要流检测方法综述
作者:
基金项目:

国家自然科学基金(62172206)


Survey on Network Heavy Hitter Detection Methods
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [62]
    • |
  • 相似文献
    • | | |
  • 文章评论
    摘要:

    网络的管理与监测是网络领域的重要话题, 这一领域的相关技术通常也称为网络测量(network measurement). 网络重要流检测(network heavy hitter detection)是网络测量的一项关键技术, 也是研究对象. 重要流指占用网络资源(如带宽或发送的数据包数量)超过某一给定标准的流, 检测重要流有助于快速识别网络异常, 提升网络运行效率, 但链路的高速化为其实现带来了挑战. 按出现时间顺序, 可将重要流检测方法划分为两大类: 基于传统网络框架的和基于软件定义网络(SDN)框架的. 围绕网络重要流检测相关的框架与算法, 系统地总结其发展过程与研究现状, 并尝试给出其未来可能的发展方向.

    Abstract:

    Network management and monitoring are crucial topics in the network field, with the technologies used to achieve this being referred to as network measurement. In particular, network heavy hitter detection is an important technique of network measurement, and it is analyzed in this study. Heavy hitters are flows that exceed an established threshold in terms of occupied network resources (bandwidth or the number of packets transmitted). Detecting heavy hitters can contribute to quick anomaly detection and more efficient network operation. However, the implementation of heavy hitter detection is impacted by high-speed links. Traditional methods and software defined network (SDN)-based methods are two categories of heavy hitter detection methods that have been developed over time. This study reviews the related frameworks and algorithms, systematically summarizes the development and current status, and finally tries to predict future research directions of network heavy hitter detection.

    参考文献
    [1] Vinton GC. Formation of Network Measurement Group (NMG). IETF RFC 323, 1972.
    [2] Leland WE, Taqqu MS, Willinger W, Wilson DV. On the self-similar nature of Ethernet traffic. ACM SIGCOMM Computer Communication Review, 1993, 23(4): 183-193. [doi: 10.1145/167954.166255]
    [3] Vern E. Measurements and analysis of end-to-end Internet dynamics [Ph.D. Thesis]. Berkeley: University of California, 1997.
    [4] Zhou Y, Sun C, Liu HH, Miao R, Bai S, Li B, Zheng ZL, Zhu LJ, Shen Z, Xi YQ, Zhang PC, Cai D, Zhang M, Xu MW. Flow event telemetry on programmable data plane. In: Proc. of the 2020 Annual Conf. of the ACM Special Interest Group on Data Communication on the Applications, Technologies, Architectures, and Protocols for Computer Communication. ACM, 2020. 76-89.
    [5] Dean J, Ghemawat S. MapReduce: Simplified data processing on large clusters. Communications of the ACM, 2008, 51(1): 107-113. [doi: 10.1145/1327452.1327492]
    [6] Zaharia M, Chowdhury M, Franklin MJ, Shenker S, Stoica I. Spark: Cluster computing with working sets. In: Proc. of the 2nd USENIX Conf. on Hot Topics in Cloud Computing. Boston: USENIX Association, 2010. 1-7
    [7] Kreutz D, Ramos FMV, Veríssimo PE, Rothenberg CE, Azodolmolky S, Uhlig S. Software-defined networking: A comprehensive survey. Proceedings of the IEEE, 2015, 103(1): 14-76. [doi: 10.1109/JPROC.2014.2371999]
    [8] Soliman MA, Ilyas IF, Chang KCC. Top-k query processing in uncertain databases. In: Proc. of the 23rd IEEE Int’l Conf. on Data Engineering. Istanbul: IEEE, 2007. 896-905.
    [9] Mirylenka K, Cormode G, Palpanas T, Srivastava D. Conditional heavy hitters: Detecting interesting correlations in data streams. The VLDB Journal, 2015, 24(3): 395-414. [doi: 10.1007/s00778-015-0382-5]
    [10] Zhang Y, Fang BX, Zhang YZ. Identifying heavy hitters in high-speed network monitoring. Science China Information Sciences, 2010, 53(3): 659-676. [doi: 10.1007/s11432-010-0053-5]
    [11] Estan C, Varghese G. New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice. ACM Transactions on Computer Systems, 2003, 21(3): 270-313. [doi: 10.1145/859716.859719]
    [12] Yang T, Jiang J, Liu P, Huang Q, Gong JZ, Zhou Y, Miao R, Li XM, Uhlig S. Elastic Sketch: Adaptive and fast network-wide measurements. In: Proc. of the 2018 Conf. of the ACM Special Interest Group on Data Communication. Budapest: ACM, 2018. 561-575.
    [13] Yang T, Zhang HW, Li JY, Gong JZ, Uhlig S, Chen SG, Li XM. HeavyKeeper: An accurate algorithm for finding top-k elephant flows. IEEE/ACM Transactions on Networking, 2019, 27(5): 1845-1858. [doi: 10.1109/TNET.2019.2933868]
    [14] 周爱平, 程光, 郭晓军. 高速网络流量测量方法. 软件学报, 2014, 25(1): 135-153. http://www.jos.org.cn/1000-9825/4445.htm
    Zhou AP, Cheng G, Guo XJ. High-speed network traffic measurement method. Ruan Jian Xue Bao/Journal of Software, 2014, 25(1): 135-153 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4445.htm
    [15] 戴冕, 程光, 周余阳. 软件定义网络的测量方法研究. 软件学报, 2019, 30(6): 1853-1874. http://www.jos.org.cn/1000-9825/5832.htm
    Dai M, Cheng G, Zhou YY. Survey on measurement methods in software-defined networking. Ruan Jian Xue Bao/Journal of Software, 2019, 30(6): 1853-1874 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5832.htm
    [16] Tan LZ, Su W, Zhang W, Lv JH, Zhang ZY, Miao JY, Liu XX, Li N. In-band network telemetry: A survey. Computer Networks, 2021, 186: 107763. [doi: 10.1016/j.comnet.2020.107763]
    [17] Mohan V, Reddy YRJ, Kalpana K. Active and passive network measurements: A survey. International Journal of Computer Science and Information Technologies, 2011, 2(4): 1372-1385.
    [18] Wang M, Li B, Li Z. sFlow: Towards resource-efficient and agile service federation in service overlay networks. In: Proc. of the 24th Int’l Conf. on Distributed Computing Systems. Tokyo: IEEE, 2004. 628-635.
    [19] CISCO. Introduction to Cisco IOS NetFlow—A technical overview. 2012. https://www.cisco.com/c/en/us/products/collateral/ios-nx-os-software/ios-netflow/prod_white_paper0900aecd80406232.html
    [20] Metwally A, Agrawal D, El Abbadi A. Efficient computation of frequent and Top-k elements in data streams. In: Proc. of the 10th Int’l Conf. on Database Theory. Edinburgh: Springer, 2005. 398-412.
    [21] Karp RM, Shenker S, Papadimitriou CH. A simple algorithm for finding frequent elements in streams and bags. ACM Transactions on Database Systems, 2003, 28(1): 51-55. [doi: 10.1145/762471.762473]
    [22] Demaine ED, López-Ortiz A, Munro JI. Frequency estimation of internet packet streams with limited space. In: Proc. of the 10th European Symp. on Algorithms. Rome: Springer, 2002. 348-360.
    [23] Manku GS, Motwani R. Approximate frequency counts over data streams. In: Proc. of the 28th Int’l Conf. on Very Large Data Bases. Hong Kong: VLDB Endowment, 2002. 346-357.
    [24] Ting D. Data sketches for disaggregated subset sum and frequent item estimation. In: Proc. of the 2018 Int’l Conf. on Management of Data. Houston: Association for Computing Machinery, 2018. 1129-1140.
    [25] Charikar M, Chen K, Farach-Colton M. Finding frequent items in data streams. In: Proc. of the 29th Int’l Colloquium on Automata, Languages, and Programming. Malaga: Springer, 2002. 693-703.
    [26] Cormode G, Muthukrishnan S. An improved data stream summary: The count-min sketch and its applications. Journal of Algorithms, 2005, 55(1): 58-75. [doi: 10.1016/j.jalgor.2003.12.001]
    [27] Yu ML, Jose L, Miao R. Software defined traffic measurement with OpenSketch. In: Proc. of the 10th USENIX Conf. on Networked Systems Design and Implementation. Lombard: USENIX Association, 2013. 29-42.
    [28] Li JZ, Li ZK, Xu YF, Jiang SQ, Yang T, Cui B, Dai YF, Zhang G. WavingSketch: An unbiased and generic sketch for finding Top-k items in data streams. In: Proc. of the 26th ACM SIGKDD Int’l Conf. on Knowledge Discovery & Data Mining. Association for Computing Machinery, 2020. 1574-1584.
    [29] Li YL, Miao R, Kim C, Yu ML. FlowRadar: A better NetFlow for data centers. In: Proc. of the 13th USENIX Conf. on Networked Systems Design and Implementation. Santa Clara: USENIX Association, 2016. 311-324.
    [30] Liu ZX, Manousis A, Vorsanger G, Sekar V, Braverman V. One sketch to rule them all: Rethinking network flow monitoring with UnivMon. In: Proc. of the 2016 ACM SIGCOMM Conf. Florianopolis: Association for Computing Machinery, 2016. 101-114.
    [31] Yang T, Gong JZ, Zhang HW, Zou L, Shi L, Li XM. HeavyGuardian: Separate and guard hot items in data streams. In: Proc. of the 24th ACM SIGKDD Int’l Conf. on Knowledge Discovery & Data Mining. London: Association for Computing Machinery, 2018. 2584-2593.
    [32] Zhang YD, Li JY, Lei YT, Yang T, Li ZT, Zhang G, Cui B. On-off sketch: A fast and accurate sketch on persistence. Proceedings of the VLDB Endowment, 2020, 14(2): 128-140. [doi: 10.14778/3425879.3425884]
    [33] Huang Q, Sun HF, Lee PPC, Bai W, Zhu F, Bao YG. OmniMon: Re-architecting network telemetry with resource efficiency and full accuracy. In: Proc. of the 2020 Annual Conf. of the ACM Special Interest Group on Data Communication on the Applications, Technologies, Architectures, and Protocols for Computer Communication. New York: Association for Computing Machinery, 2020. 404-421.
    [34] Kučera J, Popescu DA, Wang H, Moore A, Kořenek J, Antichi G. Enabling event-triggered data plane monitoring. In: Proc. of the Symp. on SDN Research. San Jose: Association for Computing Machinery, 2020. 14-26.
    [35] Sivaraman V, Narayana S, Rottenstreich O, Muthukrishnan S, Rexford J. Heavy-hitter detection entirely in the data plane. In: Proc. of the 2017 Symp. on SDN Research. Santa Clara: Association for Computing Machinery, 2017. 164-176.
    [36] Zhang YD, Liu ZX, Wang RX, Yang T, Li JZ, Miao RJ, Liu P, Zhang RW, Jiang JC. CocoSketch: High-performance sketch-based measurement over arbitrary partial key query. In: Proc. of the 2021 ACM SIGCOMM Conf. Association for Computing Machinery, 2021. 207-222.
    [37] Lee S, Levanti K, Kim HS. Network monitoring: Present and future. Computer Networks, 2014, 65: 84-98. [doi: 10.1016/j.comnet.2014.03.007]
    [38] Leiner BM, Cerf VG, Clark DD, Kahn RE, Kleinrock L, Lynch DC, Postel J, Roberts LG, Wolff S. A brief history of the internet. ACM SIGCOMM Computer Communication Review, 2009, 39(5): 22-31. [doi: 10.1145/1629607.1629613]
    [39] McKeown N, Anderson T, Balakrishnan H, Parulkar G, Peterson L, Rexford J, Shenker S, Turner J. OpenFlow: Enabling innovation in campus networks. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 69-74. [doi: 10.1145/1355734.1355746]
    [40] Doria A, Salim JH, Haas R, Khosravi H, Wang W, Dong L, Gopal R, Halpern J. Forwarding and Control Element Separation (ForCES) Protocol Specification. IETF RFC 5810, 2010.
    [41] Pfaff B, Davie B. The Open vSwitch Database Management Protocol. IETF RFC 7047, 2013.
    [42] Pfaff B, Pettit J, Koponen T, Jackson EJ, Zhou A, Rajahalme J, Gross J, Wang A, Stringer J, Shelar P, Amidon K, Casado M. The design and implementation of Open vSwitch. In. Proc. of the 12th USENIX Symp. on Networked Systems Design and Implementation. Oakland: USENIX Association, 2015. 117-130.
    [43] Lockwood JW, McKeown N, Watson G, Gibb G, Hartke P, Naous J, Raghuraman R, Luo J. NetFPGA—An open platform for gigabit-rate network switching and routing. In: Proc. of the 2007 IEEE Int’l Conf. on Microelectronic Systems Education. San Diego: IEEE, 2007. 160-161.
    [44] Bosshart P, Daly D, Gibb G, Izzard M, McKeown N, Rexford J, Schlesinger C, Talayco D, Vahdat A, Varghese G, Walker D. P4: Programming protocol-independent packet processors. ACM SIGCOMM Computer Communication Review, 2014, 44(3): 87-95. [doi: 10.1145/2656877.2656890]
    [45] Estan C, Keys K, Moore D, Varghese G. Building a better NetFlow. ACM SIGCOMM Computer Communication Review, 2004, 34(4): 245-256. [doi: 1030194.1015495]
    [46] Whang KY, Vander-Zanden BT, Taylor HM. A linear-time probabilistic counting algorithm for database applications. ACM Transactions on Database Systems, 1990, 15(2): 208-229. [doi: 10.1145/78922.78925]
    [47] Durand M, Flajolet P. Loglog counting of large cardinalities. In: Proc. of the 11th European Symp. on Algorithms. Budapest: Springer, 2003. 605-617.
    [48] Heule S, Nunkesser M, Hall A. HyperLogLog in practice: Algorithmic engineering of a state of the art cardinality estimation algorithm. In: Proc. of the 16th Int’l Conf. on Extending Database Technology. Genoa: ACM, 2013. 683-692.
    [49] Misra J, Gries D. Finding repeated elements. Science of Computer Programming, 1982, 2(2): 143-152. [doi: 10.1016/0167-6423(82)90012-0]
    [50] Bloom BH. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 1970, 13(7): 422-426. [doi: 10.1145/362686.362692]
    [51] Agarwal PK, Cormode G, Huang ZF, Phillips JM, Wei ZW, Yi K. Mergeable summaries. ACM Transactions on Database Systems, 2013, 38(4): 26. [doi: 10.1145/2500128]
    [52] Mandal A, Jiang H, Shrivastava A, Sarkar V. Topkapi: Parallel and fast sketches for finding Top-k frequent elements. In: Proc. of the 32nd Int’l Conf. on Neural Information Processing Systems. Montréal: Curran Associates Inc., 2018. 10921-10931.
    [53] Lu JY, Pan T, He S, Miao M, Zhou GZ, Qi YN, Lyu B, Zhu SM. A two-stage heavy hitter detection system based on CPU spikes at cloud-scale gateways. In: Proc. of the 41st Int’l Conf. on Distributed Computing Systems. Washington: IEEE, 2021. 348-358.
    [54] Pan T, Yu NB, Jia CH, Pi JW, Xu L, Qiao YS, Li ZG, Liu K, Lu J, Lu JY, Song EG, Zhang J, Huang T, Zhu SM. Sailfish: Accelerating cloud-scale multi-tenant multi-service gateways with programmable switches. In: Proc. of the 2021 ACM SIGCOMM Conf. ACM, 2021. 194-206.
    [55] Suh J, Kwon TT, Dixon C, Felter W, Carter J. OpenSample: A low-latency, sampling-based measurement platform for commodity SDN. In: Proc. of the 34th IEEE Int’l Conf. on Distributed Computing Systems. Madrid: IEEE, 2014. 228-237.
    [56] Chen XQ, Landau-Feibish S, Braverman M, Rexford J. BeauCoup: Answering many network traffic queries, one memory update at a time. In: Proc. of the 2020 Annual Conf. of the ACM Special Interest Group on Data Communication on the Applications, Technologies, Architectures, and Protocols for Computer Communication. ACM, 2020. 226-239.
    [57] Harrison R, Cai QZ, Gupta A, Rexford J. Network-wide heavy hitter detection with commodity switches. In: Proc. of the 2018 Symp. on SDN Research. Los Angeles: ACM, 2018. 8.
    [58] Huang Q, Sheng SY, Chen X, Bao YG, Zhang R, Xu YW, Zhang G. Toward nearly-zero-error sketching via compressive sensing. In: Proc. of the 18th USENIX Symp. on Networked Systems Design and Implementation. USENIX Association, 2021. 1027-1044.
    [59] Høiland-Jørgensen T, Brouer JD, Borkmann D, Fastabend J, Herbert T, Ahern D, Miller D. The eXpress data path: Fast programmable packet processing in the operating system kernel. In: Proc. of the 14th Int’l Conf. on Emerging Networking Experiments and Technologies. Heraklion: ACM, 2018. 54-66.
    [60] Gebara N, Lerner A, Yang MR, Yu ML, Costa P, Ghobadi M. Challenging the stateless quo of programmable switches. In: Proc. of the 19th ACM Workshop on Hot Topics in Networks. ACM, 2020. 153-159.
    相似文献
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

钱昊,郑嘉琦,陈贵海.网络重要流检测方法综述.软件学报,2024,35(2):852-871

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2022-03-11
  • 最后修改日期:2022-07-27
  • 在线发布日期: 2023-08-23
  • 出版日期: 2024-02-06
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号