基于抽樣和兩級CBF的長流識別算法

翟金鳳， 孫立博， 魯 凱， 林學(xué)勇， 秦文虎

(1. 東南大學(xué)儀器科學(xué)與工程學(xué)院，江蘇 南京 210096; 2. 南京市計(jì)量監(jiān)督檢測院，江蘇 南京 210049)

0 引 言

諸多研究表明，網(wǎng)絡(luò)流具有顯著的重尾分布特征，數(shù)量較少的長流占據(jù)了網(wǎng)絡(luò)流量的大部分[5]。因此掌握長流信息就可以對鏈路上經(jīng)過的所有網(wǎng)絡(luò)流有個(gè)整體的認(rèn)識，便于對網(wǎng)絡(luò)流量進(jìn)行管理和監(jiān)測分析，對網(wǎng)絡(luò)流量計(jì)費(fèi)、安全檢測、流量調(diào)控等工程應(yīng)用起著重大作用，并且對長流進(jìn)行識別可以有效縮減處理和存儲(chǔ)的數(shù)據(jù)量，提高系統(tǒng)處理效率和資源利用率。

目前長流識別算法主要使用抽樣技術(shù)、哈希技術(shù)以及Bloom Filter技術(shù)。單獨(dú)使用抽樣技術(shù)需要對流信息進(jìn)行維護(hù)，同時(shí)會(huì)產(chǎn)生較大的計(jì)算開銷；而單獨(dú)使用哈希技術(shù)或Bloom Filter技術(shù)則會(huì)增大哈希沖突，影響測量精度[6]。因此可以將抽樣技術(shù)和哈希技術(shù)或者Bloom Filter技術(shù)相結(jié)合以實(shí)現(xiàn)更高效的長流識別。景泉等[7]提出了一種將分層隨機(jī)抽樣與哈希技術(shù)相結(jié)合的長流識別算法，能夠較準(zhǔn)確地識別出長流，但對流長度的測量存在一定誤差，且哈希技術(shù)仍需對流信息進(jìn)行維護(hù)，浪費(fèi)存儲(chǔ)資源。吳燁等[8]提出利用雙重計(jì)數(shù)型布隆過濾器（counting bloom filter,CBF）對長流進(jìn)行識別的算法，并進(jìn)行了一定的理論分析，表示算法可以適應(yīng)于大規(guī)模網(wǎng)絡(luò)的流量監(jiān)測，但對每個(gè)報(bào)文進(jìn)行長流過濾并不能有效節(jié)約空間和時(shí)間資源。劉元珍[9]則先對報(bào)文進(jìn)行隨機(jī)抽樣，再通過多級CBF過濾出達(dá)到閾值的長流，一定程度上可以提高長流識別的準(zhǔn)確率，但同時(shí)也犧牲了一定的時(shí)間和存儲(chǔ)資源。

本文提出一種基于抽樣和兩級CBF的長流識別算法，將長流過濾和流長計(jì)數(shù)分開處理。首先對觀測時(shí)間內(nèi)鏈路上通過的報(bào)文進(jìn)行系統(tǒng)抽樣。繼而利用兩級CBF對被抽樣報(bào)文進(jìn)行處理，第一級CBF對長流進(jìn)行過濾，識別出報(bào)文數(shù)達(dá)到閾值的長流；第二級則對識別出的長流所含報(bào)文數(shù)進(jìn)行統(tǒng)計(jì)。最后利用第二級CBF對所有未被抽樣的報(bào)文進(jìn)行查詢，若屬于已識別出的長流，則對流長繼續(xù)計(jì)數(shù)。

1 抽樣技術(shù)和Bloom Filter技術(shù)介紹

1.1 報(bào)文抽樣技術(shù)

在網(wǎng)絡(luò)測量中，抽樣是指以某種方式從網(wǎng)絡(luò)中提取一定數(shù)目的報(bào)文或流數(shù)據(jù)，通過樣本盡可能準(zhǔn)確描述總體數(shù)據(jù)的參數(shù)，以節(jié)約系統(tǒng)空間和時(shí)間資源，因而被廣泛應(yīng)用于高速網(wǎng)絡(luò)流量測量領(lǐng)域。使用抽樣進(jìn)行網(wǎng)絡(luò)流量測量時(shí)，必須考慮如何從感興趣的數(shù)據(jù)總體中提取具有充分代表性的樣本對象，以確保所提取的樣本與總體特征相近[10]。

