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

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

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

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

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

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