基于Counting Bloom Filter的流抽樣算法研究

翟金鳳,, ,,

(1.東南大學 儀器科學與工程學院,南京 210096; 2.南京市計量監督檢測院,南京 210049)

0 概述

網絡流量測量作為一種用來掌握網絡運行狀況和行為特征的基本方法,已被廣泛應用于安全檢測、運營管理和流量工程等領域。新一代互聯網的規模更大、速率更快,對系統計算和存儲資源提出了更高的要求[1],且增加了傳統的對流經鏈路所有數據包進行捕獲和測量的難度。因此,需要在流量測量中引進一些必要的測量策略,用來對數據量進行縮減并保留流量數據的特征信息。抽樣技術作為一種可擴展的數據縮減技術[2],已被眾多大規模網絡引進到實際的網絡流量測量中,其能夠有效保留原始流量行為的細節,提高系統的處理效率和資源利用率。因此,抽樣測量已成為網絡流量測量領域的重要研究方向之一。

但是,當前網絡的高速發展使得網絡的異構性和復雜性在不斷加強,而系統處理分析能力的局限性和存儲資源的缺乏,導致基本的抽樣方法已難以滿足實際測量的需求。為解決該問題,同時保證測量具備一定的高效性和準確性,以及系統資源具有一定的可控性,有研究者考慮在測量中引入一些其他的關鍵技術。目前,應用較廣泛的技術主要有哈希算法、超時策略和概要數據結構[3],并由此衍生出如流抽樣、抽樣與哈希結合的測量以及基于Bloom Filter的抽樣測量等[4]。其中,Bloom Filter憑借其簡便易實現、資源利用率高以及處理速度快等優點,吸引了眾多研究者的關注,如何將其與抽樣技術進行高效地結合,成為近年來網絡流量測量領域的熱點論題[5]。

文獻[6]較早將哈希函數引進抽樣測量中。文獻[7]使用Time-Out Bloom Filter來緩解對長流的抽樣偏差,以提高對短流的抽樣概率。該方法與隨機抽樣相比,能夠在相同的抽樣率下記錄并識別出更多的短流,但是因為未考慮具體的流信息,所以其存在局限性。文獻[8]提出一種基于Dynamic Count Filter的公平抽樣算法,可以高效地獲取全面的流信息,但Dynamic Count Filter存在誤判率,導致算法會出現一定的測量誤差。文獻[9]基于改進型Bloom Filter數據結構,提出一種簡單實用的流抽樣算法,其通過調整抽樣頻率來實現對網絡流的等概率抽樣。其中,改進型Bloom Filter設置3層位向量,通過對2層位向量的判定結果取交集來實現對新流的識別,但該算法在3層位向量中交替使用時,會將某些已識別的流再次判斷為新流,導致某些網絡流的重復抽樣。

針對上述方法存在的不足,本文將基于報文的流抽樣技術和Bloom Filter相結合,提出一種基于Counting Bloom Filter的流抽樣算法,用以實現對網絡流的等概率抽樣,然后通過實驗驗證該算法的性能。

1 流量抽樣測量技術

1.1 基于報文的流抽樣

報文抽樣不考慮報文之間的相關性,其相對平等地對組成網絡流量的報文進行抽樣。常用的報文抽樣方法主要有3種:系統抽樣,隨機抽樣,分層抽樣。然而,組成網絡流量的報文并非獨立的,它們是為實現特定的行為應用而產生的,彼此間有著一定的相關性,流則是反映這種相關性的一種途徑。基于報文的抽樣忽略了報文之間的相關性,不能體現更高層面的信息,從而無法實現掌控和提升網絡性能的目的[10]。為解決該問題,衍生出基于報文的流抽樣測量,其先對報文實施抽樣,再對具有相同特征的報文進行流歸并操作。這樣可以將屬于特定流的分組綜合起來進行分析,從而縮減需要處理的數據量。此外,將部分重要特征信息保留下來,具有一定程度的可擴展性,更適合于當前的高速網絡環境。

基于報文流抽樣的普遍實現策略是在測量設備中,為抽中的流維護一塊存儲空間,先按某種頻率對報文實施隨機抽取,再按報文的特征信息將其歸并為不同的流,并以流的形式存儲在開辟的緩存中,最終構成抽中的流集合。對于在鏈路上傳輸的每一條報文,都將其與抽中的流集合中的屬性信息作比對,如果其與某條流的屬性相匹配(如具有相同的源IP地址、目的IP地址、源端口、目的端口和協議類型),則該報文被抽中,更新與該報文具有相同屬性的相關流信息;如果其與集合中任何流的屬性都不匹配,則該報文被丟棄。對網絡流進行測量和分析,有助于了解網絡的流量行為細節,且能在很大程度上釋放系統存儲資源。

