一種基于FEFS與CBF的網(wǎng)絡(luò)大流識別算法

劉曉陸，劉 淵，王春龍

(江南大學數(shù)字媒體學院，江蘇無錫214122)

1 概述

在高速網(wǎng)絡(luò)鏈路中，快速、準確地測量網(wǎng)絡(luò)流量是網(wǎng)絡(luò)安全、帶寬控制及計費的重要基礎(chǔ)，網(wǎng)絡(luò)大流識別作為流量測量問題的一個分支，應(yīng)用十分廣泛。通過關(guān)注大流的詳細信息，能使人們迅速定位導致事故發(fā)生的對象，從而有效地應(yīng)對網(wǎng)絡(luò)攻擊、合理調(diào)配網(wǎng)絡(luò)資源。

但在當今時代，隨著計算機網(wǎng)絡(luò)向高速化、大規(guī)模化、復雜化方向發(fā)展［1］，高速網(wǎng)絡(luò)鏈路中數(shù)據(jù)規(guī)模巨大、報文到達速率極高，導致完整地存儲每個數(shù)據(jù)包的信息難度很大。基于實際硬件水平和優(yōu)化成本的考量，面向數(shù)據(jù)包級的傳統(tǒng)全數(shù)據(jù)采集的網(wǎng)絡(luò)流量測量手段已不再適用［2］。

網(wǎng)絡(luò)流的分布呈現(xiàn)出顯著的重尾分布特征，例如在一個監(jiān)控周期里，大流的數(shù)量只占總流數(shù)的0．02%，但是卻包涵了傳輸流量的近60%［3］。這種現(xiàn)象通常被稱為“大象和老鼠效應(yīng)”。因此，文獻［4］首先引入“抓大放小”的策略，在周期采樣和多級hash表的基礎(chǔ)上分別提出了SH(Sample and Hold)算法和MF(Multistage Filter)算法，SH算法實現(xiàn)簡單，但是涉及到抽樣，誤差較高;MF算法對大流識別的準確性較高，但是可能將小流誤報為大流。

LRU(Least Recently Used)最早是一種內(nèi)存管理算法，文獻［5］將它引入到網(wǎng)絡(luò)大流的檢測中。此后，衍生出多種基于LRU的升級算法，文獻［6］提出了LLR算法，將LRU淘汰機制和LEAST淘汰機制相結(jié)合，將被LRU淘汰的但滿足一定閾值的流重新放入LEAST中進行二次篩選，彌補了兩者的不足;文獻［7］提出一種新的基于LRU的大流檢測算法，通過引入“小流早期丟棄”和“大流預(yù)保護”機制來提高了檢測準確性;文獻［8］提出了Landmark-LRU算法，在LRU結(jié)構(gòu)中設(shè)置“Landmark”來區(qū)分大流和小流的存儲區(qū)域;文獻［9］提出了FEFS算法，在原始LRU基礎(chǔ)上，通過引入流尺寸因子s和自適應(yīng)調(diào)節(jié)因子M，來篩選要淘汰的流記錄，提高了大流提取的準確率。以上基于LRU［10］方法在處理速度、識別效率、硬件消耗方面各有優(yōu)點，但是當大量小流突發(fā)到達時，由于多種原因，均會造成某些大流被錯誤地替換出緩存。

此外在高速網(wǎng)絡(luò)中，流量測量還會受到計算速度和存儲資源的限制。恰恰相反，現(xiàn)實情況中卻是速度快的存儲器容量小，容量大的存儲器訪問速度慢［11］。運用哈希技術(shù)能夠緩解存儲速率和存儲器容量的矛盾。基于哈希計算的數(shù)據(jù)結(jié)構(gòu)Bloom Filter具有空間效率高、計算復雜度低的優(yōu)點，常被用于網(wǎng)絡(luò)大流測量中，但是此結(jié)構(gòu)不具有計數(shù)統(tǒng)計功能，因此又產(chǎn)生了Count Bloom Filter、Space Code Bloom Filter、Loop Bloom Filter等多種數(shù)據(jù)結(jié)構(gòu)［12-14］。運用這些數(shù)據(jù)結(jié)構(gòu)進行網(wǎng)絡(luò)大流的識別，能夠?qū)Ψ蠗l件的流信息進行精確維護，極大降低了對存儲空間的需求，明顯提高了存儲速度和識別的準確度。

