[發明專利]基于抽樣和兩級CBF的長流識別方法

有效

• 申請號: 201710934979.3
• 申請日: 2017-10-10
• 公開（公告）號: CN107948007B
• 公開（公告）日: 2021-09-10
• 發明（設計）人: 秦文虎;翟金鳳;孫立博;魯凱;林學勇
• 申請（專利權）人: 東南大學;南京市計量監督檢測院
• 主分類號: H04L12/26
• 分類號: H04L12/26
• 代理公司: 南京眾聯專利代理有限公司 32206
• 代理人: 葉涓涓

1.基于抽樣和兩級CBF的長流識別方法，其特征在于，包括如下步驟：

步驟1，對觀測時間內鏈路上通過的報文按抽樣頻率進行周期抽樣；

步驟2，設定長流的閾值T，同時配置兩級Counting Bloom Filter結構參數；

所述步驟2具體包括如下過程：

設置長流閾值為T＝N·m％，其中N為觀測時間內鏈路上通過的報文總數，m為長流占據報文總數的百分比；使用抽樣報文進行長流識別的閾值設置為T₁＝T/n；兩級CountingBloom Filter選用相同的k個沖突小的哈希函數h(1),h(2),…,h(k)；第一級CountingBloom Filter結構中Counter數組的長度m₁設置為大于抽樣報文總數N/n的2的冪次方，每個計數器分配的位數b₁滿足條件：第二級Counting Bloom Filter結構中Counter數組的長度m₂設置為大于報文總數N的2的冪次方，每個計數器分配的位數b₂滿足條件：

步驟3，對于每個被抽樣的報文，先通過第二級Counting Bloom Filter判斷其是否屬于已識別出的長流，若屬于已識別出的長流，則將其插入第二級Counting Bloom Filter中，繼續處理下一報文；若不屬于已識別出的長流，則執行步驟4；

所述步驟3具體包括如下過程：

對于每個被抽樣的報文，先通過k個哈希函數將其映射到第二級Counting BloomFilter的相應位置，若相應位置的k個計數器值均不為0，則判定該報文屬于已識別出的長流，將其插入第二級Counting Bloom Filter中，繼續處理下一報文，若相應位置的k個計數器值中有任意一個為0，則判定該報文不屬于已識別出的長流，執行步驟4；

步驟4，通過第一級Counting Bloom Filter判斷其所屬流是否為長流，若為長流，則將該報文的流標識記錄下來，并更新其在兩級Counting Bloom Filter中的記錄，繼續處理下一報文；若不為長流，則執行步驟5；

所述步驟4具體包括如下過程：

通過k個哈希函數將被抽樣的報文映射到第一級Counting Bloom Filter中，求取相應位置的k個計數器的最小值；若這k個計數器的最小值等于閾值T₁，則判定其所屬流為長流，記錄下該報文的流標識，將這k個計數器值分別減去閾值T₁，并將其映射到第二級CountingBloom Filter中，設置相應位置的k個計數器值為T₁+1，繼續處理下一報文；若這k個計數器的最小值不等于閾值T₁，則判定其所屬流不為長流，執行步驟5；

步驟5，將報文插入第一級Counting Bloom Filter中，繼續處理下一報文；

步驟6，重復步驟3-5完成對所有被抽樣報文的處理后，通過第二級Counting BloomFilter對所有未被抽樣的報文進行查詢，若報文屬于已識別出的長流，則將其插入第二級Counting Bloom Filter，否則不做任何處理。

2.根據權利要求1所述的基于抽樣和兩級CBF的長流識別方法，其特征在于，所述步驟1中抽取頻率為每隔n個報文抽取一個。

3.根據權利要求1所述的基于抽樣和兩級CBF的長流識別方法，其特征在于，當報文總數較大時，降低抽樣頻率，當報文總數較小時，提高抽樣頻率。

4.根據權利要求1所述的基于抽樣和兩級CBF的長流識別方法，其特征在于，每個計數器分配的位數比滿足條件中的數量多分配若干位。

5.根據權利要求1所述的基于抽樣和兩級CBF的長流識別方法，其特征在于，所述步驟5中將報文插入第一級Counting Bloom Filter的過程包括：將第一級Counting BloomFilter中k個計數器值分別加1。