An Adaptive Counter-Splicing-Based Sketch for Efficient Per-Flow Size Measurement

Accurate and fast per-flow size traffic measurement is fundamental to some network applications, e.g., load balancing, anomaly detection, traffic engineering, especially in face of the processing and memory constraints of switches. Sketch, a compact data structure, can output high-fidelity approximate perflow statistics. However, most existing sketches such as Count-Min are trapped in the dilemma between a large counting range and memory waste, due to the highly skewed characteristics of traffic size distribution. In this paper, we propose an adaptive counter-splicing-based sketch for per-flow size measurement. Specifically, we first allocate a small number of bits for each counter to handle mouse flows, and then splice several basic counters on the same layer to satisfy the counting range requirement for elephant flows. Extensive experiments based on real-world datasets CAIDA show that our proposed sketch can achieve better estimation performance in per-flow size estimation, flow size distribution, entropy estimation, heavy hitter detection, and heavy change detection, compared to several existing algorithms.