任高明,夏靖波,柏 駿,陳 珍

(空軍工程大學信息與導航學院,陜西西安 710077)

網絡數據流流量測量新方法

任高明,夏靖波,柏 駿,陳 珍

(空軍工程大學信息與導航學院,陜西西安 710077)

針對現有的數據流流量測量概率多重計數方法空間復雜度高和空間利用率低的問題,提出了一種基于兩層位域的數據流流量測量方法.該方法分為兩個步驟:數據捕獲階段.將到達數據包采用兩個獨立的哈希函數分別映射至兩層位域;數據恢復階段.對位域恢復得到的兩個虛擬矩陣按位取交集,消除哈希碰撞引起的誤差.實驗結果表明,和概率多重計數方法相比,兩層位域方法在存儲空間降低75%的前提下,仍具有高的數據流估算精度.

計算機網絡;流量測量;數據流估算;位域

網絡流量測量對流量計費、流量工程與異常檢測等網絡運營管理具有重要意義[1].隨著以太網技術的迅速發(fā)展和40 GB/100 GB標準的發(fā)布,基礎網絡快速進入超高速時代.隨著網絡鏈路速率的增長,數據包到達頻率越來越高,單位數據包的處理時間越來越短,測量每個數據包的信息變得越發(fā)困難[2-3].根據吉爾德定律,主干網的帶寬每6個月增長1倍,其增長速度是莫爾定律預測的CPU增長速度的3倍.也就是說,用于網絡測量的硬件性能和網絡帶寬之間的差距會越來越大,網絡流量測量任務將越來越艱巨[4].

在網絡流量測量初期,通用的方法是全數據測量,該方法測量準確.然而網絡鏈路速率的提高暴露了該方法的缺點,即處理速度慢、產生數據量大和所需存儲空間大等[5].網絡流量抽樣技術的應用很好地解決了全數據測量方法的缺點[6],大幅提高了網絡流量測量設備的處理效率,同時,又能保證準確性在可接受的錯誤范圍內[7].抽樣方法很快得到普及應用,例如當前廣泛使用的思科推出的網絡設備Net Flow就采用了抽樣技術[8].但是,數據包抽樣技術由于測量不準確,隨著鏈路速率的提高已難以滿足需要[9-10].近年來,基于概率的網絡流量測量機制方法以流(通常流的定義為,在測量時間內五元組相同的數據包組成的集合)為單位,其可滿足當前網絡線速處理要求,并能較為準確地估算出所有流的大小[11],受到越來越多的關注.

1 相關工作

在當前的高速網絡中,準確測量每個流的大小非常困難,并且代價昂貴.根本原因是,網絡帶寬的增加,使得數據包到達頻率越來越高,每個數據包的處理間隙越來越短.以40 Gbit/s鏈路為例,數據包處理間隙只有12 ns,也就是說,測量設備必須在12 ns內完成1個數據包的處理,因此,直接進行數據流流量的準確測量代價極高.目前,網絡流量測量方法的時間復雜度通常以哈希映射和內存訪問的次數來衡量,哈希映射和內存訪問的次數越少,時間復雜度就越低.近年來,基于概率理論的數據流流量測量方法受到越來越多的關注.文獻[12]提出一種新的計數器結構分層計數器(Counter Braids,CB),通過隨機圖編織分層的計數器和計數器共享,能較好地完成數據流流量的估算,但該方法時間復雜度高,處理每個數據包至少需要3次哈希映射和6次內存訪問.文獻[13]采用多個具有不同解析度的空間編碼布魯姆過濾器(Space-Code Bloom Filter, SCBF),每個SCBF對某一段值(流大小)有較高的精度.因此,對于一個任意大小的流,都有一個適合的SCBF,使得對它的估算達到一定的準確性.但上述兩種方法都存在相同的缺點,即較高的時間復雜度限制了其擴展性.

