一種新的基于LRU的大流檢測算法

張毅卜，夏靖波，孫 昱，任高明

(空軍工程大學信息與導航學院，陜西西安710077)

網(wǎng)絡流是由相同屬性的數(shù)據(jù)分組組成的集合，由于其在網(wǎng)絡運營管理、計費等方面的巨大應用，所以基于流的網(wǎng)絡測量不斷受到重視。IETF(Internet Engineering Task Force)推薦的流測量方法是在測量設備中維護一個流表，為每個流保存一個流記錄，但是當前網(wǎng)絡中流的數(shù)量十分巨大，而目前的半導體技術并不能提供容量足夠大的快速存儲器SRAM來記錄每個流的信息，因此實現(xiàn)IETF的方法十分困難。已有研究顯示，網(wǎng)絡中的流大小呈重尾分布，即少量的大流產(chǎn)生了網(wǎng)絡中大部分的流量，而對于網(wǎng)絡運營管理、計費等相關應用而言，只需要獲取大流的流量信息就足以滿足應用需求［1］。現(xiàn)有的大流檢測算法普遍存在準確率不高的問題，不能滿足實際應用需求。因此，如何更有效率地檢測大流成為了網(wǎng)絡流量測量中的一個熱點問題。

1 研究現(xiàn)狀

LRU算法是目前大流檢測算法中時空效率較高的一種，它最早由Smitha等人提出［2］，其基本思想是:設置一個用于保存流記錄的固定大小的緩存，保持最新到達的數(shù)據(jù)分組所屬流記錄位于緩存頂部，而最久未到達的數(shù)據(jù)分組所屬流的記錄位于緩存的最底部。當有新流到達且緩存已滿時，淘汰最久未更新的流來為新流騰出存儲空間。由于大流持續(xù)時間長且分組到達速率高，所以其總能排在緩存的上部，從而以較大的概率留在LRU緩存中。該類方法處理速度快，識別效率高，硬件實現(xiàn)簡單，但當有大量小流突發(fā)到達時，會造成某些大流被替換出LRU緩存，從而引起漏檢。

為了進一步優(yōu)化LRU算法，降低其漏檢率，張果等人提出的基于分層多粒度最近最久未使用的流量統(tǒng)計算法［3］，將多級LRU表“串聯(lián)”在一起來降低原算法漏檢率，該算法的實質(zhì)是犧牲存儲空間來換取測量精度的提高。考慮到高速緩存資源有限，文獻［4］和文獻［5］在原有單級結構的基礎上提出采用兩級結構來檢測大流，其相同之處在于第一級結構都采用LRU算法，在第二級結構的設計中，文獻［4］采用LEAST淘汰策略(當有新流到達且緩存已滿時，流量大小最小的流被淘汰)，文獻［5］仍然采用LRU淘汰策略。實驗表明，這兩種算法對大流的檢測效果較好而且性能接近，因此本文所提算法將與文獻［5］中的LRU2-V2算法進行對比。文獻［6］提出了一種基于LRU和SCBF的大流檢測算法，但是該算法僅適用于檢測大流，并不具備大流流量統(tǒng)計功能。文獻［7］所提出的基于滑動窗口的LRU算法在判斷的基礎上需要進行抽樣，處理過程較為繁瑣，且滑動窗口的設置也較為復雜。

為了進一步降低LRU算法的大流漏檢率并提高其對大流流量的測量精度，本文提出了一種基于LRU和CBF兩級結構的大流檢測算法。算法在時間窗口內(nèi)將大流檢測的篩選和過濾分開處理，然后對時間窗口進行刷新，此舉最大限度地運用了LRU算法和CBF的優(yōu)點，緩解了LRU和CBF的處理壓力，達到了較好的效果。本文首先對該算法進行介紹，然后從理論上分析影響該算法性能的因素，并給出最佳的參數(shù)設置方式，最后通過實驗驗證該算法的有效性。

2 LRU-CBF算法

2.1 算法思想

