基于改進型Bloom Filter 的網(wǎng)絡(luò)流抽樣算法

王少龍， 張毅卜， 徐 敏， 陳 珍， 夏靖波

（空軍工程大學(xué) 信息與導(dǎo)航學(xué)院， 陜西 西安 710077）

作為網(wǎng)絡(luò)流量測量的重要組成部分，網(wǎng)絡(luò)流測量將大量具有統(tǒng)一屬性的數(shù)據(jù)分組聚類分析[1]，有效的節(jié)約了測量過程中所需的存儲資源，更好地反應(yīng)了用戶的行為特征，逐漸受到重視。

傳統(tǒng)的固定周期抽樣和簡單隨機抽樣中廣泛存在對小流數(shù)據(jù)抽樣不足的缺點，致使大量流分布信息丟失，不能有效獲得網(wǎng)絡(luò)流的真實分布情況，對于異常檢測等應(yīng)用構(gòu)成了隱患[2]。 因此，有必要以更加公平的方式對網(wǎng)絡(luò)流進行抽樣。文獻[3]在對所有分組歸并的基礎(chǔ)上，對每一個流進行等概率抽樣，其缺點在于不能支持對網(wǎng)絡(luò)流的在線測量。 SGS 算法[4]（Sketch Guided Sampling）將對數(shù)據(jù)分組的抽樣率與其所屬流的流量相結(jié)合，增加了對短流所屬數(shù)據(jù)包的抽樣，對各流的抽樣更加公平。 但SGS 算法必須實時計算相應(yīng)流的流量，對算法的精度造成影響。 文獻[5]提出的算法對哈希函數(shù)的誤差概率進行了計算，通過適時調(diào)整抽樣概率，保證了對網(wǎng)絡(luò)流的等概率抽樣，簡單實用，適合大規(guī)模部署。 但該算法在使用新位向量進行測量時會造成一定數(shù)量的網(wǎng)絡(luò)流被重復(fù)抽樣。SEFS 算法[6]運用多解析度抽樣統(tǒng)計器實現(xiàn)對流的公平抽樣，有效避免了測量過程中的哈希碰撞， 具有良好的空間效率，但其計算過程較為復(fù)雜，不便于大規(guī)模使用。

文中在文獻[5]的基礎(chǔ)上，提出了一種基于改進型Bloom Filter 的網(wǎng)絡(luò)流抽樣算法，有效減少了對網(wǎng)絡(luò)流的重復(fù)抽樣，具有較高的測量精度。

1 相關(guān)工作

1.1 原算法實現(xiàn)過程

在原算法內(nèi)，Bloom Filter 用于判斷數(shù)據(jù)分組所屬網(wǎng)絡(luò)流是否是第一次到達（即新流）；誤差吸收模塊的主要用于計算抽樣過程中產(chǎn)生的誤差概率；隨機抽樣模塊的主要功能是以調(diào)整后的概率對Bloom Filter 認(rèn)定的新流進行抽樣， 算法結(jié)構(gòu)如圖1 所示。

圖1 基于Bloom Filter 的網(wǎng)絡(luò)流抽樣算法Fig. 1 Network flow algorithm based on Bloom Filter

1.2 原算法理論分析

由文獻[7]知，Bloom Filter 在對新流進行判定過程中的誤差概率為：

式（1）中m 為位向量的長度，k 為哈希函數(shù)數(shù)量，n 為已經(jīng)插入Bloom Filter 的網(wǎng)絡(luò)流數(shù)量。 對于到達的數(shù)據(jù)分組使用Bloom Filter 對其進行檢測， 判定其是否已經(jīng)插入Bloom Filter。 由于Bloom Filter 存在檢測誤差，因此任意新流在此階段被成功檢測的概率為。 當(dāng)Bloom Filter 檢測到新流時，調(diào)整隨機抽樣模塊的抽樣概率為r/（1-p）（r 為算法對任意流總的抽樣概率），則可以保證對任意新流的抽樣概率都等于r（即（1-p）×r/1-p）。