文獻[14]在FM sketches方法[15]的基礎上提出概率多重計數(the Probability of Multiple Counting, PMC)網絡數據流流量測量方法.該方法由流量捕獲和流信息提取兩個步驟組成,分別在實時測量階段和后臺分析時完成.其中,每個流對應一個虛擬矩陣,實現過程以流f為例說明.當屬于流f的數據包p到達時,分別采用函數rand(m)和georand(w)確定p在對應虛擬矩陣VMf中的行和列.函數rand(m)生成范圍是在[1,m]之間的均勻分布的隨機整數;函數georand(w)生成服從幾何分布的隨機數,滿足以下關系:

之后,p經哈希函數H(f,i,j)(f為流關鍵字,i和j分別為數據包在所屬流對應的虛擬矩陣中的位置編號)映射至一個長度為L的位域(bit field)B中,并將B[H(f,i,j)]位賦值為1;在測量周期結束后,根據位域中存儲的信息估算出每個流的大小.和其他方法相比,PMC方法的最大優(yōu)勢在于,將測量過程分為線上采集和線下恢復兩個階段,只需在線上采集時滿足測量設備限速處理的要求即可,而對線下恢復階段的效率不進行實質性的要求.同時,PMC利用位域存儲特點,在采集時處理每個數據包只需1次哈希映射和1次內存訪問,避免了根據流關鍵字信息去查找流所屬的存儲單元這一最消耗資源的操作,其處理速度足夠快,可滿足高速網絡流量測量的線速處理需求.PMC方法的具體內容請參考文獻[14],在此不再贅述.

然而PMC方法的不足之處在于,其估算誤差由位域B的填充率惟一決定,對于同一組實驗數據,位域長度越大,B的填充率越小,存儲資源消耗越大,PMC方法的準確率越高.但在實際應用中,大量的存儲資源意味著高昂的代價,因此,必須在準確性和實現代價之間做出合理的折中.為保持準確性,文獻[14]提到,在一般情況下,PMC方法中位域的長度設置為幾百萬時是較合理的.但此時,算法的空間復雜度較高,且空間利用率低,極大限制了測量方法的靈活部署.基于此,找到一種所需存儲空間小、單個數據包處理時間短,同時具有很高準確性的方法,成為當前流量測量工程應用中亟待解決的問題.

2 兩層位域法

文中在保留PMC方法優(yōu)勢的基礎上,提出一種新的網絡數據流流量測量方法,在大幅降低所需存儲空間的同時,仍保證更高的準確率.

PMC方法所需存儲空間的大小由位域的長度L決定,減小存儲空間的惟一方法就是縮短L.對相同的流量數據,L的縮短必然會增大哈希碰撞發(fā)生的概率,進而導致準確率的降低.在保證準確率的前提下,降低空間復雜度,似乎是不可能完成的任務.下面分析縮短PMC方法中位域長度L后導致測量誤差變大的原因.

在測量時間段內,當流f包含的數據包全部到達后,對應的虛擬矩陣VMf將確定.假定位域L的長度無限大,哈希函數的散列性足夠好,那么,虛擬矩陣VMf經哈希函數H(f,i,j)映射后,會將位域B中兩兩不同的位賦值為1,不會出現虛擬矩陣中不同的位置被映射至位域中相同位的情況.類似地,不同流對應的虛擬矩陣在被哈希函數映射后,相互之間也不會發(fā)生哈希碰撞.因此,在流信息提取階段,對于流f,從位域恢復得到的虛擬矩陣V′Mf將和VMf相同.但在現實條件下,基于成本優(yōu)化和實際硬件水平的考量,并不能滿足理想條件,尤其在存儲空間大幅減小的情況下,必然會引起大量的哈希碰撞,導致恢復得到的虛擬矩陣V′Mf和流f的虛擬矩陣VMf之間存在較大的誤差.

假定虛擬矩陣VMf中(i,j)位為0,經哈希函數H(f,i,j)映射后,位域B中B[H(f,i,j)]位的值仍為0;那么,從位域中恢復虛擬矩陣VMf時,(i,j)位為0.類似地,若虛擬矩陣VMf中(i,j)位為1,經過存儲至位域B后,再恢復虛擬矩陣時,仍然會得到V′Mf中的(i,j)位為1,并不會誤判為0,即不會出現假陰性誤判.而由于哈希碰撞的存在,可能會出現下面的情況:屬于不同流的兩個數據包映射至同一位,如H(f1,i,j)=H(f2, i′,j′),由于流f2的虛擬矩陣中(i′,j′)為1,導致恢復時,將流f1的虛擬矩陣中原本為0的(i,j)位確定為1,從而出現假陽性誤判.

