A New Virtual Indexing Method for Measuring Host Connection Degrees

The authors present a new virtual indexing method for estimating host connection degrees for high-speed links. It is based on the virtual connection degree sketch where a compact sketch of network traffic is built by generating the associated virtual bitmaps for each host. Each virtual bitmap consists of a fixed number of bits selected randomly from a shared bit array by a new method for recording the traffic flows of the corresponding host. The shared bit array is efficiently utilized by all hosts since its every bit is shared by the virtual bitmaps of multiple hosts. To reduce the "Noise" contaminated in a host's virtual bitmaps due to sharing, they propose a new method to generate the "Filtered" bitmap used to estimate host connection degree.