空間高效的計(jì)數(shù)器結(jié)構(gòu)

黃清杉，張 進(jìn)，肖 剛，顧曉鳴

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

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

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

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

文獻(xiàn)［11］提出的SBF(spectral bloom filter)采用動(dòng)態(tài)的計(jì)數(shù)器空間分配策略，在一定程度上提升了空間效率，但是動(dòng)態(tài)分配策略的實(shí)現(xiàn)機(jī)制較為復(fù)雜，難以應(yīng)用到高速計(jì)算場(chǎng)合。

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

1 典型的主動(dòng)式空間高效計(jì)數(shù)器

主動(dòng)式計(jì)數(shù)器都是僅使用SRAM的空間高效計(jì)數(shù)器。SAC可以將計(jì)數(shù)值存儲(chǔ)在SRAM中，但每個(gè)計(jì)數(shù)器需要有額外的存儲(chǔ)開銷和額外的處理開銷。以下重點(diǎn)介紹2種典型的主動(dòng)式空間高效的計(jì)數(shù)器——DISCO計(jì)數(shù)器和BRICK計(jì)數(shù)器。

1.1 DISCO

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

其中b＞1為常數(shù)。

當(dāng)長(zhǎng)度為l的數(shù)據(jù)包到來且計(jì)數(shù)器值為c時(shí)，計(jì)數(shù)器以概率pd(c，l)使計(jì)數(shù)器值增加δ(c，l)+1，計(jì)數(shù)器以概率1－pd(c，l)使計(jì)數(shù)器值增加δ(c，l)，其中:

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

圖1 計(jì)數(shù)值壓縮存儲(chǔ)

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

1.2 BRICK

文獻(xiàn)［10］提出的另一種主動(dòng)式計(jì)數(shù)器BRICK(bucketized rank indexed counter)是基于分級(jí)索引(rank index)技術(shù)的。BRICK的主要思想是將計(jì)數(shù)器隨機(jī)捆綁到固定大小的桶中來實(shí)現(xiàn)統(tǒng)計(jì)復(fù)用，并通過采用比特位向量作為排列索引來動(dòng)態(tài)分配計(jì)數(shù)器位空間。這里的比特位向量是關(guān)鍵。對(duì)于每個(gè)計(jì)數(shù)器Ci，將其分割為 d個(gè)子計(jì)數(shù)器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計(jì)數(shù)器結(jié)構(gòu)

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

圖3 BRICK計(jì)數(shù)器更新過程

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

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

2 空間高效計(jì)數(shù)器的應(yīng)用分析

2.1 DISCO計(jì)數(shù)器對(duì)數(shù)據(jù)流測(cè)量算法的影響

由于DISCO算法在進(jìn)行數(shù)據(jù)處理的時(shí)候?qū)儆谟袚p壓縮，在還原數(shù)據(jù)時(shí)不可避免地會(huì)有一定的誤差，這些誤差在理論上肯定會(huì)影響到數(shù)據(jù)流測(cè)量算法。如圖4可見，通過簡(jiǎn)單的模擬分析，DISCO處理前，越大的計(jì)數(shù)值其處理后的壓縮值的絕對(duì)誤差越大，而在計(jì)數(shù)值較小時(shí)其相對(duì)誤差卻會(huì)比較大。

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

進(jìn)一步模擬骨干網(wǎng)的數(shù)據(jù)流量進(jìn)行應(yīng)用分析。通過對(duì)骨干網(wǎng)流量數(shù)據(jù)的流長(zhǎng)分布進(jìn)行統(tǒng)計(jì)分析，發(fā)現(xiàn)數(shù)據(jù)流長(zhǎng)基本符合Zipf統(tǒng)計(jì)分布，因此模擬這樣一組數(shù)據(jù)流，其流長(zhǎng)區(qū)間為［1，M］，流長(zhǎng)分布服從Zipf分布，則流長(zhǎng)取x的概率為

