Measuring network flow sizes is important for accounting/billing, network forensics and security. Per-flow measurement is considered hard because it requires that many counters be updated at a very high speed, and a flow-to-counter perfect hash function. Therefore, current approaches aim to obtain approximate flow counts; that is, to detect large "elephant" flows and then measure their sizes. We present a novel method for per-flow traffic measurement that is fast, highly memory efficient and accurate. At the core of this method is an architecture, which we call "counter braids." We present two results: (i) The optimality of counter braids, in the sense that the total number of bits needed store flow sizes losslessly equals the entropy lower bound. Since network traffic has an entropy rate less than 3 bits per flow, this makes possible an implementation in an on-chip SRAM. (ii) A low-complexity message-passing estimation algorithm, that recovers flow sizes with vanishing error at link speed. Evaluation on Internet traces demonstrates that almost all flow sizes are estimated error-free with only 5 bits per flow. Joint work with: Sarang Dharmapurikar, Abdul Kabbani, Yi Lu, Andrea Montanari.
