基于多級CBF的長流識別

劉元珍

0 引言

高速網絡因其速度快、數據量巨大而使得對網絡流量的測量非常困難，在高速網絡流量測量領域，采用各種算法針對不同應用的研究被廣泛關注[1-4]。

在互聯網中，由于少量的長流占據了網絡流量的大部分，因此對長流的識別顯得尤其重要，長流識別也成為研究熱點。吳樺等[6]提出了基于雙重Counter Bloom Filter的長流識別算法，使用兩層Counter Bloom Filter結構將長流過濾和長流存在分開處理。YuZhang[5]提出Weighted Lossy Counting（WLC）方法，以常量時間（O(1)）識別出長流，并以大的存儲空間獲取高的精確率。

本文提出了基于多級 CBF的長流識別算法，首先對組成網絡流的報文進行抽樣，然后通過哈希映射查找被抽樣的報文所屬的流是否在長流信息表中，若存在則更新流信息表，若不存在則將抽樣報文用多級CBF（Multistage Counting Bloom Filters，MSCBF）進行過濾，對各級CBF均達到閾值的抽樣流，創建長流記錄來維護該長流的信息，并將該流對應的各級CBF計數器減去閾值。多級CBF極大的降低了哈希沖突引起的誤報率，而由于采用抽樣和只對達到閾值的流進行長流信息維護，又有效的控制了資源損耗。第一節描述了長流及多級CBF，第二節描述了具體的長流識別算法，第三節對算法進行性能分析，第四節進行實驗分析，最后一節總結全文。

1 長流及多級CBF

在網絡中，流是指具有相同屬性的報文的集合，屬性一般采用源/宿IP地址、源/目的端口號、協議類型等。長流是指占據了大部分的網絡通信量的流，但這部分流在數量上卻相對較少。長流也可被定義為包含的報文數（字節數）超出了某個預先定義好的閾值的流。

Bloom Filter是一種哈希結構，支持集合元素查詢，它的核心算法是一個V向量和一組哈希函數，使用長為m的位串V表達n個元素的集合 S= {s1,s2...sn}。使用k個哈希函數 hi，對于集合每個元素s，向量位串中對應于 h1( s) , h2(s ),...,hk(s )的位置被設置成1，否則為0。但在該向量位串中，存在某個位可能被多次置1，因此會導致某個元素不屬于集合而被指稱為屬于集合，其概率誤差稱“p誤報率”。經過一系列計算可得當 k=(m / n )ln2時，誤報率err取得最小值 0.6185m/n。

標準Bloom Filter支持集合成員的插入和查詢，但并不支持刪除操(作)。計數型Bloom Filter即Counting Bloom Filter，以計數器 c i代替BF中的位，對于每個元素s，位串中對應的計數器值都增加1，刪除該元素時則將對應的計數器值都減去1，從而在刪除元素時不會修改其它元素的置位。

本文中的多級CBF（Multistage Counting Bloom Filters，MSCBF）使用并行的多級CBF，各級CBF采用相異的哈希函數組，雖然BF固有的誤報率存在，但相異的哈希函數組在多級CBF匹配時可以極大減小誤報率。

2 長流識別算法

長流識別首先在測量時間段內隨機抽取 m個報文，然后通過多級CBF來識別報文數達到閾值的長流并使用長流信息表來維護這些長流的信息，多級CBF結構如圖1所示：

圖1 多級CBF結構

當一個報文被抽取時其所在的流也即被抽樣，首先將抽取的報文通過經過一系列哈希映射得到哈希值作為地址指針，查找長流信息表中是否存在該流信息。若已存在，則更新該流信息。若不存在則將該報文通過多級CBF進行過濾，在每級CBF中，經過一系列哈希計算后，將對應的計數器加1。對各級CBF均達到閾值即 c( i)＞ =Tthd的抽樣流，在流信息表中創建并維護該長流的信息，為了防止CBF溢出，創建了長流信息后，將該流對應的各級CBF計數器減去閾值。

算法的具體描述如下：

3 性能的分析

3.1 誤報率及空間復雜度

通過一些具體數據對多級 CBF（MSCBF）的誤報率及空間復雜度進行分析。

假設一個寬帶為100MB/s的鏈路，有100000個活動的流，將閾值T定義為每秒流量大于鏈路傳輸容量的1%，即1MB。假設多級CBF中每級CBF有1000個計數器，那么一個不大于100KB的流通過MSCBF的可能性有多大呢？在一級CBF的情況下，這個流要通過，則其它的流必須要至少貢獻 1M-100K=900KB（為了便于計算，按照1MB=1000KB計算）。在 1000個計數器中，最多有 99900/900=111個這樣的計數器，因此，這個流能夠通過一級CBF的概率為111/1000=11.1%。對于4級相互獨立的CBF，一個不大于 100KB的流能夠通過所有 4級 CBF的概率為(11.1%)4≈1.52×10-4。

