李景富，楊志強

（黃淮學院，河南駐馬店463000）

一種面向不均衡網(wǎng)絡(luò)流的綜合抽樣方法*

李景富，楊志強

（黃淮學院，河南駐馬店463000）

針對互聯(lián)網(wǎng)流量中短流數(shù)量多但承載信息少、長流數(shù)量少但承載報文數(shù)多的特點，提出了一種面向不均衡網(wǎng)絡(luò)流的綜合抽樣IS（Integrated Sampling）方法。IS方法首先采用容量固定的高速緩存實現(xiàn)有限時間窗口內(nèi)報文的實時歸并，在此基礎(chǔ)上，IS方法采用可部分重構(gòu)的哈希函數(shù)實現(xiàn)單報文流聚類，采用流長和時間組合賦權(quán)的權(quán)值更新模塊和頻繁項模塊共同實現(xiàn)頻繁項流的抽取，對于網(wǎng)絡(luò)中的其他流量，IS方法通過多個蓄水池模塊實現(xiàn)蓄水池分段抽樣。實驗證明，相對于單一的抽樣方法，IS方法在相同緩存下能夠抽取出更為豐富地網(wǎng)絡(luò)流信息，算法能夠?qū)崟r應(yīng)用于高速網(wǎng)絡(luò)中。

網(wǎng)絡(luò)流，流抽樣，哈希聚類，頻繁項提取，蓄水池抽樣

0 引言

隨著大數(shù)據(jù)時代的到來，互聯(lián)網(wǎng)中產(chǎn)生的流量數(shù)據(jù)規(guī)模急劇增長，在同一時刻一條骨干鏈路中就可能活躍著數(shù)百萬條流，如此巨大的數(shù)據(jù)量給網(wǎng)絡(luò)流量采集、傳輸、存儲、分析及管理帶來了巨大的壓力［1-5］，流量抽樣通過一定的方式從整體流量數(shù)據(jù)空間中抽取出特定樣本，是一種以有限樣本數(shù)據(jù)獲得總體數(shù)據(jù)認識的有效方法，網(wǎng)絡(luò)流量抽樣作為一種以有限資源獲取網(wǎng)絡(luò)行為統(tǒng)計信息的方式引起了廣泛地關(guān)注［6-9］。

由于網(wǎng)絡(luò)流分布不均衡，網(wǎng)絡(luò)流長處于兩端的流其特性嚴重偏離均值［10-11］：①網(wǎng)絡(luò)流長大的流在總體流數(shù)中所占比例極小，采用均勻流抽樣方法將遺漏掉大部分的大流，但是該部分流承載的報文數(shù)中所占比例極大，對大流進行監(jiān)控只需很少的流緩存就能掌握網(wǎng)絡(luò)流量的總體特性，因此，在能夠有效識別大流的基礎(chǔ)上應(yīng)當盡量采集網(wǎng)絡(luò)中全部的大流；②網(wǎng)絡(luò)流長小的流在總體流數(shù)中所占比例極高，采用均勻流抽樣方法將抽取到過多的小流，同時小流攜帶的有效信息有限，將大部分的流緩存用于保存小流是不值得的，為了降低小流占用的緩存數(shù)量，在保證實時性的情況下可以通過聚類小流實現(xiàn)小流宏觀信息的保存。

基于此，本文提出了一種面向不均衡網(wǎng)絡(luò)流的綜合抽樣方法（Integrated Sampling，IS）。該方法能夠抽取出更為豐富的流信息，算法能夠?qū)崟r應(yīng)用于高速網(wǎng)絡(luò)中。

1 網(wǎng)絡(luò)流綜合抽樣方法設(shè)計

