基于流抽樣和LRU的高速網(wǎng)絡(luò)大流檢測算法

白 磊 田立勤 陳 超,2

基于流抽樣和LRU的高速網(wǎng)絡(luò)大流檢測算法

白 磊1田立勤1陳 超1,2

1(華北科技學(xué)院計(jì)算機(jī)學(xué)院 北京 101601)

2(浙江大學(xué)機(jī)械工程學(xué)院 浙江 杭州 310058)

在高速主干網(wǎng)絡(luò)中，隨著網(wǎng)絡(luò)鏈路速率的不斷提高和網(wǎng)絡(luò)流數(shù)量的增加，如何及時(shí)、準(zhǔn)確地檢測出網(wǎng)絡(luò)中的大流信息，成為目前網(wǎng)絡(luò)流測量的熱點(diǎn)問題。根據(jù)傳統(tǒng)LRU算法由于突發(fā)性大量小流導(dǎo)致淘汰大流的測量缺陷和網(wǎng)絡(luò)重尾分布的特點(diǎn)，提出一種新的識(shí)別大流的算法——基于流抽樣和LRU的大流檢測算法。算法通過流抽樣技術(shù)過濾大部分的小流，并通過LRU算法識(shí)別大流信息，將過濾和識(shí)別過程分離，減少小流錯(cuò)誤淘汰大流的可能性，提高算法測量準(zhǔn)確性。分析算法的復(fù)雜度和漏檢率，并通過實(shí)際試驗(yàn)數(shù)據(jù)分析了算法參數(shù)配置對(duì)于大流測量的準(zhǔn)確性的影響。理論分析和仿真結(jié)果表明，與標(biāo)準(zhǔn)LRU算法和LRU_BF算法相比，在使用相同的存儲(chǔ)空間下，新算法具有更高的測量準(zhǔn)確性和實(shí)用性。

網(wǎng)絡(luò)測量 大流 抽樣 哈希 近期最少使用算法(LRU)

0 引 言

網(wǎng)絡(luò)流量測量是網(wǎng)絡(luò)管理的基礎(chǔ)，是分析網(wǎng)絡(luò)業(yè)務(wù)、網(wǎng)絡(luò)行為的重要方法。通過測量可以對(duì)數(shù)據(jù)進(jìn)行分析和處理，并提取網(wǎng)絡(luò)行為特征和規(guī)律，對(duì)網(wǎng)絡(luò)監(jiān)控、網(wǎng)絡(luò)設(shè)計(jì)和網(wǎng)絡(luò)規(guī)劃都具有重要意義[1]。然而隨著互聯(lián)網(wǎng)的快速發(fā)展和網(wǎng)絡(luò)新應(yīng)用的不斷出現(xiàn)，計(jì)算機(jī)網(wǎng)絡(luò)呈現(xiàn)向高速化、大規(guī)模、復(fù)雜化方向發(fā)展的趨勢(shì)。顯著特點(diǎn)是產(chǎn)生的數(shù)據(jù)量大、數(shù)據(jù)分組到達(dá)頻率高，導(dǎo)致單位數(shù)據(jù)分組的處理時(shí)間越來越短，對(duì)系統(tǒng)的存儲(chǔ)能力、處理能力和傳輸能力都提出了極大的挑戰(zhàn)，這便對(duì)網(wǎng)絡(luò)流量處理設(shè)備提出了更高的要求。當(dāng)前廣泛采用的測量方法是把網(wǎng)絡(luò)數(shù)據(jù)流歸并為流(flow)，通過把數(shù)據(jù)包歸并到相應(yīng)流中，極大地壓縮了數(shù)據(jù)量，使得網(wǎng)絡(luò)數(shù)據(jù)的存儲(chǔ)、處理和傳輸更為容易。但骨干網(wǎng)絡(luò)在峰值下并發(fā)流的數(shù)量仍然高達(dá)幾十萬甚至上百萬，完整保存這些流的狀態(tài)需要很高的計(jì)算和存儲(chǔ)開銷。