在此背景下,文中提出一種基于兩層位域的數據流估算方法(D-BF),其基本出發(fā)點是通過減少恢復虛擬矩陣時的假陽性誤判,保證在減小存儲空間的同時,仍具有較高的準確率.該方法由兩層長度為L′(L′＜1/(2L))的位域組成,基本思想如圖1所示,包括網絡流量的實時捕獲和流信息提取兩部分.

圖1 D-BF方法結構

在流量捕獲階段,當屬于流f的數據包p到達時,根據函數ran d(m)和georan d(w)確定到達的數據包在虛擬矩陣VMf中的位置(i,j)后,采用并行的哈希函數H1和H2將數據包分別映射至位域B1和B2中的B1(H1(f,i,j))和B2(H2(f,i,j))位,賦值為1,并保存.圖2為流a和流b映射到位域B1和B2的示意圖.

在流信息提取階段,首先,對于給定的流f,將數據包關鍵字和虛擬矩陣的行與列分別組合,即根據不同的(f,i,j)組合(其中,i=1,2,3,…;j=1,2,3,…),分別使用哈希函數H1和H2,從位域B1和B2得到VM1和VM2;然后,對二者按位取交集得到虛擬矩陣VMinter,具體實現過程如算法1所示.

算法1 GET VMinter(f)

VM1=0,VM2=0,VMinter=0

for i=1…m do

for j=1…w do

if B1[H1(f,i,j)]=1 then VM1(i,j)←1

if B2[H2(f,i,j)]=1 then VM2(i,j)←1

if(VM1(i,j)==1)&&(VM2(i,j)==1)

then VMinter(i,j)←1

end for

end for

return VMinter(f)

對虛擬矩陣VM1和VM2取交集時,相同的位置同為1,則將虛擬矩陣VMinter中相同的位置為1;否則,置為0.

文中提出使用兩層并行位域記錄流信息,對從兩層位域恢復得到的虛擬矩陣VM1和VM2按位取交集得到VMinter,其某一位置出現假陽性誤判的前提條件是,VM1和VM2中相同的位置均出現假陽性誤判.因此,誤判概率大大降低,進而減小了虛擬矩陣VMinter和VM之間的誤差.得到虛擬矩陣VMinter后,借鑒PMC方法計算出k和Z,估算出流大小.具體如下:在虛擬矩陣中,如果k/(1-p)＞0.3m,則可以估算出流f的大小(文中流的大小指流所包含的數據包個數),n=-2m log(k(m(1-p))),其中,k為虛擬矩陣中第1列中0的個數;否則,n=2Z/mm/φ(p),其中,Z為每一行初始的、連續(xù)的1的個數之和;φ的值取決于n,Flajolet和Martin證明,當n→∞時,φ=0.773 51.φ值收斂得非常快,在使用時,可認為是常量.具體計算Z的方法如算法2所示.

圖2 D-BF方法映射示意圖

算法2 GET ZSUM(f)

Z←0

for i=1…m do

For j=1…w do

if B[H(f,i,1)]=0 then break

end for

Z←Z+(j-1)

end for

return Z

3 理論分析

3.1 準確性分析

虛擬矩陣VM的維數為w×m,假定用于確定位置的函數rand(m)和georand(m)隨機性足夠好,不會出現碰撞,流f包含n個數據包.根據函數georand(m)易知,有數據包到達時,定位在前5列的概率可近似認為流f的數據包到達時,會全部落在前5列.假定位域B的長度為L,填充率為p.

(1)如果0.97n≥5m,則可近似為n≥5m,即B中5m個位置被置1,剩余(w-5)m個位置為0.在從位域B恢復的時候,每個位置被錯誤地置為1的概率為(Lp-5m)(L-5m),由于在實際測量過程中數據量巨大,可近似表示為p剩余(w-5)m個位置被錯誤地置為1的概率為

