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

劉曉陸，劉 淵，王春龍

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

1 概述

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

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

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

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

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

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

2 相關(guān)算法

2．1 LRU基本原理及拓展

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

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

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

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

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

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

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

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

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

3 基于FEFS與CBF的大流識(shí)別算法

3．1 大流定義

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

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

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

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

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

3．3 算法流程

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

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

算法1Search

算法2InsertLRU

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

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

4 理論結(jié)果分析

4．1 誤報(bào)率

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

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

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

4．2 漏報(bào)率

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

4．3 時(shí)間復(fù)雜度

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

4．4 空間復(fù)雜度

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

5 實(shí)驗(yàn)結(jié)果分析

在實(shí)驗(yàn)室有限的硬件環(huán)境中，使用2組數(shù)據(jù)集進(jìn)行實(shí)際流量數(shù)據(jù)仿真，測(cè)試本文算法性能。實(shí)驗(yàn)中所使用的2個(gè)數(shù)據(jù)集分別為:MIT林肯實(shí)驗(yàn)室入侵檢測(cè)數(shù)據(jù)集中較大的一個(gè)文件——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ù)集的詳細(xì)介紹如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集信息

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

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

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

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

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

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

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

6 結(jié)束語

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

［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］ 夏靖波，任高明．大流識(shí)別方法綜述［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］ 王風(fēng)宇，云曉春，王曉峰，等．高速網(wǎng)絡(luò)監(jiān)控中大流對(duì)象的提?。跩］．軟件學(xué)報(bào)，2007，18(12):3060-3070．

［7］ 王洪波，裴育杰，林 宇，等．基于LRU的大流檢測(cè)算法［J］．電子與信息學(xué)報(bào)，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］ 王風(fēng)宇，郭山清，李亮雄，等．一種高效率的大流提取方法［J］．計(jì)算機(jī)研究與發(fā)展，2013，50(4):731-740．

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

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

［12］ 謝冬青，周再紅，駱嘉偉．基于LRU和SCBF的大象流提取及其在DDoS防御中的應(yīng)用［J］．計(jì)算機(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ù)流識(shí)別方法研究綜述［J］．計(jì)算機(jī)應(yīng)用研究，2011，28(1):6-9．