[發(fā)明專利]IPv6地址前綴壓縮存儲方法及設(shè)備

有效

• 申請?zhí)枺?/td>: 201010611546.2
• 申請日: 2010-12-28
• 公開（公告）號: CN102045412A
• 公開（公告）日: 2011-05-04
• 發(fā)明（設(shè)計）人: 黃友俊;李星;吳建平;胡松;張輝
• 申請（專利權(quán)）人: 賽爾網(wǎng)絡(luò)有限公司
• 主分類號: H04L29/12
• 分類號: H04L29/12
• 代理公司: 中科專利商標(biāo)代理有限責(zé)任公司 11021
• 代理人: 趙偉

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

本發(fā)明涉及下一代互聯(lián)網(wǎng)領(lǐng)域，更具體地，涉及一種IPv6地址前綴存儲方法和設(shè)備。

背景技術(shù)

眾所周知，IPv6地址長度是128比特，而IPv4地址長度是32比特。就地址長度而言，IPv6比IPv4擴(kuò)大了4倍；就容量而言，則擴(kuò)大了2⁹⁶倍。由于IPv6地址容量的急劇增長，因此需要一種高效可行的IPv6地址存儲和查找方式。

隨著技術(shù)的發(fā)展，人們提出了基于多分支Trie樹的IPv6地址前綴存儲和查找算法。字典樹(Trie)是一種用于快速字符串檢索的多叉樹結(jié)構(gòu)。其原理是利用字符串的公共前綴來降低時空開銷，從而達(dá)到提高程序效率的目的。Trie樹在本質(zhì)上是一個確定的有限狀態(tài)自動機(jī)，每個結(jié)點(diǎn)代表一個狀態(tài)，根據(jù)輸入變量的不同，進(jìn)行狀態(tài)轉(zhuǎn)移。用Trie樹搜索一個關(guān)鍵碼的時間與關(guān)鍵碼自身及其長度有關(guān)，最快是0(1)，即在第一層即可判斷是否搜索到，最壞的情況是0(n)，n為Trie樹的層數(shù)。由于很多時候Trie樹的大多數(shù)結(jié)點(diǎn)分支很少，因此Trie樹結(jié)構(gòu)空間浪費(fèi)比較多。如果把每次查找檢查的字符個數(shù)定義為步長，傳統(tǒng)的Trie樹步長為1，多分支Trie樹的查找步長大于1。利用多分支Trie樹可以有效減少查找過程中的存儲器訪問次數(shù)。

雖然該算法在查找速度上獲得了很大的提高，但仍然需要較大的存儲空間。圖1示出了步長為K＝16、層數(shù)為128/16＝8的多分支Trie樹(MT)的示意結(jié)構(gòu)。如圖1所示，多分支Trie樹的每一個節(jié)點(diǎn)都包含2¹⁶＝65536個分支節(jié)點(diǎn)。因此，每個節(jié)點(diǎn)包含一塊連續(xù)的大小為65536個單元的內(nèi)存，分別指向65536個子節(jié)點(diǎn)。由于IPv6地址長度為128比特，因此MT的最大層數(shù)(深度)為8(128/16＝8)。MT的實(shí)際層數(shù)由存儲的IPv6地址前綴決定，當(dāng)MT中不存儲任何IPv6地址前綴時，MT中只包含根節(jié)點(diǎn)，層數(shù)為0，當(dāng)存儲的IPv6地址前綴中包含長度為16的前綴時，層數(shù)為1。依此類推，當(dāng)存儲的IPv6地址前綴中包含長度為128的前綴時，層數(shù)為8。

因此，當(dāng)IPv6地址前綴較多且比較分散時，需要非常大的存儲空間，同時產(chǎn)生了很多的空指針，一方面會造成內(nèi)存的巨大浪費(fèi)，另一方面會影響查找效率。

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

本發(fā)明提出了一種IPv6地址前綴存儲方法，可以在使用有限內(nèi)存的情況下實(shí)現(xiàn)IPv6地址前綴的存儲，并且能夠?qū)崿F(xiàn)高效查找。

根據(jù)本發(fā)明的一個方面，提供了一種用于存儲IPv6地址前綴的方法，包括：將IPv6地址前綴劃分為具有固定長度K的L個部分，其中K和L均為正整數(shù)；使用步長為K、層數(shù)為L的多分支Trie樹結(jié)構(gòu)存儲IPv6地址前綴，其中每一個節(jié)點(diǎn)使用長度為2^K的數(shù)組來存儲節(jié)點(diǎn)指針，節(jié)點(diǎn)指針在數(shù)組中的位置表示IPv6地址前綴的K個比特；以及利用額外數(shù)組對生成的多分支Trie樹中的每一個節(jié)點(diǎn)進(jìn)行壓縮存儲。

優(yōu)選地，所述壓縮存儲包括：針對多分支Trie樹中的每一個節(jié)點(diǎn)，利用兩個數(shù)組來代替，第一數(shù)組存儲該節(jié)點(diǎn)中的非空指針值，而第二數(shù)組存儲每一個非空指針值在該節(jié)點(diǎn)中的對應(yīng)位置。

優(yōu)選地，初始化多分支Trie樹結(jié)構(gòu)，使得與根節(jié)點(diǎn)相對應(yīng)的數(shù)組中均為空指針。

優(yōu)選地，針對多分支Trie樹中的每一個節(jié)點(diǎn)，通過遍歷與該節(jié)點(diǎn)相對應(yīng)的數(shù)組，將非空指針和其相應(yīng)的位置分別存儲在第一數(shù)組和第二數(shù)組中。

優(yōu)選地，所述方法還包括：如果需要查找已存儲的IPv6地址前綴，則使用二分法依次查找每一層節(jié)點(diǎn)的第二數(shù)組。

優(yōu)選地，步長K等于16。

根據(jù)本發(fā)明的另一個方面，提供了一種用于存儲IPv6地址前綴的設(shè)備，包括：劃分單元，將IPv6地址前綴劃分為具有固定長度K的L個部分，其中K和L均為正整數(shù)；存儲單元，使用步長為K、層數(shù)為L的多分支Trie樹結(jié)構(gòu)存儲IPv6地址前綴，其中每一個節(jié)點(diǎn)使用長度為2^K的數(shù)組來存儲節(jié)點(diǎn)指針，節(jié)點(diǎn)指針在數(shù)組中的位置表示IPv6地址前綴的K個比特；以及壓縮單元，利用額外數(shù)組對生成的多分支Trie樹中的每一個節(jié)點(diǎn)進(jìn)行壓縮存儲。

優(yōu)選地，所述壓縮單元針對多分支Trie樹中的每一個節(jié)點(diǎn)，利用兩個數(shù)組來代替，第一數(shù)組存儲該節(jié)點(diǎn)中的非空指針值，而第二數(shù)組存儲每一個非空指針值在該節(jié)點(diǎn)中的對應(yīng)位置。

優(yōu)選地，所述存儲單元初始化多分支Trie樹結(jié)構(gòu)，使得與根節(jié)點(diǎn)相對應(yīng)的數(shù)組中均為空指針。

優(yōu)選地，所述壓縮單元針對多分支Trie樹中的每一個節(jié)點(diǎn)，通過遍歷與該節(jié)點(diǎn)相對應(yīng)的數(shù)組，將非空指針和其相應(yīng)的位置分別存儲在第一數(shù)組和第二數(shù)組中。