skip to main content
research-article

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

Published: 02 June 2008 Publication History

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.

References

[1]
http://www.cisco.com/warp/public/732/Tech/netflow.
[2]
Juniper networks solutions for network accounting. www.juniper.net/techcenter/appnote/350003.html.
[3]
B. Bloom. Space/time trade-offs in hash coding with allowable errors. Comm. ACM, 13, July 1970.
[4]
J. W. Byers, M. Luby, M. Mitzenmacher, and A. Rege. A digital fountain approach to reliable distribution of bulk data. In SIGCOMM, pages 56--67, 1998.
[5]
G. Caire, S. Shamai, and S. Verdú. Noiseless data compression with low density parity check codes. In DIMACS, New York, 2004.
[6]
E. Candès and T. Tao. Near optimal signal recovery from random projections and universal encoding strategies. IEEE Trans. Inform. Theory, 2004.
[7]
G. Cormode and S. Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1), April 2005.
[8]
T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley, New York, 1991.
[9]
M. Crovella and A. Bestavros. Self-similarity in world wide web traffic: Evidence and possible causes. IEEE/ACM Trans. Networking, 1997.
[10]
S. Dharmapurikar and V. Paxson. Robust tcp stream reassembly in the presence of adversaries. 14th USENIX Security Symposium, 2005.
[11]
D. Donoho. Compressed sensing. IEEE Trans. Inform. Theory, 52(4), April 2006.
[12]
C. Estan and G. Varghese. New directions in traffic measurement and accounting. Proc. ACM SIGCOMM Internet Measurement Workshop, pages 75--80, 2001.
[13]
R. G. Gallager. Low-Density Parity-Check Codes. MIT Press, Cambridge, Massachussetts.
[14]
M. Grossglauser and J. Rexford. Passive traffic measurement for ip operations. The Internet as a Large-Scale Complex System, 2002.
[15]
F. Kschischang, B. Frey, and H.-A. Loeliger. Factor graphs and the sum-product algorithm. IEEE Trans. Inform. Theory, 47:498--519, 2001.
[16]
A. Kumar, M. Sung, J. J. Xu, and J. Wang. Data streaming algorithms for efficient and accurate estimation of flow size distribution. Proceedings of ACM SIGMETRICS, 2004.
[17]
Y. Lu, A. Montanari, and B. Prabhakar. Detailed network measurements using sparse graph counters: The theory. Proceedings of the Allerton Conference, September 2007.
[18]
M. Luby, M. Mitzenmacher, A. Shokrollahi, D. A. Spielman, and V. Stemann. Practical loss-resilient codes. In Proceedings of the 29th annual ACM Symposium on Theory of Computing, pages 150--159, 1997.
[19]
M. Mézard and A. Montanari. Constraint satisfaction networks in Physics and Computation. In Preparation.
[20]
S. Ramabhadran and G. Varghese. Efficient implementation of a statistics counter architecture. Proc. ACM SIGMETRICS, pages 261--271, 2003.
[21]
T. Richardson and R. Urbanke. Modern Coding Theory. Cambridge University Press, 2007.
[22]
D. Shah, S. Iyer, B. Prabhakar, and N. McKeown. Analysis of a statistics counter architecture. Proc. IEEE HotI 9.
[23]
Q. G. Zhao, J. J. Xu, and Z. Liu. Design of a novel statistics counter architecture with optimal space and time efficiency. SIGMetrics/Performance, June 2006.

Cited By

View all
  • (2024)From CountMin to Super kJoin Sketches for Flow Spread EstimationIEEE Transactions on Network Science and Engineering10.1109/TNSE.2023.327966511:3(2353-2370)Online publication date: May-2024
  • (2024)A Probabilistic Sketch for Summarizing Cold Items of Data StreamsIEEE/ACM Transactions on Networking10.1109/TNET.2023.331642632:2(1287-1302)Online publication date: Apr-2024
  • (2024)Decoding Errors in Difference-Invertible Bloom Filters: Analysis and ResolutionIEEE Access10.1109/ACCESS.2024.337722212(40622-40633)Online publication date: 2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review
ACM SIGMETRICS Performance Evaluation Review  Volume 36, Issue 1
SIGMETRICS '08
June 2008
469 pages
ISSN:0163-5999
DOI:10.1145/1384529
Issue’s Table of Contents
  • cover image ACM Conferences
    SIGMETRICS '08: Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems
    June 2008
    486 pages
    ISBN:9781605580050
    DOI:10.1145/1375457
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 June 2008
Published in SIGMETRICS Volume 36, Issue 1

Check for updates

Author Tags

  1. message passing algorithms
  2. network measurement
  3. statistic counters

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)40
  • Downloads (Last 6 weeks)2
Reflects downloads up to 17 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)From CountMin to Super kJoin Sketches for Flow Spread EstimationIEEE Transactions on Network Science and Engineering10.1109/TNSE.2023.327966511:3(2353-2370)Online publication date: May-2024
  • (2024)A Probabilistic Sketch for Summarizing Cold Items of Data StreamsIEEE/ACM Transactions on Networking10.1109/TNET.2023.331642632:2(1287-1302)Online publication date: Apr-2024
  • (2024)Decoding Errors in Difference-Invertible Bloom Filters: Analysis and ResolutionIEEE Access10.1109/ACCESS.2024.337722212(40622-40633)Online publication date: 2024
  • (2024)Jigsaw-Sketch: a fast and accurate algorithm for finding top-k elephant flows in high-speed networksScience China Information Sciences10.1007/s11432-022-3794-167:4Online publication date: 20-Mar-2024
  • (2023)BitSense: Universal and Nearly Zero-Error Optimization for Sketch Counters with Compressive SensingProceedings of the ACM SIGCOMM 2023 Conference10.1145/3603269.3604865(220-238)Online publication date: 10-Sep-2023
  • (2023)ChameleMon: Shifting Measurement Attention as Network State ChangesProceedings of the ACM SIGCOMM 2023 Conference10.1145/3603269.3604850(881-903)Online publication date: 10-Sep-2023
  • (2023)TreeSensing: Linearly Compressing Sketches with FlexibilityProceedings of the ACM on Management of Data10.1145/35889101:1(1-28)Online publication date: 30-May-2023
  • (2023)Self-Adaptive Sampling Based Per-Flow Traffic MeasurementIEEE/ACM Transactions on Networking10.1109/TNET.2022.321206631:3(1010-1025)Online publication date: Jun-2023
  • (2023)Enhanced Machine Learning Sketches for Network MeasurementsIEEE Transactions on Computers10.1109/TC.2022.318556072:4(957-970)Online publication date: 1-Apr-2023
  • (2023)FASTeller: A Hardware Partial Aggregator for Accurate Flow Counting in Cloud Networks2023 IEEE 31st International Conference on Network Protocols (ICNP)10.1109/ICNP59255.2023.10355603(1-12)Online publication date: 10-Oct-2023
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media