很多基于網(wǎng)絡(luò)流測量的研究表明，即便在不同的網(wǎng)絡(luò)環(huán)境中，網(wǎng)絡(luò)流的統(tǒng)計(jì)呈現(xiàn)很強(qiáng)的重尾分布特性。這種特性被稱為“the elephants and mice phenomenon”，即大部分流(mice流)只產(chǎn)生很少數(shù)量的報(bào)文，而小部分流(elephant流)卻產(chǎn)生很大數(shù)量的報(bào)文[2,3]。大流的一個(gè)顯著的特性就是它們僅占總體流的數(shù)目的一小部分卻產(chǎn)生總流量的絕大部分。這樣，在實(shí)際應(yīng)用中，多數(shù)情況下只需掌握占據(jù)大部分流量的大流信息即可滿足需要。因此，如何利用有限的硬件資源用于大流檢測，盡可能收集字節(jié)流量超過某個(gè)固定閾值的大流信息成為高速網(wǎng)絡(luò)測量的研究熱點(diǎn)問題。

Cristian等人首次采用“抓大放小”策略將大流檢測引入流量測量領(lǐng)域，并提出抽樣保持(sample and hold)和多級(jí)過濾(multistage Bloom filters)算法用于長流識(shí)別。前者算法簡單、易于實(shí)現(xiàn)，但當(dāng)網(wǎng)絡(luò)流數(shù)量較多，而抽樣頻率較低時(shí)需維護(hù)較大的存儲(chǔ)空間，且誤差偏高；后者對(duì)存儲(chǔ)空間需求較小，處理速度較快，但算法的錯(cuò)誤肯定率較高，會(huì)把小流誤檢為大流[4]。Tatsuya等提出一種使用周期抽樣識(shí)別長流的機(jī)制。這一機(jī)制的關(guān)鍵是在恰當(dāng)?shù)貦?quán)衡錯(cuò)誤肯定和錯(cuò)誤否定的基礎(chǔ)上，使用貝葉斯理論計(jì)算出抽樣流的報(bào)文數(shù)的閾值，通過這一閾值可以判定其原始流是否是長流。但它的缺點(diǎn)是實(shí)現(xiàn)時(shí)精度不高，錯(cuò)誤的肯定率和錯(cuò)誤的否定率之間的平衡不易實(shí)現(xiàn)[2]。Duffield等提出由抽樣流數(shù)據(jù)推斷出原始流數(shù)據(jù)、獲取原始流信息的思想，并提出兩種推斷方法：比例法和EM算法[5]。程光等提出使用積分推斷法和迭代法根據(jù)未抽樣流數(shù)和已抽樣流數(shù)推斷原始流量的統(tǒng)計(jì)信息[6]。使用報(bào)文抽樣技術(shù)，會(huì)造成一些內(nèi)在信息的損失，所以往往使用推斷的方法來減少這種損失，但是這些估計(jì)方法像EM算法計(jì)算量太大，不適合數(shù)據(jù)的在線處理。Kim等提出在路由器隊(duì)列管理中，利用頁面置換策略LRU機(jī)制來識(shí)別持續(xù)時(shí)間長、高速率的IP流[7]。張震等提出將流識(shí)別和流過濾分開處理的方式使用Bloom Filter及LRU算法實(shí)現(xiàn)長流信息統(tǒng)計(jì)[8]。使用LRU的方法具有處理速度快、識(shí)別率高、存儲(chǔ)空間可控等優(yōu)點(diǎn)，但在實(shí)際測量中，當(dāng)流的數(shù)量較多，某些突發(fā)性的小流有可能導(dǎo)致大流量對(duì)象被替換出緩存[9]，從而引起較大的測量誤差。

本文根據(jù)網(wǎng)絡(luò)流量分布的特性，提出流抽樣的測量方法，并結(jié)合LRU算法實(shí)現(xiàn)長流識(shí)別，算法能夠在使用較小的高速緩存資源情況下，精確提取大流量對(duì)象。

1 網(wǎng)絡(luò)流的定義

網(wǎng)絡(luò)中的“流”概念可以定義為對(duì)一個(gè)呼叫或連接的人為邏輯對(duì)應(yīng)。流是流量的一部分，由起始時(shí)間和停止時(shí)間定界。與流相關(guān)的屬性值(源/目的地址、分組計(jì)數(shù)、字節(jié)計(jì)數(shù)等)具有聚合性質(zhì)，反映了在起始和停止范圍發(fā)生的事件。由于研究背景的不同，對(duì)于流采用了不同的定義。

