在高速網絡中，流量測量是非常重要的網絡管理。近年來有許多演算法提出用來解決封包流量偵測的問題。其中一個名為Counter Braids的計數器架構，可在高速網路中測量每個封包流流量。此演算法解決兩個封包流測量的核心問題：flow對計數器的一對一對映，以及減少大量閒置的記錄空間。Counter Braids藉由hash function將flow label(來源端位址、目的端位址、來源埠口、目的埠口、通訊協定)隨機指定到多個計數器，解決flow對計數器的映射問題。Counter Braids採用壓縮演算法，可共用高位元的記憶體，解決只有少數burst flow，卻必須根據最差的情況分配記憶體造成浪費的情況。
我們提出幾個此架構可能出現的問題，例如，Counter Braids是透過hash函數取得需要更新的計數器索引，但是如果發生兩個或兩個以上的flow label都映射到相同的計數器時，就無法判斷這個計數器是被哪些flow所影響，最後在解碼時就會得到錯誤的流量資訊。因此，我們提出一個可檢查hash碰撞的方法，可快速判斷最壞情形是否發生。此外，解碼演算法需要執行多次迭代演算法步驟，不斷的在flow和計數器之間傳遞資訊，直到它得到正確的流量大小，這個演算法需要多個步驟才能得到正確值，在本篇論文中，我們提出一個可加快解碼速度的演算法。最後我們將實作在NetFPGA上，用兩個Counter Braids架構輪流記錄、解碼，運用此機制可同時寫入、讀取NetFPGA上的registers，達到on-line update及decode的目的。

Traffic measurement in high-speed networks is important for network management. A counter architecture, called Counter Braids, has been proposed for accurate per-flow measurement on high-speed links. Counter Braids solves two central problems of flow measurement: avoid the storage of one-to-one flow-to-counter association and reduce the counter space by sharing the counters among flows. A flow label (source ip, destination ip, source port, destination port, protocol) is mapped to multiple counters. It performs the one-to-one association by random hash functions and minimizes counter space by incrementally compressing counts. The random values are reproduced from a list of flow labels, with which flow sizes are decoded using a message passing algorithm.
We mention some possible problems of Counter Braids. For example, the hash functions randomly map flows to counters, but if two or more flow labels map to the same counter, the count reconstruction operations will not distinguish which flow affects the counter. After the decoding process, we will obtain false results. We propose a scheme to detect the hash collision. Besides, the decoding algorithm is one of the bottlenecks in Counter Braids since it executes many iterations to pass messages between flows and counters until it gets correct flow sizes. We propose an estimation method to evaluate approximate values with less execution time. Our scheme achieves about ten to hundred fold improvement in decoding speed. Finally, we implement our structure in NetFPGA. We use two Counter Braids so that we can perform reading and writing at the same time.

[1] KC Claffy and Sean McCreary, "Internet measurement and data analysis: Passive and active measurement," in American Statistical Association, Auguest 1999.
[2] Sriram Ramabhadran and George Varghes, "Efficient implementation of a statistics counter architecture," in ACM SIGCOMM, June 2003.
[3] Devavrat Shah, Sundar Iyer, Balaji Prabhakar, and Nick McKeown, "Maintaining statistics counters in router line cards," in IEEE Micro, January 2002.
[4] Qi Zhao, Jun (Jim) Xu, and Zhen Liu, "Design of a novel statistics counter architecture with optimal space and time efficiency," in ACM SIGMETRICS, June 2006.
[5] Baek-Young Choi, Jaesung Park, and Zhi-Li Zhang, "Adaptive random sampling for load change detection," in ACM SIGMETRICS, June 2002.
[6] Nick Duffield, Carsten Lund, and Mikkel Thorup, "Estimating flow distributions from sampled flow statistics," in ACM SIGCOMM 2003, Auguest 2003.
[7] Yi Lu, Andrea Montanari, Balaji Prabhakar, Sarang Dharmapurikar, and Abdul Kabbani, "Counter Braids: A novel counter architecture for per-flow measurement," in ACM SIGMETRICS, June 2008.
[8] Yi Lu, and Balaji Prabhakar, "Robust Counting Via Counter Braids: An Error-Resilient Network Measurement Architecture," in IEEE INFOCOM, April 2009.
[9] Robert G. Gallager, "Low-Density Parity-Check Codes," 1963.
[10] Jianying Luo, Yi Lu and Balaji Prabhakar, "Prototyping Counter Braids on NetFPGA," in Technical Report, 2008.
[11] Burton H. Bloom, "Space/time trade-offs in hash coding with allowable errors," in ACM Communications, July 1970.
[12] Nan Hua, Bill Lin, Jun (Jim) Xu, and Haiquan (Chuck) Zhao, "BRICK: A Novel Exact Active Statistics Counter Architecture," in ANCS, November 2008.
[13] Bill Lin and Jun (Jim) Xu, "DRAM is plenty fast for wirespeed statistics counting," in ACM HotMetrics, June 2008.
[14] Haiquan (Chuck) Zhao, Hao Wang, Bill Lin, and Jun (Jim) Xu, "Design and Performance Analysis of a DRAM-based Statistics Counter Array Architecture," in ANCS, October 2009.
[15] Frederick A. Ware, and Craig Hampel, "Micro-threaded row and column operations in a DRAM core," in Rambus White Paper, March 2005.
[16] XDR datasheet. Rambus, Inc., Copyright 2002-2003.
[17] XDR-2 datasheet. Rambus, Inc., Copyright 2004-2005.
[18] Wei-fen Lin, Steven K. Reinhardt, and Doug Burger, "Reducing DRAM latencies with an integrated memory hierarchy design," in Proc. of IEEE HPCA, page 301, Washington, DC, USA, January 2001.
[19] "NetFPGA: Programmable Networking Hardware," http://netfpga.org/.
[20] Jad Naous, Glen Gibb, Sara Bolouki, and Nick McKeown, "NetFPGA: Reusable Router Architecture for Experimental Research," in SIGCOMM PRESTO Workshop, Seattle, WA, August 2008.
[21] Glen Gibb, John W. Lockwood, Jad Naous, Paul Hartke, and Nick McKeown, "NetFPGA: An Open Platform for Teaching How to Build Gigabit-rate Network Switches and Routers," in IEEE Transactions on Education, August 2008.
[22] "MAWI Working Group Traffic Archive," http://mawi.wide.ad.jp/mawi/.
[23] "Tcpreplay: PCAP editing and replay tools for *nix," http://tcpreplay.synfin.net/trac/.