一种哈希表和HOT相结合的IPv6路由查找方法

摘要

本发明属于路由查找技术领域，具体来说是涉及一种哈希表和HOT相结合的IPv6路由查找方法。本发明在分析骨干路由表前缀地址分布规律的基础上，提出一种哈希表与HOT相结合的路由查找算法，其核心思想在于将地址前缀分成两个区间，第一区间不易发生冲突，采用哈希表存储，第二区间查询更新频繁，采用HOT存储。经验证，本发明的方法在查询时间以及空间占用等方面都具有较好的性能。

说明书

技术领域

本发明属于路由查找技术领域，具体来说是涉及一种哈希表和HOT相结合的IPv6路由查找方法。

背景技术

近年来，日益枯竭的IPv4地址资源已严重阻碍了互联网的蓬勃发展，目前IPv4地址已全部分配完毕，地址紧缺问题十分严峻。由于IPv4协议本身所存在的缺陷已经逐渐成为限制下一代网络发展的瓶颈，因此由IETF设计用于替代IPv4协议的IPv6开始逐步普及并加速部署，截至2021年底，我国IPv6活跃用户数从2019年底的2.7亿增长至6.08亿，占我国全部网民数60.11％。基于IPv6的下一代互联网，有效缓解和解决了IPv4地址枯竭问题，但目前由于IPv6网络仍处于发展阶段，因此在其性能方面也面临着诸多困难与挑战。与IPv4相比，IPv6将地址长度从32位增加到了128位，导致原有的IPv4路由查找算法无法完全兼容IPv6，同时，目前主流的IPv6路由查找算法也存在动态更新困难、时间复杂度过高、严重的哈希冲突等问题，导致路由查找效率低、用户体验差。因此，如何设计一种高性能IPv6路由查找算法，已成为当前亟须解决的问题。

随着互联网的飞速发展，IPv6的全球商业部署进入了一个新的发展阶段，业界对IPv6的重要性也有了新的认识，并在IPv6高效路由转发方面做了大量研究。目前基于IPv6前缀地址的路由查找结构主要分为两类：一类是基于Trie的路由查找结构，一类是基于哈希表的路由查找结构。

基于Trie的路由查找结构如BinT(Binary Trie)、RadT(Radix Trie)、ART(Adaptive Radix Trie)等。BinT是一种二进制树，每个节点只存储一位二进制位，而IPv6的地址长度为128位，因此在进行路由查找时，最坏情况下需要进行128次存储器访问。为了降低BinT搜索深度，研究人员提出了RadT，RadT采取增大步宽的核心思想，压缩了树的层次以减小RadT的高度，在查找过程中，可以减少访存次数，提高查找效率，但对于RadT来说，空间利用率不高，导致存在大量空闲空间无法回收。ART是基于RadT的优化，能预先定义多种节点类型，且节点可根据自身大小动态选择节点类型，以防止多余空间浪费。基于Trie的路由查找结构，虽然有较好的查询效率，但仍存在树高不平衡等问题，导致该类算法难以保证路由查询时间的稳定性。

基于哈希表的路由查找结构是最常用的路由查找方法，一般情况下，算法会为每个地址前缀长度维护一张哈希表，在路由查找时，会从最长的地址前缀开始依次匹配，直到匹配成功为止，在理想情况下，哈希表具有O(1)的搜索时间复杂度，但随着路由表项的增加，哈希冲突问题会越发严重，甚至在必要时，还需进行哈希表移植，严重影响查询性能。

发明内容

针对上述问题，本发明将多数据结构融合技术引入IPv6路由领域，提出一种哈希表与HOT相结合的路由查找算法HHR，用以解决IPv6路由查找效率低、哈希冲突等问题。

本发明的技术方案为：

一种哈希表和HOT相结合的IPv6路由查找方法，其特征在于，包括以下步骤：

构建数据结构

S1、建立哈希表：