定義1 流是指符合特定的流規(guī)范和超時(shí)約束的一系列數(shù)據(jù)包的集合。在本文中流是指具有相同的源IP、宿IP、源端口、宿端口的按超時(shí)約束的TCP或UDP報(bào)文集合(不考慮協(xié)議)。流超時(shí)決定什么時(shí)候結(jié)束一個(gè)流，即同屬一個(gè)流的相鄰兩個(gè)報(bào)文的到達(dá)時(shí)間間隔，在本文中流超時(shí)都設(shè)置為30秒。

定義2 大流是一段時(shí)間內(nèi)某個(gè)流的長度超過事先定義的閾值TH的流。

定義3 高速網(wǎng)絡(luò)大流監(jiān)測算法的約束條件：1) 存儲(chǔ)空間有限，用來維護(hù)摘要統(tǒng)計(jì)信息且所需存儲(chǔ)空間遠(yuǎn)小于網(wǎng)絡(luò)流空間的大小，通常只存儲(chǔ)少量數(shù)據(jù)項(xiàng)的摘要信息；2) 實(shí)時(shí)處理，對(duì)每個(gè)數(shù)據(jù)項(xiàng)的處理時(shí)間很短，操作少而簡單；3) 一次線性掃描，每個(gè)報(bào)文的到達(dá)次序完全隨機(jī)，只能依序從頭至尾讀取一次數(shù)據(jù)流。

2 基于流抽樣和LRU的大流檢測算法

2.1 標(biāo)準(zhǔn)的LRU算法

LRU算法又稱為近期最少使用算法，其基本原理是：維護(hù)固定大小的緩存空間，將到達(dá)的元素依次存儲(chǔ)到緩存中，并始終保持最新到達(dá)的元素置于緩存的頂端，而最久未到達(dá)的元素則保留在緩存的最底部。當(dāng)有新元素加入而緩存已滿情況下，把緩存最底部的元素替換出去，并將新元素置于頂部。LRU算法在計(jì)算系統(tǒng)中有著廣泛的應(yīng)用，如內(nèi)存管理、數(shù)據(jù)庫緩存管理以及磁盤緩存管理等領(lǐng)域。

文獻(xiàn)[7]首先將其引入網(wǎng)絡(luò)流量測量領(lǐng)域，通過維護(hù)一個(gè)固定大小的LRU高速流緩存，并使用LRU思想對(duì)到達(dá)的每個(gè)分組所屬的流標(biāo)識(shí)進(jìn)行置換。由于小流持續(xù)時(shí)間短、長度小、到達(dá)速率低，根據(jù)LRU算法總有可能被替換出去；而大流由于持續(xù)時(shí)間長、長度大、訪問緩存頻繁，所以往往會(huì)留在LRU 緩存的頂部，從而可以實(shí)現(xiàn)大流檢測。但是，在實(shí)際測量過程中，當(dāng)大量突發(fā)性的小流到達(dá)時(shí)，由于小流的數(shù)量較多，會(huì)充滿LRU的緩存空間，這樣會(huì)致大流對(duì)象被置換出LRU緩存空間。文獻(xiàn)[7]的實(shí)驗(yàn)結(jié)果也表明有10%至20%的大流信息沒有檢測到。因此需要對(duì)傳統(tǒng)的LRU算法進(jìn)行改進(jìn)，減少小流進(jìn)入LRU緩存空間的概率，提高測量準(zhǔn)確性。

2.2 流抽樣機(jī)制

