利用抽樣技術和分層多哈希方法實現長流的識別

景泉

摘要：本文提出了一種利用抽樣技術和分層多哈希的方法來識別長流，選取合適的哈希函數，能夠方便還原出五元組信息，減少了資源的開銷;使用多哈希函數，可以極大的降低哈希沖突，保證數據的準確性。

關鍵詞：抽樣技術;分層多哈希

中圖分類號：TP393.08 文獻識別碼：A 文章編號：1001-828X（2016）005-000-01

隨著互聯網規模和用戶數量的迅速擴大，導致網絡流量不斷增大，網絡行為越劇復雜，安全攻擊的頻率和對網絡造成的破壞性也在急劇的增長。為了更好的保障網絡安全，需要對網絡流量進行有效的監測和分析。現代網絡面臨的又一緊迫任務是為用戶提供可靠的業務質量保障。而用戶獲得的服務質量以及網絡供應商可提供的服務能力都必須通過流量數據分析獲得。因此，研究網絡流量特性是改善網絡服務質量問題的一個關鍵。而網絡流量測量技術是目前唯一能用于分析網絡狀況、掌握流量特性的有效方法。

一、國內外研究概況、水平和發展趨勢

Cristian Estan在長流識別的過程中就提出了一種抽樣技術和哈希技術結合的算法——sample and hold算法。sample and hold 算法是按照一定的概率對字節進行抽樣，如果一個報文被抽到，且其所屬的流標識未被創建，則以概率P創建這個流標識;而一個流的標識在內存中已經存在，則更新屬于該流標識的報文的記錄。這種方法可以較精確地識別長流，所用的內存空間也較小，但它對每個報文進行處理的同時都要訪問內存，因此要求內存的速度達到線速，給測量系統帶來很大的壓力。同時哈希的過程中也會造成一定的沖突，導致一定的誤差。并且在哈希的過程中還要記錄流標識的信息，會帶來存儲空間的增加。

國內的網絡測量研究起步較晚，近年研究網絡行為學逐步增加。長流占據了大部分的網絡通信量，了解長流的信息就能對一次通信行為有著很好的描述。長流識別在網絡測量領域也有很大的研究，提出了多種識別長流的方法。

二、識別過程

（一）分層隨機抽樣

分層隨機抽樣：如果每層中的抽樣都是獨立地按照簡單隨機抽樣進行的，那么這樣的抽樣稱為分層隨機抽樣，所得的樣本稱為分層隨機樣本。

分層隨機抽樣由于抽樣在每一層中獨立進行，所以各層的數據可以用于對本層（子總體）進行較精確的參數估計，然后將這些總和全部累加，就能得到對總體的一個較精確的參數估計。使用分層隨機抽樣可使樣本中分布更加均勻，從而具有更好的代表性。這樣就避免了樣本分布不平衡的現象。

（二）Bloom Filter的使用

Bloom Filter最早由Burton Bloom提出，并開始廣泛的應用到數據庫領域中，最近在網絡研究中得到了廣泛的應用，并取得了一些進展。如在高速網絡測量方面。

Bloom Filter是一個基于多個哈希函數映射來壓縮參數空間的數據結構，它支持成員查詢、隨機存儲。其具體的工作原理是，它描述了一個源串的集合S={x1， x2…， xn}，我們把xi稱作是一個源串。申請一個內存大小為m比特位的存儲空間A，并定義一個哈希函數集合H={H1， H2，…， Hk}，我們把Hi稱作是一個哈希函數。對于源串集合S中的任何一個元素xi來說，通過集合H中的K個獨立的哈希函數映射到存儲空間A中，得到K個[1…m]之間的數，并把存儲空間A中的這K個對應比特位置1。也可以利用哈希函數集合H的映射過程來檢驗 是否屬于集合S。下面的兩個算法分別描述了源串集合S中的元素被哈希到存儲空間的過程和驗證給定元素 是否屬于源串集合S的過程。

（三） 閾值的確定

識別長流的第一步就是要確定閾值。中給出了兩種確定閾值的辦法。第一種方法是考慮到收集的數據集合存在著重尾分布的特征。第二種方法更加的直接。閾值的確定會考慮到操作的環境。它要求計算一個參數，這個參數與總通信量有著密切的關系。利用這一參數可以把流分為兩類：一類就是超出了這個參數值，我們這一類的流定義為長流。另一類是沒有超過這個參數值，就把它們定義為短流。

本文采用的確定閾值的方法類似第二種辦法。即在測量的過程中利用一個計數器記錄總的報文數，設為M。我們約定把占據報文總數1%以上的流記為長流，則閾值T=M/100。在測量結束后，Bloom Filter中具有相同流標識的報文的命中次數如果超出了T值，就把這個流識別出來。

然后，我們要在測量的時間內選用簡單的哈希函數對到來的報文按照報文頭中的流標識分組，并對分組后的流標識進行Counting Bloom Filter變換。測量結束后，利用第二部分中所介紹的長流的定義，對每個哈希空間中的命中次數加以統計，把超出閾值的流識別出來，并存儲在存儲器中。我們利用段地址重疊的比特還原出主機的原始信息。中指出活躍IP分布是非常不均勻的重尾分布，相鄰網段或者IP活躍度較大。但是他們的活躍度相差較大不會影響我們分析的結論，我們可以用短標簽重疊的比特進行糾正。

（四）識別的基本步驟

1.構建一個多哈希站的模塊，每個哈希站都存放一個獨立的哈希函數

2.利用分層哈希方法依次哈希到對應的存儲空間

3.統計在某一時間粒度下總的報文數，并計算閾值。

4.對TCP的五元組進行Counting Bloom Filter變換。

5.統計每個流的報文數，把超過閾值的流記錄下來。

6.對記錄下的長流進行原始信息的還原。

圖1利用Counting Bloom Filter進行長流識別的過程。結構體BF由兩個成員組成。分別攜帶了主機原始信息和經過哈希函數作用后所命中該存儲空間中的報文數。圖中把IP地址分為三段，每一段都維護一個相應的Bloom Filter數據結構。把超出閾值的信息存儲在存儲器中。

圖1 ?利用Counting Bloom Filter進行長流識別的過程

三、結論

本文使用抽樣技術和分層多哈希方法實現了長流的識別，利用Bloom Filter這種數據結構在識別長流的過程中可以不用維護五元組信息，降低了在維護五元組信息的過程中帶來的資源的開銷。經數據測試，本文提出的識別長流的算法在識別長流的同時，可以還原成五元組信息，使用多哈希可以降低沖突，保證數據的準確性。

參考文獻：

[1] Veru Paxson，Jamshid Mahdavi. Scale Internet measurement[J].IEEE Communications，1998， 36（8）：48-54.

[2]彭艷兵，龔儉，劉衛江，等. Bloom Filter哈希空間的元素還原[J]. 電子學報，2006，34（5）：822-827.

[3]龔儉，彭艷兵，楊望，等.基于Bloom Filter的大規模異常TCP連接參數再現方法[J].軟件學報， 2006，17（3）：434-444.