一种针对可变长地址的路由查找方法及装置

1.本说明书一个或多个实施例涉及分组交换网络中的路由查找技术领域，尤其涉及一种针对可变长地址的路由查找方法及装置。


背景技术：

2.目前，采用“存储-转发”技术的分组交换网络在数字通信领域中得到了蓬勃发展。分组交换技术将信息负载分割成较小、限长的数据段，并对每个数据段添加相应的标识信息(如目的地址、源地址和报文类型等)组成一个数据报文。
3.然而，在进行数据传输时，分组交换网络中的网络设备收到数据报文后，首先将报文存储下来并进行解析，得到报文头部中的相应标识信息(如目的地址)，然后根据标识信息到相应的转发信息库中进行查询得到下一跳接口，最后转发模块将数据报文从所查询到的接口传送出去，从而完成数据报文的查找转发。
4.网络设备可以面向不同长度的地址建立一个统一的路由转发表，因此，具备不同长度网络地址的数据报文可以由同一张路由转发表提供查找下一跳接口的功能。在进行查找转发时，网络设备根据任意长度的地址进行路由表查找操作，从而决定数据报文的下一跳接口。查找转发的效率很大程度上决定了网络传输的性能，因而针对数据报文路由查找的研究受到了业界的广泛关注。
5.经过几十年的发展，路由查找技术已经广泛应用各种分组交换网络中，特别是在计算机网络中，各式各样的路由查找方法不断被提出。然而，随着ip网络应用环境和用户需求的不断增长，越来越多的新型网络应用逐渐兴起，面向未来智能机器通信、万物互联、万网互联等新业务能力需求不断高涨。传统互联网基于固定有界ip地址实现互连互通的缺陷逐渐暴露，且缺乏灵活有效的扩展方式来适应未来多样化、专业化业务的发展需求。
6.可变长地址技术是解决上述问题的一种有效方案，它能够根据网络规模及应用场景需求的不同提供适应长度的地址结构，因此能够满足各种异构网络、异构终端实现万物互联的需求。然而，可变长地址虽然是具有灵活可变长的优点，能够依据实际需求定制地址长度，但是这也给路由查找工作带来了一定的困难。如果仍然以传统最长前缀的地址长度统一存储所有路由条目并基于此进行路由查找，将会对路由查找算法的存储空间和查找性能带来巨大挑战。
7.具体到数据报文的路由查找转发而言，可变长地址的路由条目是灵活多样的，现有的路由查找方法是基于固定长度的地址格式进行查找、转发的，直接使用传统适用于固定地址长度的路由查找方法很难满足可变长地址灵活高效路由的需求。同时，通过对可变长地址按照一定方式进行分类，将其转化成多种固定长度的地址，使其适用传统的路由查找方法。但是，这些方式不但会造成资源上的浪费，还会极大地降低数据报文的处理性能，从而影响网络的通信质量。
8.因此，可变长地址背景下的路由查找相关解决方案成为领域内亟需解决的难题。然而，现有面向可变长地址网络的研究尚且过少，而针对可变长地址的路由查找方法的研
究更为缺乏。本发明专利就是针对这一场景提出的一种在分组交换网络中针对可变长地址的路由查找方法和装置。


技术实现要素：