為解決突發(fā)性大量流信息同時(shí)到達(dá)，導(dǎo)致LRU算法大流漏檢情況，本文提出基于流抽樣的處理機(jī)制，減少大部分的小流信息進(jìn)入LRU緩存的概率。流抽樣的處理過程與傳統(tǒng)的報(bào)文抽樣不同，不是簡單隨機(jī)或周期性的抽取報(bào)文，而是根據(jù)流標(biāo)識(shí)抽樣情況進(jìn)行抽樣。其過程如下：按照概率P對(duì)鏈路上的報(bào)文進(jìn)行周期抽樣，一旦一個(gè)報(bào)文被抽取到后，其所屬的流信息被標(biāo)識(shí)，并哈希到內(nèi)存相應(yīng)位置。隨后這個(gè)流所屬的報(bào)文不管是否屬于抽樣周期，將都會(huì)被抽到，即該流的后續(xù)的每一個(gè)報(bào)文都會(huì)被處理。這樣由于網(wǎng)絡(luò)上的流統(tǒng)計(jì)呈現(xiàn)重尾分布的特性，通過抽樣，可以過濾掉大部分的小流信息，減少小流進(jìn)入LRU緩存空間的概率，而大流由于長度較長，其所屬的報(bào)文更容易被抽取，一旦大流的某個(gè)報(bào)文被抽取到，其后續(xù)的報(bào)文都將被抽取。

實(shí)現(xiàn)流抽樣的關(guān)鍵是如何識(shí)別已識(shí)別的流信息，我們使用Bloom Filter(BF)結(jié)果實(shí)現(xiàn)此過程。BF是用來表示一個(gè)集合的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，它支持成員查詢、隨機(jī)存儲(chǔ)[10]。其工作原理是：對(duì)于一個(gè)源串集合S={x1,x2,…,xn}，BF申請(qǐng)一個(gè)內(nèi)存大小為m單元的存儲(chǔ)空間A，每個(gè)單元維護(hù)一個(gè)計(jì)數(shù)器初始值置0，并使用哈希函數(shù)集合H={H1,H2,…,Hk}，每一個(gè)Hi，均是一個(gè)哈希函數(shù)。對(duì)于源串集合S中的任何一個(gè)元素xi，通過集合H中的k個(gè)獨(dú)立的哈希函數(shù)映射到存儲(chǔ)空間A中，得到k個(gè)[1，M]之間的數(shù)，并將內(nèi)存空間A中的這k個(gè)對(duì)應(yīng)單元比特位置1。因此Bloom Filter隨機(jī)存儲(chǔ)的過程就是通過k個(gè)哈希函數(shù)把某一元素哈希到Bloom Filter的存儲(chǔ)空間，并把相應(yīng)的位置置1的過程。當(dāng)BF需要判斷任一元素x′是否屬于集合S中的元素時(shí)，BF對(duì)x′經(jīng)k個(gè)哈希函數(shù)作用判斷哈希位置是否均為1，如果是則認(rèn)為x′屬于集合S，否則就不是集合中的元素。然而當(dāng)對(duì)x′哈希的結(jié)果均為1，而實(shí)際x′卻不屬于集合S時(shí)，就出現(xiàn)了錯(cuò)誤的肯定。Bloom Filter錯(cuò)誤肯定的x′屬于集合S的概率，即為錯(cuò)誤肯定率FPR(False Positive Rate)。研究表明，BF的錯(cuò)誤肯定率滿足公式fBF=(1-e-kn/m)k，其中k為哈希函數(shù)個(gè)數(shù)，n為元素個(gè)數(shù)，m為BF的存儲(chǔ)空間數(shù)。BF存儲(chǔ)和查找過程如圖1所示。

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

因此可以利用BF隨機(jī)存儲(chǔ)和查詢機(jī)制判斷一個(gè)流是否已被抽樣，通過使用哈希函數(shù)集合H={H1,H2,…,Hk}對(duì)到達(dá)的報(bào)文的流標(biāo)識(shí)(協(xié)議類型、源/宿IP、源/宿端口)xi進(jìn)行作用。如果某個(gè)報(bào)文恰好屬于抽樣周期，或該報(bào)文所屬的流已被BF存儲(chǔ)，則抽取此報(bào)文，否則丟棄。

2.3 使用流抽樣和LRU算法檢測大流

基于流抽樣和LRU的大流檢測算法由流抽樣機(jī)制和LRU算法兩部分組成。流抽樣機(jī)制的作用是用來過濾掉大部分的小流信息，抽取大流信息，其又分為周期抽樣和BF流識(shí)別兩個(gè)模塊；LRU算法的作用是用來對(duì)抽取的報(bào)文實(shí)現(xiàn)大流檢測。圖2給出流抽樣和LRU算法的結(jié)構(gòu)示意圖。