本文的設(shè)計目標是以有限的緩存實時抽取盡可能多的流量信息，與之相對應(yīng)的流量抽樣方法是全流抽樣方法。然而目前全流抽樣中研究的多是抽取IP流中部分報文組成不完整的IP流，并調(diào)整不同流的抽樣概率確保流相對標準差恒定。此種情況下全流抽樣方法抽取的IP流的流量特征具有較大地偏差，在整體抽樣率較低時使用這些不完整的IP流進行流量分類等應(yīng)用時會引起較大的誤差。因此，比較理想的抽樣方法是先將網(wǎng)絡(luò)報文歸并成流，然后針對歸并好的IP流進行抽樣獲取相對完整的網(wǎng)絡(luò)流。

考慮到IP流歸并的時間和空間復(fù)雜度，傳統(tǒng)的NetFlow組流方式不能夠?qū)崟r應(yīng)用于高速骨干鏈路，于是本文通過最近最少使用LRU（Least Recently Used）方式在線歸并有限時間內(nèi)的網(wǎng)絡(luò)報文，然后根據(jù)歸并的有限時間內(nèi)的流量信息指導(dǎo)流抽樣，整個綜合抽樣IS方法的原理如圖1所示。

圖1 IS算法基本原理

系統(tǒng)由LRU歸并模塊、聚類模塊和權(quán)值抽樣模塊3部分組成。LRU歸并模塊以最近最久未使用LRU方式歸并新到的網(wǎng)絡(luò)報文，聚類模塊通過哈希方式聚類LRU歸并模塊中淘汰出的單報文流，權(quán)值抽樣模塊根據(jù)不同的流長實現(xiàn)權(quán)值抽樣。對于流長超過閾值的流，權(quán)值抽樣模塊盡量全部保存；對于不同流長的流，權(quán)值抽樣模塊設(shè)置不同的蓄水池實現(xiàn)分段抽樣。

同時為了提高LRU報文歸并的準確性，對于當前保存在權(quán)值抽樣模塊中的IP流，若其有新報文到來，直接令該報文進入權(quán)值抽樣模塊進行更新，而對于LRU歸并模塊中流長超過閾值的流，直接將其從LRU歸并模塊中移至頻繁項模塊中。這樣權(quán)值抽樣模塊中將保存大量流長較大的IP流，這些IP流將承擔網(wǎng)絡(luò)流中大部分的報文負載，從而使得進入LRU歸并模塊中的報文數(shù)量大為減少。該操作等同于增加了報文歸并的時間窗口長度，能夠提高LRU報文歸并的準確性。

1.1 單報文流聚類方法

由于高速骨干網(wǎng)絡(luò)中單報文流在流總數(shù)中占有較高的比率，且單報文流通常情況下對應(yīng)于網(wǎng)絡(luò)中的異常流量，單個單報文流并不承載有用信息，直接存儲網(wǎng)絡(luò)中的全部單報文流會導(dǎo)致耗費大量的內(nèi)存空間保存一些價值不高的信息，此種做法是不值得的。通過聚類將具有相似特性的單報文流歸并到一起，不僅減少了內(nèi)存使用量，而且聚類后的流量能夠清晰地刻畫出單個單報文流無法描述的異常特征，如網(wǎng)絡(luò)中的“多對一”、“一對多”等特性必須通過聚類才能體現(xiàn)出來。因此，對單報文流進行聚類是十分必要的。

哈希函數(shù)能夠?qū)⑤^長的字串映射成短字串，通過哈希函數(shù)能夠很容易地實現(xiàn)多個五元組字符串的聚類，但哈希函數(shù)的可逆性差。為了直接反映原始五元組的信息，本文采用文獻［12］中構(gòu)建的帶哈希增強算法的Bloom Filter Reproduction（BFR）方法實現(xiàn)哈希聚類。BFR方法的原理是通過8個哈希函數(shù)將96 bit的源/目的地址、源/目的端口長字串按照比特劃分為8個16 bit的段。為了確保從所劃分段中還原出原字串的精度較高，BFR采用劃分段比特位部分重疊的方法，同時為了降低哈希沖突帶來的干擾，BFR為所劃分的8個段設(shè)置8個相互獨立的存儲空間。令Tuple={（a.b.c.d），（e），（f.g.h.i），（j）}分別表示單報文流的源地址、源端口、目的地址、目的端口，則BFR使用的哈希函數(shù)為：