将IPv6地址的前64位定义为前缀地址，并划分为[1，16]，[17，32]，[33，48]，[49，64]四个区间，并分别取地址前16位，17位，33位，49位建立4个哈希表，分别定义为HTable1、HTable2、HTable3、以及HTable4，则HTable1存储前缀地址长度为16位的路由表项，HTable2存储前缀地址长度位于[17,32]区间的地址，HTable3存储前缀地址长度位于[33,48]区间的地址，HTable4存储前缀地址长度位于[49,64]区间的地址，其中，HTable1的结构中存储前缀值和下一跳路由地址，HTable2、HTable3、HTable4的结构中存储前缀值、哈希冲突指针、指向HOT的地址指针、下一跳路由地址；

S2、建立HOT：

基于S1中的哈希表，将前缀地址剩余部分插入HOT，在进行数据存储时，存储所有数据比对后的特征位Partial key，同时采用复合节点的方式在一个节点存储多个特征位；

基于S1中的哈希表，分别建立对应的HOT，并通过存于哈希表中的HOT指针来定位具体位置，例如前缀地址长度为64位的路由表项，取出前49位存于哈希结构，将[49,64]区间的比特位存于HOT。HOT采用复合节点方式存储数据，即定义为一个节点最多存储8个value值，其数据结构主要存储特征位位置、特征值(Partial key)、下一节点指针以及value值。首先头部存储所有value值的特征位位置，并借助单掩码技术，将其编码为特征位位置与单掩码相结合的形式，其次将每个value值的对应特征位取出，组成Partial key，Partial key选取8位数组结构并连续存储，以此实现基于单掩码技术的Partial key并行查找，加快查询速度。由于可能增加新的特征位，因此最终也需要与value值进行依次匹配，若匹配成功并存在下一节点指针，则需进入下一节点进行更深层次的匹配，直到匹配至最长地址前缀，反之，按照最新value值进行转发。

路由查找

A.对接收到的IPv6数据包，取地址的前49位进行哈希计算并与HTable4进行比对，匹配成功则记录对应的value值，并进入HOT查找，否则进入步骤E；

B.根据HOT节点的特征位位置，依次取出[49,64]之间对应的特征位，并行的与特征值Partial key进行对比，匹配Partial key成功，则取出该Partial key对应的value值，否则按照最新的value值进行路由转发；

C.将value值与[49,64]对应的比特值依次进行比对，相同则更新此时的value值，否则按照最新的value值进行路由转发；

D.判断该Partial key是否存在指向下一节点的指针，若存在，则查找下一节点是否存在更长的匹配项，否则按照之前记录的value值进行路由转发；

E.取地址的前33位进行哈希计算并与HTable3进行比对，匹配成功则记录对应的value值，并进入HOT查找，否则进入步骤F，HOT查找方法与步骤BCD同理；

F.取地址的前17位进行哈希计算并与HTable2进行比对，匹配成功则记录对应的value值，并进入HOT查找，否则进入步骤G，HOT查找方法与步骤BCD同理；

G.取地址的前16位进行哈希计算并与HTable1进行比对，匹配成功，则按下一跳路由信息转发，否则按照默认路由转发。

本发明的有益效果为：当应用于IPv6时，避免了哈希表移植难度大的问题，实现了IPv6路由查找算法低成本、高速度的性能。

附图说明

图1为IPv6全球单播地址结构示意图。

图2为核心路由器路由表项前缀长度分布特点示意图。

图3为HTable2/3/4结构示意图。

图4为标明所有数据的特征位示意图。

图5为复合节点结构示意图。

图6为HOT编码格式示意图。

图7为HOT overflow插入过程示意图。

图8为算法流程图。

图9为查询性能对比结果示意图。

图10为存储空间占用对比结果示意图。

具体实施方式

下面结合附图，对本发明技术方案进行详细描述并结合仿真示例证明本发明的实用性。