圖2 流抽樣和LRU算法過程原理圖

算法偽碼描述如下所示：

initialize (BF,LRU)

//初始化BF和LRU鏈表

While a packet x arrives

calculate H=h(1),h(2),…,h(k)

//計(jì)算出k 個(gè)哈希函數(shù)值

if( P ){

//如果是抽樣周期

sample(x);

//抽取報(bào)文x

BF(k)+1;

//BF的k個(gè)哈希位置置為1

LRU();

//轉(zhuǎn)交LRU算法處理

}else{

//非抽樣周期

if(all BF(k)=1){

//判斷k個(gè)位置是否為1

sample(x);

//抽取報(bào)文x

LRU();

//轉(zhuǎn)交LRU算法處理

} else

discard(x);

//丟棄該報(bào)文x

}

LRU(){

//LRU算法

if(Find(x) or not full){

//如果已在LRU鏈表中，或鏈表未滿時(shí)

update(count);

//流報(bào)文計(jì)數(shù)+1

setTop();

//將該流標(biāo)識(shí)節(jié)點(diǎn)置頂

}

else

//不在鏈表中，且鏈表已滿

eliminate(last);

//淘汰最后一個(gè)流節(jié)點(diǎn)

}

基于流抽樣和LRU算法的大流檢測過程：當(dāng)報(bào)文到達(dá)時(shí)，首先判斷該報(bào)文是否滿足概率P的抽樣周期，如果符合抽樣周期則直接抽取此報(bào)文，并根據(jù)所屬的流標(biāo)識(shí)使用BF的哈希函數(shù)集在相應(yīng)位置置1，并將報(bào)文轉(zhuǎn)交LRU算法處理；否則如果報(bào)文不在抽樣周期，則由BF判斷該報(bào)文是否為已識(shí)別的流。如果屬于已識(shí)別流，則抽取報(bào)文轉(zhuǎn)交LRU算法處理；如果不屬于任何已識(shí)別流，則丟棄該報(bào)文，繼續(xù)處理下一報(bào)文。LRU算法采用散列雙向鏈表的數(shù)據(jù)結(jié)構(gòu)[11,12]，每個(gè)鏈表節(jié)點(diǎn)都存儲(chǔ)流標(biāo)識(shí)和流的報(bào)文計(jì)數(shù)器，對(duì)于采用流抽樣機(jī)制抽取的每個(gè)報(bào)文，先判斷該報(bào)文所屬流標(biāo)識(shí)是否已在鏈表中，如果已存在，則對(duì)應(yīng)計(jì)數(shù)器加1，同時(shí)將該節(jié)點(diǎn)置于LRU 鏈表頂部；當(dāng)所屬流標(biāo)識(shí)不在鏈表中，需要?jiǎng)?chuàng)建新的流量記錄時(shí)，若LRU 鏈表已滿，應(yīng)根據(jù)“近期最少使用”原則，淘汰LRU 鏈表的最后一個(gè)流；同時(shí)，為了降低大流漏檢率，在淘汰流時(shí)，需要判斷其是不是已經(jīng)為大流。最終輸出流長度大于指定閾值的流即為需識(shí)別的大流信息。

從以上分析可以看出，流抽樣和LRU算法只會(huì)處理處于抽樣周期或者已抽樣的流的報(bào)文。小流信息由于抽樣機(jī)制，僅有滿足抽樣概率P的小流需要處理，大部分被丟棄掉，從而減少突發(fā)性的大量小流同時(shí)進(jìn)入LRU緩存，導(dǎo)致錯(cuò)誤淘汰大流的可能性。對(duì)于大流，由于長度較長，較容易被抽取，而且一旦大流的某個(gè)報(bào)文被抽取到，其后續(xù)的報(bào)文都將被抽取，這樣實(shí)現(xiàn)抓大放小的過程。

2.4 算法分析

