空間高效的計數器結構

黃清杉，張 進，肖 剛，顧曉鳴

(1.解放軍理工大學 通信工程學院，南京 210007;2.中國電子設備系統工程公司研究所，北京 100039)

隨著互聯網鏈路速率和數據流數量的飛速增長，流測量對內存的大小和內存的處理速度提出了苛刻的要求，需要計數器具備高速的在線計數處理能力［1－2］。例如，在40 Gbit/s的 OC －768 鏈路中，每隔8 ns就會有一個新的數據包到來，相應的計數器需要在這段時間內完成更新，這就需要具有快速處理能力的SRAM計數器。但是在最壞情況下所需的SRAM計數器數量也往往是不切實際的，因此如何提升計數器空間效率，使其適應高速流測量的需求，成為當前的研究重點［3］。

文獻［4－5］提出了一種被動式(passive)計數器。該計數器是基于SRAM+DRAM的混合結構，基本思想是在SRAM中存儲一些低位數值(例如9位)，將對應的所有高位數值存儲在DRAM中(例如64位)，當數值較小時只有這些SRAM計數器有增量。當SRAM計數器的值接近溢出時，相應的DRAM計數器將對應的SRAM計數器值記錄下來，這樣可以顯著降低SRAM的成本，快速進行SRAM計數器寫操作(延遲2～5 ns)，但DRAM計數器部分的讀取訪問就比較慢(延遲60～100 ns)。這種方法稱之為被動式計數，即其中一般計數器值不需要經常讀出(直到測量周期結束)。文獻［6－7］提出了另一種被動式計數器 CB(counterbraids)，它基于數據壓縮與編碼技術，核心是采用類似低密度校驗碼的思想對計數型布魯姆過濾器的計數器空間進行壓縮，在查詢階段再采用解碼算法對計數值進行還原。

文獻［8］提出了一種主動式計數器SAC(simple active counter)，它基于數值壓縮的思想。SAC可以將計數值存儲在SRAM中，但每個計數器需要有額外的存儲開銷和額外的處理開銷。文獻［9］提出了另一種主動式計數器DISCO(DIScount Counting)，它也是基于數值壓縮的思想。它將計數值進行壓縮后存儲，這種壓縮存儲存在一定的壓縮誤差，但比較適用于計數精度要求不是很高的情況。文獻［10］提出的一種主動式計數器BRICK(bucketized rank indexed counter)，是基于分級索引(rank index)技術。BRICK采用標記索引方式將計數器位空間分級，然后按照標記索引存儲，查詢時再按照計數的反操作，通過標記位求出計數器的值。這樣就不需要將每一個計數器的位寬設為一樣，在引入少量的空間標記比特的情況下可有效提升空間效率。

文獻［11］提出的SBF(spectral bloom filter)采用動態的計數器空間分配策略，在一定程度上提升了空間效率，但是動態分配策略的實現機制較為復雜，難以應用到高速計算場合。

以上這些空間高效的計數器都在一定程度上提升了計數器的空間效率，但由于被動式計數器的完整信息保存在DRAM中，相對于SRAM讀取較緩慢，不能很好滿足高速網絡中讀取線速的要求，因此本研究重點研究主動式計數器，并將這些空間高效的主動式計數器引入到數據流測量算法中，用于改善數據流測量算法的空間效率。

1 典型的主動式空間高效計數器

主動式計數器都是僅使用SRAM的空間高效計數器。SAC可以將計數值存儲在SRAM中，但每個計數器需要有額外的存儲開銷和額外的處理開銷。以下重點介紹2種典型的主動式空間高效的計數器——DISCO計數器和BRICK計數器。

1.1 DISCO

文獻［9］提出了DISCO(discount counting)計數器，它是基于數值壓縮的思想，將要存儲的計數值進行壓縮，然后再將壓縮值存儲到計數器中。由于壓縮后數值變小，所需的SRAM計數器位相對會少些，尤其是計數值越大，空間節省越明顯。DISCO的壓縮方法是將流的大小規范化為另一個數作為計數器值的增量。假設c為計數器值，n為流長度，有函數

其中b＞1為常數。

當長度為l的數據包到來且計數器值為c時，計數器以概率pd(c，l)使計數器值增加δ(c，l)+1，計數器以概率1－pd(c，l)使計數器值增加δ(c，l)，其中:

式中0≤pd(c，l)≤1。顯然，n=f(c)是一個凸函數，要存儲的計數值越大，計數器值的增量就越小，因此所需的計數器位寬是大大減小了。如圖1所示，要存儲的計數值為81，經過DISCO處理后計數值的增量就壓縮為59，以此類似。最后將原本需要存儲的計數值2334壓縮為321，有效提升了計數器的空間效率。

圖1 計數值壓縮存儲

