Unbiased Real-Time Traffic Sketching
Yuhan Wu, Shiqi Jiang, Yifei Xu, Siyuan Dong, Kai-Cheng Yang, Peiqing Chen, Tong Yang · IEEE Transactions on Network Science and Engineering · 2023
In network measurement, sliding window measurement has the advantage of providing recent and timely measurement results. Recently, sketches have become the most popular method of conducting flow-level network measurements due to their favorable trade-off between small memory overhead and high measurement accuracy. However, it remains a challenge that no current sketches are able to support unbiased estimation toward flow size measurement, which can improve the performance of tasks including network diagnoses, delay measurement and heavy hitter detection. In this paper, we propose the first work that achieves unbiased flow size measurement in sliding windows, namelyUnbiased Cleaning sketch (UC sketch). The key technique of the UC sketch isUnbiased Cleaningwhich can remove outdated keys from the sliding windows in a balanced way. Besides, we significantly reduce the variance of flow size by two optimization techniques, namelyLinear ScalingandColumn Randomizing. To prove the result, we conduct rigorous mathematical analysis and reasonable experiments. All related source codes are open-sourced at Github anonymously.