BFR方法可以在實時的情況下實現(xiàn)單報文流的聚類，同時由文獻［12］可知：若長字串Tuple是活躍的，則BFR映射后的短字串一定是活躍的；若BFR映射后的短字串部分是活躍的，則短字串可以反映單報文流的聚類特征。通過BFR方法聚類單報文流能夠以較少的資源占用和較高的準確率揭示網(wǎng)絡(luò)流量中混雜的多種異常現(xiàn)象。

1.2 權(quán)值抽樣策略

由于網(wǎng)絡(luò)流量分布極其不均衡，常用的抽樣方法很難兼顧到各種流量的特點?；诖?，本文采用基于流長的權(quán)重抽樣策略實現(xiàn)網(wǎng)絡(luò)流采樣。①由于網(wǎng)絡(luò)流中的頻繁項主導(dǎo)著網(wǎng)絡(luò)的行為，且頻繁項流均包含著大量網(wǎng)絡(luò)報文，從流量縮減的效果看，采集頻繁項流的縮減效果要遠遠優(yōu)于采集短流的縮減效果，在內(nèi)存允許的情況下抽取網(wǎng)絡(luò)中全部的頻繁項是值得的，因此，有必要設(shè)置頻繁項緩存模塊抽取網(wǎng)絡(luò)流中的全部頻繁項；②由于未達到頻繁項閾值的不同流長的流出現(xiàn)的頻率存在較大的差異，為了使得抽取到的流更具有代表性，本文對于未達到頻繁項閾值的流采用分段抽樣的策略，對于流長頻率高的流，抽樣概率相對低一些，流長頻率低的流，抽樣概率相對高一些；③由于LRU歸并模塊采用的是基于時間的更新方式，不管網(wǎng)絡(luò)流的流長多大，只要該流一段時間內(nèi)無報文到來，在LRU緩存被占滿時，該流將被淘汰。LRU歸并模塊對流長的重視程度不夠，因此，權(quán)值抽樣模塊中設(shè)置了權(quán)值更新緩存模塊用于更好地歸并網(wǎng)絡(luò)流，權(quán)值更新模塊通過流長和時間計算網(wǎng)絡(luò)流的權(quán)值，并且權(quán)值更新模塊每次淘汰的均是權(quán)值最小的流。

權(quán)值抽樣策略的原理如圖1中權(quán)值抽樣模塊所示，權(quán)值抽樣方法的步驟為：

（1）若新到報文Xi命中頻繁項模塊中流Ffr，則流Ffr的流長加1；若新到報文Xi命中蓄水池抽樣模塊中流Fre，則流Fre的流長加1，從蓄水池中刪除流Fre并將該流加入到權(quán)值更新模塊中；若新到報文Xi命中權(quán)值更新模塊中流Fhit，按照1.2.1節(jié)的權(quán)值更新策略完成權(quán)值更新并判斷Fhit流長是否達到閥值T0，若Fhit流長達到T0，則將流Fhit放入到頻繁項模塊中。

（2）對于從LRU歸并模塊或蓄水池抽樣模塊中進入權(quán)值更新模塊中的流Fin，按照式（2）計算權(quán)值并將該流插入到權(quán)值更新模塊中，若權(quán)值更新模塊被占滿，則刪除權(quán)值更新模塊中權(quán)值最小的流Flrast，進入步驟（3）。

（3）若Flrast流長在［2，L1）區(qū)間，則采用蓄水池1進行抽樣；若Flrast流長在［L1，T0）區(qū)間，則采用蓄水池2進行抽樣。

1.2.1 權(quán)值更新策略

根據(jù)數(shù)據(jù)流的特點，流的流長越大，該流的權(quán)值越大，同時流的時間越新，該流在最近一段時間內(nèi)有報文到來的可能性越大，因此，流的權(quán)值與流長及流中最近一個報文到達時間密切相關(guān)。令權(quán)值更新模塊中流F表示為〈ID，f，weight〉，其中ID表示五元組，f表示流F的流長，weight表示權(quán)值，令進入權(quán)值更新模塊中的新流Fin為〈IDin，fin，iin〉，其中iin是流Fin中最近一個報文在整體網(wǎng)絡(luò)報文中的序號，則流Fin的權(quán)值weightin為：

