[發(fā)明專利]一個(gè)基于Wavelet Tree的網(wǎng)絡(luò)數(shù)據(jù)包索引系統(tǒng)

在審

• 申請(qǐng)?zhí)枺?/td>: 201610027911.2
• 申請(qǐng)日: 2016-01-15
• 公開（公告）號(hào): CN105718521A
• 公開（公告）日: 2016-06-29
• 發(fā)明（設(shè)計(jì)）人: 孫建華;姚姝娜
• 申請(qǐng)（專利權(quán)）人: 湖南大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

技術(shù)領(lǐng)域

本發(fā)明涉及計(jì)算機(jī)網(wǎng)絡(luò)安全領(lǐng)域的網(wǎng)絡(luò)數(shù)據(jù)分析，具體涉及針對(duì)海量網(wǎng)絡(luò)數(shù)據(jù)包進(jìn)行索引和查詢分析的方法。

背景技術(shù)

在網(wǎng)絡(luò)監(jiān)測(cè)和網(wǎng)絡(luò)安全的研究中，對(duì)抓取的網(wǎng)絡(luò)數(shù)據(jù)包進(jìn)行分析是一個(gè)重要的主題。通過(guò)對(duì)其進(jìn)行抓取和分析，實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)有效的監(jiān)控，準(zhǔn)確定位網(wǎng)絡(luò)中出現(xiàn)的故障。而當(dāng)前的網(wǎng)絡(luò)數(shù)據(jù)分析任務(wù)，例如協(xié)議性能評(píng)估、網(wǎng)絡(luò)監(jiān)測(cè)及辯證分析，在分析錯(cuò)誤和評(píng)估性能時(shí)，網(wǎng)絡(luò)數(shù)據(jù)包查詢過(guò)程需要快速而有效地完成。事實(shí)上，該過(guò)程為一個(gè)CPU計(jì)算密集任務(wù)，特別是當(dāng)處理一個(gè)包含復(fù)雜通信方式的大文件時(shí)，會(huì)給CPU帶來(lái)很大負(fù)擔(dān)。與此同時(shí)，隨著網(wǎng)絡(luò)飛速發(fā)展，網(wǎng)絡(luò)通信越來(lái)越復(fù)雜，導(dǎo)致數(shù)據(jù)包路徑的長(zhǎng)度變得更大，同時(shí)查詢條件也變得更為復(fù)雜，因此查詢延時(shí)也隨之快速地增加。

因此在該環(huán)境下，對(duì)網(wǎng)絡(luò)數(shù)據(jù)包的查詢效率的提升變得十分重要，而在此過(guò)程中最重要的是查詢的精度與速度。目前，主要通過(guò)以下途徑來(lái)提高海量數(shù)據(jù)的查詢性能，一是改變數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)使其更好地滿足上層查詢；二是建立高效的索引提高數(shù)據(jù)檢索的效率；其三是通過(guò)查詢優(yōu)化技術(shù)來(lái)優(yōu)化查詢語(yǔ)句，如啟發(fā)式優(yōu)化、基于代價(jià)的優(yōu)化等。

而索引技術(shù)是上述幾種方法中最常用的提高查詢效率速度的手段。目前常用的索引結(jié)構(gòu)主要有三種，B-樹索引、R-樹索引和位圖索引。與前面兩者，位圖索引將比較、連接和聚集都變成了位邏輯運(yùn)算，大大減少了運(yùn)行時(shí)間，從而得到性能上的極大的提升。但將位圖索引技術(shù)運(yùn)用到網(wǎng)絡(luò)數(shù)據(jù)包查詢環(huán)境下，當(dāng)數(shù)據(jù)包數(shù)量上升為百萬(wàn)時(shí)，采用該技術(shù)所建立的索引大小會(huì)異常地增加。因此，在抽取一個(gè)大的數(shù)據(jù)包的路徑時(shí)，需在索引數(shù)據(jù)大小和數(shù)據(jù)包提取性能之間有一個(gè)折衷點(diǎn)。針對(duì)于該問題，有學(xué)者提出了一個(gè)新型的數(shù)據(jù)結(jié)構(gòu)WaveletTree，采用該結(jié)構(gòu)所建立的索引在索引數(shù)據(jù)的大小和數(shù)據(jù)包提取性能兩者之間獲取了一個(gè)平衡點(diǎn)，而且同時(shí)滿足快速查找的性能和提供了高壓縮比。