9.本发明描述一种针对可变长地址的路由查找方法及装置，可以解决上述技术问题。
10.根据第一方面，提供一种针对可变长地址的路由查找方法。该方法包括：对路由转发信息库进行统计分析，获得路由前缀长度范围和每个路由前缀长度所对应的路由前缀数目；将路由前缀长度范围划分为n个相等区间并统计每个区间内的路由前缀数目；依据每个区间路由前缀数量进行排序，获取高频路由集合和低频路由集合；使用布隆过滤器和哈希表存储所述高频路由集合，使用字典树存储所述低频路由集合；将到达路由器的数据包在所述高频路由集合进行路由查询，如果在所述高频路由集合没有找到匹配项，则查找低频路由集合。
11.在一个实施例中，所述使用布隆过滤器和哈希表存储高频路由前缀包括：针对高频路由前缀的每个区间，都构建一个布隆过滤器及其哈希表来存储相应的路由前缀信息。
12.在一个实施例中，所述使用布隆过滤器和哈希表存储高频路由集合包括：将高频路由集合切分成定长部分和变长部分，定长部分存储于哈希表中，变长部分指向一个字典树存储。
13.在一个实施例中，所述将到达路由器的数据包在高频路由集合进行路由查询包括：先通过在每个哈希表上构建布隆过滤器进行预筛选。
14.在一个实施例中，如果在所述高频路由集合找到匹配条目后，则获取下一跳端口信息进行转发。
15.在一个实施例中，还包括对所述路由器的路由转发信息库进行路由前缀添加，路由前缀长度属于高频路由集合则添加到哈希表中，路由前缀长度属于低频路由集合，则存储于字典树中。
16.根据第二方面，提供一种针对可变长地址的路由查找装置。该装置包括：路由信息统计模块，用于对路由转发信息库进行统计分析，获得路由前缀长度范围和每个路由前缀长度所对应的路由前缀数目；路由前缀长度划分模块，配置为将路由前缀长度范围划分为n个相等区间并统计每个区间内的路由前缀数目；路由前缀排序模块，配置为依据每个区间路由前缀数量进行排序，获取高频路由集合和低频路由集合；路由前缀存储模块，配置为使用布隆过滤器和哈希表存储高频路由集合，使用字典树存储低频路由集合。路由前缀查询模块，配置为将到达路由器的数据包在高频路由集合进行路由查询，如果在所述高频路由集合没有找到匹配项，则查找低频路由集合。
17.在一个实施例中，该装置还包括路由前缀添加模块。
18.在一个实施例中，所述路由前缀排序模块具体用于：
19.将排序前k个区间的路由前缀条目作为高频路由集合，排序[k+1]-[n]区间的路由前缀条目作为低频路由集合。
[0020]
在一个实施例中，所述路由前缀存储模块具体用于：针对高频路由前缀的每个区间，都构建一个布隆过滤器及其哈希表来存储相应的路由前缀信息。
[0021]
在一个实施例中，所述路由前缀存储模块具体用于：将高频路由集合中的路由条目切分成定长部分和变长部分，定长部分存储于哈希表中，变长部分指向一个字典树存储。
[0022]
在一个实施例中，所述路由前缀查询模块具体用于：先通过在每个哈希表上构建布隆过滤器进行预筛选。
[0023]
在本说明书实施例提供的上述方法和装置中，通过采用布隆过滤器和字典树来实现可变长地址的高效路由查找。该方法主要是依靠统计分析等技术，将转发信息库中的路由条目，按高频使用和低频使用原则进行划分，并应用不同的数据结构去处理这些路由条目。为了加速路由查找速度，在每个哈希表上构建布隆过滤器来进行预筛选，减少哈希表的访问次数。
附图说明
[0024]
为了更清楚地说明本发明实施例的技术方案，下面对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其它的附图。
[0025]
图1示出本技术实施例提供的一种针对可变长地址的路由查找方法的流程示意图；
[0026]
图2示出本技术实施例提供的可变长地址路由前缀分布情况；
[0027]
图3示出本技术实施例提供的高频路由前缀的存储结构示意图；
[0028]
图4示出本技术实施例提供的低频路由条目的存储数据结构；
[0029]
图5示出本技术实施例提供的基于布隆过滤器和字典树查找方法的架构；
[0030]
图6示出本技术实施例提供的查找路由前缀条目流程；
[0031]
图7示出本技术实施例提供的添加路由前缀条目流程；
[0032]
图8示出本技术实施例提供的可变长路由查找模块部署图；
[0033]
图9示出本技术实施例提供的一种针对可变长地址的路由查找装置的结构示意图。
具体实施方式
[0034]
下面结合附图，对本说明书提供的方案进行描述。
[0035]
为了使本技术实施例的目的、技术方案和优点更加清楚，下面将结合附图，对本技术实施例中的技术方案进行描述。
[0036]
在本技术实施例的描述中，“示例性的”、“例如”或者“举例来说”等词用于表示作例子、例证或说明。本技术实施例中被描述为“示例性的”、“例如”或者“举例来说”的任何实施例或设计方案不应被解释为比其它实施例或设计方案更优选或更具优势。确切而言，使用“示例性的”、“例如”或者“举例来说”等词旨在以具体方式呈现相关概念。
[0037]
在本技术实施例的描述中，术语“和/或”，仅仅是一种描述关联对象的关联关系，表示可以存在三种关系，例如，a和/或b，可以表示：单独存在a，单独存在b，同时存在a和b这三种情况。另外，除非另有说明，术语“多个”的含义是指两个或两个以上。
[0038]
此外，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性
或者隐含指明所指示的技术特征。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括一个或者更多个该特征。术语“包括”、“包含”、“具有”及它们的变形都意味着“包括但不限于”，除非是以其他方式另外特别强调。
[0039]
图1示出本说明书实施例提供的一种针对可变长地址的路由查找方法的流程示意图，如图1所示，该方法包括以下步骤：
[0040]
步骤s110，对路由转发信息库进行统计分析，获得路由前缀长度范围和每个路由前缀长度所对应的路由前缀数目。
[0041]
为了区分路由前缀的高低频性质，可通过对路由器转发信息库的路由前缀条目分布情况进行统计分析来确定。图2示出本技术实施例提供的可变长地址路由前缀分布情况，如图2所示，可变长地址网络某个有限域网元节点的路由前缀分布，路由前缀在某些长度区间占有较多的数量，因而应当以此规律设计路由查找方法，在该网元节点中，路由前缀长度为25-31bit，73-79bit，91-97bit，103-115bit的数量相对较多。
[0042]
在一些实施例中，本步骤的实施包括：首先，按照前缀长度对路由前缀集合进行分类统计分析，得到每个前缀长度下所拥有的路由前缀数目。
[0043]
步骤s120，将路由前缀长度范围划分为n个相等区间并统计每个区间内的路由前缀数目。
[0044]
在一些实施例中，对步骤s110得出的路由前缀长度统计结果，平均分为n个相等的区间，统计每个区间的路由前缀数量，即把该区间内的每个路由前缀长度对应的数量相加。按照每个区间的路由前缀数量递减的顺序排序。
[0045]
步骤s130，依据每个区间路由前缀数量进行排序，获取高频路由前缀集合和低频路由前缀集合。
[0046]
将排序前k个区间的路由前缀条目作为高频路由集合。排序[k+1]-[n]区间的路由前缀条目作为低频路由集合。
[0047]
步骤s140，使用布隆过滤器(bloom filter，简称bloom过滤器)和哈希表存储高频路由集合，使用字典树(trie tree，简称trie树)存储低频路由集合。
[0048]
图3为本技术实施例提供的高频路由前缀的存储结构示意图，如图3所示，为每个高频路由集合的路由前缀长度都维护一张哈希表。一个哈希表对应于一个区间的路由前缀，步骤s130的前k个区间分别为：长度属于[len1,len1+l]，[len2,len2+l]，[len3,len3+l]
…
[lenk,lenk+l]的区间，对应的路由前缀存储依次存储在哈希表1，哈希表2，哈希表3
…
哈希表k中，其中len的值根据函数传入的参数确定。
[0049]
现在有k个哈希表，每个哈希表存储有若干路由前缀，这些路由前缀长度都属于一个区间。以前k个区间的任意区间为例，说明高频路由前缀的存储结构，每个路由前缀分为定长部分f和变长部分v，其中，定长部分f存储在对应的哈希表中，变长部分v存储在小型tire树中，通过指针技术指向一个小型的trie树来存储。
[0050]
使用trie树存储低频路由前缀，图4为本技术实施例提供的低频路由条目的存储数据结构，如图4所示，根据低频路由前缀区间的路由前缀构建至少一个根节点，根节点包含路由表中所有的前缀，通过路由前缀的比特位的值，0表示左子节点，1表示右子节点，构建树的左右节点，并将下一跳出口信息存储在节点中，在一个实施例中，路由110*的下一跳端口为h，路由011*的下一跳端口为c。
[0051]
步骤s150，将到达路由器的数据包在高频路由集合进行路由查询，如果在所述高频路由集合没有找到匹配项，则查找低频路由集合。
[0052]
图5示出本技术实施例提供的基于布隆过滤器和字典树查找方法的架构，如图5所示，网络数据报文进入到网元设备后，先将数据报文进行解析，然后交给分组交换模块处理，分组交换模块将转发信息库中的路由条目，即可变长路由集合，进行统计建模分析，把路由前缀分为高频路由集合和低频路由集合。其中k个高频路由集合对应k张哈希表。低频路由集合由对应的trie树进行查找。
[0053]
图6示出本技术实施例提供的查找路由前缀条目流程，如图6所示，在高频路由前缀查找中，哈希查找首先根据不同的路由前缀长度分别构建与每个路由前缀对应的哈希表，使得每一个路由前缀都有一个哈希表。步骤s120中高频路由部分划分的k个区间分别创建k个哈希表。
[0054]
在一个实施例中，bloom滤波器为一个长为m比特的位向量v，用于存储集合元素的映射信息，k个相互独立的哈希表，哈希表1，哈希表2，哈希表3
…
哈希表k，对应于k个bloom滤波器。将哈希表中的路由前缀条目映射到位向量v中。在每个哈希表上构建bloom滤波器进行预筛选，减少了哈希表的访问次数。
[0055]
首先，将位向量v初始化，将v中每个比特位置零，计算哈希表中的路由前缀条目的m个哈希值，根据计算出的哈希值将位向量v中对应的比特位置1或者0。
[0056]
在一个实施例中，若v中的某个比特位在执行映射之前已经置1，则该位在执行映射时不做任何变化。
[0057]
在一个实施例中，每一个路由前缀区间都对应一个bloom滤波器，将哈希表中的路由前缀输入到滤波器中进行查询，查询结果被存储到一个匹配向量中，最后，根据匹配向量得到各比特位的取值情况。
[0058]
将一个元素通过哈希函数映射到一个m长度的阵列上的一个点，当这个点是1时，将不同长度的路由前缀插入到不同的布隆滤波器中。
[0059]
如果在高频路由集合中找到匹配项，则记录当前匹配前缀的路由信息，返回下一跳查询结果。
[0060]
查找哈希表k中没有匹配项，则继续查找哈希表k-1，直到遍历完成最后一张哈希表1。因为哈希表k的存储条目最多，获得匹配的概率更大，可以减少查询次数。
[0061]
在高频路由部分查找阶段，这里所记录的路由信息是定长部分f和变长部分v的长度，然后查看查询标志位flag字段和最优标志位mark字段。
[0062]
1)若flag字段值为0，则表明找到了匹配的路由条目，则读取已经记录的路由信息转发数据分组。
[0063]
2)若flag字段值为1，则表明没有找到匹配的路由条目，指针s指向下一个哈希表。
[0064]
3)当查找到一条匹配的路由条目时，需要再次检查mark位来验证该路由条目是否为最佳路由前缀。如果mark字段值为0则说明当前路由条目为最佳前缀；如果mark字段值为1则说明当前路由条目不是最佳前缀，还存在更长的路由前缀，因而还需要继续往后查找，直到获取最佳路由前缀。
[0065]
在一个实施例中，如果在高频路由集合没有匹配条目，则到低频路由集合对应的trie树中查找。
[0066]
在低频路由查找阶段，到低频路由集合对应的trie树中查找。
[0067]
本技术采用不同路由地址长度公用同一个滤波器，减少了滤波器的总数，减少了路由查找过程的次数。
[0068]
以下为基于bloom过滤器和trie树的可编程地址路由查找方法在路由前缀添加时的说明，当分组交换数据到达时，根据可变长路由前缀的分布规律进行预判断，将路由前缀推送到相适应的地方进行存储。图7为本实施例提供的添加路由前缀条目流程。如图7所示，
[0069]
前缀长度属于[len1,len1+l]，则将该前缀存储与哈希表1中，
[0070]
前缀长度属于[lenk,lenk+l]，则将该前缀存储与哈希表k中，
[0071]
如果前缀长度属于低频路由集合，则存储在对应的trie树中。
[0072]
以下结合在网元设备中的部署拓扑图来说明本发明。图8示出本技术实施例提供的可变长路由查找模块部署图。依据本发明的一个方面，提供了一种基于网元设备的通过布隆过滤器和trie树来实现可变长地址路由查找的装置模块，该模块在网元设备中的部署拓扑图如图7所示：
[0073]
该网元设备由三大部分组成，分别是输入输出模块、分组报文交换模块、路由查找模块。
[0074]
网络数据报文由输入端口进入到网元设备之后，首先将数据报文解析后交由分组交换模块处理；然后可变长路由查找模块查询由路由生成模块依据路由协议生成的路由表来建立相应的转发表来得到下一跳及输出接口；最后交由输出端口进行排队输出。
[0075]
输入输出模块，为网元设备处理的起点和终点，主要用于接收和发送数据报文，即把数据报文数据从传输信道中还原出来，并存储于相应队列中，以便网元后续进行处理。
[0076]
分组交换模块，主要根据数据报文中携带的控制信息并通过可变长路由查找模块来查询路由选择模块的路由表并生成相应的转发表来指导数据报文的转发。可变长路由查找模块主要是基于bloom过滤器和trie树实现的路由查找算法，首先对路由选择协议生成的路由表进行统计分类，然后对其中的各个类别采用bloom过滤器和trie树来存储生成转发表，最后查找模块依据地址在该转发表中进行路由查找转发。
[0077]
路由生成模块的主要功能为根据所配置的路由协议来获取域内各个网元节点的信息并生成相应的路由表项。数据报文在进行转发时，可以通过该路由表来建立相应的转发表。
[0078]
上述说明仅是本发明技术方案的概述，为了能够更清楚了解本发明的技术手段，而可以依照说明书的内容予以实施，并且为了让本发明的上述和其它目的、特征和优点能够更明显易懂，以下将以基于本发明的具体实施方式进行描述。下面将参照以上说明更详细地描述本公开的示例性实施例。虽然本实施案例显示了本公开的示例性实施例，然而应当理解，可以以各种形式实现本公开而不应被这里阐述的实施案例所限制。相反，提供这些实施例是为了能够更透彻地理解本公开，并且能够将本公开的范围完整的传达给本领域的技术人员。
[0079]
以下将通过一个具体路由转发信息库的例子来阐释该发明是如何对可变长路由前缀进行查找转发的。图2所示的可变长地址路由前缀分布情况，从中我们可以看出，路由前缀在某些长度区间占着较多的数量，因而我们应当以此规律设计路由查找方法。
[0080]
依据本发明的步骤所述，本实施例的具体操作如下：
[0081]
1)通过对网元节点的路由转发信息库进行统计分析，获取所在网络的路由前缀分布情况及其每个前缀长度下所拥有的路由前缀数目。然后对所划分的n个相等区间进行统计并按照数量进行排序，并将排序前k个区间的所有路由前缀条目作为高频路由前缀，而其余区间的路由前缀条目作为低频路由前缀。具体函数处理流程如下所示：
[0082][0083]
2)根据所划分的路由，对于高频部分，每个区间建立相应的哈希表及bloom过滤器来处理，对于低频部分则有trie树存储，具体代码如下；
[0084][0085]
3)建立路由查找处理流程，首先将可变长地址在最长的哈希表k进行查找，如果找到则返回下一跳查询结果，否则将继续在哈希表k-1查找；如果在高频路由部分不匹配，则去低频路由前缀部分的trie树查找。代码如下：
[0086]
[0087][0088]
以上代码部分为本方案实现方式的一种，该发明方法可基于硬件实现，也可基于软件编码实现，在本次实施演示中，采用软件编码的方式来展现该发明。具体的，本发明的具体实施例是基于c语言来进行研究开发，也可以采用其他语言。
[0089]
与本发明提供的上述方法相对应的，本发明还提供一种装置。图9示出本说明书实施例提供的一种针对可变长地址的路由查找装置的结构示意图。
[0090]
如图9所示，该装置900包括：
[0091]
路由信息统计模块910，用于对路由转发信息库进行统计分析，获得路由前缀长度范围和每个路由前缀长度所对应的路由前缀数目；
[0092]
路由前缀长度划分模块920，配置为将路由前缀长度范围划分为n个相等区间并统计每个区间内的路由前缀数目；
[0093]
路由前缀排序模块930，配置为依据每个区间路由前缀数量进行排序，获取高频路由集合和低频路由集合；
[0094]
路由前缀存储模块940，配置为使用bloom过滤器和哈希表存储高频路由集合，使用trie树存储低频路由集合。
[0095]
路由前缀查询模块950，配置为将到达路由器的数据包在高频路由集合进行路由查询，如果在高频路由集合没有找到匹配项，则查找低频路由集合。
[0096]
在路由查询模块950之后还包括路由添加模块960，具体用于：对路由器的路由转发信息库进行路由前缀添加，路由前缀长度属于高频路由集合则添加到哈希表中，路由前缀长度属于低频路由集合，则存储于字典树中。
[0097]
路由前缀排序模块930具体用于：将排序前k个区间的路由前缀条目作为高频路由集合，排序[k+1]-[n]区间的路由前缀条目作为低频路由集合。
[0098]
路由前缀存储模块940具体用于：针对高频路由前缀的每个区间，都构建一个布隆过滤器及其哈希表来存储相应的路由前缀信息。
[0099]
路由前缀存储模块940还用于：将高频路由集合中的路由切分成定长部分和变长部分，定长部分存储于哈希表中，变长部分指向一个字典树存储。
[0100]
路由前缀查询模块950具体用于：先通过在每个哈希表上构建bloom过滤器进行预筛选。
[0101]
需要说明，对图9中装置的描述，还可以参见对前述方法的描述。
[0102]
根据另一方面的实施例，还提供一种计算机可读存储介质，其上存储有计算机程序，当所述计算机程序在计算机中执行时，令计算机执行结合图1所描述的方法。
[0103]
根据再一方面的实施例，还提供一种计算设备，包括存储器和处理器，所述存储器
中存储有可执行代码，所述处理器执行所述可执行代码时，实现结合图1所描述的方法。本领域技术人员应该可以意识到，在上述一个或多个示例中，本发明所描述的功能可以用硬件、软件、固件或它们的任意组合来实现。当使用软件实现时，可以将这些功能存储在计算机可读介质中或者作为计算机可读介质上的一个或多个指令或代码进行传输。
[0104]
在此提供的算法和显示不与任何特定计算机、虚拟装置或者其它设备固有相关。各种通用装置也可以与基于在此的示教一起使用。根据上面的描述，构造这类装置所要求的结构是显而易见的。此外，本发明也不针对任何特定的编程语言。应当明白，可以利用各种编程语言实现在此描述的本发明内容，并且上面对特定语言、系统功能模块的调用所做的描述仅仅是为了披露发明的最佳实施方式。
[0105]
在此处所提供的说明书中，说明了大量的具体细节。然而，能够理解，本发明的实施例可以在没有这些具体细节的情况下完成实现。在一些示例中，并未详细示出公知的方法、结构和技术，以便不模糊对本说明书的理解。
[0106]
显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精神和范围。这样，倘若对本发明的这些修改和变型属于本发明权利要去及其同等技术的范围之内，则本发明也意图包含这些改动和变型在内。

