A New Sketch Method for Measuring Host Connection Degree Distribution

Abstract

The host connection degree distribution (HCDD) is an important metric for network security monitoring. However, it is difficult to accurately obtain the HCDD in real time for high-speed links with a massive amount of traffic data. In this paper, we propose a new sketch method to build a probabilistic traffic summary of a host's flows using a uniform Flajolet-Martin sketch combined with a small bitmap. To study its performance in comparison with previous sampling and sketch methods, we present a general model that encompasses all these methods. With this model, we compute the Cramér-Rao lower bounds and the variances of HCDD estimations. The theoretic analysis and numerical experimental results show that our sketch method is six times more accurate than state-of-the-art methods with the same memory usage.