典型的報(bào)文抽樣技術(shù)主要包括系統(tǒng)抽樣、隨機(jī)抽樣和分層抽樣3種[11]。系統(tǒng)抽樣是在總體中按固定的間隔進(jìn)行樣本的選取，如圖1（a）所示[12]。其主要優(yōu)點(diǎn)是易于理解、簡便易行，適用于總體容量很大的情況；缺點(diǎn)則是易存在同步問題，引起測量失真。隨機(jī)抽樣即嚴(yán)格按照隨機(jī)原則從觀察對象總體中提取一定數(shù)量的樣本，如圖1（b）所示。該方法操作最為簡便迅速，樣本間相互獨(dú)立性高，但樣本分配較分散，代表性恐有不足。分層抽樣先根據(jù)額外信息將觀察對象總體分成不同的層，然后分別在各層中以獨(dú)立、隨機(jī)的方式進(jìn)行樣本對象的提取，如圖1（c）所示[13]。分層抽樣樣本和總體結(jié)構(gòu)相似度高，代表性強(qiáng)，但層界的設(shè)定會(huì)增加樣本選擇的成本和復(fù)雜性，同時(shí)怎樣選取分層特征或規(guī)則也是個(gè)難點(diǎn)。

圖1 3種抽樣方法

本文綜合考慮樣本對總體的代表性以及計(jì)算和時(shí)間的復(fù)雜度后，選用系統(tǒng)抽樣作為長流識別過程中的抽樣方式。

1.2 Bloom Filter技術(shù)

Bloom Filter是一種基于哈希的二進(jìn)制向量數(shù)據(jù)結(jié)構(gòu)[14]，其利用一個(gè)位向量簡潔地表示一個(gè)包含大量元素的集合，同時(shí)實(shí)現(xiàn)快速查詢某一元素，并檢測該元素是否屬于某一集合[15-16]。元素插入和查詢的時(shí)間都是常數(shù)級，可以顯著節(jié)約空間和時(shí)間資源，缺陷是存在一定的誤判率和不支持元素刪除操作。

初始化Bloom Filter時(shí)，將位向量的每一位均設(shè)置為0，選取k個(gè)相互獨(dú)立的哈希函數(shù)h1,h2,···,hk[17]。插入元素時(shí)，計(jì)算元素的k個(gè)哈希值，將元素映射到位向量中相應(yīng)的k個(gè)位置，設(shè)置這k個(gè)位置為1，其余位置不做改變。查詢元素時(shí)，若元素的k個(gè)哈希值映射到位向量中的位置均為1，則判定該元素屬于Bloom Filter所表示的集合。但由于映射過程中存在某一位被重復(fù)置1以及哈希沖突的可能性，進(jìn)而會(huì)導(dǎo)致某個(gè)不屬于集合的元素被判定為屬于集合，這樣的誤判概率定義為“誤判率”[18]。

當(dāng)級配碎石拌和完畢后應(yīng)及時(shí)采用大噸位自卸式卡車將其運(yùn)輸至施工現(xiàn)場，運(yùn)輸過程中車輛的行駛速度不宜過快，避免混合料出現(xiàn)較為嚴(yán)重的離析現(xiàn)象，另外，運(yùn)輸車的車廂上方宜覆蓋一層帆布，以減小級配碎石混合料的水分散失。

標(biāo)準(zhǔn)Bloom Filter不支持元素的刪除操作，CBF[19]作為Bloom Filter典型的改進(jìn)結(jié)構(gòu)之一，將Bloom Filter的每一位擴(kuò)展為一個(gè)counter計(jì)數(shù)器，增加元素刪除功能。如圖2所示，插入元素時(shí)，將對應(yīng)位置的k個(gè)計(jì)數(shù)器值加1；刪除元素時(shí)則將對應(yīng)的k個(gè)計(jì)數(shù)器值減1；查詢元素時(shí)，若元素映射到對應(yīng)位置的k個(gè)計(jì)數(shù)器值都不為0，則判定為屬于集合。與Bloom Filter一樣，CBF在判斷元素是否屬于集合時(shí)仍存在一定的誤判率。

