分布式ipv6路由查找方法和系统

摘要

本发明公开了分布式ipv6路由查找方法和系统，该方法包括：构建前缀长度为32位和前缀长度为48位的多分支Trie树；将所有前缀长度除了32位与48位的路由项以前缀长度划分，并建立哈希表；当添加路由项时，判定添加路由项的前缀长度是否为32或48，若是，则将添加路由项添加到多分支Trie树中的对应位置，若不是，则添加到哈希表中；当转发报文时，根据报文分别在多分支Trie树和哈希表中匹配结果转发报文。本发明具有如下优点：将前缀长度为32位和48位的路由占的总数较大，使用多分支Trie树极大的提高了查找速度；其它前缀长度的路由长度分布广、总数较少，用基于前缀长度的算法实现查找，能极大地提高查找速度。

说明书

技术领域

本发明涉及互联网路由路由技术领域，具体涉及一种分布式ipv6路由查找方法和系统。

背景技术

现有技术中，针对前16位种类少，且多以0x2001开头，通过多层次，多阶段逐步解决ipv6存储空间过大的问题。例如在TSB中，将二叉树、段表和路由桶技术相结合,提出一种多阶段ipv6路由表查找算法。但由于ipv6的飞速发展，现有主干网中路由项数成指数增长，前16位分布变的广泛，使得不仅仅只有0x2001需要段表，主干网中路由项数量的快速增长还使得路由桶技术不能适用，且ipv6存储方案空间需求过大，查找时间过长。

发明内容

本发明旨在至少解决上述技术问题之一。

为此，本发明的一个目的在于提出一种分布式ipv6路由查找方法，以解决现有ipv6存储方案空间需求过大，查找时间过长的问题。

为了实现上述目的，本发明的实施例公开了一种分布式ipv6路由查找方法，包括以下步骤：S110：构建前缀长度为32位和前缀长度为48位的多分支Trie树；S120：将路由器中所有前缀长度除了32位与48位的路由项以前缀长度划分，并建立哈希表；S130：当添加路由项时，判定所述添加路由项的前缀长度是否为32或48，若是，则将所述添加路由项添加到所述多分支Trie树中的对应位置，若不是，则添加到所述哈希表中；S140：当转发报文时，根据所述报文分别在所述多分支Trie树和所述哈希表中匹配结果转发报文。

根据本发明实施例的分布式ipv6路由查找方法，将前缀长度为32位和48位的路由占的总数较大，故使用多分支Trie树，极大的提高了查找速度；其它前缀长度的路由长度分布广，但总数较少，用基于前缀长度的算法实现查找，能极大地提高查找速度。

另外，根据本发明上述实施例的分布式ipv6路由查找方法，还可以具有如下附加的技术特征：

进一步地，所述步骤S140进一步包括：S141：当转发报文时，从所述多分支Trie树查找是否有匹配的路由项，若匹配，则记录第一匹配路由项和第一匹配路由项的前缀长度；若没有匹配的路由项，则进入步骤S142；S142：在所述哈希表中进行查找，若匹配，则记录第二匹配路由项和第二匹配路由项的前缀长度；S143：如果所述报文在所述多分支Trie树和所述哈希表中均无匹配项，则丢且所述报文；如果所述报文存在所述第一匹配路由项或所述第二匹配路由项，则以所述第一匹配路由项或所述第二匹配路由项转发所述报文；如果所述报文存在所述第一匹配路由项和所述第二匹配路由项，则当第一匹配路由项的前缀长度大于第二匹配路由项的前缀长度时，以所述第一匹配路由项转发所述报文；则当第一匹配路由项的前缀长度小于第二匹配路由项的前缀长度时，以所述第二匹配路由项转发所述报文。

进一步地，使用二分查找法从所述哈希表中查找匹配项。

进一步地，在步骤S142中，所述哈希表中查找路由项的前缀长度为16位至64位。

为此，本发明的一个目的在于提出一种分布式ipv6路由查系统，以解决现有ipv6存储方案空间需求过大，查找时间过长的问题。

为了实现上述目的，本发明的实施例公开了一种分布式ipv6路由查系统，包括：路由转发表构建模块，所述路由转发表构建模块用于构建前缀长度为32位和前缀长度为48位的多分支Trie树，所述路由转发表构建模块还用于将路由器中所有前缀长度除了32位与48位的路由项以前缀长度划分，并建立哈希表，所述路由转发表构建模块还用于当添加路由项时，判定所述添加路由项的前缀长度是否为32或48，若是，则将所述添加路由项添加到所述多分支Trie树中的对应位置，若不是，则添加到所述哈希表中；路由转发表查询模块，所述路由转发表查询模块用于分别从所述多分支Trie树和所述哈希表中匹配结果；报文转发模块，用于根据从所述多分支Trie树和所述哈希表中匹配结果转发报文。

