基于自適應(yīng)超時計數(shù)布魯姆過濾器的流量測量算法

侯 穎黃 海 蘭巨龍 李 鵬 朱圣平

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心 鄭州 450002)

基于自適應(yīng)超時計數(shù)布魯姆過濾器的流量測量算法

侯 穎*黃 海 蘭巨龍 李 鵬 朱圣平

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心 鄭州 450002)

針對流量測量中IP長流的檢測問題，該文設(shè)計了計數(shù)布魯姆過濾器(Count Bloom Filter, CBF)與超時布魯姆過濾器(Timeout Bloom Filter, TBF)結(jié)合的長流檢測機制。該機制動態(tài)調(diào)整布魯姆過濾器中的超時時間，及時清理結(jié)束流，解決空間擁塞問題，從而可以適用于無結(jié)束標(biāo)志IP長流檢測。依據(jù)算法整體錯誤率與超時時間的分析，根據(jù)鏈路流到達(dá)強度與布魯姆過濾器向量空間長度自適應(yīng)動態(tài)調(diào)整超時時間，使得算法整體錯誤率保持最低。該算法的性能利用真實網(wǎng)絡(luò)流量數(shù)據(jù)進行驗證，結(jié)果表明，與現(xiàn)有算法相比，該算法的測量準(zhǔn)確性更高。

網(wǎng)絡(luò)測量；流量測量；長流；動態(tài)調(diào)整

1 引言

流量測量是互聯(lián)網(wǎng)研究的重要領(lǐng)域，是網(wǎng)絡(luò)體系研究、網(wǎng)絡(luò)異常檢測和服務(wù)質(zhì)量(Quality of Service, QoS)管理的基礎(chǔ)[1,2]。目前對互聯(lián)網(wǎng)流量進行測量多以流為基本單元，即具有相同五元組(源目IP地址、源目端口號和協(xié)議類型)的數(shù)據(jù)分組集合。隨著網(wǎng)絡(luò)鏈路帶寬的增加，在高速網(wǎng)絡(luò)環(huán)境中并發(fā)網(wǎng)絡(luò)流巨大，難以緩存所有流信息進行流量測量[3]。在諸如大規(guī)模網(wǎng)絡(luò)安全事件等應(yīng)用中，只關(guān)注網(wǎng)絡(luò)中的大流量對象。因此長流檢測算法，也稱為大流檢測算法，成為網(wǎng)絡(luò)測量領(lǐng)域研究的熱點之一[4]。

本文中的長流是指在一定的測量時間段內(nèi)流大小達(dá)到或超過閾值的流。當(dāng)前主要的長流檢測方法可以分為3類：概率抽樣方法、流鏈表方法和計數(shù)布魯姆過濾器(Count Bloom Filter, CBF)方法。

代表性的概率抽樣方法為Estan等人[5]提出的抽樣保持(Sample and Hold, SH)算法，其基本思想為：當(dāng)某個數(shù)據(jù)報文到達(dá)時，如果該報文所屬的流已被抽中，則更新該流記錄；否則以一定概率p采樣該報文。該方法實現(xiàn)簡單，但是單純以概率p進行抽樣，誤差較大。

在流鏈表方法上，文獻(xiàn)[6]中提出將最近最久未使用(Least Recently Used, LRU)算法應(yīng)用到長流檢測中，算法的核心思想是：在有新流到達(dá)時，將最久未有報文的流替換出去，該算法只需維護鏈路中活躍流狀態(tài)，不用定時掃描流表，將已結(jié)束流釋放，減少了系統(tǒng)開銷。LRU算法有很多改進方案：文獻(xiàn)[7]提出基于LRU和布魯姆過濾器(Bloom Filter, BF)的長流檢測機制，將長流過濾和長流判斷分離，進一步降低了長流淘汰的錯誤概率；文獻(xiàn)[8]提出基于流更新頻率和大小的大流檢測算法(Flow Extracting with Frequency & Size, FEFS)，在鏈表中通過淘汰小流來保存和更新大流信息。流鏈表方法為了定位流表，需要保留每個流的五元組信息，占用空間較大，而且通過哈希函數(shù)定位流表，哈希沖突時需順序查詢沖突鏈表，開銷較高。

