網絡流量分布式測量新方法

夏靖波，任高明

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

網絡流量分布式測量新方法

夏靖波1，任高明2

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

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

計算機網絡；網絡流量；分布式測量；主機連接度

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

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

1　相關工作

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

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

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

圖1　分布式網絡測量結構Fig.1　The structure of distributed measurement

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

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

2.1單點測量

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

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

2.2分布式測量

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

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

2.3復雜度分析

2.3.1時間復雜度

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

2.3.2空間復雜度

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

2.3.3實現的考慮

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

3　實驗驗證

3.1實驗一

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

所用仿真環境如下：仿真工具為MATLAB R2010a；計算機cpu為pentium（R）Dual-Core，主頻2.69 GHz；內存3G；操作系統為windows XP SP3。實驗數據取自CAIDA提供的實際互聯網數據，該數據采集于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兩種方法測量主機連接度的結果，圖中每個點表示一個源地址的主機連接度，橫軸為該源地址的真實主機連接度值，縱軸為對應的估計值。對于實驗數據中主機連接度真實值相同的多個源，本文只隨機選擇一個點展示在圖中。圖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可以得出以下結論：隨著分配空間的減小，兩種方法的準確率均下降；在分配相同存儲空間的情況下，兩種哈希函數應用于CSE方法中測量主機連接度時，MD5的準確率稍高于SHA1方法，但優勢并不明顯。

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

3.2實驗二

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

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

4　結束語

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

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

［1］周愛平，程光，郭曉軍.高速網絡流量測量方法［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，Fish 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的高速網絡大流檢測算法［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—），男，河北秦皇島人，教授。研究方向：網絡管理和網絡測量。