本文研究一種基于LRU算法和BF算法的大流識別算法:FEFS_CBF算法。將CBF結(jié)構(gòu)引入到FEFS算法中，首先使用CBF過濾小流，然后將達到一定閾值的流信息放入LRU中進行篩選，并將識別出的大流隔離，可減少突發(fā)小流對大流識別造成的干擾。

2 相關(guān)算法

2．1 LRU基本原理及拓展

LRU算法通過設(shè)置一個固定大小的緩存，用來保存流記錄。每新到一個數(shù)據(jù)包，LRU即檢測它所屬的流是否存在緩存中。若存在，則更新對應(yīng)流的信息，并將此流記錄提取到緩存的最頂端;若不存在，就新建一條流記錄，插入到緩存的最頂端。以此類推，接收頻率較小的流信息就會處在緩存的最底端，當緩存已滿，且再有新流的數(shù)據(jù)包到來時，LRU將新建流信息插入緩存頂端，并將最底端的流記錄替換出緩存。由于大流傳輸?shù)某掷m(xù)時間長，到達頻率高，因此有很大概率使大流信息留在 LRU緩存中。

文獻［9］對原始的LRU算法進行了改進，形成FEFS算法。FEFS算法相較于LRU算法有以下優(yōu)勢:(1)在選取淘汰流時，并非直接淘汰處于LRU鏈表底部的流，而是選取一個相對較小的流進行淘汰。為了定位淘汰流的位置，F(xiàn)EFS算法設(shè)置了調(diào)節(jié)因子M，并為每一個流都引入一個屬性——尺寸因子s。在最開始時，s的值等于流的報文的數(shù)量，即每當有屬于該流的報文到達時，s就加1。當選擇一個流淘汰時，檢查LRU鏈表底部流的s值，如果s≤M，就淘汰該流;否則，依次檢查鏈表中前一個單元，直到找到s≤M的流，將該流淘汰。對于檢查過的流，重新定義流的s值為s=s－M。最終將新建的流與檢查過的流一起移至LRU鏈表頭部。(2)當LRU中的某條流記錄達到一定閾值，則認為此流很可能是一個大流，那么將此流隔離到一個單鏈表中，當再有此流的數(shù)據(jù)包到達時，只需要更新單鏈表中流的狀態(tài)。這樣能有效地降低計算資源的消耗。FEFS算法結(jié)構(gòu)如圖1所示。

圖1 FEFS算法結(jié)構(gòu)

2．2 Bloom Filter基本原理及拓展

Bloom Filter是一種基于hash的簡潔數(shù)據(jù)結(jié)構(gòu)。其核心是設(shè)置一個向量Vector，通過幾個hash函數(shù)，來判斷元素是否屬于一個集合。

在初始狀態(tài)時，Bloom Filter是一個m維的位數(shù)組，每一位的值都預(yù)設(shè)為0。設(shè)集合S={s1，s2，…，sn}中共有n個元素，選取并使用k個相互獨立的哈希函數(shù)，將集合中的每一個元素，映射到m維的空間中，被映射到的位置，其數(shù)值被置為1。若一個位置被多次置為1，那么此位置的值保留為1。在判斷x是否屬于該集合時，對x應(yīng)用k次hash函數(shù)，如果所有的hi(x)(1≤i≤k)所映射的位置的值都為1，則判定x是集合中的元素;否則，就認為x不是集合中的元素。Bloom Filter結(jié)構(gòu)如圖2所示。

圖2 Bloom Filter結(jié)構(gòu)

