Counting-based Algorithms For Detecting Frequent Items In Network Traffic

Today, the network plays an important role and has an irreplaceable value. With the network scale continually expanding, the number of users and the volume of network traffic have increased substantially. Network behaviors along with the development of the network have become more and more diversified and complicated. Detection of frequent items is a hotspot in network measurement. It is an effective way to understand the network behaviors and do network management.Frequent items in the network traffic include heavy-hitters and superpoints. Detection of heavy-hitters is applied to traffic billing, real-time traffic monitoring and so on. Detection of heavy-hitters is of great significance to the development of efficient traffic engineering. Detection of superpoints helps to discover the worm, port scanning, DDoS and other abnormal network behaviors. Therefore, detection of frequent items in network traffic has a wide range of applications and important significance.Two counting-based algorithms on detection of frequent items called ADH (Algorithm for Detecting Heavy-hitters) and ADS (Algorithm for Detecting Superpoints) are proposed in this paper. ADH and ADS are used to detect heavy-hitters and superpoints respectively. Every algorithm is divided into online processing module and offline statistics module. Online processing module is responsible for storing and deleting data items. Offline module counts and outputs frequent items after online module processing all items. Because the memory space is limited, ADH algorithm needs to design reasonable and efficient deletion rules and periods to clear the infrequent items stored in memory to reduce unnecessary memory consumption. The deletion rules designed according to the characteristics of flow distributions can remove the infrequent items effectively. The ADH algorithm adaptively adjusts period values based with the change of network traffic and guarantees that the errors produced by deletion are within a certain range. The deletion rules and periods of ADS are similar to ADH. Setting deletion rule and period of ADS considers of the characteristics of source host distributions and the change of network traffic.Extensive experiments are made to test two algorithms respectively, The experimental results show that ADH and ADS both exhibit a good performance in space consumption and deletion accuracy.