CBF方法由于實現(xiàn)結(jié)構(gòu)簡單，易于硬件實現(xiàn)，在長流檢測算法中一直被廣泛應(yīng)用。最初的CBF長流檢測算法為文獻(xiàn)[5]提出的多級過濾器算法(Multistage Filters, MF)，該算法應(yīng)用多個哈?？臻g對流的報文進行計數(shù)，如果每個哈?？臻g相應(yīng)的流計數(shù)器都超過了預(yù)設(shè)定的閾值，則認(rèn)為該流是長流。文獻(xiàn)[9]提出基于多粒度計數(shù)布魯姆過濾器的長流識別算法，采用空間大小遞減的多個CBF對流長度進行計數(shù)，算法所需存儲空間相對傳統(tǒng)流表方法和CBF方法都有所減少。文獻(xiàn)[10]提出基于雙重計數(shù)布魯姆過濾器進行長流識別和抽樣，將長流過濾和長流存在分開進行處理，與MF算法相比，具有更高的準(zhǔn)確度。

基于CBF的長流檢測算法存在空間擁塞問題。對于TCP流，通過報文的FIN/RST等標(biāo)志判斷流結(jié)束，可以將流占用的計數(shù)器清除。但是網(wǎng)絡(luò)鏈路中還存在大量無結(jié)束標(biāo)志的IP流，如SYN攻擊報文、路由變化等原因產(chǎn)生的無結(jié)束標(biāo)志TCP流，以及占網(wǎng)絡(luò)流量比重越來越多的UDP流[11]等。因此，對于這些無結(jié)束標(biāo)志的IP流，如何判斷流結(jié)束，并及時將這些已終結(jié)流對應(yīng)的計數(shù)器清除，是CBF方法面臨的難題。文獻(xiàn)[9]中采用定時更新方法，定時清除CBF中占用的計數(shù)器空間。但定時更新方法割裂了定時時刻前后兩個時間段流之間的關(guān)系，容易導(dǎo)致測量誤差。此外每次定時更新都需要檢測所有計數(shù)器空間，額外增加了處理開銷，尤其當(dāng)計數(shù)器空間較大時，定時更新的開銷對測量系統(tǒng)性能影響較大。

在流量測量領(lǐng)域，一些研究關(guān)注如何通過合理的超時機制將結(jié)束的數(shù)據(jù)流資源及時釋放。文獻(xiàn)[12]采用固定64 s超時機制對流結(jié)束進行判斷，并通過實驗驗證該方法在大部分情況下具有較好的效果。但64 s超時只是對大部分流有效，部分慢流還是會被截斷為多流，導(dǎo)致系統(tǒng)產(chǎn)生誤判。文獻(xiàn)[13]提出二進制指數(shù)超時(Measurement-based Binary Exponential Timeout, MBET)的流超時算法，根據(jù)每個流的數(shù)據(jù)報文吞吐量、報文間隔等信息動態(tài)調(diào)整超時時間，實現(xiàn)盡快將已結(jié)束流資源釋放。文獻(xiàn)[14]提出了一種基于流速測度的動態(tài)超時策略，對長流和短流采用不同的超時策略和預(yù)制。文獻(xiàn)[15]提出了針對不同長度的UDP流采用不同超時方式的超時策略：對單報文流采用空間受限方式淘汰過期流，對短流采用MBET策略淘汰過期流，對于長流采用預(yù)測包間隔方法來設(shè)置流超時值。這3種方法均需要利用流的歷史信息計算流的流量特性，因此難以在CBF結(jié)構(gòu)上應(yīng)用。文獻(xiàn)[16]提出了超時布魯姆過濾器(Timeout Bloom Filter, TBF)進行包抽樣的方法，其原理是：在布魯姆過濾器向量中保存舊報文到達(dá)的時間戳，根據(jù)新報文到達(dá)時間戳是否超時，判斷報文是否屬于需要抽樣的新流，避免了布魯姆過濾器空間擁塞導(dǎo)致的誤判問題。

