A Super Point Detection Algorithm Under Sliding Time Windows Based on Rough and Linear Estimators

Abstract

Detecting super points from high-speed networks can effectively help to monitor networks, which is a hot topic in network fields. Most existing algorithms are carried out under discrete time windows and the results are in a certain percentage of omission. In this paper, the phenomenon of missed super points detection in discrete time windows is analyzed based on real-world traffic. Then a new algorithm, which detects the super points under sliding time windows, is proposed. Our algorithm uses a lightweight estimator to identify candidate super points and a linear estimator to filter super points. The lightweight estimator is fast, and the linear estimator has high accuracy. Both the lightweight estimator and the linear estimator adopt a data structure, called distance recorder, to support sliding time windows. Moreover, our algorithm is also a parallel algorithm. On the basis of thoroughly discussing the mathematic principles and operation steps of our algorithm, two groups of real-world traffic from a 40-Gb/s high-speed network are applied in the experiments which running on a graphic processing unit (GPU). The experiments are conducted under discrete time windows and sliding time windows separately. The former results show that our algorithm is superior to other existing algorithms in the comprehensive performance, and the latter results indicate that our algorithm can run steadily under sliding time windows.

Keywords

• Cardinality estimation
• GPU
• sliding time window
• super points detection