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

夏靖波，任高明

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

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

夏靖波1，任高明2

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

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

計(jì)算機(jī)網(wǎng)絡(luò)；網(wǎng)絡(luò)流量；分布式測(cè)量；主機(jī)連接度

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

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

1　相關(guān)工作

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

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

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

圖1　分布式網(wǎng)絡(luò)測(cè)量結(jié)構(gòu)Fig.1　The structure of distributed measurement

2　分布式主機(jī)連接度測(cè)量方法

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

2.1單點(diǎn)測(cè)量

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

其中s為邏輯位域的長(zhǎng)度，Vs是LB（src）中0所占的比例，Vm為位域中0所占的比例。具體推導(dǎo)過程請(qǐng)參考文獻(xiàn)［3］，在此不再贅述。

2.2分布式測(cè)量

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

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

2.3復(fù)雜度分析

2.3.1時(shí)間復(fù)雜度

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

2.3.2空間復(fù)雜度

根據(jù)位共享的思路，單點(diǎn)測(cè)量中，位圖的長(zhǎng)度為m，即所需的存儲(chǔ)空間為m bit。在分布式測(cè)量中，每個(gè)測(cè)量點(diǎn)所需空間和單點(diǎn)測(cè)量相同，整個(gè)分布式結(jié)構(gòu)共需的存儲(chǔ)空間為各測(cè)量點(diǎn)所需空間之和n×m bit。

2.3.3實(shí)現(xiàn)的考慮

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

3　實(shí)驗(yàn)驗(yàn)證

3.1實(shí)驗(yàn)一

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

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

圖2　CSE_MD5、CSE_SHA1兩種方法測(cè)量結(jié)果Fig.2　The two measure results of CSE_MD5 and CSE_SHA1

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

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

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

3.2實(shí)驗(yàn)二

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

圖3　分布式測(cè)量結(jié)果Fig.3　The result of distributed measurement

4　結(jié)束語

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

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

［1］周愛平，程光，郭曉軍.高速網(wǎng)絡(luò)流量測(cè)量方法［J］.軟件學(xué)報(bào)，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)絡(luò)大流檢測(cè)算法［J］.空軍工程大學(xué)學(xué)報(bào)，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稿件編號(hào)：201503424

陜西省自然科學(xué)基礎(chǔ)研究計(jì)劃項(xiàng)目（2012JZ8005）

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