本文基于CBF和TBF的思想，設(shè)計了適用于檢測無結(jié)束標(biāo)志IP長流的超時計數(shù)布魯姆過濾器(Count Timeout Bloom Filter, CTBF)結(jié)構(gòu)，該結(jié)構(gòu)由計數(shù)器向量和計時器向量組成，一方面通過計數(shù)器向量記錄IP流的報文數(shù)量判斷長流，另一方面通過計時器向量記錄IP流最后報文的到達(dá)時刻，及時將已終結(jié)流占用的計數(shù)器自動清除，解決了無結(jié)束標(biāo)志IP流導(dǎo)致的布魯姆過濾器空間擁塞問題；分析了CTBF長流檢測結(jié)構(gòu)的誤差與計時器超時時間的關(guān)系，在此基礎(chǔ)上提出了自適應(yīng)超時計數(shù)布魯姆過濾器(Adaptive Count Timeout Bloom Filter, ACTBF)長流檢測算法，根據(jù)鏈路流到達(dá)強度與布魯姆過濾器向量空間長度自適應(yīng)調(diào)整超時時間，使得算法的整體錯誤率始終保持在較優(yōu)范圍。本文后續(xù)部分組織如下: 第2節(jié)是自適應(yīng)超時的CTBF長流檢測算法的設(shè)計與分析；第3節(jié)通過實驗對算法進行了驗證；第4節(jié)是本文的總結(jié)。

2 自適應(yīng)超時的CTBF長流檢測算法

2.1 CTBF長流檢測結(jié)構(gòu)

CTBF結(jié)構(gòu)由k個獨立的哈希函數(shù)h1,h2,…,hk以及長度均為m的兩個向量Vc和Vt組成。每個哈希函數(shù)相互獨立且函數(shù)取值范圍為{1,2,…,m}。向量Vc的每一維設(shè)置成一個計數(shù)器，記為c(i)，初值設(shè)為0，記錄流報文計數(shù)。向量Vt的每一維設(shè)置成一個計時器，記為t(i)，初值設(shè)為當(dāng)前時刻，記錄最近報文的時間戳。

CTBF結(jié)構(gòu)的長流檢測原理為：對于流集合S={s1,s2,…,sn}中的任一元素si，通過k個哈希函數(shù)得到k個取值范圍為[1,m]之間的值，從而映射到向量Vc和Vt的k個存儲單元，分別進行更新。計數(shù)器向量Vc的更新操作是把k個存儲單元的計數(shù)器加1，并判斷是否超過長流閾值。計時器向量Vt的更新操作是把k個存儲單元的時間戳更新為當(dāng)前時間戳，并判斷k個存儲單元原先保留的時間戳與當(dāng)前時間戳的差值是否超過設(shè)定的超時門限，如果超過則判斷為新流，并清除計數(shù)器向量Vc對應(yīng)的存儲單元。因此，通過計時器向量Vt進行更新操作，CTBF結(jié)構(gòu)即可將已終結(jié)流占用的計數(shù)器自動清除，節(jié)省了處理開銷。

假設(shè)N為長流報文閾值，T為預(yù)設(shè)的流報文超時時間，CTBF算法的主要過程是：

(1)設(shè)一個報文在t時刻到達(dá)，提取流標(biāo)識s(源IP地址、源端口號、目的IP地址、目的端口號、協(xié)議類型)作為哈希函數(shù)的輸入，得到k個哈希值hj(s)，且1≤j≤k；

(2)計算報文間隔時間Δtj，其中Δtj=t -t(hj(s))，且1≤j≤k；

(3)更新向量Vt中計時器t(hj(s))=t；

(4)如果存在Δtj≥T，則認(rèn)為此報文為新流的首報文，更新向量Vc中計數(shù)器c(hi(s))=1，其中i取值滿足Δtj≥T，且1≤j≤k；

(5)如果對于任意j(1≤j≤k)，均有Δtj≤T成立，則認(rèn)為此報文所屬流已存在，更新向量Vc中計數(shù)器c(hj(s))=c(hj(s))+1，取cmin=min(c(hj(s)))，如果cmin＞N，標(biāo)記該流為長流。

圖1為t時刻收到報文為新流首報文和舊流中間報文時CTBF結(jié)構(gòu)的處理示意圖。圖1(a)為收到新流首報文時，CTBF結(jié)構(gòu)向量Vc和Vt存儲單元的變化示意，其中哈希函數(shù)個數(shù)k=3，流對應(yīng)的哈希值分別為1,2,m?1，當(dāng)前時間戳為t。收到該報文后，向量Vt對應(yīng)的計時器均更新為t，由于只有t1計時器超時，向量Vc只有c(1)數(shù)值變?yōu)?，其他存儲單元不變。圖1(b)為收到舊流中間報文時，CTBF結(jié)構(gòu)向量Vc和Vt存儲單元的變化示意，流對應(yīng)的哈希值分別為1,2,m?1，當(dāng)前時間戳為t，沒有計時器超時。收到該報文后，向量Vt對應(yīng)的計時器均更新為t，由于沒有計時器超時，向量Vc對應(yīng)的計數(shù)器均加1。