對于權(quán)值更新模塊中流Fhit=〈IDhit，fhit，weighthit〉，若該流有報文Xi=〈IDhit，i〉到達，其中i是報文Xi的序號，則Fhit流更新后的流長和權(quán)重為fhit=fhit+1，weightin=α·fin+β·i。

當有新流到來且權(quán)值更新模塊被占滿時，刪除權(quán)值更新模塊中權(quán)值最小的流項F，并依據(jù)流F的流長選擇蓄水池模塊實現(xiàn)抽樣；而當權(quán)值更新模塊中存在流長達到T0的流F時，從權(quán)值更新模塊中刪除流F并將流F插入到頻繁項模塊中。

1.2.2 蓄水池抽樣

在網(wǎng)絡(luò)流抽樣中，網(wǎng)絡(luò)流的總數(shù)事先是未知的，且測量緩沖區(qū)的容量有限，此時的問題是如何在總數(shù)未知的流中抽取固定數(shù)量的流放入測量緩沖區(qū)中。蓄水池抽樣方法是在樣本總數(shù)未知的情況下，以相同概率抽取固定數(shù)量樣本的一種方法，蓄水池抽樣方法十分適合于流數(shù)未知的網(wǎng)絡(luò)流抽樣。蓄水池抽樣的基本原理是：對于容量為n的測量緩沖區(qū)，先到達的n個流全部放入測量緩沖區(qū)，當?shù)趖（t＞n）個流到達時，該流以n/t成為候選樣本并隨機替換掉緩沖區(qū)中的一個樣本。由于不同流長的流出現(xiàn)的頻率具有差異，為了使得抽取到的流更具有代表性，本文設(shè)置2個相同容量的蓄水池實現(xiàn)抽樣。對于流長在［2，L1）范圍內(nèi)的流，采用蓄水池1實現(xiàn)抽樣；對于流長在［L1，T0）范圍內(nèi)的流，采用蓄水池2實現(xiàn)抽樣。而對于需要更精確地區(qū)分抽樣流長的場合，可以通過設(shè)置更多個較小的蓄水池實現(xiàn)多蓄水池分段抽樣。

1.3 IS算法描述

IS算法的具體步驟描述如下：

（1）對于到達的每個報文X，提取報文X對應(yīng)的五元組IDX，查看五元組IDX對應(yīng)的流FX是否位于權(quán)值抽樣模塊中，若FX位于權(quán)值抽樣模塊中，按照1.2節(jié)的策略更新權(quán)值抽樣模塊；否則，進入步驟（2）；

（2）查看流FX是否位于LRU歸并模塊中，若FX位于LRU歸并模塊中，則流FX的流長fX=fX+1，進入步驟（3）；否則，進入步驟（4）；

（3）判斷流長fX是否達到頻繁項閾值T0，若流長fX達到頻繁項閾值T0，從LRU歸并模塊中刪除流FX，將流FX加入到頻繁項模塊中；否則，將流FX插入到LRU歸并模塊鏈表首部；

（4）將流FX插入到LRU鏈表首部，判斷LRU鏈表是否被占滿，若鏈表已滿，刪除LRU鏈表尾部流Ftail，進入步驟（5）；

（5）判斷流Ftail的流長ftail，若Ftail==1，進入步驟（6），否則，將流Ftail移除到權(quán)值抽樣模塊中，按照

1.2 節(jié)的策略更新權(quán)值抽樣模塊；

（6）計算流Ftail對應(yīng)的哈希值，按照1.1節(jié)的單報文流聚類策略完成哈希聚類。

1.4 算法復(fù)雜度考慮