(2)如果0.97n≤5m,則可近似為n＜5m.在從位域B恢復時,每個位置被錯誤地置為1的概率為(Lp -n)(L-n),近似為p,類似地,剩余wm-n個位置被錯誤置為1的概率為

和PMC方法相比,D-BF方法減小存儲空間后,位域長度由L減小為L′,對于同樣的實驗數據,位域的填充率將變大,假定在D-BF方法中,位域B1和B2的填充率均變?yōu)閜′,易知p′=LpL′.D-BF方法在數據恢復時,發(fā)生錯誤的條件是VM1和VM2中同一個位置均被錯誤地置為1.可知,D-BF方法在從位域B1和B2恢復時,每個位置被錯誤地置1的 概率為((L′p′-5m)(L′-5m))2或者((L′p′-n)(L′-n))2,可近似表示為(p′)2.和PMC方法相比,保證D-BF方法準確性不會降低的條件是(p′)2＜p,結合式(3),可得到

同時,要保證D-BF方法的存儲空間小于PMC方法的,需滿足2L′＜L,易得出

只要L′滿足上述條件,和PMC方法相比,D-BF方法在降低存儲空間的同時,將會提高準確性.

3.2 時間復雜度分析

與前述一致,這里使用操作次數作為衡量方法時間復雜度的性能指標.由于恢復階段的處理效率不會影響方法應對高速網絡的執(zhí)行效率,故借鑒文獻[14]的分析方法,只考慮線上采集時的時間復雜度.表1列出了D-BF方法和PMC方法在處理每一個數據包所需要的操作次數.可以發(fā)現,D-BF方法處理每個數據包需要產生隨機數兩次、哈希映射兩次和寫操作兩次.但由于兩層位域的并行性,在實際應用時,可采用并行處理方法,同時處理兩層位域的存儲操作,這樣并不會降低D-BF方法的處理效率,而且是切實可行的.

3.3 空間復雜度分析

和PMC方法類似,D-BF方法所需的存儲空間同樣取決于位域大小.PMC方法采用一層位域B,其所需空間為L bit.D-BF方法使用兩層位域B1和B2,長度相同,均為L′bit,共需2L′bit.由于L′p′=Lp,可知D-BF方法需要的存儲空間為2Lpp′.即D-BF方法與PMC方法所需存儲空間的比值2L′L=2pp′.

為方便表示,定義位域B的長度L=RN,其中,N為實驗所用的數據包個數,R為系數.假定PMC方法中采用的哈希函數效果良好,不會發(fā)生哈希碰撞,那么實驗使用N個數據包,位域B中將會有N被置1,那么,位域B的填充率p=1R,與D-BF方法類似.表2為L′、L、p和p′取幾種典型值時,D-BF方法和PMC方法所需空間之比.

表1 兩種方法的操作次數比較

表2 D-BF方法和PMC方法所需空間之比

4 仿真實驗

選用文獻[14]中的PMC方法作為參照,兩種算法在相同的存儲空間下的測量數據流流量的準確性進行比較.所用仿真環(huán)境如下:仿真工具為MATLAB R2010a;計算機CPU為Pentium(R)Dual-Core,主頻為2.69 GHz;內存為3 GB;操作系統(tǒng)為Windows XP SP3.實驗數據來自CAIDA提供的某2.5 GB鏈路的真實互聯網流量.由于計算機性能受限,選擇流量數據的前10萬個數據包作為實驗對象.

為保證實驗的公平性,參照文獻[14],m和w值分別取32和256.當m和w確定后,R系數的值決定了位域的長度,即所需空間的大小.

圖3為PMC方法在不同R值條件下的估計誤差示意圖.可以看出,隨著R系數的增大,PCM方法的誤差在不斷變小,原因是φ=0.77是在假定填充率1/R無限趨近于零時計算得到的.因此,R越大,位域B的填充率1/R越接近于零,更接近于假設條件,估計值越準確,誤差越小;當R＞800時,誤差變化幅度不大,原因是當位域B的填充率1/R非常趨近于零時,繼續(xù)減小將不會明顯降低測量誤差.

