景泉

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

關(guān)鍵詞：抽樣技術(shù);分層多哈希

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

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

一、國內(nèi)外研究概況、水平和發(fā)展趨勢

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

國內(nèi)的網(wǎng)絡(luò)測量研究起步較晚，近年研究網(wǎng)絡(luò)行為學(xué)逐步增加。長流占據(jù)了大部分的網(wǎng)絡(luò)通信量，了解長流的信息就能對一次通信行為有著很好的描述。長流識別在網(wǎng)絡(luò)測量領(lǐng)域也有很大的研究，提出了多種識別長流的方法。

二、識別過程

（一）分層隨機抽樣

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

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

（二）Bloom Filter的使用

Bloom Filter最早由Burton Bloom提出，并開始廣泛的應(yīng)用到數(shù)據(jù)庫領(lǐng)域中，最近在網(wǎng)絡(luò)研究中得到了廣泛的應(yīng)用，并取得了一些進展。如在高速網(wǎng)絡(luò)測量方面。

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

（三） 閾值的確定

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

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

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

（四）識別的基本步驟

1.構(gòu)建一個多哈希站的模塊，每個哈希站都存放一個獨立的哈希函數(shù)

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

3.統(tǒng)計在某一時間粒度下總的報文數(shù)，并計算閾值。

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

5.統(tǒng)計每個流的報文數(shù)，把超過閾值的流記錄下來。

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

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

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

三、結(jié)論

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

參考文獻：

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

[2]彭艷兵，龔儉，劉衛(wèi)江，等. Bloom Filter哈?？臻g的元素還原[J]. 電子學(xué)報，2006，34（5）：822-827.

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