根据RFC3587规定，IPv6全球单播地址标准格式如图1所示，其地址主要由4个部分组成：3位的地址类型标志、45位的全球路由前缀、16位的子网ID、64位的接口ID。其中001标识该地址为单播地址，全球路由前缀标识一个站点，子网ID标识站点内的一个子网，接口ID标识子网内的一个宿主机。根据对骨干路由表前缀地址长度分析发现，在128位的IPv6地址中，接口ID不用于子网间的路由，因此路由表中的前缀地址长度为前64位。

基于potaroo网站提供的核心路由器路由表数据，选取自治域AS131072、AS13172、AS6447合计40万余条路由表项，整理并分析其前缀地址长度分布规律，结果如图2所示。从图中可以看出，其前缀地址长度主要介于16～64位之间，不存在前缀长度小于16位的表项，而且地址分布极不均匀，其中以前缀长度/48的表项居多，占比约为45％，其次为前缀长度/32的表项，占比约为15％，其余前缀地址长度分布数量较少。

为进一步研究核心路由器路由表地址前缀值分布特点，在上述分析结论的基础上，对三个自治域所包含的地址前缀值再次进行统计分析，发现前缀值大多以2001、2600、2a02开头，以其余取值开头较少。根据IPv6地址分配策略，常用地址以2001开头居多。

通过以上研究发现，由于IPv6层次化的地址分配，导致IPv6前缀地址长度分布差异较大，其中以前缀长度/48、/32的地址居多，合计占所有路由表项的60％，其次前缀值也大多以固定数字2001、2600、2a02开头。基于IPv6前缀地址分布的独特性，本发明引入多数据融合结构，采取两阶段查询方法。第一阶段为哈希表建立，将前缀地址长度分为16，[17,32]，[33,48]，[49,64]四个区间，并分别取地址前16位，17位，33位，49位建立哈希表，作为第二阶段索引，由于前缀值大多以固定数字开头，因此上述哈希表产生冲突的概率较小。第二阶段为HOT建立，将前缀地址剩余部分插入HOT，HOT为自适应高度优化Trie树，其具有快速插入、删除以及并行处理能力，可以较好的适应路由前缀更新频繁的特点。

根据上述分析结论得知，IPv6前缀地址长度大部分为48位、32位等，假设直接以48位，32位建立哈希表，则需选择性能良好的哈希函数，能较好的适应路由表项频繁插入、删除等操作，此外，当插入数据量超过哈希表阈值时，还需扩展哈希表，多次哈希表移植会导致路由读写性能显著下降。为防止上述问题，如下表1所示，避开对集中区域(/48、/32)的直接哈希，而是将前缀地址分为两个区间段，前段用于哈希索引建立，后段存于HOT，由于用于哈希计算的前缀长度缩短以及前缀值取值的微变性，路由表项种类相对减少，继而产生哈希冲突的概率降低。

表1 IPv6前缀地址的两阶段取值

算法HHR共定义4个哈希表，HTable1、HTable2、HTable3、以及HTable4。

HTable1存储前缀地址长度为16位的路由表项，由于HTable1不存在对第二阶段的索引，因此结构体只需存储前缀值Prefix和下一跳路由地址，同时，考虑到HTable1存储的信息较少，发生哈希冲突的概率较低，所以当冲突发生时，采用线性探测法来解决冲突，即从发生哈希冲突位置开始，依次向后探测，直到找到下一个空位置为止。

HTable2存储前缀地址长度位于[17,32]区间的地址，HTable3存储前缀地址长度位于[33,48]区间的地址，HTable4存储前缀地址长度位于[49,64]区间的地址，其结构定义如图3所示。Prefix存储表1对应的Hash长度取值，例如位于[17,32]区间的地址，只需取前17位进行哈希；Next为哈希冲突指针，根据IPv6前缀地址分析结果可知，HTable2、HTable3发生冲突的概率较高，为减少冲突次数，算法HHR采取链地址法处理哈希冲突，即同一位置的冲突对象采用链表组织在一起，Next指向下一个冲突对象；NP为指向HOT的地址指针，当通过哈希索引定位到HOT时，需进入第二阶段，检查是否存在更长的地址匹配项；value为下一跳路由地址，如果HOT中不存在更长的地址匹配项，则哈希索引的value值就为当前地址的最长路由匹配项。

