夏靖波，任高明

（1.廈門大學 嘉庚學院，福建 廈門　363105；2.空軍工程大學 信息與導航學院，陜西 西安　710077）

網(wǎng)絡流量分布式測量新方法

夏靖波1，任高明2

（1.廈門大學 嘉庚學院，福建 廈門363105；2.空軍工程大學 信息與導航學院，陜西 西安710077）

主機連接度作為網(wǎng)絡流量測量的一個重要測度，近年來倍受關注。針對現(xiàn)有主機連接度測量方法不能應用于大型網(wǎng)絡的問題，提出了一種基于位域的主機連接度分布式測量方法。方法在借鑒共享存儲單元思想的基礎上，使用哈希函數(shù)將到達的數(shù)據(jù)包映射至位域存儲；測量完成后，將各測量點采集得到的位域按位取或，并利用極大似然估計方法估算主機連接度值，有效地解決了分布式測量中各點采集數(shù)據(jù)難以融合的關鍵問題。最后，通過理論推導和實驗證明了方法的有效性和準確性。

計算機網(wǎng)絡；網(wǎng)絡流量；分布式測量；主機連接度

流量測量是理解網(wǎng)絡行為和掌握網(wǎng)絡運行規(guī)律的有效方法之一，主機連接度測量作為其重要組成部分，對網(wǎng)絡安全檢測等應用具有非常重要的意義。通常，主機連接度定義為測量時間內和某一源主機發(fā)生關聯(lián)的不同目的主機的數(shù)目。在檢測端口掃描、蠕蟲傳播、DDoS攻擊時均可用到主機連接度測量，因為端口掃描和蠕蟲傳播是由在短時間內源主機與不同目的主機建立大量的連接引起的［1］；另外，大型的服務器廠家可通過主機連接度測量去分析服務器內容的受歡迎程度等等。

隨著互聯(lián)網(wǎng)的高速化、復雜化以及網(wǎng)絡規(guī)模的不斷擴大，主機連接度測量的難度越來越大。單點測量由于獲取的信息有限，往往難以反映整個網(wǎng)絡的運行狀況。分布式測量具有單點測量無法比擬的優(yōu)勢，通過在大型網(wǎng)絡的不同節(jié)點部署多個測量設備，綜合測量結果可以得到較為詳盡、全面的信息，進而推斷出全網(wǎng)運行狀況。但大型網(wǎng)絡中主機連接度的分布式測量問題非常有挑戰(zhàn)性，原因有二：一是網(wǎng)絡鏈路傳輸速率愈來愈高，要求必須在更短的時間內處理單位數(shù)據(jù)分組；二是獲取全網(wǎng)范圍的主機連接度，需要融合各測量點采集到的信息。上述兩個條件均增加了主機連接度測量的難度。

1　相關工作

測量主機連接度，最直接的方法是記錄測量時間內兩兩不同的連接對［2-3］（連接對是指一個數(shù)據(jù)包的源地址和目的地址構成的地址對）。測量結束后，統(tǒng)計得到的每個源地址對應的連接對數(shù)目，即為該源地址的主機連接度。同時，文獻［2］提出使用哈希表存儲連接對，提高了處理效率。該方法的缺點是所需存儲空間大。

文獻［4］提出使用兩個哈希表存儲的方式估算主機連接度。一個哈希表用于存儲連接對，另一個用于存儲源地址和連接對計數(shù)；同時，引入抽樣機制用于降低處理數(shù)據(jù)量。和直接測量法相比較，該方法可以支持快速查詢操作，但抽樣方法降低了測量準確率。文獻［5］引入位圖減小所需存儲空間，較好地節(jié)省了空間資源，每個連接對只需占用1 bit的存儲空間，但是該方法的空間利用率和準確率之間的平衡難以把握。

文獻［6］提出共享位圖的思想，提高了空間利用率，可以在較小空間條件下，準確地測量主機連接度，但由于無法完成測量數(shù)據(jù)的融合，不能直接應用于大型網(wǎng)絡的分布式測量。例如，當某個數(shù)據(jù)包P依次通過圖1中的B、C、D節(jié)點，假定在B、C、D 3個節(jié)點均布置了測量設備，那么，P將被測量并記錄3次。在融合測量記錄時，假設B、C、D節(jié)點對應的記錄中，源地址S的連接度分別為10，20，15，那么全網(wǎng)內源地址S的連接度究竟是多少？是最大值20？還是45？本文正是針對主機連接度的分布式測量中存在的測量數(shù)據(jù)融合問題，提出一種新的測量方法，實現(xiàn)大型網(wǎng)絡的主機連接度測量。

圖1　分布式網(wǎng)絡測量結構Fig.1　The structure of distributed measurement

2　分布式主機連接度測量方法

單點測量是分布式測量的基礎，分布式測量是單點測量的融合。文章借鑒文獻［3］提出的主機連接度單點測量方法CSE，提出一種可用于大型網(wǎng)絡的分布式主機連接度測量方法（文中稱為DSM方法）。

2.1單點測量

