張惠民， 馮林生， 邱雪歡

(陸軍裝甲兵學(xué)院信息通信系， 北京 100072)

網(wǎng)絡(luò)流量[1]分析是有效優(yōu)化網(wǎng)絡(luò)體系架構(gòu)和實現(xiàn)高效可控業(yè)務(wù)承載的有力支撐，但鏈路帶寬的快速增長和網(wǎng)絡(luò)流量的急劇膨脹給流量測量帶來了巨大挑戰(zhàn)[2-3]；處理器資源的大量消耗導(dǎo)致路由器整體性能下降；產(chǎn)生的海量數(shù)據(jù)將占用大部分存儲器的資源；輸出的流量記錄占用大量的傳輸帶寬?；诠Ｋ惴╗4-5]的流量測量方法采用可擴(kuò)展的測量機(jī)制，利用特殊數(shù)據(jù)結(jié)構(gòu)的布魯姆過濾器(Bloom Filter, BF)能快速地鑒別IP流的信息，并能將IP報文映射到很短的哈希串所代表的空間，極大地減少了因流量信息維護(hù)而帶來的資源開銷，從而實現(xiàn)快速網(wǎng)絡(luò)大流檢測與識別。

筆者根據(jù)大流識別的特點，結(jié)合網(wǎng)絡(luò)流的重尾分布特性，提出了一種改進(jìn)型分層計數(shù)布魯姆過濾器(Modified Hierarchy Counting Bloom Filter, MHCBF)的大流識別機(jī)制，較好地解決了計數(shù)器溢出的同題，提高了大流識別的精度。

1 MHCBF基本原理

標(biāo)準(zhǔn)CBF結(jié)構(gòu)能夠?qū)崿F(xiàn)元素的增加、計數(shù)和刪減功能，為保證能實現(xiàn)刪減，其計數(shù)器需要具有一定程度的冗余。借用陳庶樵等[6]分層的基本思想，筆者提出的改進(jìn)型分層MHCBF結(jié)構(gòu)中，其CBF結(jié)構(gòu)對任意元素輸入均需對計數(shù)器中的最小值進(jìn)行加1操作，因而只具備元素的增加和計數(shù)功能，沒有刪減功能。MHCBF結(jié)構(gòu)如圖1所示，其基本思想為：MHCBF的N層均采用CBF結(jié)構(gòu)，對應(yīng)的各層分別為CBF1，CBF2，…，CBFN。其中CBFi(i=1,2,…,N)計數(shù)器根據(jù)該層設(shè)定的閾值確定其字寬，長度為mi。當(dāng)某一個元素進(jìn)入MHCBF時，首先進(jìn)入第1層CBF1，檢查該元素的哈希結(jié)果對應(yīng)的計數(shù)器計數(shù)值是否全部達(dá)到該層的閾值，若未達(dá)到，則將哈希結(jié)果對應(yīng)的計數(shù)器計數(shù)值中的最小值(可能存在多個)均加1，反之將該網(wǎng)絡(luò)流進(jìn)入第2層存儲，當(dāng)對應(yīng)該流的計數(shù)器值都達(dá)到最大值時，再按照同樣的方法進(jìn)入下一層CBF，一直到第N層為止。

2 MHCBF性能分析

設(shè)k為CBF的哈希函數(shù)個數(shù)，m為計數(shù)器個數(shù)，n為存儲元素個數(shù)。龔儉等[7]指出：CBF的溢出概率在滿足k=(m/n)ln2時，溢出概率函數(shù)為單調(diào)遞減函數(shù)，且使誤判概率f達(dá)到最小。基于該特性，對MHCBF結(jié)構(gòu)的內(nèi)存資源占用量、誤判概率、計數(shù)最大值和時間復(fù)雜度進(jìn)行分析。

2.1 資源占用量

假定N層結(jié)構(gòu)中第i層CBFi的計數(shù)器數(shù)量為mi，每個計數(shù)器占用wi個字節(jié)，滿足存儲ni個元素需求。當(dāng)選取ki=(mi/ni)ln2個哈希函數(shù)時，CBFi誤判概率fi始終為最小，且因CBF的溢出概率是一個單調(diào)遞減函數(shù)，所以MHCBF的CBFi計數(shù)器的長度是按層級減小，且收斂較快，其總內(nèi)存資源占用量為

