利索能及
我要发布
收藏
专利号: 2016108291574
申请人: 首都师范大学
专利类型:发明专利
专利状态:已下证
更新日期:2025-02-06
缴费截止日期: 暂无
联系人

摘要:

权利要求书:

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位。