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

翟金鳳,, ,,

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

0 概述

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

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

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

針對上述方法存在的不足,本文將基于報(bào)文的流抽樣技術(shù)和Bloom Filter相結(jié)合,提出一種基于Counting Bloom Filter的流抽樣算法,用以實(shí)現(xiàn)對網(wǎng)絡(luò)流的等概率抽樣,然后通過實(shí)驗(yàn)驗(yàn)證該算法的性能。

1 流量抽樣測量技術(shù)

1.1 基于報(bào)文的流抽樣

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

基于報(bào)文流抽樣的普遍實(shí)現(xiàn)策略是在測量設(shè)備中,為抽中的流維護(hù)一塊存儲(chǔ)空間,先按某種頻率對報(bào)文實(shí)施隨機(jī)抽取,再按報(bào)文的特征信息將其歸并為不同的流,并以流的形式存儲(chǔ)在開辟的緩存中,最終構(gòu)成抽中的流集合。對于在鏈路上傳輸?shù)拿恳粭l報(bào)文,都將其與抽中的流集合中的屬性信息作比對,如果其與某條流的屬性相匹配(如具有相同的源IP地址、目的IP地址、源端口、目的端口和協(xié)議類型),則該報(bào)文被抽中,更新與該報(bào)文具有相同屬性的相關(guān)流信息;如果其與集合中任何流的屬性都不匹配,則該報(bào)文被丟棄。對網(wǎng)絡(luò)流進(jìn)行測量和分析,有助于了解網(wǎng)絡(luò)的流量行為細(xì)節(jié),且能在很大程度上釋放系統(tǒng)存儲(chǔ)資源。

1.2 Bloom Filter技術(shù)

1.2.1 標(biāo)準(zhǔn)Bloom Filter

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

圖1 標(biāo)準(zhǔn)Bloom Filter原理

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

為簡化分析模型,假設(shè)各哈希函數(shù)是完全隨機(jī)的,且kn

則誤判率為:

1.2.2 Counting Bloom Filter

標(biāo)準(zhǔn)Bloom Filter僅支持對元素的插入和查詢操作,當(dāng)對靜態(tài)集合進(jìn)行表示時(shí),其能夠呈現(xiàn)出較好的工作性能,但是當(dāng)要表示的集合經(jīng)常變動(dòng)時(shí),因?yàn)樗恢С謩h除操作,所以會(huì)產(chǎn)生一定的誤差。

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

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

圖2 Counting Bloom Filter原理

此外,有研究表明,若為Counting Bloom Filter中的每個(gè)計(jì)數(shù)器分配4 bit,則當(dāng)計(jì)數(shù)器值達(dá)到16時(shí),Filter會(huì)溢出,該概率為:

F≤m×1.37×10-15

(3)

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

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

2.1 算法描述

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

圖3 基于Counting Bloom Filter的流抽樣算法結(jié)構(gòu)

基于Counting Bloom Filter的流抽樣算法設(shè)計(jì)流程如圖4所示。

圖4 基于Counting Bloom Filter的流抽樣算法設(shè)計(jì)流程

算法具體實(shí)現(xiàn)步驟為:

步驟1對Counting Bloom Filter結(jié)構(gòu)的參數(shù)、哈希函數(shù)個(gè)數(shù)和向量空間大小進(jìn)行合理配置,為Counting Bloom Filter結(jié)構(gòu)中的每個(gè)Counter分配4 bit。

步驟2當(dāng)一個(gè)分組到達(dá)時(shí),先解析其流標(biāo)識(shí),然后計(jì)算其流標(biāo)識(shí)的k個(gè)哈希函數(shù)值,若Counting Bloom Filter結(jié)構(gòu)中對應(yīng)的k個(gè)Counter值均大于或等于1,則判定為沒有新流到達(dá);否則,判定為有新流到達(dá)。

步驟4如果判定為沒有新流到達(dá),則繼續(xù)處理下一分組,重復(fù)步驟2并繼續(xù)循環(huán)。

2.2 哈希函數(shù)個(gè)數(shù)和向量空間大小選擇

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

圖5 誤判率隨哈希函數(shù)個(gè)數(shù)的變化關(guān)系

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

圖6 誤判率隨的變化關(guān)系

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

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

表1 Trace 1和Trace 2流量數(shù)據(jù)信息

3.2 算法性能分析

使用報(bào)文頭中的源IP地址和目的IP地址作為網(wǎng)絡(luò)流的流標(biāo)識(shí),為Counting Bloom Filter結(jié)構(gòu)中的每個(gè)Counter分配4 bit,向量的長度即Counter向量的大小設(shè)為實(shí)際流總數(shù)的20倍,先后使用3個(gè)、10個(gè)哈希函數(shù)進(jìn)行仿真比較。

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

圖7 Trace 1流數(shù)量測量結(jié)果比較

圖8 Trace 2流數(shù)量測量結(jié)果比較

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

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

定義測量誤差為e=|n′-n|/n,其中,n′為通過算法測量出的網(wǎng)絡(luò)流數(shù)量值,n為網(wǎng)絡(luò)流數(shù)量的真實(shí)值。選取每1 000個(gè)數(shù)據(jù)分組作為記錄點(diǎn)。圖9、圖10分別為本文算法對Trace 1和Trace 2流量數(shù)據(jù)進(jìn)行仿真時(shí)的測量誤差。

圖9 Trace 1測量誤差

圖10 Trace 2測量誤差

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

4 結(jié)束語

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