Bloom Filter在使用時可能會將不屬于該集合的元素誤判為屬于該集合，所以不適合“零錯誤”的應(yīng)用場合，而且不支持計數(shù)操作，因此除了進行判斷查找，無法進行數(shù)值統(tǒng)計。Count Bloom Filter將標準Bloom Filter中的每個1 bit單元拓展為一個計數(shù)器(counter)。在插入元素時，使用k個hash函數(shù)進行映射，對映射到每一位，將其數(shù)值加1。在刪除元素的時候，對應(yīng)的k個位置的數(shù)值分別減1。Count Bloom Filter通過增加存儲空間的代價，給 Bloom Filter增加了刪除操作。Count Bloom Filter結(jié)構(gòu)如圖3所示。

圖3 Count Bloom Filter結(jié)構(gòu)

3 基于FEFS與CBF的大流識別算法

3．1 大流定義

大流的定義方法和衡量標準有很多［15］。本文將四元組(源IP、目的IP、源端口、目的端口)相同的數(shù)據(jù)包歸并為一個流。流的大小即為所含數(shù)據(jù)包的數(shù)量。大流的閾值為一個固定比值。

3．2 算法結(jié)構(gòu)

FEFS-CBF算法使用三級處理機制:(1)CBF部分由m維的計數(shù)器數(shù)組和k個相互獨立的hash函數(shù)組成，每個計數(shù)器大小為x位，每個計數(shù)器最大存儲數(shù)值為(2x－1)。CBF用來篩選有可能成為大流的流，避免小流進入LRU。(2)LRU部分為一個固定長度的雙向鏈表，在本文算法中，LRU長度一般定為1/大流閾值。每一個節(jié)點由3個部分組成:流信息(以四元組作為流信息標示符)，流所含的包數(shù)counter和尺寸因子s。LRU用來找出大流，淘汰小流。(3)大流存儲(Elephant Flows Storing，EFS)部分為一個單鏈表，其節(jié)點結(jié)構(gòu)與LRU鏈表相同，用來存儲已識別出的大流(下文中的“LRU”均指本文算法中的LRU雙鏈表存儲結(jié)構(gòu)，并非LRU算法)。

在一定時間段T內(nèi)，檢測的數(shù)據(jù)包總數(shù)為N，大流閾值為r(r為一個百分比)，含包數(shù)超過r×N的流為一個大流，那么，在監(jiān)控周期內(nèi)，最多有1/r個大流。所以，定義 LRU部分長度為 1/r。在文獻［9-11］中也表明，這樣定義能使算法存儲空間復雜度與錯誤率接近最佳水平。另外，定義過濾閾值g=(r/2)×N，作為過濾掉小流的閾值。FEFS-CBF算法結(jié)構(gòu)如圖4所示。

圖4 FEFS-CBF算法結(jié)構(gòu)

3．3 算法流程

本文算法的基本流程為:在每一個監(jiān)控周期內(nèi)，初始化EFS單鏈表，LRU雙鏈表以及CBF結(jié)構(gòu)。當一個數(shù)據(jù)包到達時，首先在EFS鏈表中從上往下進行常數(shù)次查找，若能找到對應(yīng)流的記錄，說明此流已經(jīng)被確定為大流，就更新流信息，使對應(yīng)counter加1。若在EFS單鏈表中找不到，就將此數(shù)據(jù)包信息與LRU中的流信息進行比較，若找到相應(yīng)流的記錄，則將對應(yīng)的counter和s加1，若counter值已經(jīng)超過設(shè)定的大流閾值r×N，就將此流記錄從LRU中摘除，插入到EFS鏈表頭部;若沒有達到大流閾值，將此流記錄移至LRU頭部。若在LRU鏈表中找不到對應(yīng)流記錄，就通過k個相互獨立的hash函數(shù)映射到CBF空間中，對應(yīng)的每個位置的值都加1。若此時對應(yīng)的每個位置的值都不小于過濾閾值g，則將此流信息插入LRU鏈表頭部，流數(shù)量counter和尺寸因子s設(shè)定為過濾閾值g，并將CBF中對應(yīng)位置的值減去g。

