Advancing Sketch-Based Network Measurement: A General, Fine-Grained, Bit-Adaptive Sliding Window Framework
Kejun Guo, Fuliang Li, Jiaxing Shen, Xingwei Wang · 2024
Network measurement plays a critical role in numerous network applications that rely on fundamental flow processing tasks such as frequency estimation, heavy hitter detection, and distribution estimation. Sketch has emerged as an efficient approach for network measurement due to its low overhead. However, most sketch-based solutions target static windows while enabling sliding window-based measurement remains an open challenge. This paper introduces two novel general frameworks applicable to diverse sketch models for sliding window-based network measurement: a traditional sliding window framework and a fine-grained flow-level framework. The traditional framework divides the window into parts and uses centralized flushing to remove expired parts. The flow-level framework tracks timestamps to maintain exact flow characteristics over one period, preventing truncation. To optimize memory usage, a bit-wise adaptive allocation algorithm allows dynamic borrowing of unused counter bits. The frameworks are evaluated on sketches for different flow processing tasks. Results show the frameworks are widely generalizable, reduce error substantially compared to existing approaches, and provide more efficient memory usage.