MEC-Sketch: Memory-Efficient Per-Flow Cardinality Measurement in High-Speed Networks

Per-Flow cardinality measurement in high-speed networks is essential for network security and traffic analysis applications. Flow cardinality refers to the number of distinct elements within a flow, such as the number of unique destination IPs associated with a given source IP. While extensive research has been conducted on single-flow cardinality estimation, achieving accurate per-flow cardinality measurement with real-time performance and low memory overhead remains challenging in large-scale network environments, particularly given the highly skewed distribution of flow cardinalities where mouse flows with smaller cardinalities dominate, and elephant flows with larger cardinalities are fewer. This paper introduces MEC-Sketch, a memory-efficient cardinality estimation data structure that leverages the inherently skewed distribution of flow cardinalities in network traffic. MEC-Sketch employs a dual-component architecture: a heavy part utilizing a majority vote algorithm for precise super-spreader detection, and a light part implementing compact cardinality estimators for memory-efficient measurement of mouse flows. We address two fundamental technical challenges: (1) adapting the majority vote algorithms to operate with cardinality estimators that lack native support for real-time queries, and (2) implementing an effective mapping strategy between large estimators in the heavy part and small estimators in the light part during elephant-mouse flow separation. Comprehensive evaluations on real-world network traces demonstrate that MEC-Sketch significantly outperforms state-of-the-art solutions in terms of estimation accuracy, memory efficiency, and computational performance for both cardinality estimation and super-spreader detection tasks.