Estimating Cardinality Distributions in Network Traffic
Understanding the communication connectivity patterns between network hosts, such as the number of distinct destinations or flows for each host, is important for many network management functions. Often, changes in the connectivity patterns will be reflected through changes in the cardinality distributions defined over these distinct counts (a distinct count is also called cardinality). Information on network host connectivity patterns are important for network monitoring and traffic engineering. In this paper, an efficient streaming algorithm is proposed to estimate cardinality distributions including connectivity distributions, e.g. percent of hosts with any given number of distinct communicating peers or flows.