網(wǎng)絡(luò)流量測(cè)量是網(wǎng)絡(luò)管理中一項(xiàng)重要任務(wù)。然而隨著互聯(lián)網(wǎng)的飛速發(fā)展,網(wǎng)絡(luò)流量呈現(xiàn)爆炸式的增長(zhǎng),使得對(duì)高速網(wǎng)絡(luò)流量的測(cè)量面臨著很大的挑戰(zhàn)。Sketch是一種可以對(duì)數(shù)據(jù)流進(jìn)行存儲(chǔ)和匯總的方法,可以對(duì)數(shù)據(jù)流進(jìn)行測(cè)量和查詢,它有幾種典型的Sketch算法:Count-Min Sketch、CU Sketch和Count Sketch,可以將它應(yīng)用到網(wǎng)絡(luò)測(cè)量中來(lái)。但是由于網(wǎng)絡(luò)流量自身的特點(diǎn),在使用Sketch進(jìn)行測(cè)量時(shí)可能會(huì)產(chǎn)生大量的空間浪費(fèi),造成空間利用率低等問(wèn)題。此外,由于Sketch是使用散列函數(shù)對(duì)數(shù)據(jù)流進(jìn)行匯總,散列沖突會(huì)造成估計(jì)值的誤差,尤其是對(duì)于小流量。因此,本文的工作主要針對(duì)于空間利用率低和對(duì)小流量的過(guò)高估計(jì)這兩個(gè)問(wèn)題對(duì)網(wǎng)絡(luò)流量測(cè)量的算法進(jìn)行改進(jìn)。本研究首先引入進(jìn)位的思想,提出了將多個(gè)Sketch與Counting Bloom Filter（CBF）相結(jié)合的結(jié)構(gòu)——Self-Adaption Sketch（SA Sketch）。該結(jié)構(gòu)可以根據(jù)所需測(cè)量的網(wǎng)絡(luò)流量的大小動(dòng)態(tài)地申請(qǐng)空間、創(chuàng)建Sketch,并使用CBF來(lái)存儲(chǔ)當(dāng)前流量使用的Sketch的數(shù)量,從而提高空間的利用率。實(shí)驗(yàn)結(jié)果表明,... 

【文章來(lái)源】：南京郵電大學(xué)江蘇省

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

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

【部分圖文】：

Sketch的基本結(jié)構(gòu)

SASketch的結(jié)構(gòu)

南京郵電大學(xué)碩士研究生學(xué)位論文第四章基于布谷鳥哈希的SASketch優(yōu)化方法394.2.2優(yōu)化的數(shù)據(jù)結(jié)構(gòu)為了解決CBF的查詢錯(cuò)誤給SASketch的準(zhǔn)確性帶來(lái)的影響，本文基于布谷鳥哈希的哈希表和Sketch的特性，優(yōu)勢(shì)互補(bǔ)，將它們結(jié)合形成一個(gè)新的數(shù)據(jù)結(jié)構(gòu)——CBSASketch（Cuckoo-BasedSelf-AdaptionSketch）。該結(jié)構(gòu)將原結(jié)構(gòu)中的CBF部分改為布谷鳥哈希部分，并且對(duì)原來(lái)的布谷鳥哈希進(jìn)行一定的改進(jìn)，使得它適用于多層的Sketch結(jié)構(gòu)。圖4.3CBSASketch的數(shù)據(jù)結(jié)構(gòu)CBSASketch的結(jié)構(gòu)如圖4.3所示，由Sketch部分和布谷鳥哈希部分組成。Sketch部分包含n+1個(gè)Sketch，與SASketch的Sketch部分相同。布谷鳥哈希部分包含一個(gè)布谷鳥哈希表，其中包含M個(gè)哈希表，T1,T2,…,TM，并且對(duì)應(yīng)M個(gè)哈希函數(shù)，hc1(.),hc2(.),…,hcM(.)，每個(gè)哈希表包含d個(gè)桶。為了讓布谷鳥哈希表適用于流量測(cè)量，將布谷鳥哈希表進(jìn)行了一定的改進(jìn)。改進(jìn)后的布谷鳥哈希表如圖4.4所示，每個(gè)桶中包含兩個(gè)部分，一部分存儲(chǔ)key，另一部分存儲(chǔ)對(duì)應(yīng)的值value。插入的過(guò)程如下：（1）對(duì)key進(jìn)行哈希計(jì)算，找出對(duì)應(yīng)的桶，（2）若兩個(gè)桶中均為空，則將<key,value>插入第一個(gè)桶；（3）若存在不為空的桶，將key與桶中現(xiàn)存的key進(jìn)行比較，（a）如果兩個(gè)key相同，則將該桶中的值加上value，（b）如果兩個(gè)key不同，并且存在其他空桶，則將該<key,value>插入空桶，（c）如果兩個(gè)key不同，并且不存在其他空桶，則選擇任意一個(gè)桶，將現(xiàn)存的內(nèi)容

【參考文獻(xiàn)】：
期刊論文
[1]高速網(wǎng)絡(luò)流量測(cè)量方法[J]. 周愛平,程光,郭曉軍.  軟件學(xué)報(bào). 2014(01)
[2]網(wǎng)絡(luò)測(cè)量方法和關(guān)鍵技術(shù)綜述[J]. 王海濤,朱震宇.  數(shù)字通信世界. 2010(11)
[3]網(wǎng)絡(luò)測(cè)量與分析研究綜述[J]. 陳曉霞,任勇毛,李俊,張瀟丹.  計(jì)算機(jī)系統(tǒng)應(yīng)用. 2010(07)
[4]DRAGON-Lab―Next generation internet technology experiment platform[J]. WANG JiLong1,2,LI ZhongHui2,Lü GuoHan2,JIANG CaiPing2,LI Xing1,2 & ZHANG QianLi2 1 National Laboratory for Information Science and Technology,Tsinghua University,Beijing 100084,China;2 Network Research Center,Tsinghua University,Beijing 100084,China.  Science in China（Series F:Information Sciences）. 2008(11)
[5]一種有效的挖掘數(shù)據(jù)流近似頻繁項(xiàng)算法[J]. 王偉平,李建中,張冬冬,郭龍江.  軟件學(xué)報(bào). 2007(04)



本文編號(hào)：3495553