2.2 CTBF長流檢測結(jié)構(gòu)誤差分析

基于CTBF結(jié)構(gòu)進行長流檢測的誤差主要由兩部分組成：一方面，CTBF結(jié)構(gòu)通過多個哈希函數(shù)降低哈希映射沖突的概率，但依然會存在“假陽性誤判”，使得部分短流因為哈希沖突誤判為長流；另一方面，超時機制難以避免會將慢的長流截斷為多個流，從而導(dǎo)致長流被誤判為短流或長流的流長統(tǒng)計出現(xiàn)錯誤。

2.2.1 超時時間與布魯姆過濾器誤判的關(guān)系 布魯姆過濾器的誤判可以表達(dá)為：當(dāng)新流到達(dá)時，在向量Vt中，由k個哈希函數(shù)計算的k個時間戳均未超時，這種情況下新流會被誤判為已存在的活躍流，從而產(chǎn)生錯誤判斷。

假設(shè)網(wǎng)絡(luò)中有n個活躍流，向量Vt長度為m，由于活躍流對應(yīng)的向量Vt中的k×n個時間戳均被及時更新，則向量Vt中某個時間戳判斷為超時的概率為

而新流被誤判的前提是其對應(yīng)的k個時間戳值均未超時，因此新流被誤判概率為

由式(2)可知，在向量Vt長度m和哈希函數(shù)k固定的情況下，算法誤判率與網(wǎng)絡(luò)中活躍流數(shù)量n正相關(guān)。對于CTBF結(jié)構(gòu)，已經(jīng)結(jié)束但沒有達(dá)到超時閾值的流都被認(rèn)為是活躍流，因此CTBF結(jié)構(gòu)下活躍流數(shù)量n與算法的超時閾值T相關(guān)。

定理1 設(shè)網(wǎng)絡(luò)鏈路中流到達(dá)服從強度為λ的泊松分布，流實際結(jié)束過程服從參數(shù)為μ的指數(shù)分布，T為流結(jié)束后的超時閾值，則穩(wěn)態(tài)下系統(tǒng)測量的平均流數(shù)量EX可以表示為：EX=λT+λ/μ。

證明 由于流到達(dá)過程為泊松過程，其到達(dá)間隔時間序列記為S ={Sk,k ≥0}，設(shè)超時時間T對應(yīng)的時間序列下標(biāo)k=t，則超時時間T以后流到達(dá)間隔時間序列是S的子集，記為S'={Sk+t,k ≥0},S'服從以λ為參數(shù)的指數(shù)分布。

由于流的結(jié)束過程服從指數(shù)分布，其持續(xù)時間序列記為B ={Bk,k ≥1},B服從以μ為參數(shù)的指數(shù)分布。

圖1 t時刻收到新流首報文和中間報文時CTBF處理示意圖

設(shè)X ={X(t),t≥0}為時刻t+T時系統(tǒng)測量的網(wǎng)絡(luò)流數(shù)量，XT為T時刻到達(dá)的網(wǎng)絡(luò)流數(shù)量，則記X'={X(t)?XT,t ≥0}。

根據(jù)生滅過程的性質(zhì)，其平穩(wěn)分布存在，可表示為

顯然，X'(t)為生滅過程，其出生率和死亡率分別為

因此可得X(t)穩(wěn)態(tài)下的均值

由于流到達(dá)過程為泊松過程，T時刻的到達(dá)的網(wǎng)絡(luò)流平均數(shù)量為λT，因此有

證畢

將式(6)代入式(2)，可得布魯姆過濾器的誤判率為

記θ=λ/m，由于1/μ?T，因此式(7)可以表示為

定義1 空間充滿速率θ為網(wǎng)絡(luò)鏈路流到達(dá)強度λ與向量空間長度m的比值。其物理含義為，在不考慮流結(jié)束情況下，一個空的布魯姆過濾器向量空間被占滿的速率。

設(shè)定哈希函數(shù)個數(shù)k為4，向量長度m為107，網(wǎng)絡(luò)鏈路流到達(dá)強度λ=2000，即θ為1/500時，根據(jù)上式仿真了超時閾值與布魯姆過濾器的誤判率的關(guān)系曲線，如圖2所示。從圖中可以看出，隨著超時閾值增加，布魯姆過濾器誤判率增加，超時閾值越小誤判率下降速度越快。

