發(fā)布時(shí)間：2021-04-12 04:47

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

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

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

【學(xué)位級(jí)別】：碩士

【部分圖文】：

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

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

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


本文編號(hào)：3132648