基于Wavelet Tree的網(wǎng)絡(luò)數(shù)據(jù)索引技術(shù)研究.pdf

1、近幾年來，隨著互聯(lián)網(wǎng)絡(luò)和網(wǎng)絡(luò)應(yīng)用的高速發(fā)展，網(wǎng)絡(luò)監(jiān)測和網(wǎng)絡(luò)安全變得日漸重要，其中對抓取的網(wǎng)絡(luò)數(shù)據(jù)包進(jìn)行長期的歷史分析是一個十分重要的主題。實現(xiàn)上述功能最重要的要求是如何快速準(zhǔn)確地從網(wǎng)絡(luò)數(shù)據(jù)包中檢索出符合條件的數(shù)據(jù)包。為了達(dá)到此目的，對其建立有效的索引十分重要。由于目前的網(wǎng)絡(luò)速度快速地增加，導(dǎo)致需要處理的網(wǎng)絡(luò)數(shù)據(jù)包文件大小逐漸增加，此時不僅僅需要更多的硬件資源，同樣也需要更有效的軟件工具。然而，傳統(tǒng)的查詢工具(例如Tcpdump和Wire

2、shark)不能有效地處理較大規(guī)模的網(wǎng)絡(luò)數(shù)據(jù)包文件。
　　本文對網(wǎng)絡(luò)數(shù)據(jù)索引技術(shù)進(jìn)行了研究，該技術(shù)主要存在索引文件存儲開銷以及索引和查詢性能提升的問題。針對上述問題，本文提出一種針對于網(wǎng)絡(luò)數(shù)據(jù)包進(jìn)行索引和查詢的有效方法，設(shè)計并實現(xiàn)了一個網(wǎng)絡(luò)數(shù)據(jù)索引系統(tǒng)Pi。具體的研究工作如下:
　　第一，采用一種新型的數(shù)據(jù)結(jié)構(gòu)Wavelet Tree存儲索引文件，同時結(jié)合使用RRR和變長的prefix-free編碼方式對Wavelet Tr

3、ee進(jìn)行了改進(jìn)，使得它建立索引時需要更少的時間和存儲空間開銷。第二，將改進(jìn)的Wavelet Tree和壓縮位圖技術(shù)結(jié)合使用來執(zhí)行系統(tǒng)的網(wǎng)絡(luò)數(shù)據(jù)包查詢功能，本系統(tǒng)的索引建立和查詢分析均具有較高的性能。與此同時，通過系統(tǒng)建立的索引能夠快速地創(chuàng)建而且能夠提供一個強(qiáng)有力的查詢功能集，它包含的查詢功能有:簡單和復(fù)雜的屬性點值查詢、簡單和復(fù)雜的屬性范圍值查詢、求取查詢屬性的最大值和最小值、對查詢屬性進(jìn)行升序和降序的排列。該功能集允許在索引文件上執(zhí)行

4、快速的訪問和查詢。
　　實驗的平臺為裝有普通硬盤(Hard Disk Drive，HDD)與固態(tài)硬盤(Solid StateDrive，SSD)的服務(wù)器，實驗結(jié)果表明，系統(tǒng)Pi建立的索引數(shù)據(jù)文件大小為原始網(wǎng)絡(luò)數(shù)據(jù)包文件大小的2％左右。建立索引的空間開銷和時間開銷均較少，而且在固態(tài)硬盤的機(jī)器上時間開銷更小。就索引數(shù)據(jù)文件大小和網(wǎng)絡(luò)數(shù)據(jù)包的查詢時間而言，系統(tǒng)Pi與類似Tcpdump的傳統(tǒng)工具相比表現(xiàn)出顯著的性能提升，和現(xiàn)今的工具例如P