Detecting The Cardinality Distribution Of Hosts In High-Speed Network

In the filed of network measurement, the cardinality of hosts is a new concept which has been proposed recently. Detecting the cardinality in high-speed network is very important in developing effective and efficient traffic engineering schemes. With the rapid growth of Internet, Internet attacks such as distributed denial-of-service (DDOS) attacks and worm attacks 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, and this must change the cardinality distribution of hosts in the network. Tracking and detecting the real-time cardinality distribution of hosts and obtaining the information of these cardinality are very useful for network operation and management.In this paper, we combine hash,Bloom filter and data stream algorithms, propose a data stream algorithm which is hash-based and can measure the cardinality distribution of hosts. Our algorithm can work well in high-speed network where has a huge number of hosts. Our algorithm consists of three modules, namely, filter module, counter module and output module respectively. The large number of packets in network first reach the filter module which is based on Bloom filter using four hash functions to filter all packets, to filter meaningless ones for the measurement, and ensure that up to one packet belong to each IP flow can pass the filter module. The four hash functions we designed carefully significantly reduce the phenomenon of flow loss as a result of hash collision. In counter module, the packets have passed the filter module are further processed. Thus algorithm obtains SIP-based cardinality estimation. The output module outputs the results belong to counter module in the form of< cardinality:number> pairs.To test the performance of the algorithm, in this paper, we do experiments by using packet header traces gathered at three different locations of the Internet. Because there exists inevitable conflict error in hash function, we estimate the experimental results based on EM algorithm, and make the experimental results before and after estimation, respectively, compare with the actual data. We adopt the Weighted Mean Relative Diffe- rence (WMRD) as our evaluation metric. The experimental results show that our algorithm can track and detect the real-time cardinality distribution of hosts precisely and efficiently.