An Efficient Adaptive Denoising Sketch for Per-flow Traffic Measurement

Per-flow size measurement is a fundamental problem in network engineering and plays a pivotal role in many practical applications. Constrained by on-chip memory resources and packet processing speed, most existing solutions use compact data structures (i.e., sketches) to perform the line-speed measurement. However, sketches share the record units (bits/counters) among flows, inevitably introducing noises to each flow’s measurement result. Although they adopt an average denoising strategy to remove noises from the raw estimations, the accuracy for medium flows is still lacking. This paper complements the prior art and presents a novel per-flow size measurement method, Adaptive Denoising (ADN), which can provide more accurate estimates for online and offline queries. For an online query, we use the collected flow records for real-time estimation. For an offline query, we model the propagation of noises based on the optimization algorithm to produce flow size estimation with much better accuracy. Experimental results based on real Internet traffic traces show that our measurement solutions outperform the state-of-the-art approaches and reduce the mean absolute error by around one order of magnitude under the same on-chip memory usage.