查詢時進行函數的反運算，將計數值增量還原，但是這樣的壓縮還原存在一定的計數誤差，計數值越大絕對誤差也就越大。DISCO能夠支持流量大小和流量字節計數，并提供離線和在線的測量結果。

1.2 BRICK

文獻［10］提出的另一種主動式計數器BRICK(bucketized rank indexed counter)是基于分級索引(rank index)技術的。BRICK的主要思想是將計數器隨機捆綁到固定大小的桶中來實現統計復用，并通過采用比特位向量作為排列索引來動態分配計數器位空間。這里的比特位向量是關鍵。對于每個計數器Ci，將其分割為 d個子計數器Ci，1，…，Ci，d，其中 Ci，j的地址記為 Ci，j=Aj［ai，j］。如圖2 所示，C5的值分布為 A3［1］=10，A2［2］=11，A1［5］=11011，即 C5=101111011=379。

圖2 BRICK計數器結構

對每個計數器設置一個比特位向量I，I分為p－1 個部分 I1，…，Ip－1，分別對應計數器的各個部分 A1，…，Ap－1，每個 Ij都有 k bit，一個比特Ij［a］對應一個 Aj［a］。Ij［a］既用于判別計數器Aj［a］之后是否還有值，又用于計算下一個子計數器Aj+1的地址。如圖3所示，A1［1］和 A1［5］對應的 I1［1］和 I1［5］設置為 1，說明 A1［1］和 A1［5］在 A2還有值，且分別在 A2［1］和 A2［2］。

圖3 BRICK計數器更新過程

查詢計數值，按照A1到Ap－1的順序逐個查看其標記比特位Ij［a］，然后將 Ij［a］為1的計數器位Aj［a］串起來，即得到計數值的大小。這個尋址過程需要計算Ij的和，根據Ij的和值尋址到高級計數器。這種尋址方式稱之為間接尋址。

BRICK計數器可以將計數值有效地存儲在SRAM中，同時支持快速更新和查找(例如40 Gbit/s的線率)，且查詢時不會增加新的誤差。

2 空間高效計數器的應用分析

2.1 DISCO計數器對數據流測量算法的影響

由于DISCO算法在進行數據處理的時候屬于有損壓縮，在還原數據時不可避免地會有一定的誤差，這些誤差在理論上肯定會影響到數據流測量算法。如圖4可見，通過簡單的模擬分析，DISCO處理前，越大的計數值其處理后的壓縮值的絕對誤差越大，而在計數值較小時其相對誤差卻會比較大。

圖4 DISCO算法原始值與壓縮值的比較

進一步模擬骨干網的數據流量進行應用分析。通過對骨干網流量數據的流長分布進行統計分析，發現數據流長基本符合Zipf統計分布，因此模擬這樣一組數據流，其流長區間為［1，M］，流長分布服從Zipf分布，則流長取x的概率為

通常，網絡流長分布的參數Z的取值為1.5～2.0。Zipf分布的互補累計分布函數CCDF如圖5所示。當Z=2.0時，90%的流的流長是小于8，99%的流的流長是小于64;當Z=1.5時，90%的流的流長是小于64，99%的流的流長是小于4721。為保證分析效果，選擇一個相對保守的參數Z=1.5。

圖5 Zipf分布

根據式(1)，實驗中設DISCO計數器參數b=1.01。數據流測量算法使用DISCO計數器的查詢誤差，如圖6所示。和未使用DISCO計數器的查詢誤差相比，在使用DISCO計數器后，數據流測量算法的查詢誤差有明顯增加，尤其是在120～180的時間周期變化最大。這主要是因為這一段時間的數據流數目較少。對照圖4可知，流長越大得到的查詢誤差影響也越大。

圖6 使用DISCO計數器時查詢誤差

因此，從應用效果來看，DISCO計數器可以使用在允許一定計數誤差的應用中，但在精確度要求較高的環境下難以滿足需求。

2.2 BRICK計數器對數據流測量算法的影響

BRICK將計數器分為多個桶，同時為每個桶中的計數器引入排列索引標記。同樣采用模擬骨干網的數據流量進行仿真分析。

BRICK計數器采用3級索引標記作為分析。圖7是使用BRICK計數器情況下的查詢誤差，得到的查詢誤差前后是一樣的，說明使用BRICK計數器沒有增加算法的查詢誤差。

圖7 使用BRICK時的查詢誤差

實驗表明BRICK計數器應用到數據流測量中沒有誤差影響，但是時間效率顯然要比不使用BRICK計數器時低，因為它要對每個計數器進行標記尋址后再進行查詢判斷。

3 DA-BRICK

