本文關(guān)鍵詞：網(wǎng)絡(luò)流量測量中的抽樣算法研究，由筆耕文化傳播整理發(fā)布。

【摘要】：通過對流量的測量和運行狀況的分析,網(wǎng)絡(luò)測量為網(wǎng)絡(luò)管理、性能提升和結(jié)構(gòu)優(yōu)化提供參考依據(jù)。然而,由于高速互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展和大數(shù)據(jù)時代的到來,網(wǎng)絡(luò)中的數(shù)據(jù)呈現(xiàn)爆炸式增長,捕獲每個報文信息或者流信息并進(jìn)行存儲和分析已變的不可能。將抽樣技術(shù)引入流量測量中能有效的解決該瓶頸問題,并且能大大減少測量數(shù)據(jù),因此抽樣技術(shù)成為網(wǎng)絡(luò)流量工程研究的重點內(nèi)容之一。本文系統(tǒng)全面地總結(jié)了網(wǎng)絡(luò)流量測量理論,分析了在當(dāng)前高速網(wǎng)絡(luò)環(huán)境中測量遇到的困難,指出抽樣技術(shù)在網(wǎng)絡(luò)測量中的重要作用。接著詳細(xì)闡述了抽樣技術(shù)的相關(guān)概念,討論了隨機抽樣、系統(tǒng)抽樣和分層抽樣等幾種基本的抽樣方法,分析比較了抽樣測量中哈希算法、概要數(shù)據(jù)結(jié)構(gòu)等關(guān)鍵技術(shù)。最后,通過研究目前網(wǎng)絡(luò)的特性,將抽樣技術(shù)與結(jié)構(gòu)簡單、查找匹配迅速的Bloom filter(布魯姆過濾器)相結(jié)合,提出了基于LRU_CBF的大流檢測算法和基于樹形布魯姆過濾器的流抽樣算法。經(jīng)性能分析和仿真實驗證明,本文提出的算法能夠在提高測量準(zhǔn)確性的同時,提高系統(tǒng)的資源利用率。具體研究內(nèi)容如下:(1)本文在系統(tǒng)研究了標(biāo)準(zhǔn)型、計數(shù)型、拆分型等Bloom filter特點的基礎(chǔ)上,將性能優(yōu)越的計數(shù)型Bloom Filter與操作系統(tǒng)中經(jīng)典的頁面置換算法LRU(最近最久未使用)策略相結(jié)合設(shè)計出一種大流檢測算法。該算法使用兩層結(jié)構(gòu),LRU先將大流過濾出來,CBF進(jìn)一步對大流進(jìn)行判斷,使“大流過濾”與“大流判斷”兩個過程分離開。這樣可以簡化數(shù)據(jù)的存儲結(jié)構(gòu),降低空間復(fù)雜度,精確檢測大流,提高準(zhǔn)確性。通過仿真實驗,將本文提出的基于LRU_CBF的大流檢測算法與兩層CBF算法進(jìn)行準(zhǔn)確性方面的對比得知,本文提出的算法具有更高的準(zhǔn)確性和更好的資源利用率。(2)網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)張使得網(wǎng)絡(luò)流量的特征變得異常復(fù)雜,單層次的數(shù)據(jù)結(jié)構(gòu)不能滿足網(wǎng)絡(luò)測量的要求。本文針對目前標(biāo)準(zhǔn)BF算法在流量過大時會造成計數(shù)器溢出的缺陷,設(shè)計了一種多層次結(jié)構(gòu)的樹形布魯姆過濾器。改進(jìn)過濾器的每一層都是一個標(biāo)準(zhǔn)BF,將其中置1的比特位映射出葉子節(jié)點,逐層映射后形成樹形的多層次過濾器。當(dāng)流量較大時增加新的BF,防止BF溢出造成測量誤差。將樹形BF與基于報文的流抽樣算法相結(jié)合,應(yīng)用到實際的網(wǎng)絡(luò)流量測量中,可以在減少測量個數(shù)的同時提高測量精度。通過仿真對該算法與基于其他Bloom filter的抽樣算法進(jìn)行了測量誤差方面的比較,分析可知,本文提出的算法提高了抽樣的準(zhǔn)確性,降低了空間利用率。
【關(guān)鍵詞】：流量測量 抽樣 最近最久未使用 計數(shù)型布魯姆過濾器 樹形布魯姆過濾器
【學(xué)位授予單位】：曲阜師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：TP393.06
【目錄】：