通常，網(wǎng)絡(luò)流長(zhǎng)分布的參數(shù)Z的取值為1.5～2.0。Zipf分布的互補(bǔ)累計(jì)分布函數(shù)CCDF如圖5所示。當(dāng)Z=2.0時(shí)，90%的流的流長(zhǎng)是小于8，99%的流的流長(zhǎng)是小于64;當(dāng)Z=1.5時(shí)，90%的流的流長(zhǎng)是小于64，99%的流的流長(zhǎng)是小于4721。為保證分析效果，選擇一個(gè)相對(duì)保守的參數(shù)Z=1.5。

圖5 Zipf分布

根據(jù)式(1)，實(shí)驗(yàn)中設(shè)DISCO計(jì)數(shù)器參數(shù)b=1.01。數(shù)據(jù)流測(cè)量算法使用DISCO計(jì)數(shù)器的查詢誤差，如圖6所示。和未使用DISCO計(jì)數(shù)器的查詢誤差相比，在使用DISCO計(jì)數(shù)器后，數(shù)據(jù)流測(cè)量算法的查詢誤差有明顯增加，尤其是在120～180的時(shí)間周期變化最大。這主要是因?yàn)檫@一段時(shí)間的數(shù)據(jù)流數(shù)目較少。對(duì)照?qǐng)D4可知，流長(zhǎng)越大得到的查詢誤差影響也越大。

圖6 使用DISCO計(jì)數(shù)器時(shí)查詢誤差

因此，從應(yīng)用效果來看，DISCO計(jì)數(shù)器可以使用在允許一定計(jì)數(shù)誤差的應(yīng)用中，但在精確度要求較高的環(huán)境下難以滿足需求。

2.2 BRICK計(jì)數(shù)器對(duì)數(shù)據(jù)流測(cè)量算法的影響

BRICK將計(jì)數(shù)器分為多個(gè)桶，同時(shí)為每個(gè)桶中的計(jì)數(shù)器引入排列索引標(biāo)記。同樣采用模擬骨干網(wǎng)的數(shù)據(jù)流量進(jìn)行仿真分析。

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

圖7 使用BRICK時(shí)的查詢誤差

實(shí)驗(yàn)表明BRICK計(jì)數(shù)器應(yīng)用到數(shù)據(jù)流測(cè)量中沒有誤差影響，但是時(shí)間效率顯然要比不使用BRICK計(jì)數(shù)器時(shí)低，因?yàn)樗獙?duì)每個(gè)計(jì)數(shù)器進(jìn)行標(biāo)記尋址后再進(jìn)行查詢判斷。

3 DA-BRICK

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

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

3.1 DA-BRICK的結(jié)構(gòu)設(shè)計(jì)

DA-BRICK與BRICK唯一不同之處就是將標(biāo)記比特位替換為下標(biāo)計(jì)數(shù)器，這樣當(dāng)有計(jì)數(shù)器更新需要用到次級(jí)計(jì)數(shù)器時(shí)，用下標(biāo)計(jì)數(shù)器記下溢出計(jì)數(shù)器的先后順序。在查詢時(shí)，只要計(jì)算下標(biāo)計(jì)數(shù)器的值就能直接找到相對(duì)應(yīng)的次級(jí)計(jì)數(shù)器了。DA-BRICK結(jié)構(gòu)如圖8所示。

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

圖8 DA-BRICK的結(jié)構(gòu)

3.2 DA-BRICK的參數(shù)設(shè)計(jì)

DA－BRICK結(jié)構(gòu)的關(guān)鍵是使用了直接尋址機(jī)制，所以下標(biāo)計(jì)數(shù)器大小的設(shè)計(jì)很重要，它直接影響算法的時(shí)間效率。下標(biāo)計(jì)數(shù)器的大小主要與1級(jí)計(jì)數(shù)器的多少、大小有關(guān)，而1級(jí)計(jì)數(shù)器的大小設(shè)計(jì)又與流長(zhǎng)的分布相關(guān)。因?yàn)楫?dāng)大的數(shù)據(jù)流較多時(shí)，如1級(jí)計(jì)數(shù)器較小會(huì)使得大部分計(jì)數(shù)器需要使用2級(jí)計(jì)數(shù)器，這樣1級(jí)下標(biāo)計(jì)數(shù)器的比特位也需要增加，這會(huì)影響結(jié)構(gòu)的空間效率。

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