2 長流識別算法

設(shè)觀測時(shí)間內(nèi)鏈路上通過的報(bào)文總數(shù)為N，若將占據(jù)報(bào)文總數(shù)m%以上的流定義為長流，則閾值設(shè)置為T=N·m%，長流即為觀測時(shí)間內(nèi)所含報(bào)文數(shù)超過閾值T的流。長流的定義是可調(diào)的，通過改變m的值進(jìn)而滿足各種測量應(yīng)用需求。

圖2 CBF原理圖

由網(wǎng)絡(luò)流顯著的重尾特性可見，如果對鏈路上通過的總報(bào)文按某種抽樣頻率進(jìn)行抽樣，那么長流中包含的大量報(bào)文被抽中的可能性要比短流中的少量報(bào)文大的多，因此可以先對總報(bào)文實(shí)施抽樣，再利用抽樣后的報(bào)文進(jìn)行長流識別。這樣既能大大縮減處理的數(shù)據(jù)量，有效節(jié)省時(shí)間資源，又能保證長流識別的準(zhǔn)確性。如圖3所示，基于抽樣和兩級CBF的長流識別算法的實(shí)現(xiàn)過程為：

圖3 算法流程示意圖

2）設(shè)定長流識別的閾值T1，同時(shí)合理配置兩級CBF的結(jié)構(gòu)參數(shù)。由于報(bào)文的抽樣頻率為p=1/n，根據(jù)簡單線性關(guān)系，使用抽樣報(bào)文進(jìn)行長流識別的閾值應(yīng)設(shè)置為T1=T/n。兩級CBF選用相同的k個(gè)沖突小的哈希函數(shù)h(1),h(2),···,h(k)；第一級CBF結(jié)構(gòu)中counter數(shù)組的長度m1設(shè)置為大于抽樣報(bào)文總數(shù)N/n的2的冪次方，每個(gè)counter分配的位數(shù)b1需滿足條件2b1>T1，且需適當(dāng)?shù)囟喾峙鋷孜灰员苊庥?jì)數(shù)器溢出；第二級CBF結(jié)構(gòu)中counter數(shù)組的長度m2設(shè)置為大于報(bào)文總數(shù)N的2的冪次方，每個(gè)counter分配的位數(shù)b2需滿足條件也需適當(dāng)?shù)囟喾峙鋷孜灰员苊庥?jì)數(shù)器溢出。

3）對于每個(gè)被抽樣的報(bào)文，先通過k個(gè)哈希函數(shù)將其映射到第二級CBF的相應(yīng)位置。若相應(yīng)位置的k個(gè)計(jì)數(shù)器值均不為0，則判定該報(bào)文屬于已識別出的長流，將其插入第二級CBF中，即將這k個(gè)計(jì)數(shù)器值分別加1。

4）若相應(yīng)位置的k個(gè)計(jì)數(shù)器值中有任意一個(gè)為0，則判定該報(bào)文不屬于已識別出的長流，再通過k個(gè)哈希函數(shù)將其映射到第一級CBF中，求取相應(yīng)位置的k個(gè)計(jì)數(shù)器的最小值；若這k個(gè)計(jì)數(shù)器的最小值等于閾值T1，則判定其所屬流為長流，記錄下該報(bào)文的流標(biāo)識，將這k個(gè)計(jì)數(shù)器值分別減去閾值T1，并將其映射到第二級CBF中，設(shè)置相應(yīng)位置的k個(gè)計(jì)數(shù)器值為T1+1。

5）若這k個(gè)計(jì)數(shù)器的最小值不等于閾值T1，則判定其所屬流不為長流，將其插入第一級CBF中，即將這k個(gè)計(jì)數(shù)器值分別加1。

6）重復(fù)步驟3）～5）完成對所有被抽樣報(bào)文的處理后，通過第二級CBF對所有未被抽樣的報(bào)文進(jìn)行查詢。若報(bào)文映射到第二級CBF的相應(yīng)位置的k個(gè)計(jì)數(shù)器值均不為0，則判定該報(bào)文屬于已識別出的長流，將其插入第二級CBF中，即將相應(yīng)位置的k個(gè)計(jì)數(shù)器值分別加1，否則不做任何處理。

