A new virtual indexing method for measuring host connection degrees

We 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, we propose a new method to generate the "filtered" bitmap used to estimate host connection degree. Furthermore, it can be easily implemented in parallel and distributed processing environments. The experimental and testing results based on the actual network traffic show that the new method is accurate and efficient.