H2Sketch: real-time H-value measurement of key flows in high-speed networks

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²-flow. Efficiently and accurately identifying H²-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²Sketch, which consists of two main modules. Extensive experimental results based on real datasets show that H²Sketch outperforms all the compared solutions in all evaluation metrics, such as ARE, F1 score, and throughput.