本文提出的綜合流量抽樣方法若采用哈希方式或CAM（Content Addressable Memory）查找報文地址，尋址時間復(fù)雜度為O（1），LRU歸并模塊采用雙向鏈表實現(xiàn)，其時間復(fù)雜度為O（1），哈希聚類中哈希運算的時間復(fù)雜度為O（1），權(quán)值抽樣模塊中權(quán)值更新、蓄水池抽樣及頻繁項更新操作對每個報文僅需處理1個～2個表項，時間復(fù)雜度為O（1），因此，IS算法每報文時間復(fù)雜度約為O（1）。

在將網(wǎng)絡(luò)報文歸并成流的過程中，LRU歸并模塊的表項數(shù)越多，網(wǎng)絡(luò)流的歸并效果越好?？紤]到實際情況下高速SRAM的容量是有效的，且IS算法只是歸并有限時間內(nèi)的網(wǎng)絡(luò)報文，其本身并不要求歸并后的網(wǎng)絡(luò)流十分精確，因此，這里為LRU歸并模塊分配10 000個表項，每個表項需保存五元組、指針、流長等流特征，為其分配32個字節(jié)；為權(quán)值更新模塊、蓄水池1、蓄水池2各分配1 000個表項，每個表項32個字節(jié)；為頻繁項模塊分配1 500個表項，每個表項32個字節(jié)；為單報文流聚類模塊分配8個數(shù)組，每個數(shù)組共有個元素，每個元素占用2個字節(jié)。則系統(tǒng)總共占用緩存接近1.5 M字節(jié)，而目前的半導(dǎo)體技術(shù)完全能夠提供此容量大小的SRAM緩存。因此，IS算法能夠在線用于網(wǎng)絡(luò)流量采集。

2 實驗與評價

本文實驗數(shù)據(jù)集選為CAIDA（Cooperative Association for Internet Data Analysis）2003年提供的一條OC48鏈路的流量，提取該數(shù)據(jù)集的前5 000 000個報文，記為trace_2003，將trace_2003分成5組，每1 000 000個報文為一組，按照五元組方式組流。表1顯示了trace_2003中5組報文數(shù)據(jù)的流數(shù)分布情況，可以看出，trace_2003中流長分布極其不均衡。以第1組報文為例，該數(shù)據(jù)分組共包含86 817條IP流，單報文流數(shù)量占到總流數(shù)量的39.58%，流長在16以下的流占到總流數(shù)的90.76%；流長在99以上的流只有980條，但這980條流承載的報文數(shù)量達到493 979；且最長的IP流流長達到215 209，300以上大部分流長對應(yīng)的流數(shù)僅為1條～2條。顯然，流長處于兩端的流其特性嚴重偏離均值，對此部分流單獨處理是合適的。

表1 全部5組報文的流數(shù)分布

2.1 單報文流聚類效果分析

IS方法中各模塊緩存的分配與1.3節(jié)相同，權(quán)值更新模塊中α=0.99，β=0.01，L1=16，T0=100。由于單個單報文流沒有實際的意義，只有出現(xiàn)頻率高的單報文流才有意義，同時出現(xiàn)頻率高的單報文流通常能夠反映網(wǎng)絡(luò)異常。而由BFR的原理知，出現(xiàn)頻率高的單報文流映射后的短字串出現(xiàn)的頻率一定也高，而單獨一個短字串的頻率高并不能說明某個IP的頻率高，例如聚類后的SIPH中3.74出現(xiàn)的頻率為2 496，但SIPM的Top 20中找不到74.*，說明源地址中存在大量以3.74為前綴的IP，但不存在任意一個頻率高的以3.74為前綴的源地址。于是表2統(tǒng)計了trace_2003中第1組報文聚類后出現(xiàn)頻率高且相關(guān)的前5個短字串及出現(xiàn)頻率，其中不相關(guān)的短字串如單獨某個頻率高的字串（SPIM=3.74等）并未在表中列出。

表2 單報文流聚類特性

