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

有效

• 申請?zhí)枺?/td>: 201710934979.3
• 申請日: 2017-10-10
• 公開（公告）號: CN107948007B
• 公開（公告）日: 2021-09-10
• 發(fā)明（設(shè)計）人: 秦文虎;翟金鳳;孫立博;魯凱;林學(xué)勇
• 申請（專利權(quán)）人: 東南大學(xué);南京市計量監(jiān)督檢測院
• 主分類號: H04L12/26
• 分類號: H04L12/26
• 代理公司: 南京眾聯(lián)專利代理有限公司 32206
• 代理人: 葉涓涓

本發(fā)明提供了基于抽樣和兩級CBF的長流識別算法，包括：對報文進行周期抽樣；設(shè)定長流閾值，配置兩級CBF結(jié)構(gòu)參數(shù)；對于被抽樣報文，通過第二級CBF判斷其是否屬于已識別出的長流，若屬于，則將其插入，若不屬于，再通過第一級CBF判斷其所屬流是否為長流，若為長流，則記錄其流標(biāo)識，并更新其在兩級CBF中的記錄，若不為長流，則將其插入第一級CBF；重復(fù)上述過程直至處理完所有被抽樣報文后，通過第二級CBF對所有未被抽樣的報文進行查詢，若屬于已識別出的長流，則將其插入，否則不做處理。本發(fā)明能在有效節(jié)省空間和時間資源的基礎(chǔ)上，既實現(xiàn)對長流的準(zhǔn)確識別，又實現(xiàn)對流長度的高精度測量。

技術(shù)領(lǐng)域

本發(fā)明屬于網(wǎng)絡(luò)流量測量技術(shù)領(lǐng)域，涉及一種長流識別方法，更為具體的說，是涉及一種基于抽樣和兩級Counting Bloom Filter的長流識別方法。

背景技術(shù)

高速網(wǎng)絡(luò)運行速度的日益加快和流量數(shù)據(jù)的急速增加，使得對網(wǎng)絡(luò)流量的精確測量越來越困難。許多研究表明，網(wǎng)絡(luò)流的統(tǒng)計呈現(xiàn)很強的重尾分布特性，由于少量的長流占據(jù)了網(wǎng)絡(luò)流量的大部分，多數(shù)情況下掌握長流信息即可滿足實際應(yīng)用需求，因此對長流的識別顯得尤其重要。

目前已有的長流識別方法主要使用抽樣技術(shù)、哈希技術(shù)以及Bloom Filter技術(shù)。單獨使用抽樣技術(shù)識別長流時，需要在識別的過程中維護流標(biāo)識信息，會產(chǎn)生很大的計算開銷，減慢系統(tǒng)處理速度；而單獨使用哈希技術(shù)或Bloom Filter技術(shù)對鏈路上通過的所有報文進行處理時，會增大哈希沖突，影響測量結(jié)果的準(zhǔn)確性。將抽樣技術(shù)和哈希技術(shù)或Bloom Filter技術(shù)相結(jié)合可以有效解決只使用一種技術(shù)的弊端。與哈希技術(shù)相比，BloomFilter通過維護多個獨立的哈希函數(shù)可以明顯降低哈希沖突，且大大降低了為每個流維護流標(biāo)識而帶來的存儲開銷，改進結(jié)構(gòu)之一Counting Bloom Filter更是可以對哈希到存儲空間中的報文進行計數(shù)，當(dāng)報文數(shù)超出閾值時即可將長流的流標(biāo)識記錄下來，因此將抽樣技術(shù)和Counting Bloom Filter相結(jié)合可以更高效地實現(xiàn)長流識別。

現(xiàn)有的基于抽樣和Counting Bloom Filter(CBF)的長流識別方法都普遍使用簡單線性估計來估計原始長流中包含的報文數(shù)，存在一定的流長度測量誤差，不能滿足較高精度需求。

發(fā)明內(nèi)容

為解決上述問題，本發(fā)明提供了一種基于抽樣和兩級Counting Bloom Filter的長流識別方法，基于報文抽樣，并通過兩級Counting Bloom Filter識別屬于長流的報文。

為了達(dá)到上述目的，本發(fā)明提供如下技術(shù)方案：

基于抽樣和兩級CBF的長流識別方法，包括如下步驟：

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

步驟2，設(shè)定長流的閾值T，同時配置兩級Counting Bloom Filter結(jié)構(gòu)參數(shù)；

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

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

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

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