為了降低Bloom Filter 的誤差概率， 各個位向量n≥（m/k）×Bmax內(nèi)設(shè)定裝載因子上限Bmax=0.6，當(dāng)流數(shù)量時，使用空位向量進行測量，刷新達到裝載上限的位向量，兩層位向量輪流使用，從而確保測量的連貫性。

文獻[5]所提算法可以快速對到來的網(wǎng)絡(luò)流進行識別和計算，有效吸收了Bloom Filter 產(chǎn)生的誤差，最大限度保證了對網(wǎng)絡(luò)流的等概率抽樣。 但是該算法在第一層位向量進行初始化時，由于第二層位向量為空位向量，會將第一層位向量內(nèi)已識別的部分流重新認(rèn)定為新流，造成對網(wǎng)絡(luò)流的重復(fù)抽樣，浪費了有限的存儲資源。

2 新算法的提出

文中在原算法的基礎(chǔ)上，提出了一種基于新的網(wǎng)絡(luò)流抽樣算法—MBF 算法（Modified Bloom Filter），算法主要包括改進型Bloom Filter、誤差吸收和隨機抽樣3 個模塊。 MBF 算法處理流程如圖2 所示。

圖2 MBF 算法流程Fig. 2 MBF algorithm flow chart

為了便于實際使用， 改進型Bloom Filter 模塊設(shè)置三層位向量，對不同的位向量的裝載因子上限動態(tài)設(shè)置，即將位向量每一次使用時的裝載因子上限在一定范圍內(nèi)隨機設(shè)置。在使用時運用兩層位向量同時對網(wǎng)絡(luò)流展開測量，對兩層位向量所得到的判定結(jié)果取交集。 將3 個位向量分別命名為、A1、A2和A3， 對應(yīng)的動態(tài)裝載因子上限分別表示為為B1、B2和B3。 不同的裝載因子使得位向量之間的初始化時間不同，當(dāng)A1位向量的裝載數(shù)量達到上限時，隨即進行初始化，A2和新位向量A3進行工作。 定義每個位向量都使用一次為一個測量周期，MBF 算法在一個測量周期內(nèi)的實現(xiàn)步驟如下所示。

MBF 算法

1） 分組p′到達，解析其流關(guān)鍵字f；

2） 各位向量分別生成裝載因子上限B1、B2。

3） 通過哈希函數(shù)將f 分別映射到A1，A2位向量；

4） If（A1判定為新流）

5） n1=n1+1

6） else 處理下一個分組

7） End；

8） if（A2判定為新流）

9） n2=n2=1

10） else 處理下一個分組

11） End；

12） If（兩層位向量均判定為新流）；

13） 流數(shù)量n=n+1

14） 計算Bloom Filter 誤差PTBF；

15） 調(diào)整隨機抽樣概率為r/（-pTBF）。

16） End；

17） If（ni（1=1，2）≥（m/k）×Bi（1=1，2）），刷新相 應(yīng)位向 量，生成 裝載因子上限B3使用位向量A3進行測量

18） End；

3 理論分析

3.1 動態(tài)裝載因子上限的設(shè)置

由（1）式知：

即p=eln（1-e-kn/m）k=ekln（1-e）

令p′=k ln（1-e-kn/m），當(dāng)p′取最小值時，p 也為最小值，設(shè)p″=e-kn/m，則

易知，當(dāng)p″=1/2 時，式（3）取最小值，Bloom Filter 誤差最小，此時位向量中0 和1 數(shù)量各占50%。在無哈希沖突的情況下，裝載因子上限Bi=kn/m=0.5 是最理想的狀態(tài)，但是由于哈希碰撞，當(dāng)元素數(shù)量n=0.5m/k 時，裝載因子小于0.5。 因此，從節(jié)約存儲空間的角度考慮，可以將適當(dāng)增大。 文獻[5]將裝載因子上限設(shè)置為0.6，本文中將動態(tài)裝載因子上限設(shè)置在0.5-0.8 區(qū)間內(nèi)。

3.2 算法準(zhǔn)確性

假設(shè)pi、pj分別為使用中的兩層位向量對分組進行判定時產(chǎn)生的誤差（其計算可借助式（1）完成），MBF 算法在決定是否抽取相應(yīng)分組時需要對兩層位向量的判定結(jié)果進行取交集操作，因此，MBF 算法產(chǎn)生的誤差為：