2.2.2 超時時間與長流截斷概率的關(guān)系 對網(wǎng)絡(luò)中的流報文到達(dá)間隔的研究發(fā)現(xiàn)：隨著報文到達(dá)時間的增加，在指定時段內(nèi)到達(dá)報文的數(shù)量逐漸減小，而且報文數(shù)減小的幅度也逐漸減小[14]。這說明隨著超時時間增加，流截斷概率逐漸減少，而且其減少的幅度也不斷減少。本節(jié)通過網(wǎng)絡(luò)真實流量數(shù)據(jù)，分析了超時時間與長流截斷概率的關(guān)系。流量數(shù)據(jù)選自美國國家實驗室 NLANR 公開的被動型測量數(shù)據(jù)，數(shù)據(jù)源文件為ERF格式[17]，流量數(shù)據(jù)分別采自Waikato大學(xué)校園網(wǎng)和新西蘭的某個ISP，為保護用戶隱私，流量數(shù)據(jù)中僅僅包含數(shù)據(jù)報文的頭部。

圖2 超時閾值與布魯姆過濾器誤判率的關(guān)系

實驗方法為統(tǒng)計數(shù)據(jù)集中每流的最大報文間隔，如果流的最大報文間隔大于超時時間T，則認(rèn)為該流在超時時間T時被截斷。圖3列出了數(shù)據(jù)集中報文數(shù)大于20, 50和100的長流截斷概率與超時時間的關(guān)系。橫坐標(biāo)為超時時間，圖3(a), 3(c)縱坐標(biāo)為截斷概率，圖3(b), 3(d)縱坐標(biāo)為截斷概率的自然對數(shù)。從圖中可以看出，流截斷概率為超時時間的負(fù)指數(shù)函數(shù)，并且報文數(shù)大于20, 50和100的流的截斷概率曲線基本重合。以新西蘭ISP數(shù)據(jù)集為例，在超時時間為200 s時截斷概率取值約為2.4%，在100 s時取值約為9.2%，在64 s時取值約為15.1%。根據(jù)這一分析，采用文獻(xiàn)[12]的固定64 s超時機制，高達(dá)15.1%的長流會被截斷。

通過圖3(b), 3(d)超時時間與截斷概率的自然對數(shù)關(guān)系曲線圖可以看出，截斷概率的自然對數(shù)與超時時間的圖形為多折線，整體上流截斷概率是超時時間的負(fù)指數(shù)函數(shù)，可以表示為

其中β代表了截斷概率隨超時時間的下降速度。利用不同的β，圖3(b), 3(d)中對報文數(shù)＞100的截斷概率曲線按式(9)進行了分段擬合，擬合曲線與實際曲線基本重合。

2.2.3 整體錯誤率分析 根據(jù)上面分析，CTBF結(jié)構(gòu)的整體錯誤率可以表示為

令f(T)=(1?e?kθT)k+αe?βT，則其一階導(dǎo)數(shù)為

當(dāng)kθT遠(yuǎn)小于1，根據(jù)麥克勞林公式，式(11)可以表示為

圖3 超時時間與流截斷概率的關(guān)系

當(dāng)T使得f′(T)等于0時，即T滿足式(13)時，f(T)存在極值。

轉(zhuǎn)換后可得

兩邊取自然對數(shù)后，可得則式(15)可以簡化為：c=lnT+bT 。兩邊取自然指數(shù)得：ec=TebT；兩邊同時乘以b，可得形同朗科函數(shù)的方程：bec=bTebT。根據(jù)朗科函數(shù)定義，方程解形式為

其中W(x)為朗科函數(shù)。因此，當(dāng)T=W(bec)/b 時，函數(shù)f(T)有極值，不難驗證該值為極小值。當(dāng)哈希函數(shù)個數(shù)k為4, CTBF結(jié)構(gòu)的整體錯誤率與超時時間T的關(guān)系曲線如圖4所示。

從圖4可以看出，當(dāng)超時時間較小時，會導(dǎo)致長流被截斷，由此產(chǎn)生錯判，隨著超時時間增加，長流截斷造成的錯判減少，但是由于CTBF結(jié)構(gòu)中活躍流數(shù)量增多，使得布魯姆過濾器空間占用率上升，導(dǎo)致誤判升高，算法存在最優(yōu)的超時時間，使得算法的整體錯誤率最低。

