基于LRU
—CBF 的大流識別算法

張淋淋　高仲合

曲阜師范大學(xué)信息科學(xué)與工程學(xué)院

?

基于LRU
—CBF 的大流識別算法

張淋淋高仲合

曲阜師范大學(xué)信息科學(xué)與工程學(xué)院

對網(wǎng)絡(luò)中的大流進(jìn)行提取和分析對于網(wǎng)絡(luò)管理和安全防御具有重要意義。文章通過把最近最久未使用（LRU）策略和計數(shù)型布魯姆過濾器（CBF）兩種結(jié)構(gòu)結(jié)合起來，取其各自的優(yōu)點(diǎn)，提出一種新的大流檢測算法。該算法針對大流檢測漏報率高的缺陷，將“大流過濾”和“大流判斷”分離，提高了算法的準(zhǔn)確性，降低了空間復(fù)雜度。最后通過理論分析和仿真實(shí)驗進(jìn)行了算法的驗證。

最近最久未使用 布魯姆過濾器 流量測量 漏報率

近年來，計算機(jī)網(wǎng)絡(luò)呈現(xiàn)向高速化、大規(guī)模、復(fù)雜化方向發(fā)展的趨勢，其特點(diǎn)就是產(chǎn)生的數(shù)據(jù)量大、數(shù)據(jù)分組到達(dá)頻率高，使得數(shù)據(jù)的處理難度越來越大。因此帶來的問題就是，硬件的處理速度不能滿足實(shí)際網(wǎng)絡(luò)流量測量的需要。因此，如何用有限的硬件資源條件完成高速鏈路下的流量測量成為當(dāng)前研究的熱點(diǎn)問題。在當(dāng)前的網(wǎng)絡(luò)測量中，可以采用不同的測量單位，最通常使用的是以流的方式。所謂流，是指在一段時間內(nèi)，具有一組相同屬性的數(shù)據(jù)分組的集合，一般情況下我們通過5元組（源IP地址、源端口、目的IP地址、目的端口、傳輸層協(xié)議）來定義流。由于互聯(lián)網(wǎng)中IP流長度服從重尾分布，也就是少數(shù)字節(jié)數(shù)較大的流占據(jù)了網(wǎng)絡(luò)的大部分流量，大量字節(jié)數(shù)較小的流分擔(dān)了網(wǎng)絡(luò)的小部分流量。在很多的網(wǎng)絡(luò)應(yīng)用中，我們只需知道大字節(jié)流的信息，即檢測出大流，而不需要關(guān)注到每條流的狀態(tài)?；谶@樣的策略，本文結(jié)合最近最久未使用（LIW）和計數(shù)型布魯姆過濾器（CBF）機(jī)制，使用兩個步驟，LRU負(fù)責(zé)把大流過濾下來，CBF負(fù)責(zé)迸一步對大流進(jìn)行判斷，提出了一種大流識別算法（LRU—CBF， least recent used & Counter Bloom f lter）。此算法結(jié)構(gòu)簡單，能夠精確地將大流量對象提取出來。

1　LRUCBF算法

1.1LRU 思想描述

LRU的基本原理是：建立一個長度固定的LRU緩存，在初始狀態(tài)下，緩存是空的，按順序?qū)⒌竭_(dá)的元素記錄到此緩存中，記錄的原則是最新到達(dá)的放在緩存的頂端，最久未到達(dá)的放在緩存的底部。根據(jù)這一特點(diǎn)，LRU在計算系統(tǒng)中有著廣泛的應(yīng)用，如數(shù)據(jù)庫緩存管理、在線頁面管理以及磁盤緩存管理等領(lǐng)域。由于網(wǎng)絡(luò)中的流服從重尾分布的規(guī)律，而且一般情況下小流的持續(xù)時間短、到達(dá)頻率低，大流持續(xù)時間長、訪問緩存頻繁，所以經(jīng)過一段時間，小流被淘汰，大流被留下。兩種LRU替換方式的情況：1）新報文所

屬的流Fn.1已經(jīng)存在于LRU緩存中，就把該流置于緩存的最頂端，其余流記錄依次向底部移動。2）新報文所屬的流Fn+l不是緩存中已存在的流，緩存不滿時直接添加到緩存頂部，其余流依次向底部移動，緩存已滿時，將流Fn+l置于緩存的最前面，其余流向底部移動，底部的流Fn被淘汰。

1.2Bloom Fil ter