由于大流持續(xù)的時間相對較長并且占用的帶寬較大，因此在相同的時間內(nèi)經(jīng)過鏈路的流量往往較其他流而言更大。若將測量時間分為若干個時間窗口，在任一時間窗口內(nèi)，一個流經(jīng)過鏈路的流量達到預先設定的閾值，那么這個流可能是大流。這一步過濾出大流的工作由CBF來完成，順利通過CBF的流將被記錄在LRU緩存中進行進一步篩選。在這個過程中，CBF并不需要存儲流關鍵字等信息，故能克服其需要緩存容量過大的缺點，由于CBF可以阻擋大量的小流進入LRU緩存，所以該算法的大流漏檢率也將極大地降低。

2.2 算法描述

算法結構如圖1所示。

圖1 算法結構圖

本算法分為兩級，第一級為LRU，第二級為CBF。如果一個分組到達且在LRU中發(fā)現(xiàn)對應的流記錄，那么將該分組大小累加到這條記錄中并將其置于LRU緩存的頂部，如果該分組對應的流記錄不在LRU表中，那么它將被哈希函數(shù)映射進CBF中，其分組大小將累加到相應的計數(shù)器里。如果此時這些計數(shù)器的值都不小于CBF中設定的閾值，那么該分組對應的流將被記錄到LRU中。CBF在時間窗口結束時會自動刷新，即將所有計數(shù)器清0，最后當測量時間結束時，LRU中符合大流定義的流將被讀出并保存。具體的算法步驟(偽代碼)如下所示:

3 算法分析

3.1 算法準確性分析

首先分析該算法消除漏檢的條件。當一個可能的大流f通過CBF進入LRU隊列或者已經(jīng)記錄在LRU隊列中的某個流f的分組到達時，該流f將被置于LRU隊列的首部。如果接下來到達的分組均不屬于流f，那么該流在LRU隊列中的位置將不斷向隊尾移動并最終被淘汰。現(xiàn)在考慮當流f位于LRU的隊列首部且LRU隊列長度已達最大值時，連續(xù)到達多少個不屬于流f的分組，流f將恰好被移出LRU隊列。設一共需要x個不屬于流f的分組，則可列出方程如

式中:T1為CBF中用于判斷流是否進入LRU的閾值;PT1表示一個分組屬于字節(jié)數(shù)小于T1的流的概率;PCBF為CBF的誤正率;a和b為修正因子;N為LRU隊列的最大長度。當?shù)竭_x個分組時，其中有xPT1個屬于字節(jié)數(shù)小于T1的流，從理論上說，這些小流無法通過CBF，因此不會對LRU中流f的位置造成影響。但是由于CBF存在“誤正”的原因，即不屬于同一個流的分組在CBF中可能被映射到相同的位置，因此如果恰有小流分組和某個大流的分組“誤正”在一起，或者某些小流的分組“誤正”在一起超過了CBF中設定的閾值T1，那么將會有小流進入LRU中影響到流f的位置。xPT1PCBF表示發(fā)生“誤正”的分組個數(shù)，因為發(fā)生“誤正”的分組對應的流并不會全進入到LRU中，所以再乘以一個修正因子a(0＜a≤1)表示最終對流f的位置造成影響的小流分組的個數(shù)。同理，x(1－PT1)表示屬于其他流的分組的個數(shù)，這些分組中的一部分可能會在LRU中找到對應的流記錄，而這些流記錄將被依次置于LRU隊列的首部，導致流f向隊尾移動，另一部分可能使其對應的流通過CBF進入到LRU中造成了流f的后移。顯然，這些分組并不會都影響到流f的位置，因此再乘以一個修正因子b(0＜b≤1)。當LRU隊列的最大長度為N時，處于隊列首部的流f向隊尾移動N個位置將恰好移出該隊列，故方程的右邊為N。根據(jù)式(1)，可得

因此通過設置合適的T1，T2的取值，可以將大流的測量誤差控制在一個較低的水平內(nèi)。

3.2 參數(shù)設置

如果給定的緩存容量為C，l1和l2分別為CBF和LRU隊列中每一項的字節(jié)數(shù)，那么CBF和LRU的長度如何設計才能發(fā)揮出該算法的最大性能是值得考慮的問題。假設用于LRU的緩存容量占總緩存容量的比例為α，那