由于不同哈希函數(shù)聚類的效果不一，SIPL、SPORT和DPORT來源于Top 5字串，DIPL來源于Top 7字串，SIPM來源于Top 8字串，DIPM來源于Top 10字串，SIPH來源于Top 14字串，DIPH來源于Top 17字串?？梢钥闯觯徽撌窃吹刂愤€是目的地址，其高位字符串不如低位字符串分散，更關(guān)鍵的是通過聚類后的單報文流可以重現(xiàn)出網(wǎng)絡(luò)中的“高嫌疑”主機。如表1中69.163、163.10、10.72出現(xiàn)的頻率分別為3849、3772和3522，表明以69.163.10.72為源地址的單報文流出現(xiàn)的頻率很高，而單報文流基本上不承載有效信息，主機69.163.10.72很可能在從事掃描行為，而目的地址中如主機236.67.7.3的頻率很高，該主機很可能不能正常響應(yīng)服務(wù)或者遭受DDoS攻擊。在網(wǎng)絡(luò)遭受更高強度攻擊的情況下，通過聚類單報文流不僅使得需要進一步處理的IP流數(shù)大為減少，而且聚類后的單報文流能夠清晰揭示網(wǎng)絡(luò)流量中的多種異常現(xiàn)象，因此，將單報文流從總體流量中分離出來并單獨聚類是值得的。

2.2 權(quán)值抽樣效果分析

2.2.1 頻繁項流抽取效果分析

首先分析IS算法的頻繁項流抽取效果。由于頻繁項模塊的流項同時保存著五元組和流長信息，IS算法的頻繁項抽取方式不會產(chǎn)生誤報。若某個流長f≥100的流先期到達部分報文后暫時未有報文到達，且已到達報文數(shù)量未達到閾值T0，該流將可能被淘汰到蓄水池模塊中，若該流直到從蓄水池中被替換出去均無報文到達，則該流的流長會被低估，因此，IS算法存在漏報頻繁項的可能。

圖2 IS算法頻繁項流抽取效果

圖2（a）統(tǒng)計了全部5組報文數(shù)據(jù)中流長f≥100、f≥200和f≥300的流的召回率情況，可以看出，IS算法的頻繁項抽取方式具有較高的召回率，對于流長f≥100的流，頻繁項的召回率始終位于86%～94%間；而對于流長f≥200和f≥300的流，頻繁項模塊幾乎能夠召回全部的流。

圖2（b）統(tǒng)計了5組報文數(shù)據(jù)中IS算法召回的頻繁項流流長之和與正確流長之和的差值，其中流長之和的差值中最大的為1 252，將該值平均到每個流上，每個流的流長統(tǒng)計值與流長實際值之差接近1，因此，IS算法抽取的頻繁項流是比較完整的，IS算法具有較好的頻繁項流抽取效果。

2.2.2 蓄水池抽樣效果分析

IS算法中蓄水池抽樣模塊處理流的流長總處于2～99之間，由于頻繁項模塊抽取了網(wǎng)絡(luò)中大部分的報文，而聚類模塊抽取了網(wǎng)絡(luò)中全部的單報文流，因此，到達蓄水池模塊的流數(shù)和報文數(shù)均會大為減少，極大地減輕了蓄水池模塊處理的壓力，同時本文采用了蓄水池分段抽樣的方式，確保在蓄水池容量一定的情況下能夠抽取到更多種類的流。

在不考慮實時性的情況下按照NetFlow的組流方將報文分組歸并成流，通過等概率蓄水池抽樣抽取一定數(shù)量的流，并將抽取到的流與IS方法中蓄水池抽樣模塊抽取的流進行對比。考慮到本文權(quán)值抽樣模塊中共有3 500個表項用于保存流，于是等概率抽樣方法中蓄水池的容量設(shè)置為3 500。

