Detailed network measurements using sparse graph counters: The theory

Measuring network flow sizes Is important for tasks like accounting/billing , network forensics and security. Per-flow accounting Is considered hard because it requires that many counters be updated at a very high speed; however , the large fast memories needed for storing the counters are prohibitively expensive. Therefore , current approaches aim to obtain approximate flow counts; that Is , to detect large elephant lows and then measure their sizes. Recently the authors and their collaborators have developed [1] a novel method for per-flow traffic measurement that is fast , highly memory efficient and accurate. At the core of this method Is a novel counter architecture called "counter braids". , 99 In this paper , we analyze the performance of the counter braid architecture under a Maximum Likelihood (ML) flow size estimation algorithm and show that It Is optimal; that Is , the number of bits needed to store the size of a flow matches the entropy lower bound. While the ML algorithm is optimal , It Is too complex to Implement. In [1] we have developed an easy-to-implement and efficient message passing algorithm for estimating flow sizes.