即

由于0＜pi＜1，因此pj－pipj＞0，所以式（4）和式（5）均大于0，不會有小于0 的情況出現(xiàn)。

不同的裝載因子上限使得位向量在不同時間初始化，當(dāng)系統(tǒng)使用A1、A2位向量測量時， 在一個測量周期內(nèi)，A2位向量達到裝載上限初始化時，A1位向量內(nèi)會有m×B2/k 個流記錄（B1＞B2），此時A1位向量尚未使用的比特位數(shù)為mB1－mB2，這些空間需要存儲m×（B1－B2）/k 個流后再進行初始化。 在A2位向量初始化后，使用A1和A3位向量進行測量時，部分A2位向量內(nèi)已經(jīng)認(rèn)定的網(wǎng)絡(luò)流的后續(xù)分組到來時不會被再次認(rèn)定為新流，有效的減少了由于單個位向量進行初始化造成的對已識別網(wǎng)絡(luò)流的重復(fù)認(rèn)定。

此外，由于位向量在每一次使用時其裝載因子上限隨機設(shè)置，可以有效避免由于兩層位同時初始化造成的網(wǎng)絡(luò)流重復(fù)認(rèn)定，使得算法可以更加精確的對網(wǎng)絡(luò)流進行測量。

3.3 算法復(fù)雜度分析

1）時間復(fù)雜度分析

MBF 算法實現(xiàn)過程中，時間開銷主要包括哈希運算和存儲器訪問兩部分。 文獻[5]對CRC32、Bob 和H3哈希函數(shù)進行對比，確定H3哈希函數(shù)綜合性能較為優(yōu)異，時間效率能夠達到納秒級，故在此選用H3哈希函數(shù)完成對元素的哈希運算。假設(shè)改進型Bloom Filter 中擁有個哈希函數(shù)， 則新流識別模塊處理一個數(shù)據(jù)分組需要進行次哈希運算， 時間復(fù)雜度為；對于每個位向量來說， 改進型Bloom Filter 最多需要對存儲器進行2 次訪問，相應(yīng)的時間開銷為2O（k）。 當(dāng)前高規(guī)格的存儲器的訪問速率已經(jīng)達到1－2ns/次，而在OC－192 鏈路中，相鄰分組之間的間隔為32ns。 因此在新流識別階段，通過選擇適當(dāng)?shù)母咚匐S機訪問存儲器和適當(dāng)?shù)墓：瘮?shù)數(shù)量，可以使得算法應(yīng)用于當(dāng)前的高速網(wǎng)絡(luò)環(huán)境。

2）空間復(fù)雜度分析

MBF 算法在借助兩層位向量對到來的數(shù)據(jù)分組進行判定，因此，當(dāng)有個網(wǎng)絡(luò)流需要進行測量時，在無哈希碰撞的情況下，所花費的空間開銷為2k×n；對于原算法而言，面對同樣數(shù)量的網(wǎng)絡(luò)流，相應(yīng)的空間開銷為。因此，相比于原算法，MBF 算法的空間復(fù)雜度有所提高， 但與對每條流的信息逐個維護的傳統(tǒng)方法相比，MBF 算法大幅度降低了測量過程中的空間開銷。

4 仿真實驗與結(jié)果分析

4.1 仿 真

仿真所使用的流量數(shù)據(jù)來自互聯(lián)網(wǎng)數(shù)據(jù)分析合作組織（CAIDA）在互聯(lián)網(wǎng)上采集所得到，詳情如表1 所示。 仿真工具為MATLAB R2010a；處理器為Pentium（R）E5200，2.50 GHz；1G 內(nèi)存；操作系統(tǒng)為Windows XP Professional。

表1 流量數(shù)據(jù)信息Tab. 1 Information of traffic data

由于硬件性能有限， 實驗選取兩組流量數(shù)據(jù)的前1×105個數(shù)據(jù)分組作為實驗對象，3 個位向量的長度均設(shè)置為50 000 bits，使用五元組[8]作為網(wǎng)絡(luò)流的流關(guān)鍵字，將原抽樣算法和MBF 算法的抽樣率均設(shè)置為r=0.5。為保證公平起見，原算法中位向量的長度也設(shè)置為50 000 bits， 哈希函數(shù)仍選擇使用H3哈希函數(shù)，數(shù)量與原抽樣算法相同，即設(shè)置k=3。

