基于改進型Bloom Filter 的網絡流抽樣算法

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

（空軍工程大學 信息與導航學院， 陜西 西安 710077）

作為網絡流量測量的重要組成部分，網絡流測量將大量具有統一屬性的數據分組聚類分析[1]，有效的節約了測量過程中所需的存儲資源，更好地反應了用戶的行為特征，逐漸受到重視。

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

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

1 相關工作

1.1 原算法實現過程

在原算法內，Bloom Filter 用于判斷數據分組所屬網絡流是否是第一次到達（即新流）；誤差吸收模塊的主要用于計算抽樣過程中產生的誤差概率；隨機抽樣模塊的主要功能是以調整后的概率對Bloom Filter 認定的新流進行抽樣， 算法結構如圖1 所示。

圖1 基于Bloom Filter 的網絡流抽樣算法Fig. 1 Network flow algorithm based on Bloom Filter

1.2 原算法理論分析

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

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

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

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

2 新算法的提出

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

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

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

MBF 算法

1） 分組p′到達，解析其流關鍵字f；

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

3） 通過哈希函數將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） 流數量n=n+1

14） 計算Bloom Filter 誤差PTBF；

15） 調整隨機抽樣概率為r/（-pTBF）。

16） End；

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

18） End；

3 理論分析

3.1 動態裝載因子上限的設置

由（1）式知：

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

令p′=k ln（1-e-kn/m），當p′取最小值時，p 也為最小值，設p″=e-kn/m，則

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

3.2 算法準確性

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

即

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

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

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

3.3 算法復雜度分析

1）時間復雜度分析

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

2）空間復雜度分析

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

4 仿真實驗與結果分析

4.1 仿 真

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

表1 流量數據信息Tab. 1 Information of traffic data

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

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

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

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

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

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

4.2 誤差分析

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

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

能夠發現， 新提出的MBF 算法有效的減少了對網絡流的重復認定，減小了測量誤差，結果更加準確。

5 結束語

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

[1] 錢宇. 高速網絡流測量模型研究[D]. 鄭州:解放軍信息工程大學，2008.

[2] 楊家海，吳建平，安常青. 互聯網絡測量理論與應用[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] 王洪波，程時端，林宇. 高速網絡超連接主機檢測中的流抽樣算法研究[J]. 電子學報，2008，36（4）:809-818.

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

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

[8] 張震，汪斌強，張風雨，等. 基于LRU-BF策略的網絡流量測量算法[J]. 通信學報.2013，34（1）:111-120.