圖9 DA-BRICK結(jié)構(gòu)實(shí)例

4 仿真分析

本節(jié)使用真實(shí)網(wǎng)絡(luò)流量數(shù)據(jù)進(jìn)行仿真分析。仿真實(shí)驗(yàn)的目的是驗(yàn)證在真實(shí)網(wǎng)絡(luò)流量下，計(jì)數(shù)器向量的溢出概率，并分析和BRICK相比，將DABRICK應(yīng)用于數(shù)據(jù)流測(cè)量算法后計(jì)數(shù)誤差的變化情況以及空間效率情況。

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

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

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

其次進(jìn)行DA-BRICK計(jì)數(shù)器的參數(shù)設(shè)置。由圖10所示的流長(zhǎng)分布，99%的數(shù)據(jù)流的流長(zhǎng)小于512。實(shí)驗(yàn)中DA-BRICK計(jì)數(shù)器采用3級(jí)索引標(biāo)記，1級(jí)計(jì)數(shù)器位寬設(shè)為12 bit，2級(jí)計(jì)數(shù)器位寬設(shè)為5 bit，3級(jí)計(jì)數(shù)器位寬設(shè)為2 bit。2級(jí)計(jì)數(shù)器的個(gè)數(shù)設(shè)為32，此時(shí)1級(jí)下標(biāo)計(jì)數(shù)器的大小為5 bit。又將3級(jí)計(jì)數(shù)器個(gè)數(shù)設(shè)為4，則2級(jí)下標(biāo)計(jì)數(shù)器的大小設(shè)為2 bit。

圖10 流長(zhǎng)分布

通過仿真統(tǒng)計(jì)，在這樣的參數(shù)設(shè)計(jì)下，計(jì)數(shù)器向量空間的溢出個(gè)數(shù)為12，溢出概率為12/150000=8 ×10－5。

圖11 各級(jí)計(jì)數(shù)器使用情況

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

DA-BRICK計(jì)數(shù)器使用的總空間

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

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

實(shí)驗(yàn)表明將DA-BRICK計(jì)數(shù)器應(yīng)用到數(shù)據(jù)流測(cè)量中沒有增加查詢誤差，DA_BRICK在增加少量的下標(biāo)計(jì)數(shù)器空間的情況下，時(shí)間效率顯然比BRICK計(jì)數(shù)器要高一些，因?yàn)樗辉傩枰獙?duì)每個(gè)計(jì)數(shù)器進(jìn)行標(biāo)記尋址后查詢判斷，而是采用直接尋址方式。數(shù)據(jù)流測(cè)量算法的時(shí)間復(fù)雜度不再是O(n)，而是 O(1)了。

圖12 使用DA-BRICK時(shí)的查詢誤差

圖13 使用BRICK時(shí)的查詢誤差

5 結(jié)束語

本文通過對(duì)現(xiàn)有的空間高效的計(jì)數(shù)器DISCO、BRICK進(jìn)行深入的研究和比較，發(fā)現(xiàn)DISCO計(jì)數(shù)誤差大，而BRICK計(jì)算復(fù)雜度高，因而均不適用于面向高速骨干網(wǎng)的流測(cè)量。對(duì)BRICK進(jìn)行了改進(jìn)，提出了面向高速骨干網(wǎng)流測(cè)量的DA-BRICK計(jì)數(shù)器。仿真分析表明:DA-BRICK能夠適用于高速測(cè)量的實(shí)時(shí)需要，同時(shí)不增大錯(cuò)誤概率;其代價(jià)是和BRICK相比，在支持相同數(shù)目的計(jì)數(shù)器的前提下，DA-BRICK所需的存儲(chǔ)空間增加了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.