算法測量準(zhǔn)確性的影響因素有兩個(gè)方面，一個(gè)是BF的錯(cuò)誤肯定率，即將某個(gè)不屬于已識(shí)別的流的報(bào)文，錯(cuò)誤識(shí)別為已識(shí)別流的報(bào)文。由公式fBF=(1-e-kn/m)k可知，當(dāng)m值較大時(shí)，公式值較小，即BF轉(zhuǎn)發(fā)給LRU算法的錯(cuò)誤肯定報(bào)文數(shù)量較小，不影響LRU算法處理。影響算法準(zhǔn)確性的主要因素是LRU算法的漏檢率。

(1)

將P(F=TH)=θ/THα+1代入式(1)可得：

(2)

由于算法查找過程使用哈希函數(shù)集進(jìn)行作用，BF對(duì)哈?？臻g的一次訪問內(nèi)存開銷均為O(k)。由于BF使用并行散列運(yùn)算，算法實(shí)際執(zhí)行時(shí)間接近1次散列運(yùn)算所需時(shí)間。同時(shí)，LRU 鏈表采用散列雙向鏈表，使用拉鏈法解決散列沖突，則平均查找長度為O(1+β/2)，其中β為裝填因子。

3 實(shí)驗(yàn)仿真

為了驗(yàn)證上述本文提出的流抽樣和LRU算法的有效性，本文使用采集于NLANR的Trace進(jìn)行仿真試驗(yàn)[13,14]。Traces總共報(bào)文數(shù)6 187 376個(gè)，共有68 367個(gè)流。BF使用k=6個(gè)哈希函數(shù)，存儲(chǔ)空間大小m=216=65 536,即哈?？臻g為[0，65 535]。實(shí)驗(yàn)測量網(wǎng)絡(luò)報(bào)文數(shù)據(jù)的原始分布如圖3所示，從圖中可以看出網(wǎng)絡(luò)流的分布統(tǒng)計(jì)呈現(xiàn)重尾分布特性。

圖3 實(shí)驗(yàn)數(shù)據(jù)網(wǎng)絡(luò)流原始分布

圖4顯示當(dāng)LRU算法采取固定的存儲(chǔ)空間大小(8192)時(shí)，抽樣頻率變化，對(duì)算法測量不同閾值的大流準(zhǔn)確性影響。

圖4 抽樣頻率對(duì)算法測量準(zhǔn)確性影響圖

從圖4可以看出，對(duì)于測量各種大流的閾值情況，測量準(zhǔn)確性均隨著抽樣頻率降低而增大。這是由于隨著抽樣頻率降低，導(dǎo)致丟棄大量的報(bào)文，從而影響測量準(zhǔn)確性。而且如果大流閾值越小(如128)，測量的準(zhǔn)確性要比相對(duì)較大的大流閾值(如8192)低的多，這是由于長流閾值越長，對(duì)抽樣頻率的敏感程度越低。

由于文獻(xiàn)[8]中驗(yàn)證了LRU_BF算法相對(duì)于其他類似算法如MBF算法、L_LRU算法、N_LRU算法等具有較高的精度，且使用的技術(shù)與本文類似。因此本文將基于流抽樣和LRU的算法(LRU_Sample算法)與LRU_BF算法和標(biāo)準(zhǔn)LRU算法進(jìn)行比較。表1-表3分別顯示本文提出的基于流抽樣和LRU的算法(LRU_Sample算法，抽樣頻率P=1/5)、標(biāo)準(zhǔn)LRU算法以及文獻(xiàn)[8]提出的LRU_BF算法，在LRU緩存空間變化時(shí)測量不同閾值(TH)的大流的準(zhǔn)確性比較。

表1 LRU_Sample算法(P=1/5)在

續(xù)表1

表2 標(biāo)準(zhǔn)LRU算法在LRU緩存變化時(shí)測量準(zhǔn)確性(誤差)

表3 LRU_BF算法在LRU緩存變化時(shí)測量準(zhǔn)確性(誤差)

