長流的識別方法、數據流量的測量方法及其設備的製作方法
2023-08-08 01:31:26 2
專利名稱：長流的識別方法、數據流量的測量方法及其設備的製作方法
技術領域：
本發明涉及計算機通信技術領域，特別涉及一種長流的識別方法、數據 流量的測量方法及及其設備。
背景技術：
隨著現代網際網路規模的擴大、異質性的突出、以及網絡應用呈現的多樣 性，人們迫切需要了解和掌握它在局部和整體範圍內所體現出的行為特徵， 以便更好地理解、設計和管理網際網路。網絡流量測量是研究流量工程和網 絡行為學的基礎，可以通過對網絡流量的基本參數進行測量，比如包長分布、 吞吐量、自相似係數等，根據測量的結果對網絡進行建模和分析，以便更好 地掌握網絡行為的基本特徵，保證網絡的健康運行。正是由於以上原因，使 得網絡流量測量從網絡管理的分支中分離出來，成為 一個獨立的網絡研究方 向，並作為一個新的研究領域成為近年來的研究熱點。
對網絡流進行測量、統計後發現流往往呈現4艮強烈的重尾分布特徵， 即大多流僅包含很少數目的報文，而很少一部分流卻攜帶著很大數目的報文。 統計長流可以節省大量的存儲空間，使流量信息能夠存儲在高速的靜態隨機 訪問存儲器(SRAM)中，提高處理網絡數據的速度。因此，高速網絡中，識 別長流是進行準確流量測量的一種重要可擴展的解決方案。目前長流的識別 方法主要是利用抽樣測量的技術，其具有代表性的算法主要有兩個採樣控 制(Sample and Hold)算法和多級過濾器(Multistage Filters )算法。
所述SampleandHold算法的基本思想是當某個數據報文到達時，如果該 報文所屬的流記錄在緩存中存在，則更新該流記錄；否則以一定的概率/ 採樣 該報文，若該報文被抽中，則創建該流記錄。其中，對於在緩存中已經有記 錄的流，以後屬於該流的淨艮文均糹皮抽樣。
所述MultistageFilters算法的基本思想是每級過濾器是一個計數器向量， 每個報文到達時，通過哈希(Hash)函數映射到每級過濾器中的對應計數器 上，然後更新對應計數器的值。如果每級過濾器相應的計數器都超過了預設 的閾值，則i人為該流是大流或長流，然後ii存該流。但是，在上述兩種方案中，對於流的識別和統計，需要實時在線地維護 五元組的信息，這對於主幹路由器的資源佔用是難以接受的。而評價性能優 劣的首要指標是算法的時間複雜度和空間複雜度。目前， 一種特殊的基於哈
希算法的數據結構布魯姆過濾器(Bloom Filter)能夠很好地解決上述問題， 它能快速地鑑別流的信息，並能把TCP流的信息維護從96比特的五元組映射到 很短的哈希串所代表的空間，極大地減少了由於維護五元組信息而帶來的資 源開銷。
其中，布魯姆過濾器表示信息的方式精簡，是一種能夠表示集合、支持 集合查詢的精簡數據結構。與傳統的查詢算法相比，大大節約了存儲空間。 也就是說，傳統的樹型結構和散列查詢算法存儲空間與元素自身大小和集合 規模直接相關，而布魯姆過濾器查詢算法所需空間與元素自身大小無關，僅 與元素映射到的向量位數相關，這就大大節約了存儲空間。下面簡單介紹兩 種基本的布魯姆過濾器。
一種是標準布魯姆過濾器(SBF， Standard Bloom Filter) SBF算法的核心是 一個V向量和一組Hash函數，其實現原理如圖l所示。 具體實現過程為設集合S二h, &，...，&}共有"個元素，通過A個Hash函數 /2i,/72，…/^將集合S中的"個元素映射到長度為m的向量V中。每一個Hash函數相 互獨立，且函數的取值範圍為{0,1,2，...， w-l}。集合S到向量V的映射過程為 向量V初始化，即將向量V的所有比特位置O;當元素插入集合S時，對於每一 個元素s,.,計算/z》,)(l^W)，若、(s,)",則令SBF[《]-1，將向量對應的位 置置位；當查詢元素是否屬於集合S時，對於給定的元素;c，檢查向量V的A個 位置(/^(義)》200,...; ^))是否為1。如果其中有一個為O,則xgS;若全部值為l, 則x可能屬於S中。此時就可能出現"假陽性誤判"，即將不屬於集合的元素誤 判成屬於該集合，但不會出現"假陰性誤判"(即將屬於集合的元素誤判成不屬 於該集合)。
由此可知，該SBF算法的實現過程中，用("，m，t)的形式表示SBF,其中"為 集合S的元素個數，w為向量V的長度，A為哈希函數的個數。使用SBF完成集 合存儲，保存每個元素平均使用m/"位，空間十分節儉。雖然SBF算法能夠較 好地支持集合元素的插入和散列查詢，但是卻不能夠支持元素的刪除。另一種是計數型布魯姆過濾器(CBF， Counting Bloom Filter) CBF可以支持元素的刪除，其實現過程為將向量V的每一維《/e(l,2,…;^) 設置成一個計數器，記為c(/),並設定初值為0。當要增加集合元素x時，則 c(/7/x)"c( (x))+l，(戶1,2,…,A:);當要刪除集合元素x時，貝'k(/z/(x))二c(/z乂jc))隱1 ， (戶1，2，…，"如圖2所示。
CBF不僅支持集合元素的插入和散列查詢，集合元素的刪除，還能支持集 合元素的統計計數當a.插入以後(設^對應的計數器為q，C2…cJ,若後面到 達的數據中還存在s,,則CBF不但能判斷s,存在，而且還應該在對應的計數器 位置加l計數，統計^的個數。在具體實現時，可以根據集合元素的增加與刪 除的統計規律，選擇適當的計數器大小，以防止計數器的溢出。在不考慮計 數器溢出的情況下，A的統計值可以用min(d， C2…c^來表示，但存在單邊"假 陽性"的錯誤概率(即統計值比實際值大)。
在對現有技術的研究和實踐過程中，本發明的發明人發現，現有的實現 方式中，針對高速網絡中流量測量面臨可擴展性的挑戰，雖然CBF能支持集 合元素的插入、散列查詢、以及集合元素的統計計數，但是，由於CBF的空 間利用率低，以不能針對高速網絡中實時在線的長流進行識別和統計，不能 適應當前及未來的流量測量需求。
發明內容
本發明實施例提供一種長流的識別方法、數據流量的測量方法及其設備， 以實現對高速網絡中實時在線的長流進行識別和統計，適應高速網絡中的流 量測量需求。
為此，本發明是實施例提供一種長流的識別方法，包括 確定業務流的項數/，每項對應一個先驗計數型布魯姆過濾器； 對每一項進行哈希運算，生成每一項對應每個先驗計數型布魯姆過濾器 的哈希地址；
查找每一項對應的每個哈希地址對應的計數器； 循環每個先驗計數型布魯姆過濾器中對應的計數器；
若所述每一項中每個計數器的值都大於等於預設閾值，或者若計數器的 循環次數等於先驗計數型布魯姆過濾器的個數，則判定所述業務流為/-項長流，並在所述每一項對應的每個計數器的值加1後，返回所述確定業務流的 項數/的步驟。
優選的，所述方法還包括
若每一項的每個計數器的值中有一個計數器的值小於預設閾值，根據預 設的先驗原則二，該項為非頻繁項，根據預設的先驗原則一，該項對應的業 務流為非/-項長流。
優選的，所述預設的先驗原則一具體包括如果一個業務流為/-項長流， 則所述/-項長流的所有項一定是頻繁項；
所述預設的先驗原則二具體包括如果標識某個業務流的項是頻繁項， 則該項對應的先驗計數型布魯姆過濾器中的每個計數器的值都大於預設閾 值。
優選的，在對每項進行哈希運算前，初始化每項對應的先驗計數型布魯 姆過濾器的值。
本發明實施例還提供一種長流的識別設備，包括
確定單元，用於確定業務流的項數/，每項對應一個先驗計數型布魯姆過 濾器；
生成單元，用於對每一項進行哈希運算，生成每一項對應每個先驗計數 型布魯姆過濾器的哈希地址；
查找單元，用於查找每一項對應的每個哈希地址對應的計數器；
循環單元，用於循環每個先驗計數型布魯姆過濾器中對應的計數器； 第一識別單元，用於在判斷所述每一項中每個計數器的值都大於等於預
設閾值時，或者若計數器的循環次數等於先驗計數型布魯姆過濾器的個數時，
判定所述業務流為/-項長流，並在所述每個計數器的值加1後，通知確定單元。 優選的，還包括第一判斷單元和/或第二判斷單元，其中， 所述第一判斷單元，用於判斷每一項中每個計數器的值是否都大於等於
預設閾值，並將大於等於預設閾值的判斷結果通知第一識別單元；
所述第二判斷單元，判斷計數器的循環次數是否等於先驗計數型布魯姆
過濾器的個數並將等於的判斷結果通知第 一識別單元。
優選的，所述第一判斷單元根據預設的先驗原則一進行判斷；所述第二判斷單元依次根據預設的先驗原則二、預設的先驗原則一進行判斷，其中，
所述預設的先驗原則一具體包括如果一個業務流為/-項長流，則所述/-項長 流的所有項一定是頻繁項；所述預設的先驗原則二具體包括如果標識某個 業務流的項是頻繁項，則該項對應的先驗計數型布魯姆過濾器中的每個計數 器的值都大於預設閾值。 優選的，還包括
第三判斷單元，用於判斷每一項的每個計數器的值中是否有一個計數器 的值小於預設閾值，若是，根據預設的先驗原則二，該項為非頻繁項，根據 預設的先-驗原則一，該項對應的業務流為非/-項長流。
優選的，還包括
初始化單元，用於在生成單元生成對應每個先驗計數型布魯姆過濾器的 哈希地址前，初始化每項對應的先驗計數型布魯姆過濾器的值。 本發明實施例再提供一種數據流量的測量方法，包括 確定業務流的項數/,每項對應一個先驗計數型布魯姆過濾器，初始化每 個先驗計數型布魯姆過濾器及每個先驗計數型布魯姆過濾器中的計算器的 值；
統計測量周期中的每個時間窗的業務流；
在流過所述任一時間窗的業務流結束時，重整化該項對應的每個先驗計 數型布魯姆過濾器；
在所述測量周期結束時，輸出統計的業務流。 優選的，還包括
在所述測量周期沒有結束時，對該項流過下一時間窗的業務流繼續統計，
直至測量周期結束，輸出統計的業務流。
優選的，所述統計測量周期中的每個時間窗的業務流具體包括 對該項進行哈希運算，生成該項對應每個先驗計數型布魯姆過濾器的哈
希地址；
查找該項對應的每個先驗計數型布魯姆過濾器的哈希地址對應的計數
器；
對所述對應的計數器的值加1,直至每項對應的計數器的循環次^:等於先驗計數型布魯姆過濾器的個數。
優選的，所述重整化每項對應的每個先驗計數型布魯姆過濾器具體包括 將每個先驗計數型布魯姆過濾器中的所有小於預設閾值的計數器的值初始化 為0。
本發明實施例又提供一種數據流量的測量設備，包括
確定單元，用於確定業務流的項數/,每項對應一個先驗計數型布魯姆過
濾器，初始化每個先驗計數型布魯姆過濾器及每個先驗計數型布魯姆過濾器
中的計算器的值；
統計單元，用於統計測量周期中的每個時間窗的業務流； 重整化單元，用於在流過所述任一時間窗的業務流結束時，重整化該項 對應的每個先驗計數型布魯姆過濾器；
流量輸出單元，用於在所述測量周期結束時，輸出統計的業務流。 優選的，還包括判斷單元和處理單元，
所述判斷單元，用於所述測量周期是否結束，若是，則通知流量輸出單 元輸出統計的業務流；否則，通知統計單元；
所述統計單元，還用於在接收到判斷單元的通知後，對該項流過下一時 間窗的業務流繼續統計，直至測量周期結束，通知流量輸出單元輸出統計的 業務流。
由上述^支術方案可知，本發明實施例通過確定業務流的項數l,每項對應 一個先驗計數型布魯姆過濾器；對每一項進行哈希運算，生成每一項對應每 個先驗計數型布魯姆過濾器的哈希地址；查找每一項對應的每個哈希地址對 應的計數器；判斷所述每一項中每個計數器的值是否都大於等於預設閾值， 若大於預i殳閾值，則判定所述業務流為/-項長流，並在所述每一項中每個計數 器的值加l後，返回所述確定業務流的項數/的步驟。也就是說，本發明實施 例將實時流量分析的硬體配置和硬體管理有效地結合起來，並採用可擴展性 的先驗計數型布魯姆過濾器，確保高速網路流量實時測量的需求。針對高速 骨幹鏈路流量測量面臨可擴展性的挑戰，本方案擴展了能夠表示集合、支持 集合查詢的計數布魯姆過濾器，構造了一種能夠支持表示、查詢和統計業務 流的先驗計數型布魯姆過濾器的數據結構。該數據結構將先驗原則和計數型
ii布魯姆過濾器進行有機結合，能夠存儲數據流的統計特徵，藉助於它就只需 要對數據流進行一遍掃描即可獲得誤差可控的近似結果。應用先驗計數型布 魯姆過濾器進行骨幹網實時流量測量， 一方面，可以實時統計到大於某一閾
值的業務流；另一方面，壓縮了流量信息存儲的空間，並且部署靈活，實現
代價低，對於高速骨幹網的流量分析而言具有較高的實用價值。
圖1為現有技術中標準布魯姆過濾器的實現原理示意圖； 圖2為現有技術中計數型布魯姆過濾器的實現原理示意圖； 圖3為本發明實施例中提供的一種長流的識別方法的流程圖； 圖4為本發明實施例中/-項流對應的CBF示意圖； 圖5為本發明實施例中先驗原則2的示意圖6為本發明實施例中基於Apriori-CBF判斷l-項流為長流的流程圖； 圖7為本發明實施例中基於Apriori-CBF判斷1-項流為長流的另 一流程圖； 圖8為本發明實施例中提供的一種數據流量的測量方法的流程圖； 圖9為本發明實施例中業務流的實時測量流程圖； 圖10為本發明實施例中業務流的統計計數的流程圖； 圖11為本發明實施例中CBF,重整化的示意圖； 圖12為本發明實施例中提供的一種長流的識別設備的結構示意圖； 圖13為本發明實施例中提供的一種數據流量的測量設備的結構示意圖； 圖14為本發明實施例中骨幹網流量分析系統的一種結構示意圖。
具體實施例方式
下面我們將結合附圖，對本發明的最佳實施方案進行詳細描述。 請參閱圖3，為本發明實施例中提供的一種長流的識別方法的流程圖；所 述方法包括
步驟301:確定業務流的項數/,每項對應一個先驗計數型布魯姆過濾器 (Apriori-CBF ， Apriori國Counting Bloom Filter);
步驟302:對每一項進行哈希運算，生成每一項對應每個先-瞼計數型布魯 姆過濾器的"^合希地址；
步驟303:查找每一項對應的每個哈希地址對應的計數器；步驟304:循環每個先驗計數型布魯姆過濾器中對應的計數器； 步驟305:若所述每一項中對應每個計數器的值都大於等於預設閾值，或 者每一項中計數器的循環次數等於先驗計數型布魯姆過濾器的個數，則判定 所述業務流為/-項長流，並在所述每一項中每個計數器的值加1後，返回步驟 301。
優選的，在步驟301和步驟302之間，還可以包括初始化每項對應的 先驗計數型布魯姆過濾器的值。
優選的，若每一項的每個計數器的值中有一個計數器的值小於預設閾值， 根據預設的先驗原則二，該項為非頻繁項，根據預設的先驗原則一，該項對 應的業務流為非/-項長流。
為了便於本領域技術人員的理解，先介紹下述名詞
先驗(Apriori)原理的原因在對網絡流進行測量、統計後發現，流往 往呈現很強烈的重尾分布特徵，即大多數流僅包含很少數目的報文，而很少 一部分流卻攜帶著很大數目的報文。統計長流可以節省大量的存儲空間，使 流量信息能夠存儲在靜態隨才幾訪問存儲器(SRAM, Static Random Access Memory)中，提高處理網絡數據的速度；同時，在網絡安全的應用中，由於 剝離了無關的網絡流量，使安全事件的"罪魁禍首"更加容易識別。因此，高速 網絡中，識別長流是進行準確流量測量的一種重要可擴展的解決方案。為了 統計長流，本發明實施例特引進"Apriori"原理進行長流的統計。為方<更描 述，特做出如下定義
定義一標識業務流的每一維屬性字^a,稱作項，如源IP位址、源埠
等欄位；
定義二若只用一項來標識某一業務流，且此流的大小(每流報文數來衡 量)大於預設的閾值M，那麼標識該流的項稱為頻繁項；反之，若此流的大小 小於預i殳的閾^直M，則標識該流的項稱為非頻繁項。
定義三由/個項共同標識的某業務流，稱為/-項流；若Z-項流的大小大 於預設的閾值M,則稱此流為/-項長流(/的值越大，則描述流的信息越詳細)。
由以上定義可以看出標識業務流的每一項，都有相應的一個Apriori-CBF 與之對應，即Z-項流要用/個Apriori-CBF來聯合表示、查詢和統計。如圖4所示，標識/-項流的/維屬性(AhA2,…A,;[分別對應/個Apriori-CBF，其中第 f維屬性字^殳A,.,由Apriori-CBFi表示、查詢和統計。
在本發明實施例中，提供兩種先驗原則，具體如下所述 先驗原則1:如果一個流是/-項長流，則它的所有項一定是頻繁的。其中， 設定先驗原則1的基本思想為假定某一個業務流/用/維屬性(Ai,A2,…AJ 來標識，且該流是/-項長流。並設定它的a項子集(Bc^/)來標識的業務流為 乂。因為屬於流/的報文，也必定屬於流/;,所以/也是/-項長流。相反，如 果一個"項子集是非頻繁的(即由《項標識的某業務流，其大小小於閾值M )， 則它的所有超集/ ( 〃項集，其中/ 滿足〃^a )也一定是非頻繁的。特別當"=1 時，即如果l項子集(單維屬性欄位標識的流)是非頻繁的，則它的所有超集 (大於等於1項的超集)也一定是非頻繁的。
例如如果只用源IP位址"192.168.199.27，，來標識某l-項流，並且此流的 大小小於閾值M,則它的超集(大於等於1項，如用源IP位址"192.168.199.27" 和目的IP位址"192.168.199.33")共同標識的某一業務流，其大小肯定小於等 於M。
先驗原則2:如果標識某個流的項是頻繁項，則該項對應的Apriori-CBF 中的k個計數器也一定是頻繁的(即每個計數器的值都大於M)。其中，先驗 原則2的基本思想為 -暇定只用八,.來標識某/-項流/,並且/-項流/的大小大 於閾值M。根據定義二可知，A,為頻繁項。頻繁項A,對應Apriori-CBF,中的 A個計數器為c(l), c(2),…，c(A)。用反證法來證明，假定其中某一計數器c(i)<M, 由於業務流/的大小可表示為min(c(l)， c(2),…，c(A)},則業務流/的大小必然 小於M，這與已知條件(/-項流/的大小大於闊值M)矛盾，故先驗原則二是 成立的。
相反，如果&個計數器中有任意一個為非頻繁的(計數器的值小於M), 則它所對應表示的項也一定是非頻繁的。如圖5所示，標識業務流的某項Ai 經過Hash運算後，得到對應的計數器為{2，5,...,7}，假設閾值M-3，由於其 中一個計數器的值小於3，則可判定項A為非頻繁的。
在理解上述名詞後，請參閱圖6，為本發明實施例中基於Apriori-CBF判 斷/-項流為長流的流程圖；本實施例是把先驗原則和CBF進行有機的結合，形成一種新穎的計數型 布魯姆過濾器結構，本實施例定義為先驗計數型布魯姆過濾器(簡稱 Apriori-CBF )。基於先驗計數型布魯姆過濾器判斷一個/-項流為長流的流程圖 如圖6示。具體包括
步驟601:輸入/-項流/,設標識該流的/項為{ A!,A2，...A, }，每一項對應 一個Apriori-CBF，即每一項由對應的一個Apriori-CBF來表示、統計和查詢；
步驟602:初始化第/個Apriori-CBF的值，即/=0,其中，1 < K /;
步驟603:查詢第/個Apriori-CBF;
步驟604:循環第/個Apriori-CBF中對應的A個計算器c(;.) ( 1《_/ "); 其中，本實施例以查詢A,.項對應的第/個Apriori-CBF的過程為例具體
為
對A,項進行Hash運算，生成(得到)A個Hash地址，即 /h(A,)力2(A,),…/M;A,);查找A:個Hash地址對應的A:個計數器，即c(l)=
Apriori-CBF [/zi(A孔c(2)= Apriori-CBF [/z2(A,)],...，順=Apriori-CBF [&(A,)]; 步驟605:判斷c(/) 是否小於預設閾值M;若否，執行步驟
606;若是，則執行步驟607;
步驟606: A:個計數器的值加l,即i+l，也就是說，若所述每一項中每個
計數器的值都大於等於預設閾值，則判定所述業務流為/-項長流，並在所述每
一項中每個計數器的值加1後，返回步驟603;
步驟607:判定第f個Apriori-CBF對應的第/項為非頻繁項；
步驟608: Z維屬性標識的流為非頻繁的，即Z-項流f為非長流。
另外，在該實施例中，基於先驗原則二，如果至少有一個計數器的值小
於預設閾值M，則對應的項A,為非頻繁項；基於先驗原則一，如果A,為非頻
繁項，則(A!,A2，…A，…，AJ共同標識的/-項流/為非頻繁的，即可判斷該/-
項流/不是長流。
還請參閱圖7,為本發明實施例中基於八 『^11《8 判斷/-項流為長流的 另一流程圖；在該實施例中，步驟701至步驟704、步驟706分別與圖6中的 步驟601至步驟604、步驟606的完全相同，具體詳見上述，在此不再贅述； 其不同之處為在步驟704後，執行步驟705:判斷每項對應的計數器的循環次數等於先 驗計數型布魯姆過濾器的個數，比如，當/=1， /=2,……直到/=/，若是，則執 行步驟707;否則執行步驟706;
步驟707:標識流/所有的項都是頻繁項，即如果(A,，A2,…,A,.,…，AJ所有 的項都是頻繁項；
步驟708:基於先驗原則一，可判斷該/-項流/為長流。也就是說，/維 屬性標識的流為頻繁的，即/-項流/為長流。其中，對於先驗原則一詳見上述， 在此不再贅述；
由圖6和圖7的描述可知，對於判斷c(/) ( 1 《yt)是否小於預設閾值M 與判斷每項對應的計數器的循環次數是否等於先驗計數型布魯姆過濾器的個 數，本發明實施例是擇一的，也就是"i兌，只要有一個成立，都可以判斷該/-項流f是否為長流，只不過，如果上述的兩個條件分別不成立時，需要A個計 數器的值加1，進行循環。
還請參閱圖8,為本發明實施例中提供的一種數據流量的測量方的流程 圖；所述方法包括
步驟801:確定業務流的項數/，每項對應一個先驗計數型布魯姆過濾器， 初始化每個先驗計數型布魯姆過濾器及每個先驗計數型布魯姆過濾器中的計 算器的值；
步驟802:統計測量周期中的每個時間窗的業務流； 步驟803:在流過所述任一時間窗的業務流結束時，重整化該項對應的每 個先驗計數型布魯姆過濾器；
步驟804:在所述測量周期結束時，輸出統計的業務流。 所述方法還可以包括
在所述測量周期沒有結束時，對該項流過下一時間窗的業務流繼續統計， 直至測量周期結束，輸出統計的業務流。
還請參閱圖9，為本發明實施例中業務流的實時測量流程圖；本實施例匯 總，業務流的實時測量過程主要包括在單個時間窗口，業務流的統計計數 (在第一步已經詳細闡述)；時間窗結束時，重整化每個Apriori-CBF;測量 周期結束時，強制輸出測量結果。具體包括步驟901:確定業務流的項數/，以及每項對應的Apriori-CBF，並初始化 每個Apriori-CBF,以及每項對應的A個Hash函數；
步驟902:對第A:個時間窗進行業務流的統計計^t;
步驟903:判斷測量周期中的時間窗是否結束，若是，執行步驟904;否 則返回步驟902;
步驟904:重整化每個Apriori-CBF;
步驟905:判斷測量周期是否結束，若是，執行步驟907;否則，執行步 驟906;
步驟906:對測量周期中下一時間窗進行統計，即&+1,之後，返回步驟
902;
步驟卯7:輸出測量結果。
該測量過程有兩個優勢 一方面，由於統計業務流過程只需要一次Hash 映射計數以及Hash函數的並行操作性，使得流量測量的計算複雜度大大降低； 另一方面，使用Apriori-CBF能把流信息維護從96比特的五元組映射到很短 的哈希串所代表的空間，極大地減少了由於維護五元組信息而帶來的資源開 銷，為業務流的實時統計提供了條件。
其中，統計該項流過測量周期的每個時間窗的業務流的實現過程如圖10 所示，具體包括
步驟1011:提取業務流的第f維屬性，即第/項；
步驟1012:對該項進行哈希運算，生成該項對應每個先驗計數型布魯姆 過濾器的哈希地址；
步驟1013:查找該項對應的每個p合希地址對應的計數器；
步驟1014:對所述對應的計數器的值加1,直至每項對應的計數器的循 環次數等於先驗計數型布魯姆過濾器的個數。
若所述該項中每個計數器的值都小於預設閾值，判斷先驗計數型布魯姆 過濾器的個數是否等於計數器的個數，若是，則判定所述業務流為/-項長流； 否則，則判定所述業務流為非/-項長流；令先驗計數型布魯姆過濾器的哈希地 址加1,直到每項對應的計數器的循環次數等於先驗計數型布魯姆過濾器的個 數為止。也就是說，應用Apriori-CBF進行流量測量，其具體的統計過程如下 初始化各個參數。確定流/的維數/ (例如如果用源IP位址和目的IP 地址來共同標識一個流，則/ = 2;如果用五元組標識一個流，則/=5);初始 化/個CBF,令每個CBF中的計數器的值為0;確定A:個Hash函數。
對{八1厶2,...，八;,...,^}中的第/維屬性欄位A,進行統計測量，其具體的過 程如下提取A,.屬性欄位；對A,進行Hash運算，得到得到A:個Hash地址 /21(A,)，/72(A,),.../z"A,);找到對應的A個c(l)= Apriori-CBF [/z!(A,)]， c(2)= Apriori-CBF [/z2(A0]".',順=Apriori-CBF [似A!)];令= + l，.." c(A)= ,+ 1。
Step3:令/ = /+1,重複對{ Ai,A2，…，A,，…，A, }中的第/維屬性欄位A,進 行統計測量，直到/ = /。
其中，所述重整化該項對應的每個先驗計數型布魯姆過濾器的實現過程 如圖11所示，在該圖中，對Apriori-CBF中小於預設閾值的M為4的值進行 初始化，其初始化的值具體圖ll底色為斜線所示。
對於Apriori-CBF的重整化，流量測量設備一般每隔固定的時間間隔輸出 流量測量結果，並把該測量間隔分成更小的時間窗。為方^f更描述，特^L如下 定義
定義四流量測量設備每隔一定的時間間隔輸出流量結果，稱此時間間 隔為測量周期T。
定義五測量周期分成的等長時間間隔^殳其為Th)，稱為時間窗(TW, time window)。
為了壓縮流量信息的存儲空間，需要重整化Apriori-CBF。下面針對標識 某/-項流的其中一項A,.(某屬性欄位)來說明，設表示和查詢A,.的計數型布 魯姆過濾器為Apriori-CBF,。在任意時間窗TW;結束時，對Apriori-CBF,進行 重整化，其具體過程如圖11所示設閾值M=4,則對於所有c(Q<M (卜l，2,3，…,m)的計數器c("，令c("仨0。
由於業務流的大小可表示為min{c(l)， c(2)，...， c(A)}，所以重整後為0的計 數器對應項的統計值也變成了 0，則這些項標識的流的大小也等於0 (即流量 大小小於M的流被剔除，只有大於M的流被保存下來)。相應的，本發明實施例還提供一種長流的識別設備，其結構示意圖詳見
圖12;所述設備包括確定單元121、生成單元122、查找單元123、循環單 元124和第一識別單元125。其中，所述確定單元121,用於確定業務流的項 數/，每項對應一個先驗計數型布魯姆過濾器；所述生成單元122，用於對每 一項進行哈希運算，生成每一項對應每個先驗計數型布魯姆過濾器的哈希地 址；所述查找單元123，用於查找每一項對應的每個p合希地址對應的計數器； 所述循環單元124，用於循環每個先驗計數型布魯姆過濾器中對應的計數器； 所述第一識別單元125，用於在判斷所述每一項中每個計數器的值都大於等於 預設閾值時，或者計數器的循環次數等於先驗計數型布魯姆過濾器的個數時， 判定所述業務流為/-項長流，並在所述每個計數器的值加1後，通知確定單元 121。
優選的，所述設備還包括第一判斷單元和/或第二判斷單元，其中， 所述第一判斷單元，用於判斷每一項中每個計數器的值是否都大於等於 預設閾值，並將大於等於預設閾值的判斷結果通知第一識別單元；所述第二 判斷單元，判斷計數器的循環次數是否等於先驗計數型布魯姆過濾器的個數
並將等於的判斷結果通知第 一識別單元。
優選的，還包括第三判斷單元，用於判斷每一項的每個計數器的值中 是否有一個計數器的值小於預設閾值，若是，根據預設的先驗原則二，該項 為非頻繁項，根據預設的先驗原則一，該項對應的業務流為非/-項長流。
其中，所述第一判斷單元根據預設的先驗原則一進行判斷；所述第二判 斷單元依次根據預設的先驗原則二、預設的先驗原則一進行判斷，其中，所 述預設的先驗原則一具體包括如果一個業務流為l-項長流，則所述1-項長流 的所有項一定是頻繁項；所述預設的先驗原則二具體包括如果標識某個業 務流的項是頻繁項，則該項對應的先驗計數型布魯姆過濾器中的每個計數器 的值都大於預設閾值。對於先驗原則一和先驗原則二，詳見上述，在此不再 贅述。
所述設備還包括初始化單元，用於在生成單元生成對應每個先驗計數 型布魯姆過濾器的哈希地址前，初始化每項對應的先驗計數型布魯姆過濾器 的值。
19所述設備中各個單元的功能和作用的實現過程詳見上述方法中對應的實 現過程，在此不再贅述。
相應的，本發明實施例還提供一種數據流量的測量設備，其結構示意圖
詳見圖13,所述設備包括確定單元131、統計單元132、重整化單元133和 流量輸出單元134,其中，所述確定單元131,用於確定業務流的項數/,每 項對應 一個先驗計數型布魯姆過濾器，初始化每個先驗計數型布魯姆過濾器 及每個先驗計數型布魯姆過濾器中的計算器的值；所述132統計單元，用於 統計該項流過測量周期的每個時間窗的業務流；所述重整化單元133,用於在 流過所述任一時間窗的業務流結束時，重整化該項對應的每個先-驗計數型布 魯姆過濾器；所述流量輸出單元134,用於在所述測量周期結束時，輸出統計 的業務流。
所述設備還包括判斷單元和處理單元，其中，所述判斷單元，用於所 述測量周期是否結束，若是，則通知流量輸出單元輸出統計的業務流；否貝'h 通知統計單元；所述統計單元，還用於在接收到判斷單元的通知後，對該項 流過下一時間窗的業務流繼續統計，直至測量周期結束，通知流量輸出單元 輸出統計的業務流。
所述設備中各個單元的功能和作用的實現過程詳見上述方法中對應的實 現過程，在此不再贅述。
此外，本發明實施例中還提供骨幹網流量分析系統的一種結構示意圖.， 具體如圖14所示。骨幹網流量分析系統的結構一般包含前端處理141和後端 處理142兩個部分，前端處理的功能較為簡單，主要進行數據的預處理，其 目的是對原始流量進行約減，以降低後端處理的開銷；後端處理的功能相對 複雜，其目的是從約減後的網絡流量數據中獲取有用信息。前端處理的結果 需要支持多種後端應用，因此前端處理具有通用性；後端處理往往針對某一 種具體的應用而設計，因而後端處理具有專用性。通常，前端處理採用硬體 實現而後端處理採用軟體實現，本發明實施例中的長流的識別方案主要應用 於前端處理。
顯然，若前端處理的數據約減的幅度太大，則數據中的可用信息損失越 嚴重；若前端處理的數據約減幅度太小，則會增大後端處理的處理開銷和實現難度。可見，前端處理的數據約減的方法和性能對於骨幹網流量分析系統 的性能有著非常重要的影響。
也就是說，當一個無限的數據流序列快速流入時，要求在僅對數據集進 行一遍掃描的情況下，利用有限的存儲空間快速完成計算，以實時響應用戶 請求。因此，該流量測量模型的關鍵在於設計一個遠小於數據集規模的結構，
從而可以在高速緩存(比如SRAM)中處理數據。先驗計數型布魯姆過濾器 其實本質上是一種概要數據結構，它存儲了數據流的統計特徵，是對數據流 的一種壓縮總結，藉助於它就不需要對數據流進行多遍掃描即可獲得誤差可 控的近似結果。而且據此設計的處理算法同樣可適用於海量靜態數據的情況， 當數據可在再次存取和掃描時，某些算法可獲得更加準確的處理結果。應用 Apriori-CBF進行流量測量，具體的流量測量過程主要分成詳見上述，在此不 再贅述。
由此可見，本發明實施例將實時流量分析的硬體配置和硬體管理有效地 結合起來，並採用可擴展性的先驗計數型布魯姆過濾器，確保高速網路流量 實時測量的需求。針對高速骨幹鏈路流量測量面臨可擴展性的挑戰，本方案 擴展了能夠表示集合、支持集合查詢的計數布魯姆過濾器，構造了一種能夠 支持表示、查詢和統計業務流的先驗計數型布魯姆過濾器的數據結構。該數 據結構將先驗原則和計數型布魯姆過濾器進行有機結合，能夠存儲數據流的 統計特徵，藉助於它就只需要對數據流進行一遍掃描即可獲得誤差可控的近 似結果。應用先驗計數型布魯姆過濾器進行骨幹網實時流量測量， 一方面， 可以實時統計到大於某一閾值的業務流；另一方面，壓縮了流量信息存儲的 空間，並且部署靈活，實現代價低，對於高速骨幹網的流量分析而言具有較 高的實用價值。
通過以上的實施方式的描述，本領域的技術人員可以清楚地了解到本發 明可藉助軟體加必需的通用硬體平臺的方式來實現，當然也可以通過硬體， 但很多情況下前者是更佳的實施方式。基於這樣的理解，本發明的技術方案 本質上或者說對現有技術做出貢獻的部分可以以軟體產品的形式體現出來， 該計算機軟體產品可以存儲在存儲介質中，如ROM/RAM、磁碟、光碟等， 包括若干指令用以使得一臺計算機設備(可以是個人計算機，伺服器，或者以上所述僅是本發明的優選實施方式，應當指出，對於本技術領域的普 通技術人員來說，在不脫離本發明原理的前提下，還可以作出若干改進和潤 飾，這些改進和潤飾也應視為本發明的保護範圍。
權利要求
1、一種長流的識別方法，其特徵在於，包括確定業務流的項數l，每項對應一個先驗計數型布魯姆過濾器；對每一項進行哈希運算，生成每一項對應每個先驗計數型布魯姆過濾器的哈希地址；查找每一項對應的每個哈希地址對應的計數器；循環每個先驗計數型布魯姆過濾器中對應的計數器；若所述每一項中每個計數器的值都大於等於預設閾值則判定所述業務流，或者若計數器的循環次數等於先驗計數型布魯姆過濾器的個數，則判斷所述業務流為l-項長流，並在所述每一項對應的每個計數器的值加1後，返回所述確定業務流的項數l的步驟。
2、 根據權利要求1所述的方法，其特徵在於，所述方法還包括若每一項的每個計數器的值中有一個計數器的值小於預設閾值，根據預設的先驗原則二，該項為非頻繁項，根據預設的先驗原則一，該項對應的業務流為非/-項長流。
3、 根據權利要求2所述的方法，其特徵在於所述預設的先驗原則一具體包括如果一個業務流為/-項長流，則所述/-項長流的所有項 一定是頻繁項；所述預設的先驗原則二具體包括如果標識某個業務流的項是頻繁項，則該項對應的先驗計數型布魯姆過濾器中的每個計數器的值都大於預設閾值。
4、 根據權利要求1至3任一項所述的方法，其特徵在於，在對每項進行哈希運算前，初始化每項對應的先驗計數型布魯姆過濾器的值。
5、 一種長流的識別"i殳備，其特徵在於，包括確定單元，用於確定業務流的項數/,每項對應一個先驗計數型布魯姆過生成單元，用於對每一項進行哈希運算，生成每一項對應每個先-瞼計數型布魯姆過濾器的哈希地址；查找單元，用於查找每一項對應的每個^^合希地址對應的計數器；循環單元，用於循環每個先驗計數型布魯姆過濾器中對應的計數器；第一識別單元，用於在判斷所述每一項中每個計數器的值都大於等於預設閾值，或者若計數器的循環次數等於先驗計數型布魯姆過濾器的個數時，判定所述業務流為/-項長流，並在所述每個計#:器的值加1後，通知確定單元。
6、 根據權利要求5所述的設備，其特徵在於，還包括第一判斷單元和/或第二判斷單元，其中，所述第一判斷單元，用於判斷每一項中每個計數器的值是否都大於等於預設閾值，並將大於等於預設閾值的判斷結果通知第一識別單元；所述第二判斷單元，用於判斷計數器的循環次數是否等於先驗計數型布魯姆過濾器的個數，並將等於的判斷結果通知第 一識別單元。
7、 根據權利要求6所述的設備，其特徵在於，所述第一判斷單元根據預設的先驗原則一進行判斷；所述第二判斷單元依次根據預設的先驗原則二、預設的先驗原則一進行判斷，其中，所述預設的先驗原則一具體包括如果一個業務流為/-項長流，則所述/-項長流的所有項一定是頻繁項；所述預設的先驗原則二具體包括如果標識某個業務流的項是頻繁項，則該項對應的先驗計數型布魯姆過濾器中的每個計數器的值都大於預設閾值。
8、 根據權利要求7所述的設備，其特徵在於，還包括第三判斷單元，用於判斷每一項的每個計數器的值中是否有任一個計數器的值小於預設閾值，若是，根據預設的先驗原則二，該項為非頻繁項，根據預設的先驗原則一，該項對應的業務流為非/-項長流。
9、 根據權利要求6至8任一項所述的設備，其特徵在於，還包括初始化單元，用於在生成單元生成對應每個先驗計數型布魯姆過濾器的哈希地址前，初始化每項對應的先驗計數型布魯姆過濾器的值。
10、 一種數據流量的測量方法，其特徵在於，包括確定業務流的項數/,每項對應一個先驗計數型布魯姆過濾器，初始化每個先驗計數型布魯姆過濾器及每個先驗計數型布魯姆過濾器中的計算器的值；統計測量周期中的每個時間窗的業務流；在流過所述任一時間窗的業務流結束時，重整化該項對應的每個先^^計數型布魯姆過濾器；在所述測量周期結束時，輸出統計的業務流。
11、 根據權利要求IO所述的方法，其特徵在於，還包括在所述測量周期沒有結束時，對該項流過下一時間窗的業務流繼續統計，直至測量周期結束，輸出統計的業務流。
12、 根據權利要求11所述的方法，其特徵在於，所述統計測量周期中的每個時間窗的業務流具體包括對該項進行哈希運算，生成該項對應每個先驗計數型布魯姆過濾器的哈希地址；查找該項對應的每個先驗計數型布魯姆過濾器的哈希地址對應的計數器；對所述對應的計數器的值加1，直至每項對應的計數器的循環次數等於先驗計數型布魯姆過濾器的個數。
13、 根據權利要求12所述的方法，其特徵在於，所述重整化每項對應的每個先驗計數型布魯姆過濾器具體包括將每個先驗計數型布魯姆過濾器中的所有小於預設閾值的計數器的值初始化為0。
14、 一種數據流量的測量i殳備，其特徵在於，包括確定單元，用於確定業務流的項數/,每項對應一個先驗計數型布魯姆過濾器，初始化每個先驗計數型布魯姆過濾器及每個先驗計數型布魯姆過濾器中的計算器的值；統計單元，用於統計測量周期中的每個時間窗的業務流；重整化單元，用於在流過所述任一時間窗的業務流結束時，重整化該項對應的每個先驗計數型布魯姆過濾器；流量輸出單元，用於在所述測量周期結束時，輸出統計的業務流。
15、 根據權利要求14所述的設備，其特徵在於，還包括判斷單元和處理單元，所述判斷單元，用於所述測量周期是否結束，若是，則通知流量輸出單元輸出統計的業務流；否則，通知統計單元；所述統計單元，還用於在接收到判斷單元的通知後，對該項流過下一時間窗的業務流繼續統計，直至測量周期結束，通知流量輸出單元輸出統計的業務流。
全文摘要
本發明實施例涉及一種長流的識別方法、數據流量的測量方法及其設備，所述長流的識別方法包括確定業務流的項數l，每項對應一個先驗計數型布魯姆過濾器；對每一項進行哈希運算，生成每一項對應每個先驗計數型布魯姆過濾器的哈希地址；查找每一項對應的每個哈希地址對應的計數器；循環每個先驗計數型布魯姆過濾器中對應的計數器；若所述每一項中每個計數器的值都大於等於預設閾值，或者每項對應的計數器的循環次數等於先驗計數型布魯姆過濾器的個數，則判定所述業務流為l-項長流，並在所述每一項中每個計數器的值加1後，返回所述確定業務流的項數l的步驟。本發明實施例以實現對高速網絡中實時在線的長流進行識別和統計，適應高速網絡中的流量測量需求。
文檔編號H04L12/26GK101459560SQ20091000074
公開日2009年6月17日 申請日期2009年1月9日 優先權日2009年1月9日
發明者鵬 伊, 劉勤讓, 震 張, 涓 申 申請人:中國人民解放軍信息工程大學