1.2 Bloom Filter技術

1.2.1 標準Bloom Filter

Bloom Filter是概要數據結構中最具代表性的結構之一,是由Howard Bloom于1970年提出的二進制向量數據結構[11],其在高速網絡流量測量中發揮著巨大作用。Bloom Filter使用長為m的位向量V表示含有n個元素的集合S={s1,s2,…,sn}。初始化時Bloom Filter為空,位向量全部設為0,同時定義k個相互獨立的具有分布均勻特性的哈希函數h1,h2,…,hk[12],且其值域均為[1,m]。計算每個元素si∈S的哈希值h1(si),h2(si),…,hk(si)。將位向量V中對應于哈希映射的k個位置設為1。標準Bloom Filter原理如圖1所示。

圖1 標準Bloom Filter原理

與其他數據結構相比,Bloom Filter可以充分利用有限的存儲資源,有效提高數據查詢和處理的速率,且可以表示全集。但是,由Bloom Filter原理可以看出,在哈希映射過程中其可能會將位向量中的某一位重復置1,這會導致在判斷一個元素是否屬于某個集合時,存在一定的概率將不屬于這個集合的元素誤判為屬于這個集合,本文定義這樣的誤差概率為誤判率[13]。下面對誤判率的大小進行分析估計。

為簡化分析模型,假設各哈希函數是完全隨機的,且kn

則誤判率為:

1.2.2 Counting Bloom Filter

標準Bloom Filter僅支持對元素的插入和查詢操作,當對靜態集合進行表示時,其能夠呈現出較好的工作性能,但是當要表示的集合經常變動時,因為它不支持刪除操作,所以會產生一定的誤差。

由于Bloom Filter存在誤判率,以及不能用來表示動態集合,因此諸多研究人員對Bloom Filter提出了新的改進。目前,Bloom Filter的經典改進結構主要有:Counting Bloom Filter,Compressed Bloom Filter,Spectral Bloom Filter和Dynamic Count Filter等。其中,文獻[14]提出的Counting Bloom Filter是最具代表性的改進結構之一。

Counting Bloom Filter解決了標準Bloom Filter無法刪除元素的問題。對于標準Bloom Filter,當要從集合中刪除元素時,它不能簡單地將位向量中的對應位置設為0,而Counting Bloom Filter則將標準Bloom Filter位向量的每一位擴展為一個小的Counter(計數器),并賦初值為0。Counting Bloom Filter將元素插入操作擴展為給對應的k個Counter值分別加1;元素查找操作擴展為檢驗對應的k個Counter值是否為非零;元素刪除操作擴展為將對應的k個Counter值分別減1。Counting Bloom Filter原理如圖2所示。

圖2 Counting Bloom Filter原理

此外,有研究表明,若為Counting Bloom Filter中的每個計數器分配4 bit,則當計數器值達到16時,Filter會溢出,該概率為:

F≤m×1.37×10-15

(3)

其中,m為Counter向量的大小,即向量空間的大小。此時的溢出率已經微乎其微,可以滿足大部分應用程序的需求。在實際應用中,使用Counting Bloom Filter時也可以從實際需求的角度為Counter分配合適的位數。

2 基于Counting Bloom Filter的流抽樣算法

2.1 算法描述

如圖3所示,基于Counting Bloom Filter的流抽樣算法由Counting Bloom Filter模塊、誤差吸收模塊和隨機抽樣模塊組成。Counting Bloom Filter模塊用于判定到來的數據分組所屬網絡流是否為新流;由于Counting Bloom Filter同樣存在誤判率,誤差吸收模塊就用來記錄當前到達的流數量,同時根據抽樣過程中產生的誤判率調整抽樣頻率;隨機抽樣模塊則以調整后的抽樣頻率對經Counting Bloom Filter認定的新流進行抽樣,從而實現對網絡流的等概率隨機抽樣,該模塊可以有效反映網絡流的真實分布情況,具有較高的測量精度。

圖3 基于Counting Bloom Filter的流抽樣算法結構

基于Counting Bloom Filter的流抽樣算法設計流程如圖4所示。

圖4 基于Counting Bloom Filter的流抽樣算法設計流程

算法具體實現步驟為:

步驟1對Counting Bloom Filter結構的參數、哈希函數個數和向量空間大小進行合理配置,為Counting Bloom Filter結構中的每個Counter分配4 bit。

步驟2當一個分組到達時,先解析其流標識,然后計算其流標識的k個哈希函數值,若Counting Bloom Filter結構中對應的k個Counter值均大于或等于1,則判定為沒有新流到達;否則,判定為有新流到達。

步驟4如果判定為沒有新流到達,則繼續處理下一分組,重復步驟2并繼續循環。

2.2 哈希函數個數和向量空間大小選擇