由表1可知，对于一个IPv6前缀地址，将其分为两个区间段，前段用于哈希计算，定位HOT，后段存储剩余位数以及下一跳路由地址。根据IPv6前缀地址长度分布特点可知，前缀长度为/48、/32的IPv6地址不仅数量多而且更新频繁，因此用于存储第二阶段的数据结构需满足高效的查询性能和保证稳定的插入、删除等操作。HOT为自适应高度优化Trie树，是基于多比特Trie的优化，具有快速增删能力以及并行处理特性，因此，采用HOT作为第二阶段的存储结构。

基于IPv6前缀地址分布规律结论分析，HOT存储比特位长度多为16，假设按单个比特位存储，完成一次查找操作需要访问16次存储器。为了更有效的减少存储器存取次数，在进行数据存储时，算法HHR放弃存储所有比特位，而是存储所有数据比对后的特征位Partial key，以避开无效比特位存储，如下图4所示，找出所有数据的不同比特位(第0，1，2，4位)，并存于节点中。这样做的好处是，不仅能减少空间占用，也能有效降低树高。

为了更好的利用存储空间，算法HHR还将单一节点改为复合节点(compoundnode)，即一个节点存储多个特征位。节点的逻辑结构如下图5所示，一个compound node可以看作一个二叉比特树，其左分支为0，右分支为1。内部结点存储特征位(第0，1，2，4位)，叶子结点存储完整的前缀值，通过特征位上的特征值来决定左右分支。从图中可以看出，树高由原来的4层减少为现在的2层，极大的提升了查找性能。

由图5可知，复合节点的逻辑结构并不复杂，但为了进一步加快查询速度，在实现时，算法HHR采用现代CPU的SIMD(Single Instruction/Multiple Data)指令技术优化查询性能，其主要思想是将HOT线性化为一个紧凑的能使用SIMD并行查找的数据。为了使节点存储适应于SIMD并行处理操作，特征位Partial key需要对齐，在物理层面上，Partial key提供三种存储方式：8位,16位和32位数组。由前文已知，HOT存储的地址长度范围为0～16位，因此为了降低节点扩充频率，算法HHR将compound node的特征位数限制在8位，选取8位数组。

节点编码格式如图6所示。编码主要是借助特征位的位置(8-bit offset)和单掩码技术(64-bit mask)来实现并行处理。首先将每个key的特征位组成Partial key，然后将其连续存储，最后利用SIMD并行查找所有key。与传统层次查询方法不同，运用SIMD并行处理能力，将无需依次遍历相应的Trie，极大节省查询时间，显著提高查询效率。

HOT为自适应高度优化Trie树，当插入数据量超过compound node的阈值8时，将会进行节点调整，如下图7所示，为防止节点分裂引起树高增加，算法HHR采取向上增长原则，只有当所有父节点都存满时，才创建新的节点，这种做法不仅能减少空闲空间浪费，也能防止Trie无休止增长。由图5可知，每个key对应的Partial key只存储与自己相关的特征位，其他无关特征位将未定义(图中用x表示)，因此插入操作也只需修改相应特征位的值，这样使得HOT的节点调整更简单化，更易于插入、删除等操作。

算法流程如图8所示。查找过程分为两阶段，即哈希表查找阶段和HOT查找阶段。

1)当IPv6数据包到达时，取地址的前49位进行哈希计算并与HTable4进行比对，匹配成功则记录对应的value值，并进入HOT查找，反之，则进入第5步；

2)根据HOT节点的特征位位置(Bit positions)，依次取出[49,64]之间对应的特征位，并行的与特征值Partial key进行对比，匹配Partial key成功，则取出该Partialkey对应的value值，反之，则按照最新的value值进行路由转发；

3)将value值与[49,64]对应的比特值依次进行比对，相同则更新此时的value值，反之，则按照最新的value值进行路由转发；

4)判断该Partial key是否存在指向下一节点的指针，若存在，则查找下一节点是否存在更长的匹配项(过程类似第2，3步)，反之，则按照之前记录的value值进行路由转发。

