基于流抽樣和LRU的高速網絡大流檢測算法

白 磊 田立勤 陳 超,2

基于流抽樣和LRU的高速網絡大流檢測算法

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

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

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

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

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

0 引 言

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

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

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

本文根據網絡流量分布的特性，提出流抽樣的測量方法，并結合LRU算法實現長流識別，算法能夠在使用較小的高速緩存資源情況下，精確提取大流量對象。

1 網絡流的定義

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

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

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

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

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

2.1 標準的LRU算法

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

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

2.2 流抽樣機制

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

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

圖1 標準Bloom Filter原理示意圖

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

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

基于流抽樣和LRU的大流檢測算法由流抽樣機制和LRU算法兩部分組成。流抽樣機制的作用是用來過濾掉大部分的小流信息，抽取大流信息，其又分為周期抽樣和BF流識別兩個模塊；LRU算法的作用是用來對抽取的報文實現大流檢測。圖2給出流抽樣和LRU算法的結構示意圖。

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

算法偽碼描述如下所示：

initialize (BF,LRU)

//初始化BF和LRU鏈表

While a packet x arrives

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

//計算出k 個哈希函數值

if( P ){

//如果是抽樣周期

sample(x);

//抽取報文x

BF(k)+1;

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

LRU();

//轉交LRU算法處理

}else{

//非抽樣周期

if(all BF(k)=1){

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

sample(x);

//抽取報文x

LRU();

//轉交LRU算法處理

} else

discard(x);

//丟棄該報文x

}

LRU(){

//LRU算法

if(Find(x) or not full){

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

update(count);

//流報文計數+1

setTop();

//將該流標識節點置頂

}

else

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

eliminate(last);

//淘汰最后一個流節點

}

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

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

2.4 算法分析

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

(1)

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

(2)

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

3 實驗仿真

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

圖3 實驗數據網絡流原始分布

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

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

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

由于文獻[8]中驗證了LRU_BF算法相對于其他類似算法如MBF算法、L_LRU算法、N_LRU算法等具有較高的精度，且使用的技術與本文類似。因此本文將基于流抽樣和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)在

續表1

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

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

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

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

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

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

4 結 語

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

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

[1] 周愛平,程光,郭曉軍.高速網絡流量測量方法[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] 程光,唐永寧.基于近似方法的抽樣報文流數估計算法[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策略的網絡流量測量算法[J].通信學報,2013,34(1):111-120.

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

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

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

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

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

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

[15] 張玉,方濱興,張永錚.高速網絡監控中大流量對象的識別[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。國家重點基礎研究發展計劃專項(2011 CB311809)；國家自然科學基金項目(61472137)；中央高校基本科研業務費項目(3142014085)。白磊，講師，主研領域：網絡測量。田立勤，教授。陳超，副教授。

TP393.4

A

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