另外隨著空間充滿速率θ的下降，算法的最優(yōu)超時時間也逐步變大，而且算法的整體錯誤率也降低。其原因在于隨著θ下降，布魯姆空間的占用率較低，由于布魯姆過濾器誤判造成的錯誤比重減小，算法可以使用較大的超時時間減少長流被截斷的影響。

圖4 CTBF整體錯誤率與超時時間的關(guān)系

2.3 自適應(yīng)超時機制

根據(jù)2.2節(jié)分析，CTBF長流檢測算法存在使得整體錯誤率最低的最優(yōu)超時時間，該超時時間與空間充滿速率θ，即鏈路中流量到達(dá)速率和布魯姆過濾向量長度相關(guān)。為此，提出基于自適應(yīng)超時機制的ACTBF算法，根據(jù)當(dāng)前鏈路中流到達(dá)強度λ與向量空間長度m，計算測量系統(tǒng)當(dāng)前時刻的空間充滿速率θ，從而得出當(dāng)前時刻使得長流檢測整體錯誤率最低的超時時間T，使得算法的整體錯誤率始終保持在較優(yōu)范圍。

計算最優(yōu)超時時間涉及對數(shù)計算、求解朗科函數(shù)等較復(fù)雜的數(shù)學(xué)運算，在測量系統(tǒng)中實時求解會影響系統(tǒng)處理速度。在實際應(yīng)用中，可以對空間充滿速率θ設(shè)定有限個取值區(qū)段，預(yù)先計算對應(yīng)θ區(qū)段的最優(yōu)超時時間T，通過查表方式獲得當(dāng)前θ對應(yīng)的近似最優(yōu)超時時間T。

3 算法驗證

本文選擇2.2節(jié)的數(shù)據(jù)集對ACTBF算法的長流檢測準(zhǔn)確率進行驗證。兩個數(shù)據(jù)集的流到達(dá)速率λ如圖5(a), 5(b)所示。當(dāng)k=4，布魯姆過濾器向量長度m為106時，對應(yīng)的最優(yōu)超時時間T變化情況如圖5(c), 5(d)所示?？梢钥闯鯥SP數(shù)據(jù)集的流到達(dá)速率λ主要在1000～1500之間波動，Waikato校園網(wǎng)數(shù)據(jù)集的流到達(dá)速率λ相對較小，主要在500～1000之間波動。但是Waikato數(shù)據(jù)集在時間為210 s, 563 s和672 s時刻出現(xiàn)突發(fā)流量，在210 s處流到達(dá)速率為2632，達(dá)到平均流速的一倍，其對應(yīng)的最優(yōu)超時時間T也相應(yīng)變小。

設(shè)置哈希函數(shù)k=4，長流檢測閾值N=100，在布魯姆過濾器向量長度為106時，ACTBF算法與固定超時CTBF算法的準(zhǔn)確率進行測試，結(jié)果如圖6所示，橫坐標(biāo)為固定超時算法設(shè)置的超時時間，范圍為從48 s到384 s，縱坐標(biāo)為長流誤判概率。對于固定超時CTBF算法，隨著超時時間的增加，長流檢測錯誤率先下降然后再逐漸升高，而ACTBF無需設(shè)置超時時間，其檢測錯誤率為固定值。

由于目前的基于CBF結(jié)構(gòu)的長流檢測算法，如MF, CCBF等，都只能檢測有結(jié)束標(biāo)志的TCP長流，只有LRU類長流檢測算法能夠適用于檢測UDP長流或無結(jié)束標(biāo)志的TCP長流。因此，本文選擇LRU, LRU-BF與ACTBF算法，在占用相同內(nèi)存空間的條件下進行實驗。數(shù)據(jù)源選擇New Zealand ISP數(shù)據(jù)，哈希函數(shù)k=4，長流檢測閾值N=100, LRU算法中單流記錄占用空間為22 Byte(五元組13 Byte、報文計數(shù)1 Byte、雙向鏈表指針8 Byte)。算法的錯誤率比較結(jié)果如圖7所示。從圖中可以看出，在占用相同的存儲空間條件下，ACTBF算法的準(zhǔn)確率高于LRU和LRU-BF算法，這是因為LRU類算法需要存儲流的五元組和鏈表指針等信息，在相同存儲空間下其可存放的流表記錄大幅度減少，導(dǎo)致流反復(fù)被淘汰，影響了準(zhǔn)確率。從圖7也可以看出，同樣錯誤率條件下，ACTBF比LRU算法所需內(nèi)存空間都少，當(dāng)錯誤率為1%時，ACTBF, LRUBF和LRU對應(yīng)的內(nèi)存占用分別為6 MB, 11 MB和21 MB。與LRU算法相比，由于ACTB算法需要計算k個哈希函數(shù)值，因此當(dāng)k取值較大時，影響算法處理速度。但是ACTBF算法邏輯相對簡單，在實際系統(tǒng)設(shè)計時，可以將哈希函數(shù)采用硬件實現(xiàn)并行處理，提高處理速度。