圖3 PMC方法誤差變化圖

圖4 PMC方法和D-BF方法誤差比較圖

圖4為R系數的取值在[200,800]區(qū)間時,PMC方法和D-BF方法的誤差比較圖.給定PMC方法的存儲空間L=RN bit,為保證兩種方法存儲空間相同,設定D-BF方法中兩層位域的長度均為L′=RN2 bit.由圖4可以發(fā)現,在[200,800]區(qū)間內,D-BF方法隨著R系數的增大,測量誤差基本恒定,并且均小于PMC方法的估計誤差.

圖5 PMC方法和D-BF方法實驗效果圖

圖5為兩種方法的R系數分別取200和800時,數據流流量的測量圖.圖5中的每個點代表1個流,x軸的值表示該流包含數據包的實際個數,y軸的值表示估算得到的數據包個數.理想狀況下,測量完全準確時,圖5中所有的點都應該在y=x的直線上.圖5(a)和圖5(b)分別表示R=200時,PMC方法和D-BF方法的數據流流量的測量圖.可以發(fā)現,在相同的存儲空間條件下,D-BF方法測量圖中的點明顯靠近于y=x直線;比較圖5(c)和圖5(d)可以得到相同結論.比較圖5(a)和圖5(c)、圖5(b)和圖5(d)可以發(fā)現,PMC方法取R=800時的準確率高于R=200時的準確率;而D-BF方法在R=200和R=800時,得到的效果圖區(qū)別并不明顯.

比較圖5(b)和圖5(c)可見,D-BF方法在R=200時的準確率明顯高于PMC方法在R=800時的準確率,也就是說,和PMC方法相比,D-BF方法在存儲空間降低75%的情況下,準確性仍優(yōu)于PMC方法,這和圖4分析得到的結論一致.

5 結束語

隨著網絡鏈路速率的不斷增長,用于網絡流量測量的硬件技術已無法滿足需要.靜態(tài)隨機存儲器速度足夠快,但空間小、體積大、價格高;動態(tài)隨機存儲器能夠提供足夠的存儲空間,但訪問速度慢,無法滿足當前線速處理的要求.因此,設計一種空間利用率高、計算速度快、誤差小的網絡流估算方法意義重大.

筆者提出一種基于兩層位域的網絡流估算(D-BF)方法,與已有的PMC方法相比,D-BF方法所需存儲空間少,準確率高.采用實際網絡采集的流量數據試驗后發(fā)現,D-BF方法在存儲空間節(jié)省75%的前提下,仍具有更高的準確性.盡管D-BF方法處理每個數據包需要的操作次數多于PMC方法的,但在實際應用時,可以采用并行處理方法同時處理兩層位域的存儲操作,并不會降低D-BF方法的處理效率.D-BF方法空間復雜度的大幅降低,使得其更適合于網絡流量測量設備的工程應用,在只需要較小的SRAM的條件下,完成準確性較高的流量測量,增加了部署的靈活性.

[1]Huici F,Di Pietro A,Trammell B,et al.Blockmon:a High-performance Composable Network Traffic Measurement System[J].Computer Communication Review,2012,42(4):79-80.

[2]Kodialam M S,Lakshman T V.High-speed Traffic Measurement and Analysis Methodologies and Protocols:U.S. Patent 7,808,923[P].2010-10-05.

[3]孫昱,蔣馥蔚,夏靖波,等.一種改進的高速網絡分布式流量抽樣算法[J].西安電子科技大學學報,2013,40(3):160-165. Sun Yu,Jiang Fuwei,Xia Jingbo,et al.Improved Distributed Traffic Sampling Algorithm for High Speed Network[J]. Journal of Xidian University,2013,40(3):160-165.

[4]Aghdai A,Zhang F,Dasanayake N,et al.Traffic Measurement and Analysis in an Organic Enterprise Data Center[C]// Proceedings of IEEE 14th International Conference on High Performance Switching and Routing.Piscataway:IEEE Computer Society,2013:49-55.