CSE方法中用于存儲主機連接度信息的是一個長度為m的位域。當有數(shù)據(jù)包p到達時，根據(jù)哈希函數(shù)H（src⊕R［H （des⊕K）mods］）確定數(shù)據(jù)包在位域中的位置，其中src為p的源地址，dst為P的目的地址；k為防止哈希碰撞攻擊而引入的關鍵字；H為哈希函數(shù)，后文實驗部分分別選取MD5和SHA1兩種哈希函數(shù)，對測量結果進行了比較。根據(jù)極大似然估計，推導后得到源地址src的主機連接度的估計值為

其中s為邏輯位域的長度，Vs是LB（src）中0所占的比例，Vm為位域中0所占的比例。具體推導過程請參考文獻［3］，在此不再贅述。

2.2分布式測量

為解決主機連接度分布式測量中各測量點存儲記錄的融合問題，本文方法實現(xiàn)時，在多個節(jié)點布置測量設備，并為每個測量點分配一個長度為m的位域，分別記為BF1、BF2…BFn，n為測量點的個數(shù)。每個測量點，使用相同的哈希函數(shù)H，按照單點測量方法，將通過各測量點的數(shù)據(jù)包記錄至對應的位域中。在測量結束后，將各位圖按位取或，得到的位域表示為BF，即為全網(wǎng)主機連接度信息。

根據(jù)單點測量中估算方法，從位域BF中估算主機連接度即可。

2.3復雜度分析

2.3.1時間復雜度

在流量測量領域，通常使用哈希查找次數(shù)和內存讀寫次數(shù)作為衡量算法時間復雜度的性能指標。在高速網(wǎng)絡鏈路中，流量測量面臨的主要困難之一是單位數(shù)據(jù)包的處理時間越來越短，這就要求算法處理單位數(shù)據(jù)包的操作次數(shù)盡量少。本文方法根據(jù)到達數(shù)據(jù)包的連接對信息，只需使用1個哈希函數(shù)H進行1次哈希查找，即可完成連接對至位圖的定位；之后，只用1次寫操作，即可置位圖中相應的位置為1，完成信息的記錄。

2.3.2空間復雜度

根據(jù)位共享的思路，單點測量中，位圖的長度為m，即所需的存儲空間為m bit。在分布式測量中，每個測量點所需空間和單點測量相同，整個分布式結構共需的存儲空間為各測量點所需空間之和n×m bit。

2.3.3實現(xiàn)的考慮

在處理速度方面，采用哈希查找的方式確定位圖的位置，可以實現(xiàn)時間復雜度為O（1）的查找速度；為實現(xiàn)高速網(wǎng)絡環(huán)境中數(shù)據(jù)包的線速處理，考慮采用處理速度較快的SRAM，由前述易知，處理單位數(shù)據(jù)包需要訪問內存的次數(shù)為1次，根據(jù)當前硬件技術，SRAM具備2 ns完成1次操作的處理速度，意味著本文方法處理一個數(shù)據(jù)包只需要2 ns。在OC-768鏈路上，假定滿速率傳輸包長為64 byte的數(shù)據(jù)包，則包到達間隔為12.5 ns，說明本文方法的處理速度完全滿足OC-768鏈路的測量需求。

3　實驗驗證

3.1實驗一

文獻［3］提出的CSE方法采用位共享思路，準確率高，速度快，但文中并沒有明確指出使用什么哈希函數(shù)，而哈希函數(shù)的選擇合理與否，對于測量結果的準確性來說，非常重要。因此，實驗一選擇MD5和SHA1兩種常用的哈希函數(shù)，應用于CSE方法，比較二者測量主機連接度的準確性，后文分別稱之為CSE_MD5和CSE_SHA1。為保證兩種方法具有可比性，選擇和文獻［3］相同的參數(shù)，即存儲空間分別取4 M，2 M，1 M，0.5 M。

所用仿真環(huán)境如下：仿真工具為MATLAB R2010a；計算機cpu為pentium（R）Dual-Core，主頻2.69 GHz；內存3G；操作系統(tǒng)為windows XP SP3。實驗數(shù)據(jù)取自CAIDA提供的實際互聯(lián)網(wǎng)數(shù)據(jù)，該數(shù)據(jù)采集于2011年某2.5 G鏈路。

圖2　CSE_MD5、CSE_SHA1兩種方法測量結果Fig.2　The two measure results of CSE_MD5 and CSE_SHA1

如圖2所示，為CSE_MD5方法和CSE_SHA1兩種方法測量主機連接度的結果，圖中每個點表示一個源地址的主機連接度，橫軸為該源地址的真實主機連接度值，縱軸為對應的估計值。對于實驗數(shù)據(jù)中主機連接度真實值相同的多個源，本文只隨機選擇一個點展示在圖中。圖2中（a）～（d）分別表示存儲空間取4M、2M、1M和0.5M時CSE_MD5的測量結果。圖2中的四組圖（e）～（h）分別表示存儲空間取4M、2M、1M和0.5M時CSE_SHA1的測量結果。測量圖中的點越靠近直線y=x周圍，估算方法越準確。表1列出了CSE_MD5和CSE_SHA1兩種方法的測量主機連接度的平均誤差。

