TY - GEN

T1 - Detailed network measurements using sparse graph counters

T2 - 45th Annual Allerton Conference on Communication, Control, and Computing 2007

AU - Lu, Yi

AU - Montanari, Andrea

AU - Prabhakar, Balaji

PY - 2007/1/1

Y1 - 2007/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84929326888&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84929326888&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84929326888

T3 - 45th Annual Allerton Conference on Communication, Control, and Computing 2007

SP - 1252

EP - 1259

BT - 45th Annual Allerton Conference on Communication, Control, and Computing 2007

PB - University of Illinois at Urbana-Champaign, Coordinated Science Laboratory and Department of Computer and Electrical Engineering

Y2 - 26 September 2007 through 28 September 2007

ER -