隨著網(wǎng)絡(luò)靈活性、可擴展性和可編程性的提高,網(wǎng)絡(luò)規(guī)模和鏈路帶寬的不斷增大,網(wǎng)絡(luò)行為變得更加復(fù)雜和多樣化,這些均對網(wǎng)絡(luò)管理和安全防護提出了更高的要求。網(wǎng)絡(luò)流量測量作為網(wǎng)絡(luò)領(lǐng)域的研究熱點,不僅是實現(xiàn)智能、可靠網(wǎng)絡(luò)管理的前提,而且在網(wǎng)絡(luò)性能診斷、異常檢測、服務(wù)質(zhì)量保障及安全防護等方面發(fā)揮了重要作用。隨著對網(wǎng)絡(luò)流量精細化管理以及智能調(diào)度的需要,如何在巨大的網(wǎng)絡(luò)流量場景下利用有限的內(nèi)存和計算資源來滿足嚴格的精度、包處理速率以及多任務(wù)測量的需求,是當前網(wǎng)絡(luò)流量測量技術(shù)發(fā)展所面臨的挑戰(zhàn),也是世界各地研究人員的努力方向。本文首先給數(shù)據(jù)報文引入了序列值的概念,序列值是根據(jù)數(shù)據(jù)報文的出現(xiàn)次序賦予的值,序列值間隔可以用于衡量數(shù)據(jù)流的出現(xiàn)密度,然后通過對數(shù)據(jù)流的統(tǒng)計研究,發(fā)現(xiàn)了大象流與老鼠流在序列值間隔上的顯著區(qū)別,并將這個結(jié)論加以推廣,在此基礎(chǔ)上,提出了基于Sketch結(jié)構(gòu)的網(wǎng)絡(luò)流量測量算法——Seq Sketch,其采用了大象流和老鼠流分離的思想,在普遍應(yīng)用數(shù)據(jù)流頻率進行區(qū)分的基礎(chǔ)上,將序列值間隔這一特征用來對大象流進行篩選,從而實現(xiàn)更為精確高效的流量測量。整個算法結(jié)構(gòu)由哈希表和Sketch結(jié)構(gòu)兩部分組成,... 

【文章來源】：哈爾濱工業(yè)大學黑龍江省 211工程院校 985工程院校

【文章頁數(shù)】：64 頁

【學位級別】：碩士

【部分圖文】：

基于計數(shù)器結(jié)構(gòu)的示意圖

哈爾濱工業(yè)大學工程碩士學位論文-9-法沒有舍棄任何一個數(shù)據(jù)項，而是在遇到哈希沖突時將所有信息疊加到一起。顯而易見的時，隨著測量過程的累積，最終的測量結(jié)果往往也會偏離真實值；Sketch方法的另一個誤差來源是數(shù)組元素的數(shù)據(jù)共享，由于允許哈希沖突的存在，Sketch中的計數(shù)器可以由哈希值相同的多個鍵值不同的元素共享，因此導(dǎo)致部分數(shù)據(jù)與真實值相比偏差較大，比如如果大象流和老鼠流哈希映射的位置相同，那么老鼠流也會共享大象流的計數(shù)結(jié)果。因此對于不同的Sketch測量方法而言，主要區(qū)別在于如何控制真實值與測量值的誤差。Count-Sketch[16]利用數(shù)學期望的方法來減少誤差，而Count-MinSketch[17]取K個返回值中的最小值來控制誤差，AugmentedSketch[32]和ElasticSketch[19]采用分離大象流和老鼠流的策略，將大象流記錄在第一層哈希表中，而將老鼠流記錄在下層Sketch結(jié)構(gòu)中，減小了大象流和老鼠流的沖突，提高了測量精確度。圖2-2Sketch算法示意圖2.2網(wǎng)絡(luò)流量測量算法舉例本節(jié)將分別介紹幾種典型的基于計數(shù)器方法和基于Sketch的算法，并闡述其各自的優(yōu)缺點并進行比較。2.2.1基于計數(shù)器結(jié)構(gòu)的算法（1）頻率算法頻率算法(frequentalgorithm)[14]，受最大投票算法(majorityvotealgorithm)[20]啟發(fā)，是一種大象流統(tǒng)計算法，主要用于查詢數(shù)據(jù)流的top-k元素，該算法通過設(shè)置長度為k的計數(shù)器來找出頻率超過N/（k+1）的大象流，其處理每一個數(shù)據(jù)報文需要的時間復(fù)雜度為O（1）。算法思路如下：首先將計數(shù)器初始化為空，對于每一個輸入項，如果已經(jīng)存在計數(shù)器中，則相應(yīng)值增加，如果不存在且此時有空計數(shù)器，則執(zhí)行插入操作，如果計數(shù)器已被不同的數(shù)據(jù)項占據(jù)，則將所

AugmentedSketch結(jié)構(gòu)


本文編號：3132648