即對于一個位于LRU隊列首部的流而言，只要連續(xù)到達的x個分組中有1個分組屬于該流，那么該流就不會被淘汰。由于大流持續(xù)的時間較長，分組數(shù)較多，故x越大，就越有可能在這x個分組中出現(xiàn)屬于該大流的分組從而使之不被淘汰，因此，提高x的值將降低該算法的大流漏檢率。

下面討論當測量時間結束時，若一個大流被成功檢測到，則它的流量大小測量誤差情況。設某個大流第一次出現(xiàn)時，它在對應的時間窗口內(nèi)經(jīng)過的流量為T'。若T'≥T1，則該流第一次出現(xiàn)時就將通過CBF，如果該流不被漏檢的話，則最終它的流量大小可以精確測得。若T'＜T1，此時該流在這個時間窗口內(nèi)將不被檢測到，如果該流的實際流量為T，LRU中用于判斷是否為大流的閾值為T2，那么最終流量大小的測量誤差至少為T'/T，由于T'＜T1，T≥T2，故么LRU隊列的最大長度為

經(jīng)證實，早期功能鍛煉有利于重癥患者的恢復[11]。10月13日，患者神志清楚，病情允許在床上進行活動，肌力評估為Ⅲ級。終止鍛煉標準同上。鍛煉從大關節(jié)開始：上肢屈伸10次/組，每日兩次；下肢屈膝蹬腿10次/組，每日兩次；床上端坐位10 min/次，每日兩次。每日對肌力進行評估并記錄。機械通氣第5天起以主動運動為主，被動運動為輔。主動運動：拉皮筋鍛煉；床上端坐位15 min/次，每日兩次；上肢屈伸10次/組，每日兩次；下肢屈膝腳尖內(nèi)收10次/組，每日兩次；屈膝蹬腿10次/組，每日兩次；直腿抬高、支腿外展5次/組，每日兩次。

CBF的最大長度為

式中:k為CBF所使用的哈希函數(shù)的個數(shù)，n為在一個時間窗口內(nèi)到來的流的總數(shù)量。將式(4)～(6)帶入式(2)中，得

CBF在一個時間窗口內(nèi)的最大誤正率［8］為

由于x越大，算法的漏檢率越低，因此將x視為α的函數(shù)，問題將轉換為一個簡單的數(shù)學問題，即在一個一元函數(shù)中，自變量α為何值時，函數(shù)x取得最大值。下面先確定式(7)中其余各個參數(shù)的取值。

根據(jù)式(3)可知，若大流首次出現(xiàn)時未通過CBF，則其流量的測量誤差不高于T1/T2，可以設置(T1/T2)≤ε(例如ε=1%)，將該誤差控制在一個較低的水平，此時，有T1≤εT2。由于大流通常被定義為占鏈路容量超過一定比例的流，設鏈路容量為V，故大流閾值T2=βV(β通常取0.01%，0.1%，1%等值)。綜上，知T1≤εβV。因為PT1(0＜PT1

＜1)表示一個分組屬于字節(jié)數(shù)小于T1的流的概率，所以當T1選定時，PT1可由歷史信息統(tǒng)計得到。

若已經(jīng)進入CBF的流的數(shù)量為n'，哈希函數(shù)的個數(shù)k=mln2/n'，此時 CBF 的誤正率取得最小值［9］，但是在一個時間窗口內(nèi)n'是不斷變化的，所以k將依據(jù)經(jīng)驗值確定。式(7)中參數(shù)l1，l2的取值可由對CBF，LRU的設計得到，參數(shù)a，b由經(jīng)驗值確定，緩存空間C由系統(tǒng)分配。

計算出使x最大的最佳值α后，根據(jù)式(4)和(5)可以得到LRU隊列的最大長度N以及CBF的長度m。

4 實驗驗證

本文實驗所用流量數(shù)據(jù)來自于MAWI工作組和CADIA組織在互聯(lián)網(wǎng)骨干鏈路上通過全流量采集得到，數(shù)據(jù)描述如表1所示。

表1 數(shù)據(jù)集描述

4.1 實驗參數(shù)