在使用Counting Bloom Filter進行流抽樣測量時,有一個較重要的問題,就是如何根據網絡情況確定合適的哈希函數個數和向量空間大小,這對算法的測量效果有很大影響。使用較少的哈希函數時,會造成較大的誤判率;使用較多的哈希函數時,則會引起計算復雜度的上升以及向量空間消耗的增大。而向量空間選擇過大會浪費較多的存儲資源,向量空間過小則會導致誤判率的增加[10]。

圖5 誤判率隨哈希函數個數的變化關系

2)k=8、16、32的3條誤判率變化曲線較接近,即當哈希函數達到一定數量后,繼續增加k值對誤判率的影響極其微小。因此,要根據實際情況對誤判率與計算復雜度[16]進行權衡,從而選取恰當的k、m值。

圖6 誤判率隨的變化關系

3 實驗結果與分析

3.1 實驗數據

本次實驗使用的流量數據來自互聯網數據分析合作組織CAIDA公開提供的真實被動測量數據Traces。Trace 1為2011年2月17日在芝加哥采集得到的數據,Trace 2為2012年6月21日在圣約瑟采集得到的數據,數據詳情如表1所示。實驗平臺為Visual Studio 2013和MATLAB R2014b。由于硬件性能限制,本文選取2組Traces數據的前104個數據分組進行仿真分析。

表1 Trace 1和Trace 2流量數據信息

3.2 算法性能分析

使用報文頭中的源IP地址和目的IP地址作為網絡流的流標識,為Counting Bloom Filter結構中的每個Counter分配4 bit,向量的長度即Counter向量的大小設為實際流總數的20倍,先后使用3個、10個哈希函數進行仿真比較。

圖7、圖8分別為使用Trace 1和Trace 2數據時,基于Counting Bloom Filter的流抽樣算法使用3個、10個哈希函數的測量值與流量數據真實值的對比結果。

圖7 Trace 1流數量測量結果比較

圖8 Trace 2流數量測量結果比較

由圖7、圖8可以看出,本文網絡流等概率抽樣算法得到的流數量與真實值較接近,算法測量精度較高。誤判率的存在會導致部分新流數據不被識別,從而使得Counting Bloom Filter模塊識別出的新流數量小于實際流數量,引起測量誤差。但是,本文算法中的隨機抽樣模塊將會以實時調整抽樣頻率的形式吸收該誤差,從而降低誤判率對最終測量結果的影響。

由圖7、圖8還可以看出,算法中哈希函數個數設為10時的測量精度要高于哈希函數個數設為3的情況,這與第2.2節得出的Counting Bloom Filter的誤判率在一定范圍內會隨哈希函數個數的增加而減小的結論相一致。由于哈希函數個數大于10時誤判率變化放緩,且哈希函數達到一定數量后,反而會使計算復雜度和誤判率增大,因此本文算法在實際應用中應盡量選擇約10個哈希函數。

定義測量誤差為e=|n′-n|/n,其中,n′為通過算法測量出的網絡流數量值,n為網絡流數量的真實值。選取每1 000個數據分組作為記錄點。圖9、圖10分別為本文算法對Trace 1和Trace 2流量數據進行仿真時的測量誤差。

圖9 Trace 1測量誤差

圖10 Trace 2測量誤差

由圖9、圖10可以看出,哈希函數個數設為10時,本文算法能夠有效提高對網絡新流的識別率,其測量誤差明顯低于哈希函數個數設為3時的情況,測量結果較準確。因此,哈希函數個數要盡可能地設為10左右。由圖9、圖10還可以看出,隨著數據分組數量的增加,算法結果的測量誤差都呈現先上升后趨于平穩的趨勢。算法結果控制在一定的誤差范圍內,可以滿足一定精度下的網絡流等概率抽樣,并有效獲得網絡流的真實分布情況,最終節省系統的處理和存儲資源,因此,該算法適用于當前的高速網絡環境。

4 結束語

本文對基于報文的流抽樣技術與Bloom Filter技術進行探究,將Counting Bloom Filter結構和流抽樣技術相結合,并充分利用兩者的優勢,提出一種網絡流等概率抽樣算法。該算法為Counting Bloom Filter結構中的每個Counter分配4 bit,通過4 bit的Counter向量識別是否有新流出現,并借助后續的隨機抽樣模塊以實時調整抽樣頻率的形式吸收由Counting Bloom Filter的誤判率引起的測量誤差,最終實現對網絡流的等概率抽樣。仿真結果表明,本文算法測量結果趨近于網絡流真實值,可以有效獲得網絡流的真實分布情況,測量精度較高,且具有可擴展性,能夠適應當前的高速網絡環境。下一步將考慮改進Counting Bloom Filter,以使其計數器的位數能夠動態適配高速網絡環境。