  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 flows 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.'' 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.
