Algorithms Based On Reversible Sketches For Measuring Superpoints And Elephant Flows

A host is called a superpoint if it is a distinct source (destination) that large number of network host is connected with during a given time interval. An elephant flow is a flow which has a huge number of packets during a given time interval. With the development of the Internet, the security threats posed by worms, DDoS and port scans have increased in frequency recently. Those attack events by generating a lot of traffic may cause network congestion or even paralysis in a short time. The measurements of superpoints and elephant flows is significant for traffic capacity planning, anomaly detection and service provision in networks.This paper analyzed the advantages and disadvantages of the existing algorithms of superpoints and elephant flows and propose two algorithms based on reversible sketches for measuring superpoints and elephant flows, respectively. In the two algorithms, the Chinese Remainder Theorem is applied to construct hash functions. By using the specific hash functions, packet information is stored in specific data structure. The two algorithms can record and process packets information with less storage space on high speed links. Each of two algorithms consists of two modules:online processing module and offline statistics module. In the algorithm for measuring superpoints, the online module uses a group of two dimensional bit arrays to record all arriving packets in networks, that is, it uses specific hash functions to map those packets onto the bit arrays. In the algorithm for measuring elephant flows, the online module uses a few two dimensional counter arrays to record all arriving packets in networks, that is, it uses specific hash functions to update the counter arrays. Finally, we can obtain the identities and cardinalities of superpoints and the IDs and lengths of elephant flows, respectively. The proposed algorithms do not need to explicitly store the ID information of superpoints and elephant flows. Thus, they only require less memory.In experiments, we feed packets traces collected from different networks to the two algorithms. The experimental results show that the proposed algorithms can detect superpoints and elephant flows accurately with less storage space and less time overhead. Therefore, the two algorithms can be applied in high speed networks.