基于Bloom Filters流抽樣算法的研究.pdf

1、函盔撕甓六噻’碩士學(xué)位論文基于BloomFilters流抽樣算法的研究研究生姓名：學(xué)科專業(yè)：研究方向：導(dǎo)師蓑纛!論文完成時(shí)間：胡廣昌計(jì)算機(jī)應(yīng)用技術(shù)計(jì)算機(jī)網(wǎng)絡(luò)與通信高仲合教授2010年4月0015206l，“喜≮如摯k譬，l●◆●●基于BloomFilters流抽樣算法的研究摘要隨著互聯(lián)網(wǎng)規(guī)模的不斷擴(kuò)大及其應(yīng)用的多元化發(fā)展，對(duì)網(wǎng)絡(luò)性能監(jiān)控和運(yùn)行管理的要求越來越高。因此研究網(wǎng)絡(luò)流量特征，對(duì)網(wǎng)絡(luò)管理、規(guī)劃和發(fā)展都有重要意義。其中，流量測(cè)量是網(wǎng)

2、絡(luò)測(cè)量中一個(gè)重要的研究方向，針對(duì)網(wǎng)絡(luò)流量特征、統(tǒng)計(jì)信息、異常事件等現(xiàn)象進(jìn)行的測(cè)量和研究，對(duì)網(wǎng)絡(luò)問題的解決、協(xié)議的調(diào)試、性能評(píng)估等方面均有極大的幫助。本文首先從網(wǎng)絡(luò)流量測(cè)量的背景及研究現(xiàn)狀著手分析，闡述了流量測(cè)量的意義和面臨的困難。接著詳細(xì)介紹了流量測(cè)量方法及網(wǎng)絡(luò)流量的構(gòu)成，重點(diǎn)闡述了流量抽樣方法，并對(duì)分組抽樣和流抽樣進(jìn)行了詳細(xì)論述。隨后討論了互聯(lián)網(wǎng)IP流及大流的定義，剖析了BloomFilter的結(jié)構(gòu)并分析了其工作原理，對(duì)基于Bloom

3、Filters大流抽樣的幾種方法進(jìn)行了總結(jié)和比較?；趯?duì)當(dāng)前流量測(cè)量面臨困難的討論和上述流量測(cè)量理論的分析，本文根據(jù)Parallelfilter和Serialfilter的多級(jí)判斷、層層過濾的優(yōu)點(diǎn)，設(shè)計(jì)兩級(jí)過濾結(jié)構(gòu)來捕獲互聯(lián)網(wǎng)中的大流；根據(jù)Parallelfilter的四級(jí)并行置位難度大以及Serialfilter逐級(jí)置位效率低，設(shè)計(jì)基于判別而非置位的過濾方法。從減少置位次數(shù)方面著手，降低了傳統(tǒng)BloomFilters大流抽樣方式帶來的

4、高誤正率，而且使用更少的SRAM資源實(shí)現(xiàn)了對(duì)大流的抽樣。本文從結(jié)構(gòu)框架和抽樣算法的角度進(jìn)行探討，主要在以下三個(gè)方面做出了有益的嘗試：第一，提出基于兩級(jí)過濾的大流抽樣框架：第一級(jí)使用一個(gè)BloomFilter實(shí)現(xiàn)對(duì)互聯(lián)網(wǎng)流的初始過濾，從大量的互聯(lián)網(wǎng)流中抽取接近大流的流；第二級(jí)使用一組BloomFilters實(shí)現(xiàn)對(duì)接近大流的流的過濾，從中抽取所需的大流。從高速互聯(lián)網(wǎng)流中逐級(jí)過濾出需要抽取的流量信息。第二，設(shè)計(jì)對(duì)應(yīng)的BF2算法，從減少置位次數(shù)

5、方面著手，減少誤正情況的發(fā)生。對(duì)于新到的分組先進(jìn)行第二級(jí)過濾器的判別，再進(jìn)行第一級(jí)過濾器的置位，從根本上減少了第二級(jí)過濾器的置位次數(shù)，降低了大流的誤J下率。另外，對(duì)算法產(chǎn)生的誤正情況進(jìn)行分析，BF2算法可以在較少的時(shí)間復(fù)雜度和空間復(fù)雜度下，實(shí)現(xiàn)互聯(lián)網(wǎng)中大流的識(shí)別并抽樣，提高了執(zhí)行效率。第三，提出定時(shí)刷新的方式來減少因長(zhǎng)時(shí)間置位引發(fā)的高誤正率，對(duì)每級(jí)過濾器設(shè)置刷新時(shí)隙，通過設(shè)置閾值和時(shí)I’日J(rèn)I’日J(rèn)隔在刷新前進(jìn)行預(yù)刷新，盡量減少因定時(shí)刷