Aegis Sketch: High-Throughput and Accurate Top-k Elephant Flows Detection in Large-Scale Parallel Network Traffic Processing

In large-scale parallel network traffic processing systems, detecting Top-k elephant flows is essential for real-time monitoring and traffic management. However, under the dual constraints of high update rates and limited memory, existing approaches struggle to balance throughput and accuracy. Many fail to exploit the heavy-tailed distribution of network traffic, resulting in frequent hash collisions and irreversible eviction errors that severely limit detection performance. Current methods fall into two categories: counter-based approaches, which maintain a candidate set (e.g., a min-heap) for high accuracy but suffer from high synchronization overhead and unrecoverable evictions, and sketch-based approaches, which are naturally parallelizable but prone to accuracy loss under hash collisions. To address these challenges, we propose Aegis Sketch, a novel framework for high-throughput and accurate Top- k elephant flow detection in large-scale parallel network traffic processing. Aegis Sketch incorporates an ordered storage mechanism that fundamentally reduces hash collisions without incurring additional structural overhead, thereby significantly improving throughput and accuracy. In addition, a multi-party competitive replacement policy prioritizes the preservation of true elephant flows during contention, effectively mitigating the accuracy loss caused by irreversible evictions. Experiments on real-world traffic traces show that Aegis Sketch outperforms existing methods such as Elastic Sketch and OneSketch in throughput, detection accuracy, and memory efficiency, achieving up to 1.35 times higher throughput and 22 % higher precision. These results demonstrate its effectiveness and efficiency for large-scale parallel network traffic processing.