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

翟金鳳， 孫立博， 魯 凱， 林學勇， 秦文虎

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

0 引 言

諸多研究表明，網絡流具有顯著的重尾分布特征，數量較少的長流占據了網絡流量的大部分[5]。因此掌握長流信息就可以對鏈路上經過的所有網絡流有個整體的認識，便于對網絡流量進行管理和監測分析，對網絡流量計費、安全檢測、流量調控等工程應用起著重大作用，并且對長流進行識別可以有效縮減處理和存儲的數據量，提高系統處理效率和資源利用率。

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

本文提出一種基于抽樣和兩級CBF的長流識別算法，將長流過濾和流長計數分開處理。首先對觀測時間內鏈路上通過的報文進行系統抽樣。繼而利用兩級CBF對被抽樣報文進行處理，第一級CBF對長流進行過濾，識別出報文數達到閾值的長流；第二級則對識別出的長流所含報文數進行統計。最后利用第二級CBF對所有未被抽樣的報文進行查詢，若屬于已識別出的長流，則對流長繼續計數。

1 抽樣技術和Bloom Filter技術介紹

1.1 報文抽樣技術

在網絡測量中，抽樣是指以某種方式從網絡中提取一定數目的報文或流數據，通過樣本盡可能準確描述總體數據的參數，以節約系統空間和時間資源，因而被廣泛應用于高速網絡流量測量領域。使用抽樣進行網絡流量測量時，必須考慮如何從感興趣的數據總體中提取具有充分代表性的樣本對象，以確保所提取的樣本與總體特征相近[10]。

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

圖1 3種抽樣方法

本文綜合考慮樣本對總體的代表性以及計算和時間的復雜度后，選用系統抽樣作為長流識別過程中的抽樣方式。

1.2 Bloom Filter技術

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

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

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

標準Bloom Filter不支持元素的刪除操作，CBF[19]作為Bloom Filter典型的改進結構之一，將Bloom Filter的每一位擴展為一個counter計數器，增加元素刪除功能。如圖2所示，插入元素時，將對應位置的k個計數器值加1；刪除元素時則將對應的k個計數器值減1；查詢元素時，若元素映射到對應位置的k個計數器值都不為0，則判定為屬于集合。與Bloom Filter一樣，CBF在判斷元素是否屬于集合時仍存在一定的誤判率。

2 長流識別算法

設觀測時間內鏈路上通過的報文總數為N，若將占據報文總數m%以上的流定義為長流，則閾值設置為T=N·m%，長流即為觀測時間內所含報文數超過閾值T的流。長流的定義是可調的，通過改變m的值進而滿足各種測量應用需求。

圖2 CBF原理圖

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

圖3 算法流程示意圖

2）設定長流識別的閾值T1，同時合理配置兩級CBF的結構參數。由于報文的抽樣頻率為p=1/n，根據簡單線性關系，使用抽樣報文進行長流識別的閾值應設置為T1=T/n。兩級CBF選用相同的k個沖突小的哈希函數h(1),h(2),···,h(k)；第一級CBF結構中counter數組的長度m1設置為大于抽樣報文總數N/n的2的冪次方，每個counter分配的位數b1需滿足條件2b1>T1，且需適當地多分配幾位以避免計數器溢出；第二級CBF結構中counter數組的長度m2設置為大于報文總數N的2的冪次方，每個counter分配的位數b2需滿足條件也需適當地多分配幾位以避免計數器溢出。

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

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

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

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

由上述算法的具體實現過程可以看出，對所有報文處理完后，步驟4）中記錄的流標識即為該算法識別出的長流的流標識；將記錄的流標識映射到第二級CBF中，相應位置的計數器的最小值即為該算法測量出的長流的流長度。

3 實驗分析

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

表1 真實長流信息

分別以1/10、1/50、1/100的抽樣頻率對總報文進行系統抽樣，兩級CBF的哈希函數均選用SHA1算法。分別取哈希函數個數為1，2，3進行長流識別，當哈希函數個數大于1時，對報文信息進行復制作為新的SHA1輸入以生成新的哈希值。當抽樣頻率設為1/100，哈希函數個數設為1時，算法仿真結果如表2所示，可以看出由本算法識別出的長流信息與真實的長流信息完全相同。

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

使用不同的抽樣頻率和哈希函數個數進行仿真實驗后發現：

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

4 結束語

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