由上述算法的具體實(shí)現(xiàn)過程可以看出，對所有報(bào)文處理完后，步驟4）中記錄的流標(biāo)識即為該算法識別出的長流的流標(biāo)識；將記錄的流標(biāo)識映射到第二級CBF中，相應(yīng)位置的計(jì)數(shù)器的最小值即為該算法測量出的長流的流長度。

3 實(shí)驗(yàn)分析

實(shí)驗(yàn)選取互聯(lián)網(wǎng)數(shù)據(jù)分析合作組織（CAIDA）公開提供的2016年3月17日在Chicago采集的實(shí)際Trace數(shù)據(jù)進(jìn)行仿真分析。實(shí)驗(yàn)平臺為Visual Studio 2013，原始Trace中共有1 759 536 911個(gè)報(bào)文，本文截取前5 000 000個(gè)報(bào)文數(shù)據(jù)進(jìn)行實(shí)驗(yàn)分析，閾值設(shè)置為21 000，報(bào)文數(shù)超過閾值的真實(shí)長流共有3個(gè)，具體長流信息如表1所示。實(shí)驗(yàn)中的流是指具有相同的源和目的IP地址的報(bào)文集合，具體的流標(biāo)識的定義可以根據(jù)網(wǎng)絡(luò)實(shí)際應(yīng)用需求決定。

表1 真實(shí)長流信息

分別以1/10、1/50、1/100的抽樣頻率對總報(bào)文進(jìn)行系統(tǒng)抽樣，兩級CBF的哈希函數(shù)均選用SHA1算法。分別取哈希函數(shù)個(gè)數(shù)為1，2，3進(jìn)行長流識別，當(dāng)哈希函數(shù)個(gè)數(shù)大于1時(shí)，對報(bào)文信息進(jìn)行復(fù)制作為新的SHA1輸入以生成新的哈希值。當(dāng)抽樣頻率設(shè)為1/100，哈希函數(shù)個(gè)數(shù)設(shè)為1時(shí)，算法仿真結(jié)果如表2所示，可以看出由本算法識別出的長流信息與真實(shí)的長流信息完全相同。

表2 算法識別出的長流及流長度

使用不同的抽樣頻率和哈希函數(shù)個(gè)數(shù)進(jìn)行仿真實(shí)驗(yàn)后發(fā)現(xiàn)：

2）當(dāng)系統(tǒng)抽樣的抽樣頻率分別取1/10、1/50、1/100時(shí)，該算法均可以零誤差地識別出各長流及其流長度。由此可以看出，長流識別中利用系統(tǒng)抽樣可以提取出具有充分代表性的報(bào)文樣本，且操作簡單，時(shí)間復(fù)雜度低。同時(shí)，抽樣頻率越小，算法用時(shí)越短，識別速度越快，因此在報(bào)文總數(shù)較大時(shí)，可以適當(dāng)降低抽樣頻率以提高算法的處理速度。

4 結(jié)束語

本文提出一種基于抽樣和兩級CBF的長流識別算法，對3種典型的報(bào)文抽樣技術(shù)進(jìn)行性能比較分析后，選取系統(tǒng)抽樣對總報(bào)文進(jìn)行抽樣；繼而利用兩級CBF對被抽樣報(bào)文分別進(jìn)行長流過濾和流長計(jì)數(shù)處理，最后再利用第二級CBF對所有未被抽樣的報(bào)文進(jìn)行查詢，統(tǒng)計(jì)出長流所含的總報(bào)文數(shù)。通過仿真實(shí)驗(yàn)驗(yàn)證本文算法能在有效節(jié)約空間和時(shí)間資源的基礎(chǔ)上，既實(shí)現(xiàn)對長流的準(zhǔn)確識別，又實(shí)現(xiàn)對原始流長度的零誤差的高精度測量。同時(shí)，算法還具有可擴(kuò)展性，一定誤差范圍內(nèi)可以選用相對簡單的哈希算法，或者使用硬件實(shí)現(xiàn)，以進(jìn)一步提高算法的處理效率，滿足當(dāng)前高速網(wǎng)絡(luò)發(fā)展對網(wǎng)絡(luò)流量監(jiān)測的需求。