Tree sketch: An accurate and memory-efficient sketch for network-wide measurement
Tree sketch: An accurate and memory-efficient sketch for network-wide measurement
复制标题
DOI：
10.1016/j.comcom.2022.07.009
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Lei Liu;Tong Ding;Hui Feng;Zhongmin Yan;Xudong Lu
中科院分区：
文献类型：
--
作者：
Lei Liu;Tong Ding;Hui Feng;Zhongmin Yan;Xudong Lu
流量测量为带宽管理和服务质量(QoS)提供基本信息，而服务质量是网络状态发现的推动因素。然而，随着网络流量的爆炸性增长，传统的网络测量方法在内存、计算、精度等方面都面临着挑战，尤其是在高速网络中。网络设备没有足够的CPU或内存资源来采集、统计和分析数据流，这使得测量结果不准确和不可靠。为了解决这个问题，我们设计了一种准确且节省内存的树草图。它由三种不同的结构组成，分别用于大流量检测、分布式拒绝服务(DDoS)攻击检测和超级传播程序检测。提出的重杜鹃算法根据流的大小对流进行分类存储，减少了草图中的哈希冲突。此外，Tree SKETE采用单指令多数据(SIMD)指令来加速数据包处理。实验结果表明，树形素描算法的F1评分为0.997，内存使用量为30KB，比现有的素描算法提高了0.019-0.137。它是主干网络中流量测量的有效工具，并在准确性、速度和内存使用之间提供了良好的折衷。
Traffic measurement provides essential information for bandwidth management and Quality of Service (QoS), which is an enabler of network status discovery. However, with the explosive growth of network traffic, traditional network measurement methods face challenges in terms of memory, computation, accuracy, especially in the high-speed networks. Network devices have no enough CPU or memory resources for collecting, counting and analyzing data streams, which makes measurement results inaccurate and unreliable. To address the problem, we design an accurate and memory-efficient Tree sketch. It consists of three different structures for heavy flow detection, Distributed Denial-of-Service (DDoS) attack detection, super-spreaders detection, respectively. The proposed heavy cuckoo algorithm stores the flows in categories according to their flow sizes reducing hash collisions in the sketch. Besides, Tree sketch employs the Single Instruction Multiple Data (SIMD) instructions to speed up packet processing. Experimental results show that F1 score of Tree sketch is 0.997 with 30 KB memory usage in heavy hitter detection, which is 0.019–0.137 higher than the state-of-the-art sketch algorithms. It is an efficient tool of traffic measurement in the backbone network and provides a good trade-off among accuracy, speed and memory usage.