在將CBF中的流信息插入LRU結(jié)構(gòu)過程中，若LRU結(jié)構(gòu)已滿，就需要淘汰一條流信息。設(shè)定了調(diào)節(jié)因子M［9］，在選擇流進行淘汰時，從LRU底部開始，檢測流記錄的s值，若s≤M，就淘汰該流;否則，就將該流的s值修改為s=s－(M－g)，然后檢查鏈表中的上一個流，直到找到一個滿足s≤M的流L，將LRU鏈表的尾節(jié)點指向L的上一條流記錄，然后把L從鏈表中刪除，并將前面檢查過的流記錄和從CBF中插入的流記錄一起移至LRU鏈表頭部。本文算法的實現(xiàn)過程如下:

算法1Search

算法2InsertLRU

Guolv表示過濾閾值;S表示尺寸因子;M表示衡量因子;Length表示LRU長度

參數(shù):LRU雙鏈表;pkt．info

4 理論結(jié)果分析

4．1 誤報率

誤報率(False Positive Ratio，F(xiàn)PR)是指將非大流識別為大流的概率。在本文算法中，F(xiàn)PR主要是由CBF部分產(chǎn)生的。在CBF中，設(shè)計數(shù)器數(shù)組長度為m，每個計數(shù)器位數(shù)為x。在一個監(jiān)控周期內(nèi)，檢測的數(shù)據(jù)包總數(shù)為N，所有的數(shù)據(jù)包屬于n個流。當有元素插入CBF中時，經(jīng)過k個hash函數(shù)映射到計數(shù)器數(shù)組中，對應(yīng)位置的值加1。每次映射，某位被映射到的概率為1/m。當所有元素映射完成后，總共執(zhí)行了n×k次映射，此時，計數(shù)器數(shù)組中的任意一位仍為0的概率為:

在CBF中，出現(xiàn)“錯報”(屬于某個流的數(shù)據(jù)包沒有到來，但其對應(yīng)的位置卻被其他到來的數(shù)據(jù)包映射到，該流計數(shù)器錯誤地加1)的概率為:

由式(1)～式(4)可以看出，算法的誤報率隨著k的增大而減小，但是隨著k的增大，也就是哈希函數(shù)個數(shù)的增加，不僅會增加計算量，也要相應(yīng)的增加CBF計數(shù)器的個數(shù)，從而增大了存儲成本，因此在實踐過程中，應(yīng)根據(jù)現(xiàn)實硬件水平做出權(quán)衡。

4．2 漏報率

漏報率(False Negative Ratio，F(xiàn)NR)是指真實的大流沒有被識別出來的概率。在本文算法中，F(xiàn)NR主要產(chǎn)生在LRU部分中。雖然經(jīng)過CBF部分的過濾，使數(shù)據(jù)包數(shù)超過一定閾值的流才會放到LRU結(jié)構(gòu)，但由于大量小流突發(fā)到來，還是可能將大流錯誤淘汰。例如:當LRU滿載時，在一定時間t內(nèi)，大流F到來的數(shù)據(jù)包數(shù)小于(M－g)(M為衡量因子，g為過濾閾值)，從LRU底部開始向上檢查，選擇要淘汰的流，檢查過的流記錄的尺寸因子s值均大于衡量因子M，直到檢查到大流F，算法會將F淘汰。由此可見，在過濾閾值g一定的前提下，衡量因子M值越大，造成漏報的情況越高，但M值越小，會使算法檢測距離越長，降低了算法處理速度。因此，M值的選取，要在處理速度和準確率方面進行權(quán)衡。

4．3 時間復雜度