表1-表3的測量結(jié)果可以看出，當(dāng)三種算法的LRU緩存空間較小時(shí)(128時(shí))，由于流數(shù)量巨大，而LRU緩存空間太小，導(dǎo)致絕大部分的大流信息被淘汰，測量準(zhǔn)確性較差。當(dāng)LRU緩存增加時(shí)，測量的準(zhǔn)確性也隨之提高，當(dāng)LRU緩存足夠大時(shí)，總是能將大流完全檢測出來。但本文提出的基于流抽樣的LRU算法的收斂速度遠(yuǎn)快于標(biāo)準(zhǔn)的LRU算法，也優(yōu)于LRU_BF算法，在使用相同的緩存空間條件下，測量的各種長度閾值的大流的準(zhǔn)確性均比標(biāo)準(zhǔn)LRU算法和LRU_BF算法準(zhǔn)確。

圖5顯示以測量長流閾值TH=4096為例(測量其他長流閾值與此類似)，LRU_Sample算法與LRU_BF算法及標(biāo)準(zhǔn)LRU算法，在使用相同的哈希函數(shù)和個(gè)數(shù)以及LRU緩存空間情況下測量準(zhǔn)確性的比較。

圖5 三種算法在LRU緩存變化時(shí)測量長流閾值TH=4096準(zhǔn)確性

實(shí)驗(yàn)仿真結(jié)果表明，相對(duì)標(biāo)準(zhǔn)LRU算法和LRU_BF算法，本文提出的LRU_Sample算法具有較高的測量準(zhǔn)確性。尤其當(dāng)LRU緩存空間相對(duì)較小時(shí)，LRU_Sample算法優(yōu)勢(shì)更加明顯。這是由于當(dāng)LRU緩存較小時(shí)，標(biāo)準(zhǔn)LRU算法和LRU_BF算法由于緩存空間已滿，新到達(dá)的大量小流會(huì)將LRU緩存中的未識(shí)別大流信息淘汰掉。而LRU_Sample算法通過流抽樣機(jī)制，可以將大部分的小流過濾掉，同時(shí)保留已識(shí)別的大流信息，減少小流對(duì)大流的影響，從而減少算法的測量誤差。

4 結(jié) 語

由于網(wǎng)絡(luò)的高速化和大規(guī)模化，在線完全測量網(wǎng)絡(luò)流信息變得越來越難[15]。而“抓大放小”的測量策略可以有效降低算法對(duì)計(jì)算資源的需求，較準(zhǔn)確地測量大流的信息，滿足特定網(wǎng)絡(luò)應(yīng)用的需求。

本文根據(jù)傳統(tǒng)LRU算法由于突發(fā)性大量小流導(dǎo)致淘汰大流的測量缺陷和網(wǎng)絡(luò)重尾分布的特點(diǎn)，提出基于流抽樣和LRU的大流檢測算法。通過采用流抽樣機(jī)制，可以過濾掉大部分的小流信息，減少小流進(jìn)入LRU緩存空間的概率，而大流由于長度較長，其所屬的報(bào)文更容易被抽取。一旦大流的某個(gè)報(bào)文被抽取到，其后續(xù)的報(bào)文都將被抽取，這樣實(shí)現(xiàn)“抓大放小”的策略。分析了算法的復(fù)雜度和誤判率，并通過試驗(yàn)數(shù)據(jù)驗(yàn)證算法的有效性。結(jié)果表明，與標(biāo)準(zhǔn)的LRU算法和LRU_BF算法相比，新算法可以在使用較少的存儲(chǔ)空間的條件下，及時(shí)、準(zhǔn)確地識(shí)別網(wǎng)絡(luò)中的大流信息，滿足實(shí)際測量需要。

[1] 周愛平,程光,郭曉軍.高速網(wǎng)絡(luò)流量測量方法[J].軟件學(xué)報(bào),2014,25(1):135-153.

[2] Tatsuya M,Masato U,Ryoichi K.Identifying elephant flows through periodically sampled packets[C]//Proc of ACM SIGCOMM/IMC’04.Taormina:ACM Press,2004:115-120.

[3] 吳樺,龔儉,楊望.一種基于雙重Counting Bloom Filter的長流識(shí)別算法[J].軟件學(xué)報(bào),2010,21(5):1115-1126.

[4] Cristian Estan,George Varghese.New directions in traffic measurement and accounting[J].ACM Transactions on Computer Systems,2003,21(3):270-313.

