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

張淋淋　高仲合

曲阜師范大學信息科學與工程學院

?

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

張淋淋高仲合

曲阜師范大學信息科學與工程學院

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

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

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

1　LRUCBF算法

1.1LRU 思想描述

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

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

1.2Bloom Fil ter

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

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

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

2　算法的理論分析

2.1準確性

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

2.2空間復雜度

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

3　結語

本文詳細闡述了LRU策略和CBF結構的優缺點，結合兩者各自的優點，避開各自的缺點，提出一種新的大流檢測算法。可以把將“大流過濾”和“大流判斷”分離，這樣一方面能夠減少測量的誤差，提高算法的準確性，另一方面，使用的數據結構較為簡單，工作過程也不復雜，降低了空間復雜度。經過實驗結果的分析驗證，基于LRU.CBF的大流檢測算法具有很高的準確性，能夠很好地應用到實踐中。

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

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

［3］竇文.構造基于推薦的Peer-to.Peer環境下的Trust模型［J］.軟件學報，2004，15（4）：57卜583

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

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