本文用處理每一個數(shù)據(jù)包的計算復雜度來表示算法的時間復雜度。當一個數(shù)據(jù)包到達時，先要在EFS部分進行查詢，若能找到相應(yīng)記錄，就只更新流信息，此時為最好的情況下，計算復雜度為O(1)。若找不到，移至LRU部分進行查找，若能找到相應(yīng)流記錄，需要更新流信息并將該流移至LRU頭部，查找和移動的操作為常數(shù)次，此時計算復雜度為O(1)。若在LRU部分中找不到，則要將數(shù)據(jù)包插入到CBF中，插入CBF的復雜度為O(k)。若在CBF中達到過濾閾值，應(yīng)將CBF中的相應(yīng)計數(shù)器記錄進行減法操作，計算復雜度為O(k)，并將該流信息提取到LRU中，此時為算法最壞的情況下，處理一個數(shù)據(jù)包的計算復雜度為O(1)+O(k)。因此，在監(jiān)控周期開始時，本文算法處理一個數(shù)據(jù)包的計算復雜度為O(1)+O(k)，但根據(jù)大象老鼠效應(yīng)，絕大多數(shù)數(shù)據(jù)包都能在EFS和LRU結(jié)構(gòu)中找到相應(yīng)記錄，這時的計算復雜度趨近最好情況下的復雜度O(1)。

4．4 空間復雜度

空間復雜度用占用內(nèi)存的大小來衡量。在10 Gb/s高速骨干鏈路下，取單位時間1 s，超過總數(shù)據(jù)包數(shù)0．01%的流為大流，平均每個流含10個數(shù)據(jù)分組，平均每個分組大小1 000 Byte。根據(jù)上文分析，EFS部分和LRU部分至多各需要10 000個存儲空間。每個空間最大需要192 Byte，其中包括每個流的流信息96 Byte，流包計數(shù)count、尺寸因子s和指針各32 Byte。因此，EFS和LRU所需內(nèi)存最大均為1．92 MB。在CBF中，平均要存儲990 000個小流。選取7個hash函數(shù)，計數(shù)器長度為8位，則CBF所需最大存儲約為105 MB。目前的硬件水平完全能滿足本文算法實驗的要求。

5 實驗結(jié)果分析

在實驗室有限的硬件環(huán)境中，使用2組數(shù)據(jù)集進行實際流量數(shù)據(jù)仿真，測試本文算法性能。實驗中所使用的2個數(shù)據(jù)集分別為:MIT林肯實驗室入侵檢測數(shù)據(jù)集中較大的一個文件——1999 outside．tcpdump(大小約為 314 MB)，以下簡稱 Outside;CAIDA網(wǎng)公開的2008年的OC-192主干鏈路數(shù)據(jù)集 equinix-chicago．dirB．20080717-130000．pacap(大小約為161 MB)，以下簡稱Equinix。有關(guān)數(shù)據(jù)集的詳細介紹如表1所示。

表1 實驗數(shù)據(jù)集信息

為了檢驗算法在不同流分布條件下，大流識別的準確率，在本文選取的2個仿真數(shù)據(jù)集中，Outside數(shù)據(jù)集的網(wǎng)絡(luò)流重尾分布特征較為明顯，而Equinix的流分布較為平均，Outside的大流比率遠大于Equinix。舉例說明，當取大流閾值為 0．05%時，Outside中的大流數(shù)為204，而Equinix中的大流數(shù)僅為7。

本文使用2組數(shù)據(jù)集，并設(shè)置3種大流閾值，將本文算法FEFS-CBF與FEFS、原始CBF進行測試，分別比較它們的誤報率(FPR)和漏報率(FNR)，并統(tǒng)計綜合錯誤率(FNR+FPR)。FEFS與本文算法中的LRU雙鏈表結(jié)構(gòu)長度均被設(shè)為1/大流閾值。原始CBF算法中的CBF計數(shù)器位數(shù)設(shè)定則較大，從而能在實驗條件允許的情況下取得較低誤報率。本文將FEFS-CBF的過濾閾值設(shè)為大流閾值的一半，隔離閾值設(shè)為大流閾值，尺寸因子設(shè)為(過濾閾值+10)。實驗結(jié)果如表2所示。

從實驗數(shù)據(jù)集流分布來看，在Equinix中的大流占有很小比率，突發(fā)小流更多，這對大流識別產(chǎn)生的干擾也就更大。但是從實驗結(jié)果來看，突發(fā)小流越多，越能體現(xiàn)出FEFS-CBF的優(yōu)勢。

