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

李景富，楊志強(qiáng)

（黃淮學(xué)院，河南駐馬店463000）

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

李景富，楊志強(qiáng)

（黃淮學(xué)院，河南駐馬店463000）

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

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

0 引言

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

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

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

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

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

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

圖1 IS算法基本原理

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

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

1.1 單報(bào)文流聚類方法

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2.2 蓄水池抽樣

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

1.3 IS算法描述

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

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

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

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

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

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

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

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

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

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

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

2 實(shí)驗(yàn)與評價(jià)

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

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

2.1 單報(bào)文流聚類效果分析

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

表2 單報(bào)文流聚類特性

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

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

2.2.1 頻繁項(xiàng)流抽取效果分析

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

圖2 IS算法頻繁項(xiàng)流抽取效果

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

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

2.2.2 蓄水池抽樣效果分析

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

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

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

圖3 等概率蓄水池抽樣

圖4 蓄水池分段抽樣

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

由于本文采用容量有限的SRAM緩存實(shí)現(xiàn)實(shí)時(shí)流抽樣，在緩存被占滿而有新流報(bào)文到達(dá)時(shí)，總會有部分報(bào)文被淘汰，因此，所抽取流的完整性是IS算法必須考慮的一個(gè)問題。定義流完整率為所抽取流的流長與該流實(shí)際流長之比，由2.2.1節(jié)可知所抽取的頻繁項(xiàng)流的完整率幾乎為1，圖5顯示了IS算法中蓄水池抽樣模塊抽取到的2～99流長區(qū)間的2 000條流的流完整率分布情況，圖中坐標(biāo)（x，y）表示流完整率小于x的流其流數(shù)為y。可以看出，蓄水池抽樣模塊抽取到的絕大部分流的流完整率較高，全部流中有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(shí)處理網(wǎng)絡(luò)流，且能夠抽取到分布更為合理的網(wǎng)絡(luò)流，這樣做是值得的。

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

3 結(jié)束語

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

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

［2］張震，張進(jìn)，汪斌強(qiáng)，等.基于流量負(fù)載自適應(yīng)的時(shí)間分層分組抽樣［J］.系統(tǒng)仿真學(xué)報(bào)，2009，21（23）：7421-7427.

［3］王洪波，陳時(shí)端，林宇.高速網(wǎng)絡(luò)超連接主機(jī)檢測中的流抽樣算法研究［J］.電子學(xué)報(bào)，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］.中國科學(xué)：信息科學(xué)，2010，40（2）：340-355.

［6］裴育杰，王洪波，程時(shí)端.基于兩級LRU機(jī)制的大流檢測算法［J］.電子學(xué)報(bào)，2009，37（4）：684-691.

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

［8］潘喬，裴昌幸，朱暢華.一種用于異常檢測的網(wǎng)絡(luò)流量抽樣方法［J］.西安交通大學(xué)學(xué)報(bào)，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］.計(jì)算機(jī)應(yīng)用，2009，29（7）：1806-1808.

［12］龔儉，彭艷兵，楊望，等.基于Bloom Filter的大規(guī)模異常TCP連接參數(shù)再現(xiàn)方法［J］.軟件學(xué)報(bào)，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)計(jì)劃基金（122102210510）；河南省教育廳科學(xué)技術(shù)研究重點(diǎn)基金資助項(xiàng)目（13A520786）

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