根据本发明实施例的分布式ipv6路由查系统，将前缀长度为32位和48位的路由占的总数较大，故使用多分支Trie树，极大的提高了查找速度；其它前缀长度的路由长度分布广，但总数较少，用基于前缀长度的算法实现查找，能极大地提高查找速度。

另外，根据本发明上述实施例的分布式ipv6路由查系统，还可以具有如下附加的技术特征：

进一步地，所述路由转发表查询模块进一步用于：当转发报文时，从所述多分支Trie树查找是否有匹配的路由项，若匹配，则记录第一匹配路由项和第一匹配路由项的前缀长度，如在所述多分支Trie树中没有匹配项，则在所述哈希表中进行查找，若匹配，则记录第二匹配路由项和第二匹配路由项的前缀长度；所述报文转发模块进一步用于：如果所述报文在所述多分支Trie树和所述哈希表中均无匹配项，则丢且所述报文；如果所述报文存在所述第一匹配路由项或所述第二匹配路由项，则以所述第一匹配路由项或所述第二匹配路由项转发所述报文；如果所述报文存在所述第一匹配路由项和所述第二匹配路由项，则当第一匹配路由项的前缀长度大于第二匹配路由项的前缀长度时，以所述第一匹配路由项转发所述报文；则当第一匹配路由项的前缀长度小于第二匹配路由项的前缀长度时，以所述第二匹配路由项转发所述报文。

进一步地，所述路由转发表查询模块使用二分查找法从所述哈希表中查找匹配项。

进一步地，所述哈希表中查找路由项的前缀长度为16位至64位。

本发明的附加方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实践了解到。

附图说明

本发明的上述和/或附加的方面和优点从结合下面附图对实施例的描述中将变得明显和容易理解，其中：

图1是本发明一个实施例的分布式ipv6路由查找方法的流程图；

图2是本发明一个实施例的分布式ipv6路由查找系统的结构框图。

具体实施方式

下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，仅用于解释本发明，而不能理解为对本发明的限制。

在本发明的描述中，需要理解的是，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性。

参照下面的描述和附图，将清楚本发明的实施例的这些和其他方面。在这些描述和附图中，具体公开了本发明的实施例中的一些特定实施方式，来表示实施本发明的实施例的原理的一些方式，但是应当理解，本发明的实施例的范围不受此限制。相反，本发明的实施例包括落入所附加权利要求书的精神和内涵范围内的所有变化、修改和等同物。

以下结合附图描述本发明。

图1是本发明一个实施例的分布式ipv6路由查找方法的流程图。如图1所示，一种分布式ipv6路由查找方法，包括以下步骤：

S110：构建前缀长度为32位和前缀长度为48位的多分支Trie树。

具体地，令路由器中32位和48位的路由项为X₁。构造多分支Trie树，多分支Trie树中第一层为前缀长度是16位的路由项，第二层为前缀长度是32位的路由项，第三层为前缀长度是48位的路由项。每一层查找16个比特位。将X₁中的路由项添加到Trie树中。令Trie树中除最后一层的节点为X₂，对于X₂中的每一个节点都建立一个大小为2¹⁶的数组，该数组用于记录子节点信息。将查找子节点对应的16个比特位数值化，并记录到数组中对应的位置。

S120：将路由器中所有前缀长度除了32位与48位的路由项以前缀长度划分，并建立哈希表。

具体地，在本发明的一个示例中，Hash(40)表示前缀长度为40的所有路由项的Hash表。将第i次查找的前缀长度记为S_i，基于二分查找加入标记位(若S_i<S_i-1，则对比在S_i～S_i-1中的前缀项，是否有比该节点更加匹配的路由项，若有则在该节点添加标记位。若S_i>S_i-1，则对比在S_i～2S_i-S_i-1中的前缀项，是否有比该节点更加匹配的路由项，若有则在该节点添加标记位)，使之可以进行二分查找。

S130：当添加路由项时，判定添加路由项的前缀长度是否为32或48，若是，则将添加路由项添加到多分支Trie树中的对应位置，若不是，则添加到哈希表中，并根据步骤S120加入相应的标记位。。

S140：当转发报文时，根据报文分别在多分支Trie树和哈希表中匹配结果转发报文。

在本发明的一个实施例中，使用二分查找法从哈希表中查找匹配项，能极大地提高查找速度。

