高速網(wǎng)絡(luò)流量測量關(guān)鍵問題研究.pdf

1、網(wǎng)絡(luò)流量測量是了解網(wǎng)絡(luò)運行狀況和理解網(wǎng)絡(luò)行為的基礎(chǔ)。隨著帶寬的快速增加和互聯(lián)網(wǎng)的普及，將面臨網(wǎng)絡(luò)流量測量的新挑戰(zhàn)。由于海量網(wǎng)絡(luò)流量數(shù)據(jù)與有限系統(tǒng)資源之間的矛盾存在，傳統(tǒng)的流量測量算法已經(jīng)很難滿足高速網(wǎng)絡(luò)應(yīng)用需求。近年來，多核技術(shù)已成為當前處理器體系架構(gòu)發(fā)展的必然趨勢。另外，隨著云計算技術(shù)的推廣，云計算平臺具有對海量網(wǎng)絡(luò)流量數(shù)據(jù)進行并行分布式處理的強大能力。因此，基于多核技術(shù)與云計算平臺的并行分布式設(shè)計成為提高網(wǎng)絡(luò)流量測量算法性能的有效途

2、徑。盡管網(wǎng)絡(luò)流量測量算法廣泛應(yīng)用于網(wǎng)絡(luò)安全、網(wǎng)絡(luò)計費及流量工程等領(lǐng)域，但在高速網(wǎng)絡(luò)環(huán)境下還有許多網(wǎng)絡(luò)流量測量問題需要研究與解決。
　　本論文圍繞流量突發(fā)性，提出相關(guān)模型和流量測量算法，解決高速網(wǎng)絡(luò)環(huán)境下流量測量面臨的關(guān)鍵問題，為網(wǎng)絡(luò)運行和管理提供有力支撐。從流量突發(fā)性角度，提出峰值流量測度，分析網(wǎng)絡(luò)行為和建立合理的容量規(guī)劃模型，為新建校園網(wǎng)的接入帶寬提供準確評估;針對網(wǎng)絡(luò)流量分布的重尾特性和MapReduce算法中負載不均衡問題，

3、提出一種MapReduce框架下基于自適應(yīng)抽樣的大流識別方法;針對基于流抽樣的超點檢測方法存在計算負荷重、檢測精度低、實時性差問題，提出超點檢測的并行數(shù)據(jù)流方法;為了滿足長持續(xù)時間流檢測的高速網(wǎng)絡(luò)應(yīng)用需求，設(shè)計了基于共享數(shù)據(jù)結(jié)構(gòu)的長持續(xù)時間流的并行檢測方法和基于獨立數(shù)據(jù)結(jié)構(gòu)的長持續(xù)時間流的并行檢測方法，基于獨立數(shù)據(jù)結(jié)構(gòu)的長持續(xù)時間流檢測方法更好地滿足高速網(wǎng)絡(luò)的應(yīng)用需求。實驗驗證了上述模型和算法的有效性。論文的主要工作和創(chuàng)新點為:

4、　　(1)從流量突發(fā)性角度，提出峰值流量測度，分析網(wǎng)絡(luò)行為和建立一種合理的容量規(guī)劃模型，為新建校園網(wǎng)的接入帶寬提供準確評估。首先，通過假設(shè)檢驗和擬合優(yōu)度檢驗表明峰值流量服從漸近高斯分布，通過自相關(guān)性分析表明峰值流量間彼此相互獨立;其次，研究網(wǎng)絡(luò)內(nèi)在特征對峰值流量的影響，一方面，通過統(tǒng)計學(xué)方法建立方差分析模型，研究接入帶寬與峰值流量之間的關(guān)系，分析表明接入帶寬對峰值流量的影響較小，另一方面，通過統(tǒng)計學(xué)方法建立協(xié)方差分析模型，研究接入帶寬、

