基于計數(shù)的網(wǎng)絡(luò)流量中頻繁項(xiàng)檢測算法研究.pdf

1、在現(xiàn)今社會，網(wǎng)絡(luò)占據(jù)著重要的地位，有著不可替代的價值。隨著網(wǎng)絡(luò)規(guī)模不斷地擴(kuò)大，網(wǎng)民數(shù)量和網(wǎng)絡(luò)流量激增，網(wǎng)絡(luò)行為隨著網(wǎng)絡(luò)的發(fā)展變得更加多樣化、復(fù)雜化。網(wǎng)絡(luò)流量中頻繁項(xiàng)的檢測是網(wǎng)絡(luò)測量領(lǐng)域的熱點(diǎn)，它是了解網(wǎng)絡(luò)行為、進(jìn)行網(wǎng)絡(luò)管理的有效途徑。
　　網(wǎng)絡(luò)流量中的頻繁項(xiàng)包括長流和超點(diǎn)。長流檢測應(yīng)用到流量計費(fèi)、流量實(shí)時監(jiān)測等方面，長流檢測對發(fā)展高效的流量工程意義重大。超點(diǎn)檢測有助于及時發(fā)現(xiàn)蠕蟲病毒、端口掃描、DDoS等網(wǎng)絡(luò)異常行為的產(chǎn)生。因此，

2、網(wǎng)絡(luò)流量中頻繁項(xiàng)的檢測有廣泛的應(yīng)用價值，對網(wǎng)絡(luò)研究有重要的意義。
　　本文提出了基于計數(shù)的網(wǎng)絡(luò)流量中頻繁項(xiàng)檢測算法ADH(Algorithm forDetecting Heavy-hitters)和ADS(Algorithm for Detecting Superpoints).ADH用于檢測長流，ADS用于檢測超點(diǎn)。每種算法都分為在線處理模塊和離線統(tǒng)計模塊，在線處理模塊負(fù)責(zé)存儲和刪除數(shù)據(jù)項(xiàng)，在線模塊處理之后，離線模塊統(tǒng)計頻繁項(xiàng)的

3、頻數(shù)并將其頻數(shù)輸出。由于內(nèi)存空間有限，ADH需要設(shè)計一個合理且高效的刪除規(guī)則與周期清理掉內(nèi)存中的非頻繁項(xiàng)，減少不必要的內(nèi)存消耗。根據(jù)流分布特征設(shè)定的刪除規(guī)則可有效地刪除非頻繁項(xiàng)，周期時長隨著網(wǎng)絡(luò)流量的變化自適應(yīng)調(diào)整，而且還能保證刪除操作產(chǎn)生的誤差在一定范圍內(nèi)。ADS刪除規(guī)則和周期的設(shè)定與ADH相似，綜合考慮了源主機(jī)分布特征和網(wǎng)絡(luò)流量的變化。
　　本論文對兩種算法分別進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，ADH和ADS在空間消耗和準(zhǔn)確性方面呈現(xiàn)出