@inproceedings{499862c05c444f5e9954185a4fb5f2e3,
title = "Counter braids: A novel counter architecture for per-flow measurement",
abstract = "Fine-grained network measurement requires routers and switches to update large arrays of counters at very high link speed (e.g. 40 Gbps). A naive algorithm needs an infeasible amount of SRAM to store both the counters and a flow-to-counter association rule, so that arriving packets can update corresponding counters at link speed. This has made accurate per-flow measurement complex and expensive, and motivated approximate methods that detect and measure only the large flows. This paper revisits the problem of accurate per-flow measurement. We present a counter architecture, called Counter Braids, inspired by sparse random graph codes. In a nutshell, Counter Braids {"}compresses while counting{"}. It solves the central problems (counter space and flow-to-counter association) of per-flow measurement by {"}braiding{"} a hierarchy of counters with random graphs. Braiding results in drastic space reduction by sharing counters among flows: and using random graphs generated on-the-fly with hash functions avoids the storage of flow-to-counter association. The Counter Braids architecture is optimal (albeit with a complex decoder) as it achieves the maximum compression rate asymptotically. For implementation, we present a low-complexity message passing decoding algorithm, which can recover flow sizes with essentially zero error. Evaluation on Internet traces demonstrates that almost all flow sizes are recovered exactly with only a few bits of counter space per flow.",
keywords = "Message passing algorithms, Network measurement, Statistics counters",
author = "Yi Lu and Andrea Montanari and Balaji Prabhakar and Sarang Dharmapurikar and Abdul Kabbani",
note = "Copyright: Copyright 2011 Elsevier B.V., All rights reserved.; 2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS'08 ; Conference date: 02-06-2008 Through 06-06-2008",
year = "2008",
doi = "10.1145/1375457.1375472",
language = "English (US)",
isbn = "9781605580050",
series = "SIGMETRICS'08: Proceedings of the 2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems",
number = "1 SPECIAL ISSUE",
pages = "121--132",
booktitle = "SIGMETRICS'08",
edition = "1 SPECIAL ISSUE",
}