2.2 誤判概率

如果某一個元素達(dá)到了MHCBF結(jié)構(gòu)的最大計數(shù)值，則其在每一層CBF中都有計數(shù)，組成MHCBF結(jié)構(gòu)的每一層CBFi的假陽性錯誤概率

fi=fi(ni,mi,ki)≤(1-e-kini/mi)ki。

又因為元素到達(dá)第i層的概率即該層的溢出概率P(φ≥i)[6],所以該層的誤判概率

fi′=fi×P(φ≥i)≤(1-e-kini/mi)ki×P(φ≥i)。

則單個的MHCBF結(jié)構(gòu)總的誤判概率

由于網(wǎng)絡(luò)流具有重尾分布的特征[7-8]，因此元素主要集中存儲在第1層，在這種情況下可以將第1層的誤判概率近似作為整個結(jié)構(gòu)的誤判概率，即

fMHCBF≈f1(n1,m1,k1)

。

2.3 計數(shù)最大值

MHCBF中CBFi對應(yīng)的計數(shù)器字寬為wi，那么各層計數(shù)器所能達(dá)到的計數(shù)最大值為2wi-1。當(dāng)各層計數(shù)器的計數(shù)值均達(dá)到最大時,MHCBF結(jié)構(gòu)可達(dá)到的元素計數(shù)最大值為

2.4 時間復(fù)雜度

由于MHCBF結(jié)構(gòu)基于標(biāo)準(zhǔn)的CBF，在MHCBF第1層中，元素查詢的操作復(fù)雜度與標(biāo)準(zhǔn)CBF等同，因此k個哈希查詢操作的時間復(fù)雜度為O(k)。一旦CBF確定，k值一般為較小的自然數(shù)常量，則元素在計數(shù)器列表中查詢的時間復(fù)雜度為O(1)。

元素插入和刪除操作的復(fù)雜度與查詢的復(fù)雜度基本相同。在MHCBF結(jié)構(gòu)中，CBFi對應(yīng)的哈希函數(shù)的個數(shù)為ki，所以在一般情況下，元素插人和刪除操作的時間復(fù)雜度平均值為

3 基于MHCBF結(jié)構(gòu)的大流檢測算法

3.1 大流識別模型

基于MHCBF的大流識別模型如圖2所示，采用2級處理機(jī)制：一是通過BF判斷當(dāng)前IP包是否屬于大流；二是利用MHCBF來檢測/過濾大流。由一個BF結(jié)構(gòu)和一個MHCBF結(jié)構(gòu)組成大流識別的核心框架，將 “大流判斷”和“大流檢測/過濾”分離，能夠有效提高大流識別的執(zhí)行效率。

大流識別的處理流程如圖3所示，在每個處理周期內(nèi)，首先對MHCBF結(jié)構(gòu)、BF結(jié)構(gòu)以及大流鏈表初始化。當(dāng)網(wǎng)絡(luò)數(shù)據(jù)流到達(dá)時，先提取IP包的五元組信息，從BF結(jié)構(gòu)中查詢是否存在相應(yīng)的記錄。若存在相應(yīng)記錄，則更新鏈表中對應(yīng)的節(jié)點的計數(shù)值，即將流長加1，如果鏈表中沒有對應(yīng)的節(jié)點，表明是誤判，則將數(shù)據(jù)包記錄插入MHCBF結(jié)構(gòu)；若BF結(jié)構(gòu)中不存在相應(yīng)記錄，則直接插入MHCBF結(jié)構(gòu)。處理周期結(jié)束后，鏈表中的記錄就是識別出的大流數(shù)據(jù)記錄。

3.2 MHCBF結(jié)構(gòu)處理算法

依據(jù)MHCBF結(jié)構(gòu)原理，其處理流程為：

1) 初始化MHCBF的計數(shù)器。

