[發(fā)明專利]基于優(yōu)先級Trie樹的動態(tài)IP匹配模型的建立方法有效
| 申請?zhí)枺?/td> | 201510324464.2 | 申請日： | 2015-06-12 |
| 公開（公告）號： | CN105025013B | 公開（公告）日： | 2018-04-10 |
| 發(fā)明（設(shè)計）人： | 衛(wèi)冰潔;楊武;王巍;曹首峰;苘大鵬;玄世昌;賀龍濤;賀欣;袁媛;于賀威;王嘯;李城龍 | 申請（專利權(quán)）人： | 國家計算機網(wǎng)絡(luò)與信息安全管理中心 |
| 主分類號： | H04L29/06 | 分類號： | H04L29/06;H04L29/12;H04L12/741 |
| 代理公司： | 北京理工大學(xué)專利中心11120 | 代理人： | 張瑜,仇蕾安 |
| 地址： | 100029*** | 國省代碼： | 北京;11 |
| 權(quán)利要求書： | 查看更多 | 說明書： | 查看更多 |
| 摘要： | |||
| 搜索關(guān)鍵詞： | 基于 優(yōu)先級 trie 動態(tài) ip 匹配 模型 | ||
技術(shù)領(lǐng)域
本發(fā)明屬于防火墻技術(shù)領(lǐng)域，尤其涉及一種基于優(yōu)先級Trie樹的動態(tài)IP匹配模型。
背景技術(shù)
Web防火墻可以很好的解決互聯(lián)網(wǎng)平臺監(jiān)管問題。在Web防火墻工作過程中，需要根據(jù)數(shù)據(jù)流的IP地址進(jìn)行篩選，并對相應(yīng)的數(shù)據(jù)流進(jìn)行安全控制。由于Internet規(guī)模的不斷擴大，Web防火墻中IP安全規(guī)則的更新愈加頻繁的發(fā)生。這就在Web防火墻對IP地址進(jìn)行篩選過程中，引入了一個問題：如何處理Web 防火墻中IP安全規(guī)則的大量事實更新。
最常用的IP匹配算法就是基于二進(jìn)制Trie樹的算法。在IP最長前綴匹配算法中最基本的Trie樹為二進(jìn)制Trie。前綴匹配算法是對比特串進(jìn)行逐位比較，而比特串的每一位只包含兩種情況，那就是0和1，對應(yīng)二進(jìn)制Trie樹中的左結(jié)點和右結(jié)點。在二進(jìn)制Trie樹中，將一次Trie樹的操作分為多個步驟。在Trie 樹的構(gòu)建或更新過程中，需要根據(jù)前綴各比特的值決定分支的走向。在IP最長前綴匹配過程中，需要根據(jù)地址各比特的值決定分支的走向。
綜上所述，當(dāng)前IP匹配算法的缺點是查找效率低下，開銷大。
發(fā)明內(nèi)容
為解決上述問題，本發(fā)明提供一種基于優(yōu)先級Trie樹的動態(tài)IP匹配模型，克服了當(dāng)前Web防火墻中IP匹配模塊的以下缺點，即查找效率低下，開銷比較大。
本發(fā)明的基于優(yōu)先級Trie樹的動態(tài)IP匹配模型，其包括以下步驟：
步驟1：BIPT匹配模型的構(gòu)建過程，具體包括：
步驟11，劃分前綴；
設(shè)前綴P的長度為l，則該前綴P表示為P＝P0P1...Pl-1*；以長度k(k＜l)對前綴 P進(jìn)行劃分，分為長度大于劃分點k的第一前綴集合和長度小于劃分點k的第二前綴集合，賦予第一前綴集合內(nèi)每個前綴一個索引值，賦予第二前綴集合內(nèi)每個前綴一個索引后綴，且所有的索引后綴相同；
以Prek(P)來表示有索引值的前綴，則Prek(P)＝(P0P1...Pk-1)2；以Park(P)表示有索引后綴的前綴，則Park(P)＝PkPk+1...Pl-1*；
步驟12，構(gòu)建B*索引樹；
將第一前綴集合內(nèi)的前綴P根據(jù)索引值掛載到B*索引樹上相應(yīng)的B*結(jié)點中，并用BIPT[i]表示，且0≤i≤2k-1；將第二前綴集合內(nèi)的所有前綴掛載到B*索引樹上的一個共同的B*結(jié)點中，并用BIPT[-1]表示；
步驟2：BIPT樹的前綴插入操作；
步驟21：對每一個前綴P，先求前綴P的長度，如果其長度大于劃分點k，則設(shè)置起始查找結(jié)點為根結(jié)點并進(jìn)行步驟22；否則將前綴插入BIPT[-1]對應(yīng)的優(yōu)先級Trie樹中并終止前綴插入操作；
步驟22：在B*索引樹的給定結(jié)點中進(jìn)行查找，直到葉子結(jié)點；在索引結(jié)點中若Pre(p)＜k1，則選擇索引結(jié)點的第1個分支進(jìn)行查找，并執(zhí)行步驟23；若 ki≤Pre(p)≤ki+1，則選擇索引結(jié)點的第i個分支進(jìn)行查找，并執(zhí)行步驟23；若 kn(x)＜Pre(p)，則選擇索引結(jié)點的第n(x)個分支進(jìn)行查找，并執(zhí)行步驟23；并記錄查找路徑中所搜索的給定結(jié)點以及給定結(jié)點中分支的選擇；
其中規(guī)定ki(x)是結(jié)點x的第i個索引值，cj(x)是結(jié)點x的第j個孩子指針，其中i和j滿足1≤i≤n(x)并且1≤j≤n(x)。在結(jié)點中的索引值存在如下關(guān)系：
k1(x)＜k2(x)＜...＜kn(x)(x)
步驟23：查找索引結(jié)點中是否有與B*索引樹的給定結(jié)點的索引值相同的關(guān)鍵字，如果有，則直接在該B*索引樹的給定結(jié)點優(yōu)先級Trie樹中插入索引后綴，并結(jié)束插入操作；否則執(zhí)行步驟24；
該專利技術(shù)資料僅供研究查看技術(shù)是否侵權(quán)等信息，商用須獲得專利權(quán)人授權(quán)。該專利全部權(quán)利屬于國家計算機網(wǎng)絡(luò)與信息安全管理中心，未經(jīng)國家計算機網(wǎng)絡(luò)與信息安全管理中心許可，擅自商用是侵權(quán)行為。如果您想購買此專利、獲得商業(yè)授權(quán)和技術(shù)合作，請聯(lián)系【客服】
本文鏈接：http://www.szxzyx.cn/pat/books/201510324464.2/2.html，轉(zhuǎn)載請聲明來源鉆瓜專利網(wǎng)。