結合圖3和表1可以得出以下結論：隨著分配空間的減小，兩種方法的準確率均下降；在分配相同存儲空間的情況下，兩種哈希函數(shù)應用于CSE方法中測量主機連接度時，MD5的準確率稍高于SHA1方法，但優(yōu)勢并不明顯。

表1　兩種方法測量主機連接度的平均誤差Tab.1　Average error of two measure spreader

3.2實驗二

本文提出的分布式主機連接度測量方法，主要貢獻是解決了分布式測量中各測量點采集數(shù)據(jù)的融合問題。為驗證文中方法的分布式測量特性，按照圖1所示的結構圖，在實驗室搭建模擬環(huán)境，其中A～F均表示交換機，每個交換機連接若干計算機；在除C點以外的其余5個節(jié)點布置測量設備，對采集到的數(shù)據(jù)包信息按照本文提出的分布式測量方法進行融合。同時，使用上文提到的直觀方法，測量通過各節(jié)點的數(shù)據(jù)包的主機連接度，和本文方法的估計值進行比較，結果如圖3所示，其中圖（a）至（d）依次為存儲空間取4 M，2 M，1 M，0.5 M時的測量結果。表4給出了4種存儲空間條件下，文中方法的誤差變化圖。根據(jù)圖3和圖4易知，本文提出的分布式測量方法，對于全網(wǎng)主機連接度的測量具有較好的效果，在存儲空間為4 M和2 M時，誤差能保持在較小的范圍內。

圖3　分布式測量結果Fig.3　The result of distributed measurement

4　結束語

主機連接度測量對于網(wǎng)絡安全等應用意義重大。網(wǎng)絡規(guī)模的不斷擴大，使得大型網(wǎng)絡的主機連接度測量成為急切需要解決的問題。針對現(xiàn)有的主機連接度測量方法無法直接應用于大型網(wǎng)絡的缺點，本文提出一種分布式主機連接度測量，在借鑒CSE方法中存儲單元共享思路的基礎上，提出對存儲位域按位取并的方法解決分布式測量結構中各測量點數(shù)據(jù)的融合問題［7］。在分析算法的時間復雜度和空間復雜度后，結合當前半導體發(fā)展水平，給出了方法的可實現(xiàn)性。最后，使用實際互聯(lián)網(wǎng)數(shù)據(jù)和實驗室搭建網(wǎng)絡環(huán)境采集的數(shù)據(jù)對方法進行了評價。結果表明該方法在保持準確性的同時，具有較好的實用性。

圖4　誤差比較圖Fig.4　The comparison of error

［1］周愛平，程光，郭曉軍.高速網(wǎng)絡流量測量方法［J］.軟件學報，2014，25（1）：135-153.

［2］Yoon M，Chen S.Real-Time Detection of Invisible Spreaders ［C］//Global Telecommunications Conference，2008.IEEE GLOBECOM 2008.IEEE.IEEE，2008：1-5.

［3］Yoon M，Li T，Chen S，et al.Fit a Spread Estimator in Small Memory［C］//INFOCOM 2009，IEEE.IEEE，2009：504-512.

［4］Venkatataman S，Song D，Gibbons P，et al.new streaming algorithms for fast detection of super spreaders.In：Proceeding of NDSS.2005.

［5］Estan C，Varghese G，F(xiàn)ish M.Bitmap algorithms for counting active flows on high-speed links.Proceeding IMC 03Proceedings of the 3rd ACM conference on Internet measurement，2003：153-166.

［6］Li T，Chen S.Traffic measurement on the internet.2012.

［7］徐敏，夏靖波，申健，等.基于LEAST的高速網(wǎng)絡大流檢測算法［J］.空軍工程大學學報，2015（8）：25-30.

Novel algorithm for distributed measurement of network traffic

XIA Jing-bo1，REN Gao-ming2
（1.Tan Kahkee Cooege，Xiamen University，Xiamen 363105，China；2.School of Information and Navigation，Air Force Engineering University，Xi’an 710077，China）

The spreader is paid more attention as an important content of network traffic measurement in recent years.To address the problem of the existing spreader measurement algorithms can’t be applied to large-scale network，a novel distributed measurement algorithm of spreaders is proposed.A hash function is used by the algorithm based on dynamic bit sharing to map the packet data to bit field.The bit fields collected from all measurement point is OR by bit to bit and MLE method is used to estimate the spreaders.The algorithm integrates data in distributed measurement point effectively.Finally， the algorithm is proved to be effective and accuracy through theoretical and experiments.

computer network；network traffic；distributed measurement；spreader

TN91

A

1674－6236（2016）03-0137-04

2015-03-29稿件編號：201503424

陜西省自然科學基礎研究計劃項目（2012JZ8005）

夏靖波（1963—），男，河北秦皇島人，教授。研究方向：網(wǎng)絡管理和網(wǎng)絡測量。