H2Sketch: real-time <i>H</i> -value measurement of key flows in high-speed networks

Abstract The identification of key flows, as one of the most important traffic measurement tasks in high-speed networks, has lots of practical applications, including network resource optimization and network attack detection. However, the existing works define the key flows only according to the flow size or the persistence (i.e. time dimension), all of which are one-sided definitions. To bridge the gap, we propose a new metric (named $H$-value) to identify key flows in high-speed networks, in which the flow $H$-value metric considers the joint distribution of flow size and time relationships. Specifically, the $H$-value of one flow means the flow size of this flow in at least $H$ measurement periods is not less than $H$. Based on this new metric, we redefine the key flows as the flows with large $H$-values, called $H^{2}$-flow. Efficiently and accurately identifying $H^{2}$-flows in high-speed networks faces significant challenges due to limited memory space, uneven distribution of flow $H$-values, and real-time requirements. To this end, we propose a new sketch structure called H$^{2}$Sketch, which consists of two main modules. Extensive experimental results based on real datasets show that H$^{2}$Sketch outperforms all the compared solutions in all evaluation metrics, such as ARE, F1 score, and throughput.