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

【文章來源】：南京郵電大學江蘇省

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

【學位級別】：碩士

【部分圖文】：

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

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

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

【參考文獻】：
期刊論文
[1]高速網(wǎng)絡(luò)流量測量方法[J]. 周愛平,程光,郭曉軍.  軟件學報. 2014(01)
[2]網(wǎng)絡(luò)測量方法和關(guān)鍵技術(shù)綜述[J]. 王海濤,朱震宇.  數(shù)字通信世界. 2010(11)
[3]網(wǎng)絡(luò)測量與分析研究綜述[J]. 陳曉霞,任勇毛,李俊,張瀟丹.  計算機系統(tǒ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ù)流近似頻繁項算法[J]. 王偉平,李建中,張冬冬,郭龍江.  軟件學報. 2007(04)



本文編號：3495553