Detailed Network Measurements Using Sparse Graph Counters: The Theory

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