4 結(jié)束語

在實際網(wǎng)絡(luò)鏈路中，流量到達(dá)強度及長度分布復(fù)雜多變，根據(jù)流量的變化，自適應(yīng)調(diào)整相關(guān)參數(shù)的大流識別方法具有重要意義[4]。本文提出一種適合在高速網(wǎng)絡(luò)中檢測無結(jié)束標(biāo)志IP長流的ACTBF長流檢測算法。算法設(shè)計基于兩個布魯姆過濾器組合結(jié)構(gòu)：計數(shù)布魯姆過濾器，實現(xiàn)了流的高效報文計數(shù)，節(jié)省了存儲空間；超時布魯姆過濾器及時釋放已結(jié)束的流占用的空間。超時布魯姆過濾器中超時時間根據(jù)鏈路流到達(dá)強度與布魯姆過濾器向量空間長度自適應(yīng)動態(tài)調(diào)整，使得算法整體錯誤率始終保持最低。

本文利用真實互聯(lián)網(wǎng)流量數(shù)據(jù)集對算法進行了實驗驗證，實驗結(jié)果表明：固定超時CTBF算法的錯誤率隨流量的到達(dá)速率波動較大，而動態(tài)調(diào)整超時時間的ACTBF的錯誤率較穩(wěn)定，并且性能優(yōu)于固定超時CTBF算法的最優(yōu)值。與LRU和LRU-BF算法的比較說明，在同等條件下，ACTBF算法的準(zhǔn)確率更高。

[1] 蘭巨龍, 程東年, 胡宇翔. 可重構(gòu)信息通信基礎(chǔ)網(wǎng)絡(luò)體系研究[J]. 通信學(xué)報, 2014, 1(1): 128-139.

圖5 測試數(shù)據(jù)集流到達(dá)速率以及算法超時時間的變化情況

圖6 固定超時CTBF算法與ACTBF算法的準(zhǔn)確率比較

圖7 占用相同內(nèi)存情況下ACTBF 算法與LRU類算法的比較

Lan Ju-long, Cheng Dong-nian, and Hu Yu-xiang. Research on reconfigurable information communication basal network architecture[J]. Journal on Communications, 2014, 1(1): 128-139.

[2] He Ke-qiang, Hu Cheng-chen, Jiang Jun-chen, et al.. Anti-attack counters for traffic measurement[C]. Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM 2010), Miami, USA, 2010: 1-5.

[3] 周愛平, 程光, 郭曉軍. 高速網(wǎng)絡(luò)流量測量方法. 軟件學(xué)報[J]. 2014, 25(1): 135-153.

Zhou Ai-ping, Cheng Guang, and Guo Xiao-jun. High-speed network traffic measurement method[J]. Journal of Software, 2014, 25(1): 135-153.

[4] 夏靖波, 任高明. 大流識別方法綜述[J]. 控制與決策, 2013, 28(6): 801-807. Xia Jing-bo and Ren Gao-ming. Survey on elephant flow identifying methods[J]. Control and Decision, 2013, 28(6): 801-807.

[5] Estan C and Varghese G. New directions in traffic measurement and accounting: focusing on elephants, ignoring the mice[J]. ACM Transactions on Computer Systems, 2003, 21(3): 270-313.

[6] 王洪波, 裴育杰, 林宇, 等. 基于LRU的大流檢測算法[J]. 電子與信息學(xué)報, 2007, 29(10): 2487-2492.

[7] 張震, 汪斌強, 張風(fēng)雨, 等. 基于LRU-BF策略的網(wǎng)絡(luò)流量測量算法[J]. 通信學(xué)報, 2013, 34(1): 111-120.