圖3顯示了等概率蓄水池抽樣方法對于第1組報文數(shù)據(jù)抽取的IP流的分布情況，其中“100倍抽樣流數(shù)”為22～350流長區(qū)間抽取流數(shù)的100倍放大。從圖中可以看出，等概率蓄水池抽樣方法對于流長處于兩端的流的抽樣效果較差，所抽取到的3 500個表項中共保存有1 412條單報文流，抽取到的流長f≤6的流數(shù)達到2 791條，而抽取的流長f≥100的流數(shù)僅為36條。顯然等概率蓄水池抽樣方法會抽取過多的短流，由于抽取的短流占用了絕大部分的緩存空間，同時長流出現(xiàn)的頻率通常較低，因此，等概率抽樣方法會丟棄絕大部分的長流以及少量頻率低的中、短流，等概率蓄水池抽樣方法用于分布不均衡的網(wǎng)絡(luò)流量時會產(chǎn)生較大的偏差。

圖3 等概率蓄水池抽樣

圖4 蓄水池分段抽樣

圖4顯示了IS算法中蓄水池抽樣模塊對于第1組報文數(shù)據(jù)抽取到的IP流的分布情況，其中“20倍抽樣流數(shù)”為31～99流長區(qū)間抽取流數(shù)的20倍放大。可以看出，經(jīng)過單報文流聚類、頻繁項抽取及蓄水池分段抽樣共同作用后，蓄水池抽樣模塊抽取到的2～99流長區(qū)間的2 000條流中，流數(shù)分布變得平緩，被抽取到的短流的流數(shù)顯著減少，16～99流長區(qū)間的流數(shù)具有一定程度的增加。由于本文僅設(shè)置了2個蓄水池將流長［2，99］區(qū)間劃分為2段實現(xiàn)抽樣，被抽取的短流的數(shù)量仍然偏高，對于需要抽取流長分布更加均衡的IP流的場合，可以通過設(shè)置更多個較小的蓄水池實現(xiàn)多蓄水池分段抽樣。同時IS算法對于流數(shù)較少但流長較大的頻繁項流全部抽取，對于流數(shù)很多但攜帶可用信息有限的單報文流聚類處理，更重要的是IS算法的時間和空間復(fù)雜度能夠滿足網(wǎng)絡(luò)流量在線處理的要求，IS算法的抽樣效果明顯優(yōu)于等概率蓄水池方法。

由于本文采用容量有限的SRAM緩存實現(xiàn)實時流抽樣，在緩存被占滿而有新流報文到達時，總會有部分報文被淘汰，因此，所抽取流的完整性是IS算法必須考慮的一個問題。定義流完整率為所抽取流的流長與該流實際流長之比，由2.2.1節(jié)可知所抽取的頻繁項流的完整率幾乎為1，圖5顯示了IS算法中蓄水池抽樣模塊抽取到的2～99流長區(qū)間的2 000條流的流完整率分布情況，圖中坐標（x，y）表示流完整率小于x的流其流數(shù)為y?？梢钥闯觯钏爻闃幽K抽取到的絕大部分流的流完整率較高，全部流中有1 363流的流完整率為1，流完整率在0.5以下的流數(shù)為282，流完整率在0.8以上的流數(shù)為1 503，而流完整率在0.9以上的流數(shù)為1 437。盡管IS算法會造成少數(shù)網(wǎng)絡(luò)流的流完整率降低，但換來的是系統(tǒng)能夠?qū)崟r處理網(wǎng)絡(luò)流，且能夠抽取到分布更為合理的網(wǎng)絡(luò)流，這樣做是值得的。

圖5 蓄水池抽樣模塊流完整率分布

3 結(jié)束語

隨著互聯(lián)網(wǎng)流量數(shù)據(jù)規(guī)模的急劇增長，及時準確地從海量流量中抽取出需要的網(wǎng)絡(luò)流對于網(wǎng)絡(luò)管理和網(wǎng)絡(luò)安全具有重要的意義。針對互聯(lián)網(wǎng)流量中短流數(shù)量多但承載信息少、長流數(shù)量少但承載報文數(shù)多的特點，提出了一種面向不均衡網(wǎng)絡(luò)流的綜合抽樣IS方法。IS方法在實時歸并網(wǎng)絡(luò)報文的基礎(chǔ)上，采用BFR哈希函數(shù)實現(xiàn)單報文流聚類，采用頻繁項模塊實現(xiàn)頻繁項流的抽取，對于上述之外的其他網(wǎng)絡(luò)流，IS方法采用蓄水池分段抽樣方法實現(xiàn)更多種類流長網(wǎng)絡(luò)流的抽取。通過實際網(wǎng)絡(luò)流量測試表明，相對于單一的抽樣方法，IS方法在相同的緩存下能夠抽取出更為豐富的網(wǎng)絡(luò)流信息，并且算法能夠?qū)崟r應(yīng)用于高速網(wǎng)絡(luò)中。

