基于Bloom Filter的超點檢測算法的研究.pdf

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

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

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