2) 判斷當(dāng)前的CBF結(jié)構(gòu)是否為最后一層(第N層)，是則執(zhí)行4)，否則執(zhí)行3)。

3) 對抵達(dá)當(dāng)前CBF結(jié)構(gòu)的報文五元組結(jié)構(gòu)，查詢所有本層哈希函數(shù)命中的計數(shù)器的最小值T。若T未達(dá)到本層CBF的計數(shù)最大值，則令T=T+1并執(zhí)行5)；若T達(dá)到計數(shù)最大值，則將報文五元組結(jié)構(gòu)傳入下一層CBF結(jié)構(gòu)，執(zhí)行2)。

4) 對抵達(dá)當(dāng)前層(第N層)的報文五元組結(jié)構(gòu)，查詢所有本層哈希函數(shù)命中的計數(shù)器的最小值T。若T未達(dá)到計數(shù)最大值，則令T=T+1并執(zhí)行5)；若T達(dá)到計數(shù)最大值，則將報文五元組結(jié)構(gòu)傳入BF結(jié)構(gòu)并插入大流列表。

5) 結(jié)束本次MHCBF處理。

報文信息傳入MHCBF結(jié)構(gòu)的處理過程算法描述如下：

while a packet p arrives

{

∥HKTK為MHCBF結(jié)構(gòu)中各層CBF的閾值

∥CBFTK[HTK(p)]表示對應(yīng)CBF計數(shù)器的最小值

TK=1;

while(TK

{

HK = CBFTK[HTK(p)];

if(HK

all: CBFTK[HTK(p)]=CBFTK[HTK(p)]+1;

else

TK=TK+1;

}

∥TK等于TN，說明流長超出MHCBF的范圍，

∥流長達(dá)到閾值成為頻繁項，插入BF結(jié)構(gòu)

if(TK == TN)

insert BF;

}

3.3 更新大流計數(shù)值處理算法

大流列表采用鏈表結(jié)構(gòu)實現(xiàn)，主要用來存放大流的特征(五元組)和流長信息。采用標(biāo)準(zhǔn)BF結(jié)構(gòu)，計數(shù)器字寬為1位，處理的主要目的是識別大流，當(dāng)在BF中檢測到輸入IP包屬于某一大流時，則需在大流列表中更新對應(yīng)的計數(shù)值。

更新大流鏈表中的節(jié)點信息的執(zhí)行流程為：

1) 通過BF結(jié)構(gòu)判斷當(dāng)前項是否為大流，是則執(zhí)行2)，否則執(zhí)行3)。

2) 遍歷鏈表，尋找相應(yīng)的節(jié)點。若找到則更新節(jié)點，即將流長加1，執(zhí)行4)；否則表明BF誤判，執(zhí)行3)。

3) 將當(dāng)前項插入MHCBF結(jié)構(gòu)。

4) 結(jié)束本次報文處理。

更新鏈表中的節(jié)點，具體描述如下：

∥Exist用于判斷表示p是否為大流，找到節(jié)點并更新

∥找不到表明誤判，不是大流，則插入MHCBF結(jié)構(gòu)

Exist=1;

for i from 1 to k do

if (BF[Hi(p)]==0)

{

Exist=0;

break;

}

if(Exist==1)

{

FoundNode=0

S=First;

while(S!=NULL&&FoundNode==0)

{

if(S->TupleData==p->TupleData)

{

S->Count=S->Count+1;

FoundNode=1;

break;

}

S=S->next;

}

}

if(Exist==0 or FoundNode==0)

insert MHCBF;

3.4 新大流信息更新處理算法

在MHCBF結(jié)構(gòu)中，通過N層計數(shù)達(dá)到閾值，表明產(chǎn)生新的大流，則首先將新大流信息節(jié)點插入大流列表，然后更新BF結(jié)構(gòu)對應(yīng)哈希函數(shù)命中的各位為1(無論該位之前是否為1)。

發(fā)現(xiàn)新大流后進(jìn)行新大流信息更新的執(zhí)行流程為：

1) 建立新節(jié)點，存儲新大流的五元組信息和計數(shù)值。