5)取地址的前33位进行哈希计算并与HTable3进行比对，查找方法类似第2，3，4步；

6)取地址的前17位进行哈希计算并与HTable2进行比对，查找方法类似第2，3，4步；

7)取地址的前16位进行哈希计算并与HTable1进行比对，匹配成功，则按下一跳路由信息转发，反之，则按照默认路由转发。

从哈希冲突、查询更新性能、以及存储空间等方面，对算法性能进行分析。

算法HHR共设计4个哈希表，其中HTbale1采用线性探测法处理冲突，余下HTable采用链地址法处理冲突。由图2可知，较易发生冲突的前缀地址长度为/48、/32，由于算法HHR避开对集中区域前缀长度为/48、/32的哈希取值，而是分别采取地址前缀长度的前33位、17位进行哈希计算，大大降低了哈希冲突概率。通过对AS131072、AS13172、AS6447总计40万余条路由表项进行冲突次数统计分析，结果显示，发生冲突次数40余次，发生冲突的概率为0.04％。

路由查找分为两阶段，哈希表查找阶段和HOT查找阶段，其中哈希表查找时间复杂度接近O(1)，而HOT树高近似平衡，并充分利用SIMD命令并行处理能力，将查找时间限制在微妙级别。哈希表的插入时间复杂度也接近O(1)，而HOT采用存储特征值位置Bitpositions与特征值Partial key的思想，当插入操作发生节点分裂时，只需修改相应节点的Bit positions与Partial key，无需修改所有节点的Partial key，修改数据量减少，使得更新时间缩短。

算法HHR的存储结构包括哈希表和HOT。

算法HHR共设计4个哈希表，其中HTable2、HTable3、HTable4除了包括Prefix和value值外，还包括两个指针Next和NP，每条路由表项平均共计占用200位左右。

HOT存储offset、单掩码mask、Partial key、下一节点指针Next以及value值。其中offset占用8位，单掩码mask占用64位、一个路由表项Partial key占用8位、下一节点指针Next占用16位、value值占用64位，由前文已知，一个节点最多包含8个值，所以一个节点最多占用800位。

仿真示例

仿真实验选取了自治域AS131072、AS13172、AS6447合计40万余条路由表项，并使用C++在VScode上进行代码测试。表2给出了其前缀长度分布情况。

表2三个自治域前缀分布情况

在测试查询性能部分，算法HHR分别与算法Trie、ART以及HOT做比较。图9是在存储40万余条路由表项的基础上，查找1万条数据的查询时间。由图9可知，算法HHR采用哈希表与HOT相结合的数据结构，其查询时间稍优于HOT的查询时间，远优于算法Trie和ART的查询时间，因此，与其它路由算法相比，算法HHR的查询性能较优。

在测试存储空间占用部分，算法HHR分别与算法Trie、ART以及HOT做比较。图10是在存储40万余条路由表项的基础上，查找1万条数据的空间占用结果，其中算法Trie与ART由于预先分配大量空间，导致空间消耗占比增大，而HOT以最少空间占用而著名，所以空间占比达到最优。算法HHR由于引入哈希表结构，以加快查询速度，导致最终空间占比稍多于HOT，但也接近HOT。因此，算法HHR拥有近优的空间消耗性能。

从上述实验仿真结果来看，算法HHR在避免哈希冲突、查找性能和存储空间占用等方面接近最佳平衡，各项性能指标良好。

随着IPv6网络的大规模部署，各企业以及相关行业积极组织开展IPv6网关关键技术研究。但目前仍处于发展阶段，为了改善路由查询效率，本发明在分析骨干路由表前缀地址分布规律的基础上，提出一种哈希表与HOT相结合的路由查找算法，其核心思想在于将地址前缀分成两个区间，第一区间不易发生冲突，采用哈希表存储，第二区间查询更新频繁，采用HOT存储。经验证，该算法在查询时间以及空间占用等方面都具有较好的性能。