技术特征：
1.一种针对可变长地址的路由查找方法，其特征在于，所述方法包括：对路由转发信息库进行统计分析，获得路由前缀长度范围和每个路由前缀长度所对应的路由前缀数目；将路由前缀长度范围划分为n个相等区间并统计每个区间内的路由前缀数目；依据每个区间路由前缀数目进行排序，获取高频路由集合和低频路由集合；使用布隆过滤器和哈希表存储所述高频路由集合，使用字典树存储所述低频路由集合；将到达路由器的数据包在所述高频路由集合进行路由查询，如果在所述高频路由集合没有找到匹配项，则查找所述低频路由集合。2.根据权利要求1所述的方法，其特征在于，所述获取高频路由集合和低频路由集合包括：将排序前k个区间的路由前缀条目作为高频路由集合，排序[k+1]-[n]区间的路由前缀条目作为低频路由集合。3.根据权利要求1所述的方法，其特征在于，所述使用布隆过滤器和哈希表存储高频路由集合包括：针对高频路由集合的每个区间，都构建一个布隆过滤器及其哈希表来存储相应的路由前缀信息。4.根据权利要求1所述的方法，其特征在于，所述使用布隆过滤器和哈希表存储高频路由集合包括：将高频路由集合中的路由切分成定长部分和变长部分，定长部分存储于哈希表中，变长部分指向一个字典树存储。5.根据权利要求1所述的方法，其特征在于，所述将到达路由器的数据包在所述高频路由集合进行路由查询包括：先通过在每个哈希表上构建布隆过滤器进行预筛选。6.根据权利要求1任一项所述的方法，其特征在于，还包括：如果在所述高频路由集合找到匹配条目后，则获取下一跳端口信息进行转发。7.根据权利要求1-5任一项所述的方法，其特征在于，还包括对所述路由器的路由转发信息库进行路由前缀添加，路由前缀长度属于高频路由集合则添加到哈希表中，路由前缀长度属于低频路由集合，则存储于字典树中。8.一种针对可变长地址的路由查找装置，其特征在于，所述装置包括：路由信息统计模块，用于对路由转发信息库进行统计分析，获得路由前缀长度范围和每个路由前缀长度所对应的路由前缀数目；路由前缀长度划分模块，配置为将路由前缀长度范围划分为n个相等区间并统计每个区间内的路由前缀数目；路由前缀排序模块，配置为依据每个区间路由前缀数目进行排序，获取高频路由集合和低频路由集合；路由前缀存储模块，配置为使用布隆过滤器和哈希表存储所述高频路由集合，使用字典树存储所述低频路由集合。路由前缀查询模块，配置为将到达路由器的数据包在所述高频路由集合进行路由查询，如果在所述高频路由集合没有找到匹配项，则查找低频路由集。9.根据权利要求8所述的装置，其特征在于，所述路由前缀排序模块具体用于：将排序前k个区间的路由前缀条目作为高频路由集合，排序[k+1]-[n]区间的路由前缀条目作为低频路由集合。
10.根据权利要求8所述的装置，其特征在于，所述路由前缀存储模块具体用于：将高频路由集合中的路由条目切分成定长部分和变长部分，定长部分存储于哈希表中，变长部分指向一个字典树存储。

技术总结
本发明提供一种针对可变长地址的路由查找方法及装置。该方法包括：将路由前缀长度范围划分为N个相等区间并统计每个区间内的路由前缀数目；然后，依据每个区间路由前缀数量进行排序，获取高频路由集合和低频路由集合；使用布隆过滤器和哈希表存储高频路由集合，使用字典树存储低频路由集合。将到达路由器的数据包在高频路由集合进行路由查询，如果在所述高频路由集合没有找到匹配项，则查找低频路由集合。如此，可以实现将转发信息库中的路由条目，按高频使用和低频使用原则进行划分，并应用不同的数据结构去处理这些路由条目。为了加速路由查找速度，在每个哈希表上构建布隆过滤器来进行预筛选，减少哈希表的访问次数。减少哈希表的访问次数。减少哈希表的访问次数。


技术研发人员：黄永锦 覃毅芳 周旭 张心晴
受保护的技术使用者：中国科学院计算机网络信息中心
技术研发日：2023.03.20
技术公布日：2023/8/14