2) 將新節(jié)點插入到大流列表的第1個位置。

3) 將新大流信息對應(yīng)的BF結(jié)構(gòu)中的位賦值為1，結(jié)束本次報文處理。

具體描述如下：

Node=new LargeFlowNode(Tuple,TN);

if(Node==NULL)

return ERROR

Node->next=LargeFlowList->next;

LargeFlowList->next=Node;

for i from 1 to k do

BF[Hi(p)]=1;

本算法中采用的大流鏈表結(jié)構(gòu)是無序的，其插入節(jié)點采用頭節(jié)點插入法進(jìn)行簡化，若采用有序鏈表結(jié)構(gòu)，則存在查找定位問題。

4 實驗與評價

4.1 實驗數(shù)據(jù)

實驗使用的網(wǎng)絡(luò)流數(shù)據(jù)取自The CAIDA Anonymized Internet Traces Dataset數(shù)據(jù)集[9]，該數(shù)據(jù)集由Center for Applied Internet Data Analysis(CAIDA)[10]組織采自一條真實網(wǎng)絡(luò)鏈路，且經(jīng)CAIDA處理后，數(shù)據(jù)集中只含有報文的匿名頭部信息，數(shù)據(jù)集基本信息如表1所示。在CAIDA-OC48和CAIDA-OC192數(shù)據(jù)集中隨機(jī)截取若干5 min時長的網(wǎng)絡(luò)流作為實驗的輸入樣本。

表1 實驗數(shù)據(jù)的信息

為兼顧時間效率和空間效率，在實驗中，算法使用的MHCBF結(jié)構(gòu)由2層CBF結(jié)構(gòu)組成。

4.2 實驗結(jié)果

在Windows7操作系統(tǒng)下，使用C++語言對MHCBF算法進(jìn)行了編程實現(xiàn)，使用CAIDA標(biāo)準(zhǔn)數(shù)據(jù)集對MHCBF算法和雙重計數(shù)型布魯姆過濾器(CCBF)算法[10]進(jìn)行對比實驗，實驗中使用二元組進(jìn)行流標(biāo)志，大流的閾值Y=3 000。CCBF算法中的CBF使用216個計數(shù)器，計數(shù)器字寬在考慮可能的計數(shù)最大值情況下需要適當(dāng)增大，以避免哈希沖突導(dǎo)致的頻繁溢出。MHCBF算法中第1層CBF使用216個計數(shù)器，閾值為32；文獻(xiàn)[5]中研究的數(shù)據(jù)集中短流(流長<10)比例達(dá)到87%以上，因此第2層CBF使用214個計數(shù)器，閾值為Y-32。哈希函數(shù)的個數(shù)在滿足ki=(mi/ni)ln 2的情況下，為降低CBF結(jié)構(gòu)的哈希沖突，MHCBF結(jié)構(gòu)中k1設(shè)置為9，k2設(shè)置為8。實驗得到的誤判率、漏報率對比分別如圖4、5所示。

由圖4可以看出:采用MHCBF算法可獲得較CCBF算法更小的大流誤判率。由圖5可以看出：采用MHCBF算法后，大流的漏報率為0，這是由于MHCBF方法對在BF結(jié)構(gòu)中檢測為大流的包還需要在大流列表中匹配該大流是否真實存在。

4.3 算法評價

1) 空間消耗。MHCBF算法使用了MHCBF結(jié)構(gòu)、BF結(jié)構(gòu)和鏈表，CCBF算法使用了CBF結(jié)構(gòu)、BF結(jié)構(gòu)和鏈表，其中BF結(jié)構(gòu)相同且鏈表與識別出的頻繁項數(shù)目相關(guān)，因此主要比較兩者使用的MHCBF結(jié)構(gòu)和標(biāo)準(zhǔn)CBF結(jié)構(gòu)。實驗中，MHCBF使用的2層CBF分別為CBF1和CBF2，由MHCBF的運行過程可知，CBF1和CBF2計數(shù)器的空間占用只需滿足各自閾值所需要存儲的字寬即可；而CCBF算法使用的標(biāo)準(zhǔn)CBF結(jié)構(gòu)計數(shù)器的字寬要滿足可能的計數(shù)最大值的存儲，以避免頻繁的哈希沖突，因此比閾值的字寬要大。實驗中MHCBF結(jié)構(gòu)的CBF1采用單字節(jié)字寬，CBF2采用雙字節(jié)(短整型)字寬，而CCBF采用四字節(jié)(長整型)字寬，因此MHCBF占用的空間約為CCBF的一半。

