Detailed Network Measurements Using Sparse Graph Counters: The Theory
| dc.creator | Lu, Yi | |
| dc.creator | Montanari, Andrea | |
| dc.creator | Prabhakar, Balaji | |
| dc.date | 2007-10-02 | |
| dc.date | 2007-10-07 | |
| dc.date.accessioned | 2026-07-07T08:34:14Z | |
| dc.date.available | 2026-07-07T08:34:14Z | |
| dc.description | 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. | |
| dc.description | 8 pages. Allerton conference | |
| dc.identifier | https://arxiv.org/abs/0710.0658 | |
| dc.identifier | http://arxiv.org/abs/0710.0658 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/139365 | |
| dc.subject | Networking and Internet Architecture | |
| dc.subject | Information Theory | |
| dc.title | Detailed Network Measurements Using Sparse Graph Counters: The Theory | |
| dc.type | text |