HSS: A Memory-Efficient, Accurate, and Fast Network Measurement Framework in Sliding Windows

Network measurement is indispensable to network management. This paper focuses on three fundamental network measurement tasks: membership query, frequency query, and heavy hitter query. Existing solutions, such as sketches, sliding window algorithms, and the Sliding Sketch framework, struggle to simultaneously achieve memory efficiency, accuracy, real-time operation, and generic application. Accordingly, this paper proposes the Half Sliding Sketch (HSS), an improvement over the state-of-the-art Sliding Sketch framework. The HSS framework is applied to five contemporary sketches for the three aforementioned query tasks. Theoretical analysis reveals that our framework is faster, more memory-efficient and more accurate than the state-of-the-art Sliding Sketch while still being generic. Extensive experimental results reveal that HSS significantly enhances the accuracy for the three query tasks, achieving improvements of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2\times $ </tex-math></inline-formula> to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$28.7\times $ </tex-math></inline-formula>, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$1.5\times $ </tex-math></inline-formula> to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$9\times $ </tex-math></inline-formula>, and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2.4\times $ </tex-math></inline-formula> to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$3.6\times $ </tex-math></inline-formula>, respectively. Moreover, in terms of speed, HSS is <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$1.2\times $ </tex-math></inline-formula> to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$1.5\times $ </tex-math></inline-formula> faster than the Sliding Sketch.