[發明專利]IPv6地址前綴壓縮存儲方法及設備

有效

• 申請號: 201010611546.2
• 申請日: 2010-12-28
• 公開（公告）號: CN102045412A
• 公開（公告）日: 2011-05-04
• 發明（設計）人: 黃友俊;李星;吳建平;胡松;張輝
• 申請（專利權）人: 賽爾網絡有限公司
• 主分類號: H04L29/12
• 分類號: H04L29/12
• 代理公司: 中科專利商標代理有限責任公司 11021
• 代理人: 趙偉

1.一種用于存儲IPv6地址前綴的方法，包括：

將IPv6地址前綴劃分為具有固定長度K的L個部分，其中K和L均為正整數；

使用步長為K、層數為L的多分支Trie樹結構存儲IPv6地址前綴，其中每一個節點使用長度為2^K的數組來存儲節點指針，節點指針在數組中的位置表示IPv6地址前綴的K個比特；以及

利用額外數組對生成的多分支Trie樹中的每一個節點進行壓縮存儲。

2.根據權利要求1所述的方法，其中，所述壓縮存儲包括：針對多分支Trie樹中的每一個節點，利用兩個數組來代替，第一數組存儲該節點中的非空指針值，而第二數組存儲每一個非空指針值在該節點中的對應位置。

3.根據權利要求1所述的方法，其中，初始化多分支Trie樹結構，使得與根節點相對應的數組中均為空指針。

4.根據權利要求2所述的方法，其中，針對多分支Trie樹中的每一個節點，通過遍歷與該節點相對應的數組，將非空指針和其相應的位置分別存儲在第一數組和第二數組中。

5.根據權利要求2所述的方法，還包括：如果需要查找已存儲的IPv6地址前綴，則使用二分法依次查找每一層節點的第二數組。

6.根據權利要求1-5中任意一項所述的方法，其中，步長K等于16。

7.一種用于存儲IPv6地址前綴的設備，包括：

劃分單元，將IPv6地址前綴劃分為具有固定長度K的L個部分，其中K和L均為正整數；

存儲單元，使用步長為K、層數為L的多分支Trie樹結構存儲IPv6地址前綴，其中每一個節點使用長度為2^K的數組來存儲節點指針，節點指針在數組中的位置表示IPv6地址前綴的K個比特；以及

壓縮單元，利用額外數組對生成的多分支Trie樹中的每一個節點進行壓縮存儲。

8.根據權利要求1所述的設備，其中，所述壓縮單元針對多分支Trie樹中的每一個節點，利用兩個數組來代替，第一數組存儲該節點中的非空指針值，而第二數組存儲每一個非空指針值在該節點中的對應位置。

9.根據權利要求7所述的設備，其中，所述存儲單元初始化多分支Trie樹結構，使得與根節點相對應的數組中均為空指針。

10.根據權利要求8所述的設備，其中，所述壓縮單元針對多分支Trie樹中的每一個節點，通過遍歷與該節點相對應的數組，將非空指針和其相應的位置分別存儲在第一數組和第二數組中。

11.根據權利要求8所述的設備，還包括查找單元，如果需要查找已存儲的IPv6地址前綴，則所述查找單元使用二分法依次查找每一層節點的第二數組。

12.根據權利要求7-11中任意一項所述的設備，其中，步長K等于16。