前面重點分析了DISCO計數器和BRICK計數器對數據流測量算法的影響，仿真結果表明，2種計數器在空間效率方面毫無疑問都有著顯著的提升，但是引入DISCO計數器對數據流測量的查詢誤差有影響，而且這樣的誤差還比較大，在某些地方甚至比布魯姆過濾器本身的查詢誤差還要大。

從應用結果來看，BRICK對流測量算法的查詢誤差沒有影響，但由于使用了標記比特位向量，需要通過求和尋址方式計算原始的計數器值。若1級計數器中有新的計數值溢出，則相應的次級計數器都要改變，即次級計數器的更新與先后無關。如圖3所示，1級計數器C1和C5溢出后順序使用2級計數器的C1和C2，而當1級計數器C2也產生溢出后，則需要將1級計數器C5使用的2級計數器C2讓出來給1級計數器C2使用，1級計數器C5再順序使用的2級計數器C3。這樣，每次變動都要進行大范圍的調整，顯然會增加一定的時間復雜度。因此希望改進標記比特位向量的尋址方式，即改間接尋址為直接尋址 BRICK，即 DABRICK(direct addressing BRICK)。

3.1 DA-BRICK的結構設計

DA-BRICK與BRICK唯一不同之處就是將標記比特位替換為下標計數器，這樣當有計數器更新需要用到次級計數器時，用下標計數器記下溢出計數器的先后順序。在查詢時，只要計算下標計數器的值就能直接找到相對應的次級計數器了。DA-BRICK結構如圖8所示。

在進行計數器更新過程中，1級計數器中先溢出的計數器按照先后順序使用2級計數器，下標計數器記下使用次級計數器的先后順序。當前面有新的計數器也產生溢出時，則按順序使用2級計數器，而不是像BRICK將次級計數器順次向下移位。如圖8所示，1級計數器C1和C5溢出后順序使用2級計數器的C1和C2，下標計數器的值則分別為1和2。而當1級計數器C2也產生溢出后，則使用2級計數器C3，下標計數器則記為3，次級計數器不需要順次移位。

圖8 DA-BRICK的結構

3.2 DA-BRICK的參數設計

DA－BRICK結構的關鍵是使用了直接尋址機制，所以下標計數器大小的設計很重要，它直接影響算法的時間效率。下標計數器的大小主要與1級計數器的多少、大小有關，而1級計數器的大小設計又與流長的分布相關。因為當大的數據流較多時，如1級計數器較小會使得大部分計數器需要使用2級計數器，這樣1級下標計數器的比特位也需要增加，這會影響結構的空間效率。

由于經典CBF［12］在測量時需要按照最大元素頻率值設置計數器的位寬，因此其位寬大小為b=。BRICK計數器采用3級索引標記，將每個計數器分割為3個子計數器。在流長服從Z=1.5的Zipf分布下:BRICK的1級計數器位寬設為=6bit，1級標記比特位設為1位;2級計數器位寬設為，2 級標記比特位設為1位;3級計數器位寬設為2 bit。DABRICK計數器仍然采用3級索引標記，依然將每個計數器分割為3個子計數器。考慮到1級計數器太小會需要使用較多的2級計數器導致1級下標計數器比特位的增加，因此DA-BRICK的1級計數器位寬的設置要比BRICK的多。從圖5的流長分布情況看，DA-BRICK的1級計數器位寬設為29=512就能夠滿足絕大部分的數據流計數需求，只有少量數據流會有計數溢出到2級計數器。因此將2級計數器的位寬設為級計數器位寬設為2 bit。和 BRICK相比，DABRICK所需付出的額外的空間開銷就在于1、2級下標計數器的位寬。DA-BRICK結構的一個實例如圖9所示。

圖9 DA-BRICK結構實例

4 仿真分析

本節使用真實網絡流量數據進行仿真分析。仿真實驗的目的是驗證在真實網絡流量下，計數器向量的溢出概率，并分析和BRICK相比，將DABRICK應用于數據流測量算法后計數誤差的變化情況以及空間效率情況。

實驗通過CAIDA得到網絡的真實數據。選取2組數據:trace1是2004年06月01日19:00—20:00第5、35 min的網絡流量;trace2是2002年08月14日09:00—10:00第5、35 min的網絡流量。數據以互補累計分布函數CCDF(complementary cumulative distributionfunction)形式進行統計分析，如圖10所示。

首先根據布魯姆過濾器參數設計原則可以算出所需的布魯姆過濾器空間的大小。例如要使得布魯姆過濾器的誤差為0.02135級別，且哈希函數個數為6時，則所需的布魯姆過濾器空間為

綜合考慮，數據流測量仿真時布魯姆過濾器的空間大小設定為m=1500000。此時，可知最佳哈希函數個數

