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

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

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

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

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

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

網(wǎng)絡(luò)測量；流量測量；長流；動(dòng)態(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]。目前對(duì)互聯(lián)網(wǎng)流量進(jìn)行測量多以流為基本單元，即具有相同五元組(源目IP地址、源目端口號(hào)和協(xié)議類型)的數(shù)據(jù)分組集合。隨著網(wǎng)絡(luò)鏈路帶寬的增加，在高速網(wǎng)絡(luò)環(huán)境中并發(fā)網(wǎng)絡(luò)流巨大，難以緩存所有流信息進(jìn)行流量測量[3]。在諸如大規(guī)模網(wǎng)絡(luò)安全事件等應(yīng)用中，只關(guān)注網(wǎng)絡(luò)中的大流量對(duì)象。因此長流檢測算法，也稱為大流檢測算法，成為網(wǎng)絡(luò)測量領(lǐng)域研究的熱點(diǎn)之一[4]。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 t時(shí)刻收到新流首報(bào)文和中間報(bào)文時(shí)CTBF處理示意圖

設(shè)X ={X(t),t≥0}為時(shí)刻t+T時(shí)系統(tǒng)測量的網(wǎng)絡(luò)流數(shù)量，XT為T時(shí)刻到達(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時(shí)刻的到達(dá)的網(wǎng)絡(luò)流平均數(shù)量為λT，因此有

證畢

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

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

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

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

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

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

實(shí)驗(yàn)方法為統(tǒng)計(jì)數(shù)據(jù)集中每流的最大報(bào)文間隔，如果流的最大報(bào)文間隔大于超時(shí)時(shí)間T，則認(rèn)為該流在超時(shí)時(shí)間T時(shí)被截?cái)?。圖3列出了數(shù)據(jù)集中報(bào)文數(shù)大于20, 50和100的長流截?cái)喔怕逝c超時(shí)時(shí)間的關(guān)系。橫坐標(biāo)為超時(shí)時(shí)間，圖3(a), 3(c)縱坐標(biāo)為截?cái)喔怕?，圖3(b), 3(d)縱坐標(biāo)為截?cái)喔怕实淖匀粚?duì)數(shù)。從圖中可以看出，流截?cái)喔怕蕿槌瑫r(shí)時(shí)間的負(fù)指數(shù)函數(shù)，并且報(bào)文數(shù)大于20, 50和100的流的截?cái)喔怕是€基本重合。以新西蘭ISP數(shù)據(jù)集為例，在超時(shí)時(shí)間為200 s時(shí)截?cái)喔怕嗜≈导s為2.4%，在100 s時(shí)取值約為9.2%，在64 s時(shí)取值約為15.1%。根據(jù)這一分析，采用文獻(xiàn)[12]的固定64 s超時(shí)機(jī)制，高達(dá)15.1%的長流會(huì)被截?cái)唷?/p>

通過圖3(b), 3(d)超時(shí)時(shí)間與截?cái)喔怕实淖匀粚?duì)數(shù)關(guān)系曲線圖可以看出，截?cái)喔怕实淖匀粚?duì)數(shù)與超時(shí)時(shí)間的圖形為多折線，整體上流截?cái)喔怕适浅瑫r(shí)時(shí)間的負(fù)指數(shù)函數(shù)，可以表示為

其中β代表了截?cái)喔怕孰S超時(shí)時(shí)間的下降速度。利用不同的β，圖3(b), 3(d)中對(duì)報(bào)文數(shù)＞100的截?cái)喔怕是€按式(9)進(jìn)行了分段擬合，擬合曲線與實(shí)際曲線基本重合。

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

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

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

圖3 超時(shí)時(shí)間與流截?cái)喔怕实年P(guān)系

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

轉(zhuǎn)換后可得

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

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

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

另外隨著空間充滿速率θ的下降，算法的最優(yōu)超時(shí)時(shí)間也逐步變大，而且算法的整體錯(cuò)誤率也降低。其原因在于隨著θ下降，布魯姆空間的占用率較低，由于布魯姆過濾器誤判造成的錯(cuò)誤比重減小，算法可以使用較大的超時(shí)時(shí)間減少長流被截?cái)嗟挠绊憽?/p>

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

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

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

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

3 算法驗(yàn)證

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

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

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

4 結(jié)束語

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

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

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

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

圖6 固定超時(shí)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é)報(bào)[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] 夏靖波, 任高明. 大流識(shí)別方法綜述[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é)報(bào), 2007, 29(10): 2487-2492.

[7] 張震, 汪斌強(qiáng), 張風(fēng)雨, 等. 基于LRU-BF策略的網(wǎng)絡(luò)流量測量算法[J]. 通信學(xué)報(bào), 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].計(jì)算機(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ì)[J]. 東南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2006, 36(3): 472-476.

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

[15] 趙小歡, 夏靖波, 朱長虹. 高速網(wǎng)絡(luò) UDP 流超時(shí)策略研究[J]. 合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(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年生，副研究員，研究方向?yàn)榫W(wǎng)絡(luò)測量和網(wǎng)絡(luò)信息安全.

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

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

李 鵬： 男，1978年生，工程師，研究方向?yàn)榫W(wǎng)絡(luò)流量測量.

朱圣平： 男，1967年生，工程師，研究方向?yàn)榫W(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計(jì)劃項(xiàng)目(201101A103, 2011AA010603)資助課題

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