A survey on sliding window sketch for network measurement

As an important basis for network management, effective network measurement is critical for improving network performance and security. As an efficient tool for network measurement, sketch is a probabilistic data structure which can measure traffic statistics with low overhead. Considering that the most recent data of flows are more significant, sliding window sketch is proposed by combining sliding window model with the sketch. Sliding window sketch focuses on measuring information of the most recent period, e.g., data of the last N items or in the last N time units of measured traffic. By prioritizing the latest data, sliding window sketch can better reflect the current network situation and the future trend while avoiding information loss. However, implementation of sliding window sketch is very challenging considering the memory limitations of network devices and the need to maintain the window content in real-time. This paper conducts a comprehensive survey on the latest research works and provides insights into sliding window sketch. First, we briefly review the fundamentals of network measurement and sketch, and then we thoroughly go through and analyze the existing works on sliding window sketch for three different types. Afterwards, we provide a comparative analysis on the design of sliding window sketch in terms of data structures, supported operations, measurement tasks, implementation platforms and performance. Finally, we summarize this survey paper and highlight some future research directions.