翟金鳳,, ,,

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

0 概述

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

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

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

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

1 流量抽樣測量技術

1.1 基于報文的流抽樣

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

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

1.2 Bloom Filter技術

1.2.1 標準Bloom Filter

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

圖1 標準Bloom Filter原理

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

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

則誤判率為:

1.2.2 Counting Bloom Filter

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

由于Bloom Filter存在誤判率,以及不能用來表示動態(tài)集合,因此諸多研究人員對Bloom Filter提出了新的改進。目前,Bloom Filter的經(jīng)典改進結構主要有: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(計數(shù)器),并賦初值為0。Counting Bloom Filter將元素插入操作擴展為給對應的k個Counter值分別加1;元素查找操作擴展為檢驗對應的k個Counter值是否為非零;元素刪除操作擴展為將對應的k個Counter值分別減1。Counting Bloom Filter原理如圖2所示。

圖2 Counting Bloom Filter原理

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

F≤m×1.37×10-15

(3)

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

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

2.1 算法描述

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

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

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

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

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

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

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

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

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

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

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

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

圖6 誤判率隨的變化關系

3 實驗結果與分析

3.1 實驗數(shù)據(jù)

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

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

3.2 算法性能分析

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

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

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

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

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

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

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

圖9 Trace 1測量誤差

圖10 Trace 2測量誤差

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

4 結束語

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