Charon: Stratified Priority Sampling for Differentiated Per-Flow Measurement in High-Speed Networks

Abstract

Per-flow measurement of priority-heterogeneous traffic underpins cloud service-level agreement (SLA) enforcement, anomaly detection, and distributed AI training in high-speed networks, yet remains challenging in the fast L1/L2-cache memory regime where high-priority flows are vastly outnumbered. We propose Charon, a priority-aware sketch that replaces the structural separation used by prior methods with stratified admission sampling: a single, online-adaptive, parameter-free rule decides whether each packet is admitted to the sketch. Across multiple real-world traces, Charon achieves more than 2× higher detection accuracy for high-priority flows than the best baseline and up to four orders of magnitude lower average error than state-of-the-art priority-aware sketches, with the gap widening as memory tightens, at high processing throughput. The implementation on the industry-grade Tofino switch further demonstrates low resource utilization.