5、網(wǎng)絡(luò)用戶數(shù)與峰值流量之間的關(guān)系，分析表明接入帶寬與網(wǎng)絡(luò)用戶數(shù)存在較強的相關(guān)性，網(wǎng)絡(luò)用戶數(shù)是影響峰值流量的主要因子;最后，在上述分析的基礎(chǔ)上建立線性回歸模型及容量規(guī)劃模型。通過實驗驗證容量規(guī)劃模型的有效性。
　　(2)針對網(wǎng)絡(luò)流量分布的重尾特性和MapReduce算法中負載不均衡問題，提出了一種MapReduce框架下基于自適應(yīng)抽樣的大流識別方法。由于MapReduce框架中通過Hash函數(shù)按照分組將任務(wù)分配到每個reducer，如

6、果分組服從均勻分布，那么每個reducer被分配相同的任務(wù)數(shù)，reducer之間是負載均衡的;如果分組服從偏態(tài)分布，那么每個reducer被分配不相同的任務(wù)數(shù)，導(dǎo)致reducer之間負載不均衡。另外，通過自適應(yīng)抽樣技術(shù)得到準確的流長分布估計，同時可以極大地減少所需的計算和存儲資源。方法的實施中，一個MapReduce作業(yè)通過自適應(yīng)抽樣過程獲得原始流長分布估計，在此基礎(chǔ)上制定數(shù)據(jù)劃分策略;另一個MapReduce作業(yè)通過數(shù)據(jù)劃分策略指導(dǎo)大

7、流識別。理論分析表明通過自適應(yīng)抽樣獲得的流長分布估計是無偏的，通過配置參數(shù)可以控制流長分布估計的相對誤差。實驗結(jié)果表明，與默認的基于Hash函數(shù)的數(shù)據(jù)劃分方法和TopCluster相比，提高了大流識別方法的性能，實現(xiàn)了reducer之間的負載均衡。
　　(3)針對基于流抽樣的超點檢測方法存在計算負荷重、檢測精度低、實時性差問題，提出了一種超點檢測的并行數(shù)據(jù)流方法。隨著多核處理器的發(fā)展，并行設(shè)計成為算法性能提高的一種有效途徑。首先，

8、為每個線程建立本地Sketch數(shù)據(jù)結(jié)構(gòu)，當報文到達時，通過多個Hash函數(shù)運算，將Sketch數(shù)據(jù)結(jié)構(gòu)中對應(yīng)位置為1，當測量時間周期結(jié)束后，對多個本地Sketch數(shù)據(jù)結(jié)構(gòu)進行合并;其次，估計節(jié)點的鏈接度，確定超列;最后，利用定理5.1對Sketch數(shù)據(jù)結(jié)構(gòu)中任意兩個超列的組合進行逆計算構(gòu)造節(jié)點的IP地址，估計節(jié)點的鏈接度，如果節(jié)點鏈接度大于閾值，則認為該節(jié)點是超點。重復(fù)上述步驟，直到處理完所有的超列組合。性能分析和實驗結(jié)果表明，該方法具

9、有良好的檢測精度和較低的開銷。
　　(4)為了滿足長持續(xù)時間流檢測的高速網(wǎng)絡(luò)應(yīng)用需求，在多核硬件平臺上，從共享數(shù)據(jù)結(jié)構(gòu)和獨立數(shù)據(jù)結(jié)構(gòu)角度設(shè)計長持續(xù)時間流的并行檢測方法。由于基于共享數(shù)據(jù)結(jié)構(gòu)的長持續(xù)時間流檢測方法中不同線程之間共享數(shù)據(jù)結(jié)構(gòu)（Cuckoo Hash表），共享數(shù)據(jù)結(jié)構(gòu)讀操作遠多于寫操作，引入讀寫鎖來實現(xiàn)線程之間的同步，導(dǎo)致線程之間的同步開銷過大，不能夠滿足高速網(wǎng)絡(luò)的長持續(xù)時間流檢測應(yīng)用需求。針對上述問題，基于獨立數(shù)據(jù)結(jié)構(gòu)