A Method For Detecting Superpoints Based On Bloom Filters

Detecting superpoints is very important in developing effective and efficient traffic engineering schemes. With the rapid development of Internet, Internet attacks such as distributed denial-of-service (DDOS) attack and worm attack are increasing in severity. These attacks generate a lot of traffic within a short time, which may cause network congestion. For example, a compromised host doing fast scanning for worm propagation often makes an unusually high number of connections to distinct destinations within a short time. We call such a host a superpoint, which are sources that connect to a large number of distinct destinations. Identifying realtime superpoint detection and obtaining the information of these superpoints are very useful for network operation and management.In this paper, we have a deep research on superpoint detection. This paper proposes two novel schemes for detecting superpoints and proves guarantees on their accuracy and memory requirements. The main contributions of this work are building a Reversible Counting Bloom Filter (RCBF) and reconstructing the information of superpoint by using the RCBF.The first scheme consists of two sequential Bloom Filters (BF). The first BF is a general Bloom Filter. The second BF is a Reversible Counting Bloom Filter. The RCBF consists of four hash functions which projectively select some consecutive bits from original strings as function values. We obtain the information of superpoints using the overlapping of hash bit strings of the RCBF. The independent hash space preserved for each different hash function reduces the internal confliction among hashing. An analysis demonstrates that the algorithm can support the 40Gbps line-speed processing with low space complexity.The second scheme, referred to as the scalable scheme, is based on the methodology of "filtering after sampling". To reduce the number of flow processed, we use flow sampling to enhance the first scheme's scalability. We use a hash function over flow identifier to implement flow sampling.In this paper, we do experiments by using packet header traces gathered at three different locations of the Internet. We adopt the Weighted Mean Relative Difference (WMRD) as our evaluation metric. The experimental results show that our algorithms can detect superpoints precisely and efficiently.