2) 正確性。實驗中MHCBF算法的漏報率為0，與理論推導(dǎo)的結(jié)論一致，明顯優(yōu)于CCBF算法，適合于需要零漏報率的使用環(huán)境。同時，由于在MHCBF結(jié)構(gòu)中僅對計數(shù)器的最小值進(jìn)行加1操作，大大減少了哈希沖突，因而誤判率明顯降低。

3) 時間性能。在實際處理報文流的過程中，BF處理、MHCBF處理和大流鏈表操作分別采用不同線程實現(xiàn)，當(dāng)報文數(shù)目達(dá)到600萬時，MHCBF算法和CCBF算法的運行時間差在1%以內(nèi)。

因此可以得出：本實驗中MHCBF算法的空間利用率和正確性都優(yōu)于CCBF算法，同時運行時間相差不大。

5 結(jié)論

筆者利用BF和CBF的結(jié)構(gòu)特性，通過BF識別大流、分層的CBF檢測新的大流和鏈?zhǔn)酱罅餍畔⒋鎯Φ拳h(huán)節(jié)，構(gòu)造并實現(xiàn)了一種新的網(wǎng)絡(luò)大流識別算法，在相似的算法執(zhí)行效率基礎(chǔ)上，有效減少空間消耗并獲得較低的誤判率和零漏報率。為空間有限的高速SRAM環(huán)境下，高效利用空間、快速流數(shù)據(jù)處理、高精度大流或網(wǎng)絡(luò)頻繁項分析提供了方法和手段。

參考文獻(xiàn)：

[1] 王風(fēng)宇,云曉春,王曉峰,等.高速網(wǎng)絡(luò)監(jiān)控中大流量對象的提取[J].軟件學(xué)報,2007,18(12):3060-3070.

[2] 王風(fēng)宇,郭山清,李亮雄,等.一種高效率的大流提取方法[J].計算機(jī)研究與發(fā)展,2013, 50(4):731-740.

[3] 趙小歡,夏靖波,付凱,等.高速網(wǎng)絡(luò)流頻繁項挖掘算法[J].計算機(jī)研究與發(fā)展，2014,51(11):2458-2469.

[4] 孫昱,夏靖波,趙小歡,等.基于LEAST和CBF兩級結(jié)構(gòu)的大流檢測算法[J].華中科技大學(xué)學(xué)報(自然科學(xué)版)，2014,42(4):40-44.

[5] 王春龍,劉淵,鄭哲淵.基于LRU和擴(kuò)展CBF的網(wǎng)絡(luò)大流檢測[J].計算機(jī)工程與應(yīng)用,2015,51(13):66-71.

[6] 陳庶樵,張果,扈紅超.基于HCBF的大流檢測機(jī)制[J].計算機(jī)應(yīng)用研究,2010,27(9):3239-3242.

[7] 龔儉,彭艷兵,楊望,等.基于Bloom Filter的大規(guī)模異常TCP連接參數(shù)再現(xiàn)方法[J].軟件學(xué)報,2006,17(3):434-444.

[8] 夏靖波,趙小歡,柏駿,等.基于時間和流長約束的網(wǎng)絡(luò)流頻繁項挖掘算法[J].中國科學(xué)技術(shù)大學(xué)學(xué)報,2013,43(10):790-798.

[9] The CAIDA anonymized internet traces dataset[DS/OL]. (2013-04-24) [2017-03-16]. http:∥www.caida.org/data/passive.

[10] 吳樺,龔儉,楊望.一種基于雙重Counter Bloom Filter的長流識別算法[J].軟件學(xué)報,2010,21(5):1115-1126.