[發明專利]長流的識別方法、數據流量的測量方法及其設備

有效

• 申請號: 200910000747.6
• 申請日: 2009-01-09
• 公開（公告）號: CN101459560A
• 公開（公告）日: 2009-06-17
• 發明（設計）人: 伊鵬;劉勤讓;張震;申涓
• 申請（專利權）人: 中國人民解放軍信息工程大學
• 主分類號: H04L12/26
• 分類號: H04L12/26;H04L12/56
• 代理公司: 北京集佳知識產權代理有限公司
• 代理人: 逯長明

技術領域

本發明涉及計算機通信技術領域，特別涉及一種長流的識別方法、數據流量的測量方法及及其設備。

背景技術

隨著現代互聯網規模的擴大、異質性的突出、以及網絡應用呈現的多樣性，人們迫切需要了解和掌握它在局部和整體范圍內所體現出的行為特征，以便更好地理解、設計和管理互聯網絡。網絡流量測量是研究流量工程和網絡行為學的基礎，可以通過對網絡流量的基本參數進行測量，比如包長分布、吞吐量、自相似系數等，根據測量的結果對網絡進行建模和分析，以便更好地掌握網絡行為的基本特征，保證網絡的健康運行。正是由于以上原因，使得網絡流量測量從網絡管理的分支中分離出來，成為一個獨立的網絡研究方向，并作為一個新的研究領域成為近年來的研究熱點。

對網絡流進行測量、統計后發現：流往往呈現很強烈的重尾分布特征，即大多流僅包含很少數目的報文，而很少一部分流卻攜帶著很大數目的報文。統計長流可以節省大量的存儲空間，使流量信息能夠存儲在高速的靜態隨機訪問存儲器(SRAM)中，提高處理網絡數據的速度。因此，高速網絡中，識別長流是進行準確流量測量的一種重要可擴展的解決方案。目前長流的識別方法主要是利用抽樣測量的技術，其具有代表性的算法主要有兩個：采樣控制(Sample?and?Hold)算法和多級過濾器(Multistage?Filters)算法。

所述Sample?and?Hold算法的基本思想是：當某個數據報文到達時，如果該報文所屬的流記錄在緩存中存在，則更新該流記錄；否則以一定的概率p采樣該報文，若該報文被抽中，則創建該流記錄。其中，對于在緩存中已經有記錄的流，以后屬于該流的報文均被抽樣。

所述Multistage?Filters算法的基本思想是：每級過濾器是一個計數器向量，每個報文到達時，通過哈希(Hash)函數映射到每級過濾器中的對應計數器上，然后更新對應計數器的值。如果每級過濾器相應的計數器都超過了預設的閾值，則認為該流是大流或長流，然后緩存該流。

但是，在上述兩種方案中，對于流的識別和統計，需要實時在線地維護五元組的信息，這對于主干路由器的資源占用是難以接受的。而評價性能優劣的首要指標是算法的時間復雜度和空間復雜度。目前，一種特殊的基于哈希算法的數據結構：布魯姆過濾器(Bloom?Filter)能夠很好地解決上述問題，它能快速地鑒別流的信息，并能把TCP流的信息維護從96比特的五元組映射到很短的哈希串所代表的空間，極大地減少了由于維護五元組信息而帶來的資源開銷。

其中，布魯姆過濾器表示信息的方式精簡，是一種能夠表示集合、支持集合查詢的精簡數據結構。與傳統的查詢算法相比，大大節約了存儲空間。也就是說，傳統的樹型結構和散列查詢算法存儲空間與元素自身大小和集合規模直接相關，而布魯姆過濾器查詢算法所需空間與元素自身大小無關，僅與元素映射到的向量位數相關，這就大大節約了存儲空間。下面簡單介紹兩種基本的布魯姆過濾器。

一種是：標準布魯姆過濾器(SBF，Standard?Bloom?Filter)

SBF算法的核心是：一個V向量和一組Hash函數，其實現原理如圖1所示。具體實現過程為：設集合S＝{s₁，s₂，...，s_n}共有n個元素，通過k個Hash函數h₁，h₂，...h_k將集合S中的n個元素映射到長度為m的向量V中。每一個Hash函數相互獨立，且函數的取值范圍為{0，1，2，...，m-1}。集合S到向量V的映射過程為：向量V初始化，即將向量V的所有比特位置0；當元素插入集合S時，對于每一個元素s_i，計算h_j(s_i)(1≤j≤k)，若h_j(s_i)＝q，則令SBF[q]＝1，將向量對應的位置置位；當查詢元素是否屬于集合S時，對于給定的元素x，檢查向量V的k個位置(h₁(x)，h₂(x)，...h_k(x))是否為1。如果其中有一個為0，則若全部值為1，則x可能屬于S中。此時就可能出現“假陽性誤判”，即將不屬于集合的元素誤判成屬于該集合，但不會出現“假陰性誤判”(即將屬于集合的元素誤判成不屬于該集合)。