Super point is a special host in network which communicates with lots of other hosts in a certain time period. The number of hosts contacting with a super point is called as its cardinality. Cardinality estimating plays important roles in network management and security. This paper devises a novel algorithm SRLA to estimate the cardinality of super point over sliding time window. SRLA records host cardinality by a novel structure which could be updated incrementally. In order to reduce the cardinality estimating time at the end of every sliding time window, SRLA generates a super point candidate list while scanning packets and calculates the cardinality of host in the candidate list only. It also has the ability to run parallel to deal with high speed network in line speed. This paper gives the way to deploy SRLA on a common GPU. Experiments on real world traffics which have 40 GB s bandwidth show that SRLA successfully estimates super point's cardinality in real time under sliding time window.
@cite_8 proposed a simple method to restore super hosts basing on bloom filter. They called this algorithm as Vector Bloom Filter(VBF). VBF used the bits extracted from a IP address to decide which bits to be updated when scanning packets. Compared with CRT, bit extraction only needed a small operation. But VBF would consume much time to restore super point when the number of super points was very big because it used only four bit arrays to record cardinalities.
@cite_8
2205557629
Internet attacks, such as distributed denial-of-service attacks and worm attacks, are increasing in severity and frequency. Identifying and mitigating realtime attacks are an important and challenging task for network administrators. An infected host can make a large number of connections to distinct destinations during a short time. Such a host is called a superpoint. Detecting superpoints can be utilized for traffic engineering and anomaly detection. This paper proposes a novel data streaming method for detecting superpoints and proves guarantees on its accuracy with low memory requirements. The superior performance of this method comes from a new data structure, called vector bloom filter (VBF), which is a variant of standard BF. The VBF consists of six hash functions, four of which take some consecutive bits from the input string as the corresponding value, respectively. The information of superpoints is obtained by using the overlapping of hash bit strings of the VBF. Theoretical analysis and experimental results show that the proposed method can detect superpoints precisely and efficiently through comparison with other existing approaches.