基于以上實驗結(jié)果不難看出:雖然FEFS的誤報率趨近于0，但是漏報率較大。本文算法雖然略有誤報，但由于能提前過濾掉小流，漏報率要顯著低于FEFS，算法的綜合性能優(yōu)于FEFS。原始CBF的漏報率比FEFS低，但是誤報率卻很大，綜合性能遠低于FEFS-CBF。

從所需空間上來看，在CBF算法中，由于每位計數(shù)器都要設(shè)定較大，因此需要很大內(nèi)存空間。在以上3種對比算法中，CBF占用存儲空間最大，F(xiàn)EFS-CBF所需的空間雖然大于FEFS，但在當前實驗環(huán)境中也能完全滿足。

綜合來看，F(xiàn)EFS-CBF的錯誤率(包括誤報率和漏報率)要明顯優(yōu)于以上2種對比算法。

表2 FEFS，CBF，F(xiàn)EFS-CBF算法實驗結(jié)果

6 結(jié)束語

在高速網(wǎng)絡(luò)鏈路流量測量中，完整地存儲每個數(shù)據(jù)包信息十分困難，流量測量也從傳統(tǒng)的數(shù)據(jù)包級測量發(fā)展到數(shù)據(jù)流級別的測量。大流識別作為流量測量的重要分支，應(yīng)用十分廣泛。針對高速網(wǎng)絡(luò)測量中大量小流影響大流準確識別的問題，本文提出了FEFS-CBF算法。使用CBF過濾小流，將流包數(shù)達到過濾閾值的流信息放入LRU中，當LRU滿載時，運用FEFS機制來選取淘汰流信息。本文算法結(jié)合了FEFS算法和CBF算法的優(yōu)勢，對比實驗結(jié)果表明，誤報率、漏報率均相對較低。但由于CBF與LRU會產(chǎn)生誤報和漏報的局限性，因此下一步的研究目標是選擇更為簡潔、準確的過濾結(jié)構(gòu)，并對淘汰流進行重復篩選，進一步減少誤報率和漏報率。

［1］ Yang L，Micahilidis G．Sampled Based Estimation of Network Traffic Flow Characteristics［C］//Proceedings of the 26th IEEE International Conference on Computer Communications．Washington D．C．，USA:IEEE Press，2007:1775-1783．

［2］ 夏靖波，任高明．大流識別方法綜述［J］．控制與決策，2013，28(6):801-807．

［3］ Mori T，Uchida M，Kawahara R．Identifying Elephant Flows Through Periodically Sampled Packets［C］//Proceedings of ACM IMC’04．New York，USA:ACM Press，2004:115-120．

［4］ Estan C，Varghese G．New Directions in Traffic Measurement and Accountinga:Focusing on the Elephants，Ignoring the Mice［J］．ACM Transactions on Computer System，2003，21(3):270-313．

［5］ 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:［s．n．］，2001:361-371．

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

［7］ 王洪波，裴育杰，林 宇，等．基于LRU的大流檢測算法［J］．電子與信息學報，2007，29(10):2487-2492．

［8］ Che L C，Qiu B．Landmark LRU:An Efficient Scheme for the Detection of Elephant Flows at Internet Routers［J］．IEEE Communication Letters，2006，10(7):567-569．

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

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

［11］ 張 震，汪斌強，張風雨，等．基于LRU-BF策略的網(wǎng)絡(luò)流量測量算法［J］．通信學報，2013，34(1):111-120．

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

［13］ Kummar A，Xu J，Wang J，et al．Space-code Bloom Filter for Efficient Per-flow Traffic Measurement［C］//Procee-dings of IEEE INFOCOM’04．Washington D．C．，USA:IEEE Press，2004:1762-1773．

［14］ Sun Y，Zhang Z B，Guo L，et al．An Effective Algorithm forCounting Active Active Flows Based on Loop Filter［C］//Proceedings of International Conference on Networking，Architecture and Storage．Chongqing，China:［s．n．］，2008:104-109．

［15］ 李 臻，楊雅輝，張廣興，等．大業(yè)務(wù)流識別方法研究綜述［J］．計算機應(yīng)用研究，2011，28(1):6-9．