WaveletTree是一種存儲(chǔ)壓縮字符串的簡(jiǎn)潔的數(shù)據(jù)結(jié)構(gòu)。它將字符串轉(zhuǎn)換成由位向量組成的平衡二叉樹，該樹除葉子節(jié)點(diǎn)外的每個(gè)節(jié)點(diǎn)存儲(chǔ)一個(gè)位序列，位序列的每個(gè)位置由0或1來(lái)標(biāo)記。把字符串的字符集從根部開始分成兩部分，左子樹的符號(hào)被標(biāo)記為0，其剩余的為右子樹，標(biāo)記為1。以這種方式遞歸生成下面的子樹。

WaveletTree的遞歸定義如下：

1)將字符串所包含的字符集前半部分編碼為0，后半部分編碼為1：例如對(duì)于序列S＝{1,5,1,1,8,6,3,8,7,5,7,4,3,2,8,8}，它的字符集為{1,2,3,4,5,6,7,8,9}，S可編碼為以下位序列0100110111100011；

2)字符集前半部分(即{1,2,3,4})中的每個(gè)符號(hào)編碼為0，并將其作為子樹；

3)字符集后半部分(即{5,6,7,8,9})中的每個(gè)符號(hào)編碼為1，并將其作為子樹；

4)重復(fù)應(yīng)用此方法對(duì)每個(gè)子樹遞歸，直到只有一個(gè)或兩個(gè)符號(hào)留下，即所有的符號(hào)均用葉子節(jié)點(diǎn)表示。

WaveletTree有三個(gè)基本操作：rank、select和lookup，給定一個(gè)包含n個(gè)字符序列S，來(lái)對(duì)三個(gè)基本操作進(jìn)行詳細(xì)說(shuō)明：

●rank

對(duì)于序列S具體的rank操作為rank_b(S,i)，計(jì)算字符b從開始位置一直到位置i出現(xiàn)的次數(shù)。具體實(shí)現(xiàn)為：從根部開始計(jì)算，首先得到字符b在這層的編碼為0或1，然后用rank操作來(lái)計(jì)算0或1的數(shù)量，根據(jù)計(jì)算的結(jié)果移動(dòng)到左子樹或右子樹的相應(yīng)位置，接著依次遞歸。直至葉子節(jié)點(diǎn)處，最后位向量中的位置為rank_b(S,i)的結(jié)果。

●select

select為rank的逆運(yùn)算。對(duì)于序列S具體的select操作為select_b(S,j)，即查找在序列中字符b第j次出現(xiàn)的位置。具體實(shí)現(xiàn)為：從字符b所在葉子節(jié)點(diǎn)開始，首先判斷該字符在葉子節(jié)點(diǎn)的編碼為0還是1，然后用select操作進(jìn)行計(jì)算。通過(guò)得到的結(jié)果(即位置)，向父節(jié)點(diǎn)移動(dòng)，然后查詢這個(gè)新位置。接著依次遞歸，直到根部，在根部的位置為最終結(jié)果。

●lookup

對(duì)于序列S具體的lookup操作為lookup(S,k)，返回指定位置k上的值。對(duì)于位置k可以通過(guò)以下描述的路徑來(lái)獲取：在根中，如果該位圖的位置k為0或1，根據(jù)取值找到根的左孩子或右孩子，在左子樹或右子樹用rank操作計(jì)算該位置之前0或1的個(gè)數(shù)。遞歸地執(zhí)行該操作直至葉子節(jié)點(diǎn)，最后得到葉子節(jié)點(diǎn)的值即是為結(jié)果，此時(shí)完成該操作。

發(fā)明內(nèi)容