[5] Duffield N G,Lund C,Thorup M.Estimating flow distributions from sampled flow statistics[C]//Proc of the ACM SIGCOMM Conference on Applications,Technologies 2003,Architectures.Karlsruhe:ACM Press,2003:325-336.

[6] 程光,唐永寧.基于近似方法的抽樣報(bào)文流數(shù)估計(jì)算法[J].軟件學(xué)報(bào),2013,24(2):255-265.

[7] Kim S I,Reddy N A L.Identifying long-term high-bandwidth flows at a router[C]//Proceedings of the 8th International Conference on High Performance Computing.Hyderabad,India,2001:361-371.

[8] 張震,王斌強(qiáng),張風(fēng)雨,等.基于LRU-BF策略的網(wǎng)絡(luò)流量測量算法[J].通信學(xué)報(bào),2013,34(1):111-120.

[9] 王風(fēng)宇,郭山清,李亮雄,等.一種高效率的大流提取方法[J].計(jì)算機(jī)研究與發(fā)展,2013,50(4):731-740.

[10] 王宏,龔正虎.Hits和Holds:識(shí)別大象流的兩種算法[J].軟件學(xué)報(bào),2010,21(6):1391-1403.

[11] 王風(fēng)宇,云曉春,王曉峰,等.高速網(wǎng)絡(luò)監(jiān)控中大流量對(duì)象的提取[J].軟件學(xué)報(bào),2007,18(12):3060-3070.

[12] 任高明,夏靖波,喬向東,等.基于LRU淘汰機(jī)制的自適應(yīng)大流檢測算法[J].吉林大學(xué)學(xué)報(bào)：工學(xué)版,2014,44(4):1159-1164.

[13] 王洪波,裴育杰,林宇,等.基于LRU的大流檢測算法[J].電子與信息學(xué)報(bào),2007,29(10):2487-2492.

[14] 裴育杰,王洪波,程時(shí)端.基于兩級(jí)LRU機(jī)制的大流檢測算法[J].電子學(xué)報(bào),2009,37(4):684-691.

[15] 張玉,方濱興,張永錚.高速網(wǎng)絡(luò)監(jiān)控中大流量對(duì)象的識(shí)別[J].中國科學(xué),2010,40(2):340-355.

ELEPHANT FLOW DETECTION ALGORITHM FOR HIGH SPEED NETWORKS BASED ON FLOW SAMPLING AND LRU

Bai Lei1Tian Liqin1Chen Chao1,2

1(SchoolofComputerScience,NorthChinaInstituteofScienceandTechnology,Beijing101601,China)2(SchoolofMechanicalEngineering,ZhejiangUniversity,Hangzhou310058,Zhejiang,China)

In high-speed backbone network, with the increasing speed of network link and the augment in network flow numbers, it becomes a hot issue in current network flow measurement that how to detect the elephant flow information in networks timely and accurately. According to the measurement defect of traditional LRU algorithm that the elephant flows be discarded due to bursting large numbers of mice flows and the feature of heavy tail distribution of network, we proposed a new algorithm for identifying elephant flows—an elephant flow detection algorithm based on flow sampling and LRU. The algorithm filtrates most of the mice flows by flow sampling technology, and identifies elephant flows by LRU algorithm. It separates the filtration and recognition processes, reduces the possibility of mice flows phasing out elephant flows incorrectly, and improves measurement accuracy. We analysed the complexity and missing rate of the algorithm, and analysed the influence of algorithm’s parameter configuration on accuracy of elephant flows measurement through practical test data. Theoretical analysis and simulation result indicated that compare with standard LRU algorithm and LRU_BF algorithm, when the memory spaces used were the same, our algorithm had higher measurement accuracy and practicality.

Network measurement Elephant flow Sampling Hash Least recently used (LRU)

2014-11-25。國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃專項(xiàng)(2011 CB311809)；國家自然科學(xué)基金項(xiàng)目(61472137)；中央高校基本科研業(yè)務(wù)費(fèi)項(xiàng)目(3142014085)。白磊，講師，主研領(lǐng)域：網(wǎng)絡(luò)測量。田立勤，教授。陳超，副教授。

TP393.4

A

10.3969/j.issn.1000-386x.2016.04.027