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

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

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

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

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

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

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

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

1 引言

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

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

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

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

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

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

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

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

2 自適應超時的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ù)器，記為c(i)，初值設為0，記錄流報文計數(shù)。向量Vt的每一維設置成一個計時器，記為t(i)，初值設為當前時刻，記錄最近報文的時間戳。

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

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

(1)設一個報文在t時刻到達，提取流標識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，則認為此報文為新流的首報文，更新向量Vc中計數(shù)器c(hi(s))=1，其中i取值滿足Δtj≥T，且1≤j≤k；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

證畢

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

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

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

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

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

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

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

通過圖3(b), 3(d)超時時間與截斷概率的自然對數(shù)關(guān)系曲線圖可以看出，截斷概率的自然對數(shù)與超時時間的圖形為多折線，整體上流截斷概率是超時時間的負指數(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，則其一階導數(shù)為

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

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

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

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

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

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

2.3 自適應超時機制

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

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

3 算法驗證

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

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

由于目前的基于CBF結(jié)構(gòu)的長流檢測算法，如MF, CCBF等，都只能檢測有結(jié)束標志的TCP長流，只有LRU類長流檢測算法能夠適用于檢測UDP長流或無結(jié)束標志的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算法的準確率高于LRU和LRU-BF算法，這是因為LRU類算法需要存儲流的五元組和鏈表指針等信息，在相同存儲空間下其可存放的流表記錄大幅度減少，導致流反復被淘汰，影響了準確率。從圖7也可以看出，同樣錯誤率條件下，ACTBF比LRU算法所需內(nèi)存空間都少，當錯誤率為1%時，ACTBF, LRUBF和LRU對應的內(nèi)存占用分別為6 MB, 11 MB和21 MB。與LRU算法相比，由于ACTB算法需要計算k個哈希函數(shù)值，因此當k取值較大時，影響算法處理速度。但是ACTBF算法邏輯相對簡單，在實際系統(tǒng)設計時，可以將哈希函數(shù)采用硬件實現(xiàn)并行處理，提高處理速度。

4 結(jié)束語

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

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

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

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

圖6 固定超時CTBF算法與ACTBF算法的準確率比較

圖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)絡流量測量方法. 軟件學報[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]. 電子與信息學報, 2007, 29(10): 2487-2492.

[7] 張震, 汪斌強, 張風雨, 等. 基于LRU-BF策略的網(wǎng)絡流量測量算法[J]. 通信學報, 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] 王風宇, 郭山清, 李亮雄, 等. 一種高效率的大流提取方法[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]. 東南大學學報(自然科學版), 2006, 36(3): 472-476.

[10] 吳樺, 龔儉, 楊望. 一種基于雙重Counter Bloom Filter的長流識別算法[J]. 軟件學報, 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)絡中基于流速測度的動態(tài)超時策略[J]. 軟件學報, 2005, 16(5): 562-568.

[15] 趙小歡, 夏靖波, 朱長虹. 高速網(wǎng)絡 UDP 流超時策略研究[J]. 合肥工業(yè)大學學報(自然科學版), 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)絡測量和網(wǎng)絡信息安全.

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

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

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

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

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改回

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

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