在本发明的一个实施例中，步骤S140进一步包括：

S141：当转发报文时，从多分支Trie树查找是否有匹配的路由项，若匹配，则记录第一匹配路由项和第一匹配路由项的前缀长度；若没有匹配的路由项，则进入步骤S142。

具体地，令转发的报文为S。首先在Trie树中查找是否有和S匹配的路由项。若没有匹配的路由项，则直接进行下一步二分查找。若匹配，则记录下匹配的路由项，记为A，A的前缀长度为i。

S142：在哈希表中进行查找，若匹配，则记录第二匹配路由项和第二匹配路由项的前缀长度。

具体地，在哈希表中进行二分查找。若匹配，则记录下匹配的路由项，记为B，B的前缀长度为j。

S143：如果报文在多分支Trie树和哈希表中均无匹配项，则丢且报文；

如果报文存在第一匹配路由项或第二匹配路由项，则以第一匹配路由项或第二匹配路由项转发报文；

如果报文存在第一匹配路由项和第二匹配路由项，则当第一匹配路由项的前缀长度大于第二匹配路由项的前缀长度时，以第一匹配路由项转发报文；则当第一匹配路由项的前缀长度小于第二匹配路由项的前缀长度时，以第二匹配路由项转发报文。

具体地，若Trie树中与Hash表中都无匹配项，则丢弃报文。若Trie树中与Hash表中有且仅有一项匹配，则以此路由项转发报文。若Trie树中与Hash表中都有匹配的路由项，则比较路由项的前缀长度。若i>j，以A为匹配项转发报文。若i<j,以B为匹配项转发报文。

在本发明的一个实施例中，哈希表中查找路由项的前缀长度为16位至64位。

本发明实施例的分布式ipv6路由查找方法，将前缀长度为32位和48位的路由占的总数较大，故使用多分支Trie树，极大的提高了查找速度；其它前缀长度的路由长度分布广，但总数较少，用基于前缀长度的算法实现查找，能极大地提高查找速度。

图2是本发明一个实施例的分布式ipv6路由查找系统的结构框图。如图2所示，一种分布式ipv6路由查找系统，包括路由转发表构建模块210、路由转发表查询模块220和报文转发模块230。

其中，路由转发表构建模块210用于构建前缀长度为32位和前缀长度为48位的多分支Trie树。路由转发表构建模块210还用于将路由器中所有前缀长度除了32位与48位的路由项以前缀长度划分，并建立哈希表。路由转发表构建模块210还用于当添加路由项时，判定添加路由项的前缀长度是否为32或48，若是，则将添加路由项添加到多分支Trie树中的对应位置，若不是，则添加到哈希表中

路由转发表查询模块220用于分别从多分支Trie树和哈希表中匹配结果。

报文转发模块230用于根据从多分支Trie树和哈希表中匹配结果转发报文。

在本发明的一个实施例中，路由转发表查询模块220进一步用于：当转发报文时，从多分支Trie树查找是否有匹配的路由项，若匹配，则记录第一匹配路由项和第一匹配路由项的前缀长度，如在多分支Trie树中没有匹配项，则在哈希表中进行查找，若匹配，则记录第二匹配路由项和第二匹配路由项的前缀长度。

报文转发模块230进一步用于：如果报文在多分支Trie树和哈希表中均无匹配项，则丢且报文；如果报文存在第一匹配路由项或第二匹配路由项，则以第一匹配路由项或第二匹配路由项转发报文；如果报文存在第一匹配路由项和第二匹配路由项，则当第一匹配路由项的前缀长度大于第二匹配路由项的前缀长度时，以第一匹配路由项转发报文；则当第一匹配路由项的前缀长度小于第二匹配路由项的前缀长度时，以第二匹配路由项转发报文。

在本发明的一个实施例中，路由转发表查询模块220使用二分查找法从哈希表中查找匹配项。

在本发明的一个实施例中，哈希表中查找路由项的前缀长度为16位至64位。

需要说明的是，本发明实施例的分布式ipv6路由查找系统的具体实施方式与本发明实施例的分布式ipv6路由查找方法的具体实施方式类似，具体请参见方法部分，为了较少冗余，不作赘述。

另外，本发明实施例的分布式ipv6路由查找方法和系统的其它构成以及作用对于本领域的技术人员而言都是已知的，为了减少冗余，不做赘述。

在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不一定指的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任何的一个或多个实施例或示例中以合适的方式结合。

尽管已经示出和描述了本发明的实施例，本领域的普通技术人员可以理解：在不脱离本发明的原理和宗旨的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由权利要求及其等同限定。