[5]張震,汪斌強,張風雨,等.基于LRU-BF策略的網絡流量測量算法[J].通信學報,2013,34(1):111-120. Zhang Zhen,Wang Binqiang,Zhang Fengyu,et al.Traffic Measurement Algorithm Based on Least Recent Used Bloom Filter[J].Journal on Communications,2013,34(1):111-120.

[6]周愛平,程光,郭曉軍.高速網絡流量測量方法[J].軟件學報,2014,25(1):135-153. Zhou Aiping,Cheng Guang,Guo Xiaojun.High-speed Network Traffic Measurement Method[J].Journal of Software, 2014,25(1):135-153.

[7]Estan C,Varghese G.New Directions in Traffic Measurement and Accounting[J].Computer Communication Review, 2002,32(4):323-336.

[8]De Godoy S,Jeferson W,Ling L L.A New Binomial Conservative Multiplicative Cascade Approach for Network Traffic Modeling[C]//IEEE 27th International Conference on Advanced Information Networking and Applications.Piscataway: IEEE,2013:794-801.

[9]Gebert S,Pries R,Schlosser D,et al.Internet Access Traffic Measurement and Analysis[C]//Lecture Notes in Computer Science:7189.Berlin:Springer,2012:29-42.

[10]Chang C W,Liu H,Huang G,et al.Distributed Measurement-aware Routing:Striking a Balance between Measurementand Traffic Engineering[C]//Proceedings of IEEE Conference on Computer Communications.Piscataway:IEEE,2012: 2516-2520.

[11]Marold A,Lieven P,Scheuermann B.Probabilistic Parallel Measurement of Network Traffic at Multiple Locations[J]. IEEE Network,2012,26(1):6-12.

[12]Lu Y,Montanari A,Prabhakar B,et al.Counter Braids:a Novel Counter Architecture for Per-flow Measurement[J]. Performance Evaluation Review,2008,36(1):121-132.

[13]Kumar A,Xu J,Wang J.Space-code Bloom Filter for Efficient Per-flow Traffic Measurement[J].IEEE Journal on Selected Areas in Communications,2006,24(12):2327-2339.

[14]Lieven P,Scheuermann B.High-speed Per-flow Traffic Measurement with Probabilistic Multiplicity Counting[C]// Proceedings of IEEE Conference on Computer Communications.Piscataway:IEEE,2010:1-9.

[15]Flajolet P,Nigel Martin G.Probabilistic Counting Algorithms for Data Base Applications[J].Journal of Computer and System Sciences,1985,31(2):182-209.

(編輯:齊淑娟)

Novel per-flow traffic measurement algorithm

REN Gaoming,XIA Jingbo,BAI Jun,CHEN Zhen
(School of Information and Navigation,Air Force Engineering University,Xi’an 710077,China)

It is extremely difficult to measure traffic information with a growing network link speed.In recent years,increasing focus has been put on probabilistic algorithms which are fast enough to examine all packets and can provide estimates of the sizes of all flows.However,the previously proposed flow estimating algorithm of PMC has the drawbacks of poor space efficiency and large estimation error.To address the problem,a double bit field(D-BF)algorithm is proposed.The method is divided into two steps:the newly arrived packet is mapped to two bit fields using different hash functions in the data capturing stage;two virtual matrixes recovered from the bit fields have been intersected to eliminate errors caused by the hash collision in the data recovering stage.Experimental results show that the proposed D-BF is more accurate than PMC in flow estimate,while a reduction of 75%in memory space can be achieved.

computer network;traffic measurement;flow estimate;bit field

TP393

A

1001-2400(2015)05-0125-08

2014-05-07< class="emphasis_bold">網絡出版時間:

時間:2014-12-23

國家自然科學基金資助項目(61202489);陜西省自然科學基礎研究計劃資助項目(2012JZ8005)

任高明(1986-),男,空軍工程大學博士研究生,E-mail:gaomingr_928@126.com.

http://www.cnki.net/kcms/detail/61.1076.TN.20141223.0946.022.html

10.3969/j.issn.1001-2400.2015.05.022