圖3 和圖4 為分 別使用trace－1 流量數(shù)據(jù)和trace－2 流量數(shù)據(jù)時，原算法、MBF 算法和流量數(shù)據(jù)真實值（抽樣后）的基本情況。

圖3 流數(shù)量比較圖（trace－1）Fig. 3 Comparison of flow number（trace－1）

圖4 流數(shù)量比較圖（trace－2）Fig. 4 Comparison of flow number（trace－2）

可以看出，原有的基于Bloom Filter 的網(wǎng)絡(luò)流抽樣算法，由于在每個位向量達到裝載上限后均使用新的位向量對數(shù)據(jù)分組進行判定， 因此會出現(xiàn)檢測到的流數(shù)量陡增的情況。在同等條件下， 新提出的MBF 算法運用兩層位向量同時對數(shù)據(jù)分組進行判定，并且對每層位向量的裝載因子上限動態(tài)設(shè)置， 很好地避免了由于位向量初始化造成的流數(shù)量激增，所得到的流數(shù)量更加趨近與真實值，具有較高的測量精度。

與Bloom Filter 相似， 改進后的Bloom Filter 依然存在誤差，在一定階段會有部分流數(shù)據(jù)不被識別，因此在部分階段會出現(xiàn)MBF 算法仿真結(jié)果小于實際數(shù)量的情況， 該誤差產(chǎn)生的影響會在隨后的隨機抽樣模塊被“吸收”掉，對最終的實驗結(jié)果影響有限。

4.2 誤差分析

圖5 誤差比較圖（trace-1）Fig. 5 Comparison of error（trace-1）

圖6 誤差比較圖（trace-2）Fig. 6 Comparison of error（trace-2）

能夠發(fā)現(xiàn)， 新提出的MBF 算法有效的減少了對網(wǎng)絡(luò)流的重復(fù)認(rèn)定，減小了測量誤差，結(jié)果更加準(zhǔn)確。

5 結(jié)束語

本文提出了一種基于改進型Bloom Filter 的網(wǎng)絡(luò)流等概率抽樣算法。 改進型Bloom Filter 中運用兩層位向量對到來的數(shù)據(jù)分組分別進行判定，將每層位向量的裝載因子上限動態(tài)設(shè)置，通過誤差吸收和隨機抽樣模塊最終實現(xiàn)對網(wǎng)絡(luò)流的等概率抽樣。 實驗證明新算法可以有效減少對網(wǎng)絡(luò)流的重復(fù)抽樣，所得結(jié)果更加趨近于網(wǎng)絡(luò)流真實值，測量精度較高，能夠適應(yīng)當(dāng)前的高速網(wǎng)絡(luò)環(huán)境。 三層位向量的設(shè)置，進一步拓展了算法的使用空間。

[1] 錢宇. 高速網(wǎng)絡(luò)流測量模型研究[D]. 鄭州:解放軍信息工程大學(xué)，2008.

[2] 楊家海，吳建平，安常青. 互聯(lián)網(wǎng)絡(luò)測量理論與應(yīng)用[M]. 北京:人民郵電出版社，2009.

[3] HOHN Nicolas，VEITCH Darryl. Inverting sampled traffic[J].IEEE/ACM Transactions on Net-working.2006，14（1）:68-80.

[4] KUMAR Abhishek，XU Jun. Sketch guided sampling-using on-line estimates of flow size for adaptive data collection[C].Proc. of IEEE Infocom 2006， Washington，2006.

[5] 王洪波，程時端，林宇. 高速網(wǎng)絡(luò)超連接主機檢測中的流抽樣算法研究[J]. 電子學(xué)報，2008，36（4）:809-818.

[6] 張進，鄔江興，鈕曉娜. 空間高效的數(shù)據(jù)包公平抽樣算法[J].軟件學(xué)報，2010，21（10）:26422655.

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

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