An Algorithm Based On Virtual Vector For Measuring Host Cardinality Distribution

The host cardinality is defined as the number of different peers that an Internet host communicates with in a short time. Now the measurement for host cardinality distribution is a significant part of network measurement. With the development of the Internet, the intrusion events occur frequently, such as worms, DDOS attack. An infected host sends a large number of links to other different destinations or many source hosts send attacks to a destination host in a certain time, resulting in network congestion and making the distribution of host cardinality change. So the measurement for host cardinality distribution is important for network management and application.Existing algorithms for the distribution of host cardinality have either large storage consumption or low execution speed. In order to address these problems above, we present an algorithm in which the concept of continuous virtual vector is introduced for measuring host cardinality distribution. This algorithm is able to record and process all Internet packets information with a low storage consumption and fast execution speed and obtains the estimate of host cardinality distribution. The algorithm consists of two modules online processing module and offline processing module. The online processing module uses three one-dimensional bitmap arrays to record flow information for all hosts in the network. Meanwhile, it uses a Bloom Filter to filter all source IPs in the network to record all different source IPs to an array. Offline processing module can obtain the estimate of host cardinality for every source host based on all different source IPs in the network and flow information in the bitmap arrays that are recorded by the online processing module. The final estimation result of cardinality distribution will be output as the tuple form of<host cardinality:host number>.To test the performance of the algorithm that we present above, we do experiments by using four different data trace collected from two distinct networks. The experimental results show that our algorithm for measuring the host cardinality distribution based on virtual vector not only saves memory space, but also can measure the host cardinality distribution fast and accurately.