測量時間τ=10 s，將Trace-1中的大流閾值T2設為鏈路容量的0.1%，Trace-2中的大流閾值T2設為鏈路容量的0.01%。測量誤差ε設為1%，T1取上限值，即T1=εT2。時間窗口的長度W取下限值，即W=τT1/T2。CBF的每一項只包含一個2 byte的計數(shù)器，故l1=2;LRU每一項包括流關鍵字13 byte(采用五元組)，流大小計數(shù)器4 byte(可以記錄最大值為4 Gbyte的流)，指針8 byte(用以實現(xiàn)雙向鏈表以加快LRU隊列的訪問速度)，故l2=25。參數(shù)a=0.2，b=0.8，哈希函數(shù)個數(shù)k=3，當緩存容量C給定時，由式(4)、(5)、(7)分別確定N，m，α的取值，如表2所示。

表2 緩存容量分配

4.2 實驗結果對比與分析

將本文所提算法與 LRU算法、文獻［5］提出的LRU2-V2算法進行對比，算法優(yōu)劣的評價指標為大流漏檢率和大流流量測量的平均誤差，為了保證公平性，三者均使用相同的緩存容量，實驗結果如表3所示。

表3 實驗結果對比

從表3中可以看到，LRU算法的漏檢率和平均誤差都比較大，不能滿足實際的應用。LRU2-V2算法的各個評價指標都比較小，與LRU算法相比具有明顯的優(yōu)勢，而本文所提出的LRU-CBF算法要優(yōu)于LRU2-V2算法。與LRU2-V2算法相比，LRU-CBF算法的不同點在于使用了CBF作為小流過濾器，由于CBF僅作為過濾器使用時消耗的存儲空間很小，故在同等存儲空間的條件下，可以有更多的存儲資源用于LRU，因此對大流的檢測效果更佳。通過實驗對比，證明了LRU-CBF算法不僅能有效降低大流漏檢率，同時還提高了大流流量的測量精度。

5 結束語

由于網(wǎng)絡龐大，使得網(wǎng)絡流量測量過程中所需采集的數(shù)據(jù)量巨大［10］，這為網(wǎng)絡流量的測量帶來了巨大挑戰(zhàn)，大流檢測問題正是基于這一現(xiàn)狀提出的。現(xiàn)有的基于LRU的大流檢測算法大多存在漏檢率較高的問題，無法滿足實際的應用需求，故本文采用了一種CBF與LRU兩級結構的大流檢測算法。該算法使用CBF來進行第一步過濾，濾除網(wǎng)絡中數(shù)量眾多的小流，濾出可能的大流，而使用LRU對濾出的大流做進一步篩選。在存儲資源相同的條件下，該算法的大流漏檢率低，對大流流量的測量精度高，因此能更好地應用于實際的網(wǎng)絡流量測量當中。

:

［1］ ZHANG Y，BRESLAU L，PAXSON V，et al.On the characteristics and origins of Internet flow rates［C］//Proc.ACM SIGCOMM.Pittsburgh:［s.n.］，2002:309-322.

［2］ SMITHA A，KIM I，Reddy ALN.Identifying long term high band width flows at a router［C］//Proc.HiPC.Berlin:Springer，2001:361-371.

［3］張果，陳庶樵，張震，等.基于MGLRU的IP流統(tǒng)計算法［J］.計算機工程，2010，36(17):140-146.

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

［5］裴育杰，王洪波，程時端.基于兩級LRU機制的大流檢測算法［J］.電子學報，2009，37(4):685-691.

［6］謝冬青，周再紅，駱嘉偉.基于LRU和SCBF的大象流提取及其在DDoS防御中的應用［J］.計算機研究與發(fā)展，2011，48(8):1517-1523.

［7］張娟娟，高仲合，馬兆豐.基于滑動窗口的LRU大流檢測算法［J］.通信技術，2012，45(10):684-691.

［8］楊家海，吳建平，安常青.互聯(lián)網(wǎng)絡測量理論與應用［M］.北京:人民郵電出版社，2009.

［9］胡廣昌.基于Bloom Filters流抽樣算法的研究［D］.曲阜:曲阜師范大學，2010.

［10］朱慶弦，張杰，張駿溫.網(wǎng)絡管理技術的發(fā)展趨勢［J］.電視技術，2005，29(12):54-56.