One-Sketch: A Unified Framework for Per-Flow Cardinality Measurement with Flexible Bias Control

Abstract

In the era of massive network traffic and sophisticated cyber threats, accurate per-flow cardinality measurement has become the cornerstone of modern traffic analytics and network security. However, traditional sketch-based solutions face a fundamental dilemma: they either excel at cardinality estimation or super-spreader detection, but not both, while being limited to either biased or unbiased estimations. This limitation forces network operators to deploy multiple specialized systems, increasing complexity and resource overhead. One-Sketch represents a paradigm shift in network measurement by unifying dual functionality within a single architecture. Specifically, our approach introduces a novel hybrid design combining a heavy part for tracking elephant flows with specialized unbiased cardinality estimators for remaining traffic. This architecture delivers simultaneous high-accuracy cardinality estimation and super-spreader detection while providing flexible bias control to meet diverse application demands. Furthermore, our approach introduces a cardinality buffering technique, which dramatically enhances throughput by enabling real-time estimation capabilities that traditional single-flow estimators cannot achieve. Extensive evaluation on real-world network traces demonstrates One-Sketch’s superior performance: achieving the highest accuracy for super-spreader detection while maintaining comparable cardinality estimation precision, with significantly higher throughput than existing solutions.