因此，小于等于100KB的流能通過MSCBF被識別為長流的流數量大概為100000×(11.1%)4≈1.52×10-4＜16。 而在100KB/S鏈路情況下，大于100KB的流最多有999個，按照閾值T=1M的標準，這些流并不一定能夠通過MSCBF。即使這些流全部通過，那么所有需要放入長流信息表的流的個數為：999+16=1015。所有通過MSCBF的流將被放入長流信息表中，根據以上分析，系統只需要為這些流分配1015個長流記錄空間。

因此，為了處理100000個流，只需要4級CBF分配大約4000個計數器（每級1000個計數器）和大約1015個長流記錄空間。

假設C為帶寬，即整個測量時間段內的字節數；s為流的大?。▎挝籅yte）；T為判斷長流的閾值（單位Byte），b為一級CBF中的計數器個數，d為CBF的級數；n為當前活動流的個數。假設各級 CBF使用的哈希函數都是相異獨立的，則一個大小s且s＜(T - C/ b)的流通過MSCBF的概率為ps，且有公式（1）：

若給定概率ps的要求，則可根據上式計算過 MSCBF級數d的大小。由于采用了多級CBF，成指數級得降低了單級CBF的誤報率。

3.2 誤差分析

基于多級CBF的算法主要誤差來源自以下幾個方面：抽樣的誤差、判斷報文是否屬于已知長流時哈希映射到長流信息表時產生的哈希沖突誤差和多級CBF的誤差。

抽樣會帶來不可避免的統計誤差，根據抽樣數據估計原始數據時，簡單的可使用比例估計法，也可以使用復雜度高和更接近的 EM 算法，甚至在系統負載允許的情況下采用全流量測量，完全避免由抽樣帶來的誤差。

判斷報文是否屬于已知長流時哈希映射到長流信息表時會產生哈希沖突而導致更新流信息的誤差，但由于此時修改的流信息主要是報文數，對流信息的影響也主要是報文的數目即流長度，采用合理的哈希算法可以降低這一沖突。文獻[5]中使用CBF稱作Longflow_CBF來進行哈希運算，由于只需要進行查詢操作，可使用標準BF，比CBF更節約空間，通過調整哈希函數和BF位串的長度來降低BF和CBF本身都固有的誤報率，從而減小誤差。

多級CBF結構的誤差。對于屬于某一長流的報文數目累計一定能達到閾值，因此也一定可以被識別，長流漏報率（false negative error）不存在，但存在誤報率，即不是長流的流由于多級CBF的哈希累加可能被判定為長流。單級CBF的誤報率與計數器的個數、不屬于已知長流的報文集合數及哈希函數個數有關，但由于判斷出某流是長流后，即將該流對應的計數器減去閾值，將流移到已知長流信息表，使集合樣本減少，從而減小誤報率。

4 實驗分析

利用互聯網公開提供的實際數據進行實驗分析，其中，報文數超過1000的長流比例為0.17%。多級CBF的級數與其誤報率最大值的關系如圖2所示：

圖2 多級CBF級數與誤報率最大值關系

由于在子測量段結束時清空CBF及識別出長流后即將CBF計數器減去閾值，都會使多級CBF的實際誤報率遠小于誤報率的最大值。當級數為1時，多級CBF退化成單級CBF。

5 總結

本文提出了一種基于多級CBF的長流識別算法，用多級 CBF結構來識別到達閾值的長流，可以有效的降低長流識別所需的存儲空間，提高了長流識別的準確率，并可根據系統負載能力調整抽樣率以滿足更高的精度要求。

[1]周愛平,程光,郭曉軍.高速網絡流量測量方法[J].軟件學報,2014.25(1):135-153.

[2]Sanjuàs-Cuxart J, Barlet-Ros P, Duffield N, Kompella R.Cuckoo sampling: Robust collection of flow aggregates under a fixed memory budget[C].In: Proc.of the 31st Annual IEEE Int’l Conf.on Computer Communications(Mini-Conf.).Orlando: IEEE, 2012.2751-2755.

[3]程光,唐永寧.基于近似方法的抽樣報文流數估計算法[J].軟件學報,2013,24(2):255-265.

[4]Hu CC, Liu B, Wang S, Tian J, Cheng Y, Chen Y.ANLS:Adaptive non-linear sampling method for accurate flow size measurement.IEEE Trans.on Communications[J],2012,60(3):789-798..

[5]吳樺,龔儉,楊望.一種基于雙重Counter Bloom Filter的長流識別算法[J].軟件學報, 2010,21(5):1115-1126.

[6]Zhang Y, Fang BX, Zhang YZ.Identifying heavy hitters in high-speed network monitoring.SCIENTIA SINICA Informationis[J].2010,53(3):659-676.