• 摘要3-4
• Abstract4-8
• 第1章 緒論8-14
• 1.1 課題研究背景8-9
• 1.2 網(wǎng)絡(luò)測量的意義9-11
• 1.3 高速網(wǎng)絡(luò)給網(wǎng)絡(luò)測量帶來的困難11
• 1.4 國內(nèi)外研究現(xiàn)狀11-12
• 1.4.1 國外現(xiàn)狀11-12
• 1.4.2 國內(nèi)現(xiàn)狀12
• 1.5 論文結(jié)構(gòu)12-14
• 第2章 網(wǎng)絡(luò)流量測量和抽樣技術(shù)14-21
• 2.1 網(wǎng)絡(luò)流量測量14-17
• 2.1.1 網(wǎng)絡(luò)流量14-15
• 2.1.2 網(wǎng)絡(luò)流量的特性15-16
• 2.1.3 網(wǎng)絡(luò)流量的測量方法16-17
• 2.2 流量測量的體系結(jié)構(gòu)17
• 2.3 抽樣技術(shù)的基本理論17-20
• 2.3.1 相關(guān)概念17-18
• 2.3.2 基本的抽樣方法18-19
• 2.3.3 抽樣技術(shù)中新引入的關(guān)鍵技術(shù)19-20
• 2.4 本章小結(jié)20-21
• 第3章 基于LRU_CBF的大流檢測算法21-29
• 3.1 引言21
• 3.2 關(guān)鍵技術(shù)21-24
• 3.2.1 LRU思想描述21-22
• 3.2.2 BF原理22-24
• 3.3 LRU_CBF算法流程24-25
• 3.4 算法的理論分析和實驗仿真25-28
• 3.4.1 準(zhǔn)確性25-27
• 3.4.2 空間復(fù)雜度27
• 3.4.3 時間復(fù)雜度27
• 3.4.4 實驗仿真27-28
• 3.5 本章小結(jié)28-29
• 第4章 基于樹形布魯姆過濾器的流抽樣測量算法29-38
• 4.1 引言29
• 4.2 多層次結(jié)構(gòu)的Blooming Tree算法29-30
• 4.2.1 Blooming Tree的數(shù)據(jù)結(jié)構(gòu)29
• 4.2.2 算法原理29-30
• 4.3 一種新型的樹型布魯姆過濾器30-33
• 4.3.1 新型樹形布魯姆過濾器算法的查詢過程31-32
• 4.3.2 新型樹形布魯姆過濾器算法的更新過程32-33
• 4.4 基于樹形布魯姆過濾器的流抽樣算法33-34
• 4.4.1 基本原理33
• 4.4.2 算法描述33-34
• 4.5 仿真結(jié)果比較34-36
• 4.5.1 實驗數(shù)據(jù)的選擇34-35
• 4.5.2 結(jié)果對比35-36
• 4.6 本章小結(jié)36-38
• 第5章 總結(jié)與展望38-40
• 5.1 總結(jié)38
• 5.2 展望38-40
• 參考文獻(xiàn)40-43
• 在讀期間發(fā)表的學(xué)術(shù)論文及研究成果43-44
• 致謝44

【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前4條

1 陳松;王珊;周明天;;基于實時分析的網(wǎng)絡(luò)測量抽樣統(tǒng)計模型[J];電子學(xué)報;2010年05期

2 劉衛(wèi)江;白磊;景泉;;基于Sample-CBF技術(shù)的長流識別實現(xiàn)[J];計算機工程;2007年20期

3 談杰;李星;;網(wǎng)絡(luò)測量綜述[J];計算機應(yīng)用研究;2006年02期

4 吳樺;龔儉;楊望;;一種基于雙重Counter Bloom Filter的長流識別算法[J];軟件學(xué)報;2010年05期

  本文關(guān)鍵詞：網(wǎng)絡(luò)流量測量中的抽樣算法研究，，由筆耕文化傳播整理發(fā)布。

本文編號：286526