基于Bloom Filter的超點(diǎn)檢測(cè)算法的研究.pdf

1、超點(diǎn)檢測(cè)對(duì)于設(shè)計(jì)高效的流量工程方案有著重要的意義。隨著互聯(lián)網(wǎng)的蓬勃發(fā)展，網(wǎng)絡(luò)入侵事件頻繁發(fā)生，如蠕蟲傳播、分布式DDOS攻擊、端口掃描等。這些攻擊事件在短時(shí)間內(nèi)產(chǎn)生大量的流量鏈接，導(dǎo)致網(wǎng)絡(luò)堵塞甚至癱瘓。如掃描式蠕蟲在進(jìn)行傳播時(shí)，被感染主機(jī)通常在短時(shí)間內(nèi)向大量的其他主機(jī)發(fā)送分組，我們稱這一主機(jī)為超點(diǎn)。實(shí)時(shí)識(shí)別超點(diǎn)并獲得超點(diǎn)的信息對(duì)于網(wǎng)絡(luò)操作和管理有重要的作用。
　　 本文對(duì)超點(diǎn)檢測(cè)算法展開研究，以算法的內(nèi)存消耗情況和測(cè)量的精確度為

2、出發(fā)點(diǎn)，將可逆BloomFilter技術(shù)應(yīng)用于超點(diǎn)檢測(cè)，提出了兩種超點(diǎn)檢測(cè)方案。
　　 第一種檢測(cè)方案是利用BloomFilter和可逆BloomFilter檢測(cè)超點(diǎn)。可逆BloomFilter包含4個(gè)哈希函數(shù)，它們選取源IP字符串的部分比特位作為哈希函數(shù)的哈希值，根據(jù)哈希函數(shù)的映射特性，利用選擇的哈希短串的重疊比特位還原出IP的信息。給每個(gè)哈希函數(shù)獨(dú)立的存儲(chǔ)空間，在很大程度上減少了哈希過程所帶來的內(nèi)部沖突。算法分析表明：此算法

3、具有較小的空間復(fù)雜度且能擴(kuò)展到40Gbps高速網(wǎng)絡(luò)環(huán)境中。
　　 第二種檢測(cè)方案是基于“抽樣后過濾”技術(shù)。首先對(duì)鏈路上的流進(jìn)行流抽樣，然后用BloomFilter過濾，減少測(cè)量中處理的流數(shù)，從而提高算法的可擴(kuò)展性。我們采用基于哈希的流抽樣算法，即利用哈希函數(shù)來完成流抽樣。
　　 本文對(duì)算法采用來自不同的數(shù)據(jù)源的Trace進(jìn)行測(cè)試。采用加權(quán)相對(duì)差作為測(cè)量測(cè)度，對(duì)實(shí)驗(yàn)所得的數(shù)據(jù)進(jìn)行分析。實(shí)驗(yàn)結(jié)果表明，本文提出的兩種方案可以準(zhǔn)