［1］陳松，王珊，周明天.基于實時分析的網(wǎng)絡(luò)測量抽樣統(tǒng)計模型［J］.電子學報，2010，38（5）：1177-1180.

［2］張震，張進，汪斌強，等.基于流量負載自適應(yīng)的時間分層分組抽樣［J］.系統(tǒng)仿真學報，2009，21（23）：7421-7427.

［3］王洪波，陳時端，林宇.高速網(wǎng)絡(luò)超連接主機檢測中的流抽樣算法研究［J］.電子學報，2008，36（4）：809-818.

［4］Zhao Q，Xu J，Kumar A.Detection of Super Source and Destinations in High-Speed Networks：Algorithms，Analysis and Evaluations［J］.IEEE Journal on Selected Areas in Communictions，2006，24（10）：1840-1852.

［5］張玉，方濱興，張永錚.高速網(wǎng)絡(luò)監(jiān)控中大流量對象的識別［J］.中國科學：信息科學，2010，40（2）：340-355.

［6］裴育杰，王洪波，程時端.基于兩級LRU機制的大流檢測算法［J］.電子學報，2009，37（4）：684-691.

［7］寧卓，龔儉，顧文杰.高速網(wǎng)絡(luò)中入侵檢測的抽樣方法［J］.通信學報，2009，30（11）：27-36.

［8］潘喬，裴昌幸，朱暢華.一種用于異常檢測的網(wǎng)絡(luò)流量抽樣方法［J］.西安交通大學學報，2008，42（2）：175-178.

［9］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.

［10］Androulidakis G，Papavassiliou S.Improving Network Anomaly Detection Via Selective Flow-based Sampling［J］.IET Communications，2008，2（3）：399-409.

［11］趙月愛，陳俊杰，穆曉芳.非平衡技術(shù)在高速網(wǎng)絡(luò)入侵檢測中的應(yīng)用［J］.計算機應(yīng)用，2009，29（7）：1806-1808.

［12］龔儉，彭艷兵，楊望，等.基于Bloom Filter的大規(guī)模異常TCP連接參數(shù)再現(xiàn)方法［J］.軟件學報，2006，17（3）：434-444.

An Integrated Sampling Method Over Imbalanced Network Flows

LI Jing-fu，YANG Zhi-qiang
（Huanghuai University，Zhumadian 463000，China）

Aiming at the property of huge quantity and little information of small flows and small quantity and high payload of big flows，an Integrated Sampling（IS）method over imbalanced network flows is proposed.The fixed size of high-speed memory is used to aggregate packets into flows within limited time windows on line in IS algorithm first.Then，the partially reconstructed hash functions are used to cluster single packet flows，and the weight-updating module in which the flow weight is assigned by length and time together and the frequent-item module are cooperated to mine frequent items.Lastly，the multi-reservoir modules are introduced to sample flows in a stratified way for the rest flows.The experiment on real traffic shows that IS is capable of sampling more abundant information of flows comparing with other single sampling method at the same memory cost and it can be applied in the high backbone network on the wire.

network flows，flows sampling，hash cluster，frequent items extraction，reservoir sampling

TP393

A

1002-0640（2015）12-0074-06

2014-11-29

2015-01-26

河南省科技攻關(guān)計劃基金（122102210510）；河南省教育廳科學技術(shù)研究重點基金資助項目（13A520786）

李景富（1981-），男，河南確山人，碩士。研究方向：計算機網(wǎng)絡(luò)等。