计算机科学 ›› 2025, Vol. 52 ›› Issue (2): 268-278.doi: 10.11896/jsjkx.240900059
王艺洁1, 高国举1, 孙玉娥2, 黄河1
WANG Yijie1, GAO Guoju1, SUN Yu'e2, HUANG He1
摘要： 在软件定义网络(SDN)中,统计流基数信息对于流量工程、流量重路由和攻击检测等很多应用都具有重要作用。现有的研究工作主要分为在单交换机上部署测量结构和多交换机协同测量两类。然而,这两类方案都无法实现全网流量覆盖,并且多交换机协同测量通常采用每个交换机独立测量再合并的方式,容易导致重复计数。为了解决上述问题,提出了一种基于分布式Sketch的流基数估计方法。该方法充分利用SDN控制平面集中控制的优势,协同利用每条流的最长连续公共子路径上的交换机,以构建该流的逻辑层计数结构。同时,建立了每条流从逻辑层计数结构到物理交换机空间的映射,使参与计数的交换机可以根据自身状态和实际负载情况动态调整映射区间,以实现全网交换机之间的负载均衡。以vHLL算法为例,实现了一个分布式流基数估计方法的原型,并在四元Fat-Tree网络拓扑下使用真实网络流量数据集进行了实验评估。实验结果表明,所提方法能够有效实现全网每流基数估计,在准确性方面,其ARE和AAE值最多优于对比实验方法94.7%和93.8%;在负载均衡方面,该方法充分利用全网所有交换机,其归一化后的平均数据包负载为0.394,低于所有对比方法,表现良好。
中图分类号:
| [1]HONG C Y,KANDULA S,MAHAJAN R,et al.Achievinghigh utilization with software-driven WAN[C]//Proceedings of the ACM SIGCOMM 2013 Conference on SIGCOMM.New York:Association for Computing Machinery,2013:15-26. [2]JAIN S,KUMAR A,MANDAL S,et al.B4:Experience with a globally-deployed software defined WAN[J].ACM SIGCOMM Computer Communication Review,2013,43(4):3-14. [3]XU H,YU Z,LI X Y,et al.Joint route selection and updatescheduling for low-latency update in SDNs[J].IEEE/ACM Transactions on Networking,2017,25(5):3073-3087. [4]XU H,HUANG H,CHEN S,et al.Achieving high scalability through hybrid switching in software-defined networking[J].IEEE/ACM Transactions on Networking,2018,26(1):618-632. [5]LIU Z,MANOUSIS A,VORSANGER G,et al.One sketch to rule them all:Rethinking network flow monitoring with univmon[C]//Proceedings of the 2016 ACM SIGCOMM Confe-rence.New York:Association for Computing Machinery,2016:101-114. [6]YANG T,ZHANG H,LI J,et al.HeavyKeeper:an accurate algorithm for finding Top-$ k $ elephant flows[J].IEEE/ACM Transactions on Networking,2019,27(5):1845-1858. [7]ZHAO B,LI X,TIAN B,et al.Dhs:Adaptive memory layout organization of sketch slots for fast and accurate data stream processing[C]//Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining.New York:Association for Computing Machinery,2021:2285-2293. [8]YANG T,JIANG J,LIU P,et al.Elastic sketch:Adaptive and fast network-wide measurements[C]//Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication.New York:Association for Computing Machinery,2018:561-575. [9]LI T,CHEN S,LUO W,et al.Scan detection in high-speed networks based on optimal dynamic bit sharing[C]//2011 Procee-dings IEEE INFOCOM.Montreal:IEEE,2011:3200-3208. [10]XIAO Q,CHEN S,ZHOU Y,et al.Cardinality estimation for elephant flows:A compact solution based on virtual register sharing[J].IEEE/ACM Transactions on Networking,2017,25(6):3738-3752. [11]JIA P,WANG P,ZHANG Y,et al.Accurately estimating user cardinalities and detecting super spreaders over time[J].IEEE Transactions on Knowledge and Data Engineering,2020,34(1):92-106. [12]ZHANG H,HUANG H,SUN Y E,et al.MIME:Fast and Accurate Flow Information Compression for Multi-Spread Estimation[C]//2023 IEEE 31st International Conference on Network Protocols(ICNP).Montreal:IEEE,2023:1-11. [13]JING X,HAN H,YAN Z,et al.SuperSketch:A multi-dimen-sional reversible data structure for super host identification[J].IEEE Transactions on Dependable and Secure Computing,2021,19(4):2741-2754. [14]BASAT R B,EINZIGER G,TAYH B.Cooperative network-wide flow selection[C]//2020 IEEE 28th International Confe-rence on Network Protocols(ICNP).Montreal:IEEE,2020:1-11. [15]AL-FARES M,LOUKISSAS A,VAHDAT A.A scalable,commodity data center network architecture[J].ACM SIGCOMM Computer Communication Review,2008,38(4):63-74. [16]LI Y,YU X,YANG Y,et al.Pyramid family:Generic frameworks for accurate and fast flow size measurement[J].IEEE/ACM Transactions on Networking,2021,30(2):586-600. [17]ESTAN C,VARGHESE G,FISK M.Bitmap algorithms forcounting active flows on high speed links[C]//Proceedings of the 3rd ACM SIGCOMM Conference on Internet Measurement.New York:Association for Computing Machinery,2003:153-166. [18]FLAJOLET P,MARTIN G N.Probabilistic counting algorithms for data base applications[J].Journal of Computer and System Sciences,1985,31(2):182-209. [19]DURAND M,FLAJOLET P.Loglog counting of large cardinali-ties[C]//Algorithms-ESA 2003:11th Annual European Symposium,Budapest,Hungary,September 16-19,2003.Proceedings 11.Berlin Heidelberg:Springer,2003:605-617. [20]FLAJOLET P,FUSY É,GANDOUET O,et al.Hyperloglog:the analysis of a near-optimal cardinality estimation algorithm[J] Discrete Mathematics & Theoretical Computer Science,2007:137-156.https://dmtcs.episciences.org/3545/pdf. [21]DU Y,HUANG H,SUN Y E,et al.A Better Cardinality Estimator with Fewer Bits,Constant Update Time,and Mergeability[C]//IEEE INFOCOM 2023－IEEE Conference on Computer Communications.Montreal:IEEE,2023:1-10. [22]TANG L,HUANG Q,LEE P P C.SpreadSketch:Toward in-vertible and network-wide detection of superspreaders[C]//IEEE INFOCOM 2020－IEEE Conference on Computer Communications.Montreal:IEEE,2020:1608-1617. [23]JING X,YAN Z,HAN H,et al.ExtendedSketch:Fusing network traffic for super host identification with a memory efficient sketch[J].IEEE Transactions on Dependable and Secure Computing,2021,19(6):3913-3924. [24]CAIDA.Anonymized internet traces 2019 [EB/OL].(2019-01)[2024-08-08].https://catalog.caida.org/details/dataset/passive_2019_pcap. |
|
||
首页