Bloom Filter是由Burton Bloom在1970年提出的，是一種簡潔的二進(jìn)制向量數(shù)據(jù)結(jié)構(gòu)。在查詢元素方面具有很好的空間和時間效率，被應(yīng)用于很多大型系統(tǒng)。BF結(jié)構(gòu)擁有很多顯著的優(yōu)點(diǎn)，空間效率、時間效率都遠(yuǎn)遠(yuǎn)超于一般算法，所需硬件條件不高，使其在很多領(lǐng)域應(yīng)用廣泛。近年來，在網(wǎng)絡(luò)測量方面的應(yīng)用也備受關(guān)注。標(biāo)準(zhǔn)的Bloom Filter的主要組成部分就是一個m位數(shù)組加一組散列函數(shù)。在標(biāo)準(zhǔn)BF中，不同的元素被哈希函數(shù)映射后的位置可能相同，即數(shù)組中的某位可能需要置1多次，但是標(biāo)準(zhǔn)BF的數(shù)組只包含0或l兩種狀態(tài)，因此多次置1的位只有第一次起作用。因此當(dāng)需要刪除元素時，就會出現(xiàn)錯誤。標(biāo)準(zhǔn)的BF不是實(shí)現(xiàn)元素的刪除功能。為了增加刪除元素的功能BF在以后的發(fā)展中出現(xiàn)了許多改進(jìn)，其中計數(shù)型BF（CBF）是最典型的一種。當(dāng)進(jìn)行元素的插入操作時，使用哈希函數(shù)將元素進(jìn)行映射后對應(yīng)的尼個計數(shù)器值均加1；刪除操作時，映射得到的七個計數(shù)器值減1；查詢操作時，檢查映射得到的k個計數(shù)器的值，若都大于/等于1則判斷為屬于該集合，只要有等于0的計數(shù)器則判斷為不屬于該集合。

本文提出的LRUCBF算法的核心思想是將CBF和LRU兩種結(jié)構(gòu)結(jié)合起來，使用兩級處理機(jī)制，用CBF結(jié)構(gòu)來判斷網(wǎng)絡(luò)中是否存在大流；用LRU來進(jìn)一步過濾大流，達(dá)到更高的準(zhǔn)確性，使“大流判斷”和“大流過濾”兩個過程分離開來。之所以選用這樣的機(jī)制，有兩個方面的優(yōu)點(diǎn)，先用CBF將大流判斷出來后放到緩存中，這時LRu進(jìn)一步確保這些大流不丟失；另一方面，CBF的預(yù)先判斷使得LRU不用對所有的數(shù)據(jù)包進(jìn)行過濾，用兩者的互相幫助來提高算法的執(zhí)行效率，提高準(zhǔn)確性。LRUCBF算法的基本過程：某一新的報文來到，提取出流標(biāo)識，利用哈希函數(shù)的值判斷此流是不是大流。如果這條新流是已經(jīng)識別出來的

大流，就將CBF相應(yīng)的計數(shù)器加1，如果這條新流不是已經(jīng)識別出來的大流，就將這條新流放到LRU鏈表的最頂部，然后把LRU鏈表最底部的流淘汰掉。

2　算法的理論分析

2.1準(zhǔn)確性

本文提出的LRUCBF算法由于采用了LRU策略和CBF結(jié)構(gòu)，因此，此算法的錯誤概率就從這兩部分中產(chǎn)生。在LRU中，鏈表中的大流可能被淘汰出去，而CBF中，由于本身存在的誤判會將接收到的小流當(dāng)作大流提取到LRU鏈表中，增大LRU的計算壓力。因此本算法的錯誤概率包括LRU的漏判概率PLRU幣［1CBF的誤判概率RBF。

2.2空間復(fù)雜度

在2.1中，隨著m、n、k的增大，準(zhǔn)確性會迅速提高，隨之帶來的就是空間的增加。所以CBF中空間復(fù)雜度就是哈希函數(shù)的個數(shù)，以及計數(shù)器的個數(shù)。

3　結(jié)語

本文詳細(xì)闡述了LRU策略和CBF結(jié)構(gòu)的優(yōu)缺點(diǎn)，結(jié)合兩者各自的優(yōu)點(diǎn)，避開各自的缺點(diǎn)，提出一種新的大流檢測算法?？梢园褜ⅰ按罅鬟^濾”和“大流判斷”分離，這樣一方面能夠減少測量的誤差，提高算法的準(zhǔn)確性，另一方面，使用的數(shù)據(jù)結(jié)構(gòu)較為簡單，工作過程也不復(fù)雜，降低了空間復(fù)雜度。經(jīng)過實(shí)驗結(jié)果的分析驗證，基于LRU.CBF的大流檢測算法具有很高的準(zhǔn)確性，能夠很好地應(yīng)用到實(shí)踐中。

［1］劉慶生.反病毒研究與檢測技術(shù)一一試探式掃描技術(shù)［J］.個人電腦，2003（2）：134-135.

［2］李景濤，荊一楠，肖曉春，等.基于相似度加權(quán)推薦的P2P環(huán)境下的信任模型［J］。軟件學(xué)報，2007，18（1）：157—167.

［3］竇文.構(gòu)造基于推薦的Peer-to.Peer環(huán)境下的Trust模型［J］.軟件學(xué)報，2004，15（4）：57卜583

［4］劉文芬.基于信任域的分布式動態(tài)信任管理模型［J］.四川大學(xué)學(xué)報，2014，46（4）：61—66.

［5］高磊，郭玉翠.基于信任迭代的P2P網(wǎng)絡(luò)信任管理模型［J］.計算機(jī)工程，2012，38（19）：92—95.