白 磊 田立勤 陳 超,2

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

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

1(華北科技學院計算機學院 北京 101601)

2(浙江大學機械工程學院 浙江 杭州 310058)

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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

2.1 標準的LRU算法

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

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

2.2 流抽樣機制

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

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

圖1 標準Bloom Filter原理示意圖

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

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

基于流抽樣和LRU的大流檢測算法由流抽樣機制和LRU算法兩部分組成。流抽樣機制的作用是用來過濾掉大部分的小流信息，抽取大流信息，其又分為周期抽樣和BF流識別兩個模塊；LRU算法的作用是用來對抽取的報文實現(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)

//計算出k 個哈希函數(shù)值

if( P ){

//如果是抽樣周期

sample(x);

//抽取報文x

BF(k)+1;

//BF的k個哈希位置置為1

LRU();

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

}else{

//非抽樣周期

if(all BF(k)=1){

//判斷k個位置是否為1

sample(x);

//抽取報文x

LRU();

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

} else

discard(x);

//丟棄該報文x

}

LRU(){

//LRU算法

if(Find(x) or not full){

//如果已在LRU鏈表中，或鏈表未滿時

update(count);

//流報文計數(shù)+1

setTop();

//將該流標識節(jié)點置頂

}

else

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

eliminate(last);

//淘汰最后一個流節(jié)點

}

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

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

2.4 算法分析

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

(1)

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

(2)

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

3 實驗仿真

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

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

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

圖4 抽樣頻率對算法測量準確性影響圖

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

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

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

續(xù)表1

表2 標準LRU算法在LRU緩存變化時測量準確性(誤差)

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

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

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

圖5 三種算法在LRU緩存變化時測量長流閾值TH=4096準確性

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

4 結(jié) 語

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

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

[1] 周愛平,程光,郭曉軍.高速網(wǎng)絡(luò)流量測量方法[J].軟件學報,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的長流識別算法[J].軟件學報,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] 程光,唐永寧.基于近似方法的抽樣報文流數(shù)估計算法[J].軟件學報,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] 張震,王斌強,張風雨,等.基于LRU-BF策略的網(wǎng)絡(luò)流量測量算法[J].通信學報,2013,34(1):111-120.

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

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

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

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

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

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

[15] 張玉,方濱興,張永錚.高速網(wǎng)絡(luò)監(jiān)控中大流量對象的識別[J].中國科學,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。國家重點基礎(chǔ)研究發(fā)展計劃專項(2011 CB311809)；國家自然科學基金項目(61472137)；中央高?；究蒲袠I(yè)務(wù)費項目(3142014085)。白磊，講師，主研領(lǐng)域：網(wǎng)絡(luò)測量。田立勤，教授。陳超，副教授。

TP393.4

A

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