[發明專利]分布式ipv6路由查找方法和系統

有效

• 申請號: 201610829157.4
• 申請日: 2016-09-18
• 公開（公告）號: CN106656816B
• 公開（公告）日: 2019-09-24
• 發明（設計）人: 陳文龍;唐曉嵐;張沛;張銘書
• 申請（專利權）人: 首都師范大學
• 主分類號: H04L12/743
• 分類號: H04L12/743
• 代理公司: 北京清亦華知識產權代理事務所(普通合伙) 11201
• 代理人: 張大威

1.一種分布式ipv6路由查找方法，其特征在于，包括以下步驟：

S110：構建前綴長度為32位和前綴長度為48位的多分支Trie樹；

S120：將路由器中所有前綴長度除了32位與48位的路由項以前綴長度劃分，并建立哈希表；

S130：當添加路由項時，判定所述添加路由項的前綴長度是否為32或48，若是，則將所述添加路由項添加到所述多分支Trie樹中的對應位置，若不是，則添加到所述哈希表中；

S140：當轉發報文時，根據所述報文分別在所述多分支Trie樹和所述哈希表中匹配結果轉發報文。

2.根據權利要求1所述的分布式ipv6路由查找方法，其特征在于，所述步驟S140進一步包括：

S141：當轉發報文時，從所述多分支Trie樹查找是否有匹配的路由項，若匹配，則記錄第一匹配路由項和第一匹配路由項的前綴長度；若沒有匹配的路由項，則進入步驟S142；

S142：在所述哈希表中進行查找，若匹配，則記錄第二匹配路由項和第二匹配路由項的前綴長度；

S143：如果所述報文在所述多分支Trie樹和所述哈希表中均無匹配項，則丟棄所述報文；

如果所述報文存在所述第一匹配路由項或所述第二匹配路由項，則以所述第一匹配路由項或所述第二匹配路由項轉發所述報文。

3.根據權利要求1或2所述的分布式ipv6路由查找方法，其特征在于，使用二分查找法從所述哈希表中查找匹配項。

4.根據權利要求2所述的分布式ipv6路由查找方法，其特征在于，在步驟S142中，所述哈希表中查找路由項的前綴長度為16位至64位。

5.一種分布式ipv6路由查找系統，其特征在于，包括：

路由轉發表構建模塊，所述路由轉發表構建模塊用于構建前綴長度為32位和前綴長度為48位的多分支Trie樹，所述路由轉發表構建模塊還用于將路由器中所有前綴長度除了32位與48位的路由項以前綴長度劃分，并建立哈希表，所述路由轉發表構建模塊還用于當添加路由項時，判定所述添加路由項的前綴長度是否為32或48，若是，則將所述添加路由項添加到所述多分支Trie樹中的對應位置，若不是，則添加到所述哈希表中；

路由轉發表查詢模塊，所述路由轉發表查詢模塊用于分別從所述多分支Trie樹和所述哈希表中匹配結果；

報文轉發模塊，用于根據從所述多分支Trie樹和所述哈希表中匹配結果轉發報文。

6.根據權利要求5所述的分布式ipv6路由查找系統，其特征在于，所述路由轉發表查詢模塊進一步用于：

當轉發報文時，從所述多分支Trie樹查找是否有匹配的路由項，若匹配，則記錄第一匹配路由項和第一匹配路由項的前綴長度，如在所述多分支Trie樹中沒有匹配項，則在所述哈希表中進行查找，若匹配，則記錄第二匹配路由項和第二匹配路由項的前綴長度；

所述報文轉發模塊進一步用于：

如果所述報文在所述多分支Trie樹和所述哈希表中均無匹配項，則丟棄所述報文；

如果所述報文存在所述第一匹配路由項或所述第二匹配路由項，則以所述第一匹配路由項或所述第二匹配路由項轉發所述報文。

7.根據權利要求5或6所述的分布式ipv6路由查找系統，其特征在于，所述路由轉發表查詢模塊使用二分查找法從所述哈希表中查找匹配項。

8.根據權利要求6所述的分布式ipv6路由查找系統，其特征在于，所述哈希表中查找路由項的前綴長度為16位至64位。