Counter braids: A novel counter architecture for per-flow measurement

Yi Lu, Andrea Montanari, Balaji Prabhakar, Sarang Dharmapurikar, Abdul Kabbani

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationSIGMETRICS'08
Subtitle of host publicationProceedings of the 2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems
Pages121-132
Number of pages12
Edition1 SPECIAL ISSUE
DOIs
StatePublished - 2008
Event2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS'08 - Annapolis, MD, United States
Duration: Jun 2 2008Jun 6 2008

Publication series

NameSIGMETRICS'08: Proceedings of the 2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems
Number1 SPECIAL ISSUE
Volume36

Other

Other2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS'08
CountryUnited States
CityAnnapolis, MD
Period6/2/086/6/08

Keywords

  • Message passing algorithms
  • Network measurement
  • Statistics counters

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Software

Fingerprint Dive into the research topics of 'Counter braids: A novel counter architecture for per-flow measurement'. Together they form a unique fingerprint.

  • Cite this

    Lu, Y., Montanari, A., Prabhakar, B., Dharmapurikar, S., & Kabbani, A. (2008). Counter braids: A novel counter architecture for per-flow measurement. In SIGMETRICS'08: Proceedings of the 2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (1 SPECIAL ISSUE ed., pp. 121-132). (SIGMETRICS'08: Proceedings of the 2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems; Vol. 36, No. 1 SPECIAL ISSUE). https://doi.org/10.1145/1375457.1375472