[發明專利]一種IPv6數據分區及快速查找方法

有效

• 申請號: 201210353161.X
• 申請日: 2012-09-20
• 公開（公告）號: CN102868779A
• 公開（公告）日: 2013-01-09
• 發明（設計）人: 萬月亮;金波;孔華鋒
• 申請（專利權）人: 北京銳安科技有限公司;公安部第三研究所
• 主分類號: H04L29/12
• 分類號: H04L29/12;G06F17/30
• 代理公司: 北京君尚知識產權代理事務所(普通合伙) 11200
• 代理人: 余功勛

1.一種IPv6數據分區方法，其特征在于，對IPv6地址采用分區樹的方式進行多層分區儲存，步驟包括：

1）構造分區樹，根據IPv6地址分配和實際使用情況將IPv6地址分為n層，從第1層到第n層的映射關系為1：2^c1：2^c2：…：2^cn；其中C1+C2+…+Cn=128，第n層分區段為葉節點，儲存IPv6地址；

2）依據構造的分區樹，對于給定的IPv6地址確定分區樹葉節點，將IPv6地址儲存在給定的葉節點。

2.如權利要求1所述的方法，其特征在于，步驟還包括：

3）設定葉節點的離散閾值Ds，計算歸屬同層分支上的葉節點離散度D，如果離散度D大于閾值Ds，將相鄰分區段進行聚合；

4）重復步驟3），直到葉節點不滿足聚合條件，聚合結束，完成IPv6地址的儲存。

3.如權利要求1所述的方法，其特征在于，每層的分區用兩個數字表示分區大小，一個是分區開始值，一個是分區結束值。

4.如權利要求1所述的方法，其特征在于，n=15，從第1層到第15層的映射關系為1：2¹⁶：2⁸：2⁸：2⁸：2⁸：2⁸：2⁸：2⁸：2⁸：2⁸：2⁸：2⁸：2⁸：2¹⁶。

5.如權利要求1至4任一項所述的方法，其特征在于，采用并行計算的方法確定葉節點，步驟為：

1）按照16、8、8、8、8、8、8、8、8、8、8、8、8、16位分割128位；

2）計算分割的IPv6地址，確定該地址所屬的層和分區。

6.如權利要求1所述的方法，其特征在于，步驟3）中的聚合方法為：

1）計算葉節點離散度D_i=[N_i]/2¹⁶，統計各分區離散度不為零的值；其中D_i∈D，D=[D₀,…,D_n]，n=2^(128-16)，[N_i]為葉節點IPv6地址數量；

2）對滿足D_i>D_s或D_i+1>D_s的分區，（[N_i]+[N_i-1]）<2¹⁶，合并相鄰的兩個分區D_i和D_i+1為一個分區D_i。

7.如權利要求2所述的方法，其特征在于，所述離散閾值Ds設置為50%。

8.如權利要求2所述的方法，其特征在于，步驟3）所述分區段的IP數量超過葉節點數量，時，不聚合。

9.一種按照權利要求1所述的IPv6數據分區方法進行IPv6數據查找方法，其特征在于，跟據給定的IPv6地址進行葉節點的定位查找。

10.如權利要求9所述的方法，其特征在于，所述定位查找的步驟為：

1）將各層分區范圍存放在一個數組或者多hash鏈表數據結構中；

2）根據并行計算出來的各層分區值，自上而下地按層次進行查找；

3）當路徑達到葉節點，完成定位查找。