Zhang Zhen, Wang Bin-qiang, Zhang Feng-yu, et al.. Traffic measurement algorithm based on least recent used and Bloom filter[J]. Journal on Communications, 2013, 34(1): 111-120.

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

Wang Feng-yu, Guo Shan-qing, Li Liang-xiong, et al.. A method of extracting heavy-hitter flows efficiently[J]. Journal of Computer Research and Development, 2013, 50(4): 731-740.

[9] 周明中, 龔儉, 丁偉, 等. 基于MGCBF算法的長流信息統(tǒng)計[J]. 東南大學(xué)學(xué)報(自然科學(xué)版), 2006, 36(3): 472-476.

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

[11] Zhang M, Dusi M, John W, et al.. Analysis of udp traffic usage on internet backbone links[C]. Proceedings of 9th Annual International Symposium on Applications and the Internet(SAINT 2009), Seattle, USA, 2009: 280-281.

[12] Claffy K C, Braun H W, and Polyzos G C. A parameterizable methodology for Internet traffic flow profiling[J]. IEEE Journal on Communications, 1995, 13(8): 1481-1494.

[13] Ryu B, Cheney D, and Braun H W. Internet flow characterization: adaptive timeout strategy and statistical modeling[C]. Proceedings of Passive and Active Measurements, Amsterdam, Netherlands, 2001: 94-105.

[14] 周明中, 龔儉, 丁偉. 高速網(wǎng)絡(luò)中基于流速測度的動態(tài)超時策略[J]. 軟件學(xué)報, 2005, 16(5): 562-568.

[15] 趙小歡, 夏靖波, 朱長虹. 高速網(wǎng)絡(luò) UDP 流超時策略研究[J]. 合肥工業(yè)大學(xué)學(xué)報(自然科學(xué)版), 2013, 36(2): 176-180.

Zhao Xiao-huan, Xia Jing-bo, and Zhu Chang-hong. Research on UDP flow timeout strategy in high-speed network[J]. Journal of Hefei University of Technology (Natural Science Edition), 2013, 36(2): 176-180.

[16] Kong S, He T, Shao X, et al.. Time-out bloom filter: a new sampling method for recording more flows[C]. Proceedings of the International Conference on Information Networking (ICOIN 2006), Sendai, Japan, 2006: 590-599.

[17] NLANR. National Laboratory for Applied Network Research [OL]. http://pma.nlanr.net/.2014. 04

侯 穎： 女，1973年生，副研究員，研究方向為網(wǎng)絡(luò)測量和網(wǎng)絡(luò)信息安全.

黃 海： 男，1975年生，副教授，研究方向為網(wǎng)絡(luò)體系結(jié)構(gòu)和網(wǎng)絡(luò)信息安全.

蘭巨龍： 男，1962年生，教授，研究方向為網(wǎng)絡(luò)體系結(jié)構(gòu)和路由交換技術(shù).

李 鵬： 男，1978年生，工程師，研究方向為網(wǎng)絡(luò)流量測量.

朱圣平： 男，1967年生，工程師，研究方向為網(wǎng)絡(luò)管理.

An Adaptive Timeout Counter Bloom Filter Algorithm for Traffic Measurement

Hou Ying Huang Hai Lan Ju-long Li Peng Zhu Sheng-ping
(National Digital Switching System Engineering & Technological R&D Center, Zhengzhou 450002, China)

A novel mechanism combining Counting Bloom Filter (CBF) and Timeout Bloom Filter (TBF) is proposed, aiming at identifying IP long flow precisely. By adjusting the timeout dynamically and deleting end flows timely, the mechanism can solve the space congestion of Bloom filter and identify heavy hitters without normal end flag. The timeout and accuracy are analyzed. When adjusting the timeout dynamically according to the traffic arrival intensity and Bloom filter vector length, the mechanism can get minimum error. The experiments are conducted based on the real network trace. The results demonstrate that the proposed method is more accurate than the existing algorithms.

Network measurement; Traffic measurement; Heavy hitters; Dynamic adjust

TP393.06

： A

：1009-5896(2015)04-0887-07

10.11999/JEIT140820

2014-06-23收到，2014-09-15改回

國家自然科學(xué)基金(61309019)和國家863計劃項目(201101A103, 2011AA010603)資助課題

*通信作者：侯穎 ndschy@139.com