劉元珍

0 引言

高速網(wǎng)絡(luò)因其速度快、數(shù)據(jù)量巨大而使得對網(wǎng)絡(luò)流量的測量非常困難，在高速網(wǎng)絡(luò)流量測量領(lǐng)域，采用各種算法針對不同應(yīng)用的研究被廣泛關(guān)注[1-4]。

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

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

1 長流及多級CBF

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

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

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

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

2 長流識別算法

長流識別首先在測量時間段內(nèi)隨機(jī)抽取 m個報文，然后通過多級CBF來識別報文數(shù)達(dá)到閾值的長流并使用長流信息表來維護(hù)這些長流的信息，多級CBF結(jié)構(gòu)如圖1所示：

圖1 多級CBF結(jié)構(gòu)

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

算法的具體描述如下：

3 性能的分析

3.1 誤報率及空間復(fù)雜度

通過一些具體數(shù)據(jù)對多級 CBF（MSCBF）的誤報率及空間復(fù)雜度進(jìn)行分析。

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

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

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

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

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

3.2 誤差分析

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

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

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

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

4 實驗分析

利用互聯(lián)網(wǎng)公開提供的實際數(shù)據(jù)進(jìn)行實驗分析，其中，報文數(shù)超過1000的長流比例為0.17%。多級CBF的級數(shù)與其誤報率最大值的關(guān)系如圖2所示：

圖2 多級CBF級數(shù)與誤報率最大值關(guān)系

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

5 總結(jié)

本文提出了一種基于多級CBF的長流識別算法，用多級 CBF結(jié)構(gòu)來識別到達(dá)閾值的長流，可以有效的降低長流識別所需的存儲空間，提高了長流識別的準(zhǔn)確率，并可根據(jù)系統(tǒng)負(fù)載能力調(diào)整抽樣率以滿足更高的精度要求。

[1]周愛平,程光,郭曉軍.高速網(wǎng)絡(luò)流量測量方法[J].軟件學(xué)報,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]程光,唐永寧.基于近似方法的抽樣報文流數(shù)估計算法[J].軟件學(xué)報,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].軟件學(xué)報, 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.