A Unified Framework for High-Accuracy and Memory-Efficient Per-Flow Cardinality Measurement

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 high-accuracy and memory-efficient cardinality measurement 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 high-accuracy super-spreader detection, and a light part implementing compact cardinality estimators for memory-efficient measurement of mouse flows. We address three fundamental technical challenges: (1) adapting the majority vote algorithm to operate with cardinality estimators that lack native support for real-time queries, (2) designing an effective mapping strategy between large and small estimators, and (3) eliminating noise introduced by hash collisions. 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.