利用抽樣技術(shù)和分層多哈希方法實現(xiàn)長流的識別

1、利用抽樣技術(shù)和分層多哈希方法實現(xiàn)長流的識別摘要：本文提出了一種利用抽樣技術(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)測和分析?，F(xiàn)代網(wǎng)絡(luò)面臨的又一 緊迫任務(wù)

2、是為用戶提供可靠的業(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 算法。 sampleand hold 算法是按照一定的概率對字節(jié)進行抽樣，如果一個 報文被抽到，且其所屬的流標識未被創(chuàng)建，則以概率P 創(chuàng)建這個流標識 ; 而一個流的標識在內(nèi)存中已經(jīng)存在， 則更新屬于

3、該流標識的報文的記錄。這種方法可以較精確地識別長流， 所用的內(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)域也有很大的研究，提出了多種識別長流的方法。二、識別過程（一）分層隨機抽樣 分層隨機抽樣：如果每層中的抽樣都是獨立地按照簡單 隨機抽樣進行的，那么

4、這樣的抽樣稱為分層隨機抽樣，所得 的樣本稱為分層隨機樣本。分層隨機抽樣由于抽樣在每一層中獨立進行，所以各層 的數(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ù)

5、空間的數(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個1m之間的數(shù)，并把存儲 空間A中的這K個對應(yīng)比特位置1。也可以利用哈希函數(shù)集 合H的映射過程來檢驗 是否屬于集合So下面的兩個算法分 別描述了源串集合S中的元素被哈希到存儲空間的過程和驗 證給定元素 是否屬于源串集合 S

6、的過程。（三）閾值的確定 識別長流的第一步就是要確定閾值。中給出了兩種確定 閾值的辦法。第一種方法是考慮到收集的數(shù)據(jù)集合存在著重 尾分布的特征。第二種方法更加的直接。閾值的確定會考慮 到操作的環(huán)境。它要求計算一個參數(shù)，這個參數(shù)與總通信量 有著密切的關(guān)系。利用這一參數(shù)可以把流分為兩類：一類就 是超出了這個參數(shù)值，我們這一類的流定義為長流。另一類 是沒有超過這個參數(shù)值，就把它們定義為短流。本文采用的確定閾值的方法類似第二種辦法。即在測量 的過程中利用一個計數(shù)器記錄總的報文數(shù)，設(shè)為M 。我們約定把占據(jù)報文總數(shù) 1%以上的流記為長流， 則閾值 T=M/100 。 在測量結(jié)束后， Bloom Filte

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

8、本步驟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)。把超

9、出閾值的信息存儲在存儲器中。圖 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 measurementJ.IEEE C o m m u n icat i o ns，1998， 36（ 8）：48-54 .2