HeavyCuckoo: A Flexible and Fast Sketch for Heavy Hitter Detection in High-Speed Networks
Chao Cui, He Huang, Zhaojie Wang, Yu-E Sun, Hanwen Zhang · 2024
Heavy hitter detection is a fundamental network measurement task that provides critical support for many network applications. However, achieving flexible and fast heavy hitter detection in massive network traffic is challenging. Existing works generally perform detection by tracking large flows that may become heavy hitters, but they struggle to accurately identify these large flows, leading to poor accuracy. In this paper, we propose an efficient detection algorithm called HeavyCuckoo, which shows high flexibility and fast processing. We track only those large flows likely to be heavy hitters, replacing small flows of limited use for detection by exploring the activity of flow arrivals. During replacement, we utilize a tailored Conservative Replacement strategy and a tailored Selective Cuckoo Hash strategy to avoid large flows from being replaced incorrectly. We conduct theoretical analyses of memory space complexity and time complexity, and provide the error bound for heavy hitter detection. Our proposed algorithm is evaluated on real-world Internet traffic traces. Experimental results show that, compared to the prior art, the algorithm improves the Fβ-score by 56.94% and achieves 1.4724 times throughput.