Computer Science – Networking and Internet Architecture
Scientific paper
2007-10-02
Computer Science
Networking and Internet Architecture
8 pages. Allerton conference
Scientific paper
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.
Lu Yi
Montanari Andrea
Prabhakar Balaji
No associations
LandOfFree
Detailed Network Measurements Using Sparse Graph Counters: The Theory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Detailed Network Measurements Using Sparse Graph Counters: The Theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Detailed Network Measurements Using Sparse Graph Counters: The Theory will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-285155