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

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

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

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

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