其次進行DA-BRICK計數器的參數設置。由圖10所示的流長分布，99%的數據流的流長小于512。實驗中DA-BRICK計數器采用3級索引標記，1級計數器位寬設為12 bit，2級計數器位寬設為5 bit，3級計數器位寬設為2 bit。2級計數器的個數設為32，此時1級下標計數器的大小為5 bit。又將3級計數器個數設為4，則2級下標計數器的大小設為2 bit。

圖10 流長分布

通過仿真統計，在這樣的參數設計下，計數器向量空間的溢出個數為12，溢出概率為12/150000=8 ×10－5。

圖11 各級計數器使用情況

在以上的參數設計下，分析DA-BRICK空間效率。設實驗中數據流測量算法使用了m個計數器，各級計數器使用情況如圖11所示，則經典CBF按照最大元素頻率值設置計數器的位寬使用的總空間MCBF=m×19，BRICK計數器使用的總空間

DA-BRICK計數器使用的總空間

顯然，BRICK計數器空間效率比普通計數器提高了31.5%，而DA－BRICK的空間效率比普通計數器提高了10.5%。由于使用直接尋址方式，使得改進后的DA-BRICK的空間效率比BRICK低了30%，但是時間效率提高100%了，因為數據流測量算法的時間復雜度不再是 O(n)，而是O(1)了。

仿真得到的查詢誤差如圖12所示，和使用BRICK計數器的查詢誤差(圖13)相同，即使用改進后的DA_BRICK計數器沒有增加新的查詢誤差。

實驗表明將DA-BRICK計數器應用到數據流測量中沒有增加查詢誤差，DA_BRICK在增加少量的下標計數器空間的情況下，時間效率顯然比BRICK計數器要高一些，因為它不再需要對每個計數器進行標記尋址后查詢判斷，而是采用直接尋址方式。數據流測量算法的時間復雜度不再是O(n)，而是 O(1)了。

圖12 使用DA-BRICK時的查詢誤差

圖13 使用BRICK時的查詢誤差

5 結束語

本文通過對現有的空間高效的計數器DISCO、BRICK進行深入的研究和比較，發現DISCO計數誤差大，而BRICK計算復雜度高，因而均不適用于面向高速骨干網的流測量。對BRICK進行了改進，提出了面向高速骨干網流測量的DA-BRICK計數器。仿真分析表明:DA-BRICK能夠適用于高速測量的實時需要，同時不增大錯誤概率;其代價是和BRICK相比，在支持相同數目的計數器的前提下，DA-BRICK所需的存儲空間增加了30%。

［1］Roeder M，Lin B.Maintaining exact statistics counters with a multilevel counter memory［C］//Proc.of IEEE Globecom.Dalas，USA:［s.n.］，2004.

［2］Shah D，Iyer S，Prabhakar B，et al.Analysis of a statistics counter arc hitecture［J］.IEEE Micro，2002，22(1):76 －81.

［3］Peter Lieven，Bjorn Scheuermann.High-Speed Per-Flow Traffic Measurement with Probabilistic Multiplicity Counting［C］//Proc.of IEEE Infocom.New York，USA:［s.n.］，2010.

［4］Ramabhadran S，Varghese G.Efficient implementation of a statistics counter architecture［C］//Proc.of Sigmetrics.San Diego，USA:［s.n.］，2003.

［5］Zhao Q，Xu J，Liu Z.Design of a Novel Statistics Counter Architecture with Optimal Space and Time Efficiency［C］//Proc.of ACM SIGMETRICS ’06.France:［s.n.］，2006.

［6］Yi Lu，Andrea Montanari，Balaji Prabhakar.Counter Braids:A Novel Counter Architecture for Per-Flow Measuremen［C］//Proc.of ACM Sigmetrics.USA:［s.n.］，2008.

［7］Yi Lu，Balaji Prabhakar.Robust Counting Via Counter Braids:An Error-Resilient Network Measurement Architecture［C］//Proc.of IEEE Infocom.USA:IEEE，2009.

［8］Rade Stanojevic.Small active counters［C］//in Proc.of IEEE Infocom .USA:IEEE，2007.

［9］Chengchen Hu，Bin Liu，Kai Chen.Compressing Flow Statistic Counters［C］//Proceeding of IEEE ICNP 2009(poster).New Jersey，USA:IEEE，2009.

［10］Hua N，Lin B，Xu J，et al.BRICK:A novel exact active statistics counter architecture［C］//ACM/IEEE Symposium on Architectures for Networking and Communications Systems(ANCS).USA:［s.n.］，2008.

［11］Cohen S，Matias Y.Spectral Bloom Filters［C］//Proceedings of the ACM SIGMOD.San Diego，USA:［s.n.］，2003:224－236.

［12］Fan L，Cao P，Almeida J，et al.Broder.Summary Cache:a Scalable Wide-area Web Cache Sharing Protocol［J］.IEEE/ACM Transactions on Networking，2000，8(3):281－293.