基于哈希表与多比特树的路由查找算法

范富明，李念军，雷升平，吉 萌

(1．光纤通信技术和网络国家重点实验室，武汉430074;2．武汉烽火网络有限责任公司，武汉430074)

1 概述

当前路由查找主要有Trie树和哈希表等方法［1-3］。基于Trie树路由算法在路由表项增多情况下，树的深度变大，路由查找过程中平均匹配次数变多，算法效率较低。为了提高算法的查找效率，路由查找过程中采用步长为8的查找方式，在一定程度上提高了查找的效率。基于哈希表的路由算法，依据前缀长度路由表划分为多张路由子表，在路由条目较少的情况下，取得了较好的性能，但在路由条目较多的情况下，哈希冲突迅速上升，查找效率下降明显［4-5］。当前高端路由设备中大多采用基于Trie树的方式存储路由表项，路由查找过程依据表项的数目采用变步长的查找方式。在算法实际设计的过程中，为了权衡查找速率与消耗存储空间之间的矛盾，对插入的表项要进行再平衡，使得树的高度不至于太高和太低。

传统基于哈希表或Trie树的算法在表项较少的情况下能够取得满意的查找效率，但是在表项达到百万以上时，查找效率迅速下降，难以满足高端路由设备的需求［6-9］。TCAM(Ternary Content Addressable Memory)专用芯片凭借其出色的硬件查找性能，能显著提高路由查找性能，可应用与高端路由设备，但是TCAM价格昂贵，在一定程度上限制了其应用的广泛性［10］。当前随着存储设备容量的快速翻倍，内存价格进一步下降，高端路由设备迫于对性能的强烈要求，在算法中适当地采用内存空间置换时间也是可行的。

本文借鉴上述路由查找算法的特点，综合考虑内存消耗和查找效率的因素，提出一种基于哈希表和多比特树的路由最长前缀匹配查找算法。路由表项根据前缀长度采用分段储的方式，表项查找和放置过程均从顶层开始。从数据结构上来看，每一级都是相当一个完全多比特树。本文根据表项结构的存储特点，在算法的内存消耗方面采取了进一步优化，同时为解决因表项重复而导致的遍历困难问题，引入哈希表用于优化。

2 路由算法原理

当前处理芯片大多具有用于动态随机存取存储器(Dynamic Random Access Memory，DRAM)管理的专用接口，为数据在内存中的读写效率提供了较好的硬件条件，也为基于DRAM的大表项路由查找算法的设计与实现提供了可能性。高效的路由查找方法的设计在依赖硬件基础的同时，良好的算法数据结构的设计显得更加关键。

2．1 路由查找机制

16-8-8路由查找机制如图1所示。在路由条目存储是根据前缀长度分为第1部分1 bit～16 bit，第2部分17 bit～24 bit，第3 部分 25 bit～32 bit。

图1 16-8-8查找机制

查找是采用最长前缀匹配(LPM)查找机制，首先取地址前16 bit的数值，在第1部分数组定位表项位置，并对表项的有效性进行测试。Valib为表项有效性的标志位，如果Valib=1，表明当前表项是有效的，如果Valib=0，则表明表项为空;Cont表示是否有更长路由可供查找的标志位，表明可以进行下一部分的查找，如果Valib=1，Cont=0，表明当前找的路由是唯一最长的匹配的路由，则可以在表项结构Info指针的地址中直接获取下一跳的输出信息，表项数据结构如图2所示。

图2 路由表项数据结构

如果Valib=1，Cont=1，表明有比当前长度为16 bit的表项更长的路由表项存在下一部分中，并需要抽取目的IP地址的17 bit～24 bit的数值作为偏移量，在第2级的对应数组中查询表项。在第2级的表项判别过程同上一部分完全相同，主要对2个标志位进行判别。区分是查找成功、失败或还是需要进入下一步中继续查找，如图3所示。

图3 表项存储实例

第2级表的起始位置Min和结束位置Max，Max－Min+1表示第2级表中可供查找的表项数，Max和Min的取值都不超过第2级表的最大有效表项数。Info路由信息指针，指向路由的下一跳信息。L1_Entry指向第2级表中相应表项的起始位置。

2．2 路由存储机制

如图2所示，当路由前缀长度小于16 bit时，将路由添加到路由表的第1级表Tbl_L1_Entry中。当路由前缀长度介于17 bit～24 bit之间时，将路由添加到路由表的第2级表Tbl_L2_Entry中。但需要根据路由前16位前缀在第一级表中找到对应的表项位置，并将Valid和Cont位置为有效。当路由前缀长度介于25 bit～32 bit之间时，将路由添加到路由表的第3级表Tbl_L3_Entry中。但需要根据路由前16位前缀在第一级表中找到对应的表项位置，并将Valid和Cont位置为有效;并且根据17 bit～24 bit为前缀在第2级表中找到对应的表项位置，同样将该表项的Valid和Cont位置为有效。

例如有3个路由表项先后需要插入到路由表中:

A=10．0．0．0/8，B=10．34．128．0/17

C=10．34．192．0/18

首先 A=10．0．0．0/8，前缀长度小于 16 故而直接存储到表的第1部分，则根据表项IP的前16位，找到table1［2560］的表项作为地址，前缀长度为8的表项 A=10．0．0．0/8，在第一级表项中作用域10．0．X．X ～10．255．X．X，第一级的下一跳指向 A 的表项都是其作用域。

第2 条表项 B=10．34．128．0/17，其前缀长度大于16，因此需要动用第1级和第2级进行表项的存储，首先在第一部分的Tbl_L1_Entry［2594］的表项中将Cont标志位置为1，表明有比10．34给长的表项供匹配。在第2部分中的Tbl_L2_Entry［128］个表项起始，开始插入表项，其作用域是从10．34．128．X到10．34．255．X，第2级的下一跳指向B的表项都是其作用域。

第3 条表项 C=10．34．192．0/18，同样长度大于16，并且同样在第1部分的 Tbl_L1_Entry［2594］表项中，指向第二部分的列表，由于其前缀长度为18，故而其作用域为 10．34．192．X ～ 10．34．255．X，在第2部分表项插入过程中，需要进行判别已经存在表项的前缀长度Len是否小于当前需要插入的表项前缀18，如果小于，则需要对已存在表项进行替换。由于第2条表项插入的前缀Len为17，小于当前的前缀长度18，因此如图3表项下一跳指向C的所示，其对原有的部分下一跳指向B的表项进行了替换。

3 算法优化

由上述算法的原理可知，在设计上采用三级的表项设计，前缀1到16的第一级完全采用连续的内存空间存储表项，二三级以近似256个表项为单位的连续内存存储方式。这些连续的内存存储组织方式，使得路由在查找或存储的过程中，根据目的IP或路由可以很简便的计算出地址偏移量，从而快速定位到表项的位置，相对于传统的动态树形结构的路由组织方式在路由查找和路由添加效率上确实高很多。但算法是这种设计方式耗用了大量内存，并且有相当一部分的路由表项是空的，同时由于作用域的存在造成很多表项的键值是重复的，这些重复键值的存在导致路由遍历操作的困难，难以完成用户的Show或Dump路由条目的操作，因此需要对算法进行进一步的优化。

3．1 内存空间的优化

根据网络研究机构的有效数据统计IPV4的路由前缀99．93%是小于等于24的［3］，也就是说大部分表项在树形结构中分布于第一级和第二级中。第一层的长度16的前缀路由表项的存储空间是在初始化的时候一次分配完成，大约为Tbl_L1_Entry［52000］(除去多播地址区间)，但是对于第2级和第3级的空间是根据添加路由的前缀长度动态分配。

二三级前缀范围分别从17～24和25～32，前缀跨度为8，一般二三级存储的时标号是0～255，需要的存储块大小统一都是256个表项空间，这中内存分配方式在一定程度上造成空间的浪费。算法在设计的过程中，在第一级和第二级的表项中设置了2个参数:Min和Max域，其分别用来标示下一级中表项的起始和结束段地址，其值是0～255范围内的一个子区间，这个区间的大小取决与路由前缀的长度，该区间总是0～255范围的一个子区间，消耗的内存空间块大小总是不超过256个表项空间。

3．2 哈希表的引入

为了解决表项遍历的问题，算法在设计上增加了一张用于存储下一跳的信息的Hash表。Hash表根据前缀的长度建立32张子表，相同前缀的路由表项下一跳信息存储在同一张子表中。每次在树形结构中添加表项的时候，先把下一跳的信息结构Info添加到Hash表中，并把该地址指针传给树形表项的Info指针。

虽然树形结构中有多个重复的表项，但是每个重复的表项的Info域指向哈希表中的地址是相同的Htbl_Entry，如图3所示。添加的路由表项根据前缀长度在Hash表中的信息是唯一的，因此，在进路由Dump或Show进行路由遍历的时候，从在Hash表中32张子表中依次遍历出路由信息。

哈希表在冲突域中采用单链表的组织方式，虽然由于表项条目巨大，路由信息的添加和删除的过程中，碰撞比较多。但是哈希表管理与维护是由控制平面来完成的，不会给数据平面的转发效率带来影响。

4 算法实现

为了实现最长匹配，依次从顶层开始向下查找。如果在第一层没有匹配到路由前缀项，则表明路由不存在，则对数据包进行丢弃或送默认路由。如果在尽可能深的层次中匹配到表项，表明是最长的路由匹配，并通过表项中Info指针在哈希表中获取下一跳的信息，并找到相应的出接口。

步骤1根据目的IP地址计算出高16位数值L1_Base_Idx，在第一级路由表结构中找到对于的表项Tbl_L1_Entry［L1_Base_Idx］。判别表项中的Valid标志位，如果 Valid=0进入步骤 8;如果Valid=1，进一步判别Cont标志位，如果Cont=1，进入步骤3，否则进入步骤2。

步骤2根据Tbl_L1_Entry［L1_Base_Idx］表项中的Info指针，找到路由信息Htbl_Entry，即可获得出接口Index和下一跳网关等信息，进入步骤7。

步骤3表明第二级中可能存在更长的路由表项，其中L2_Entry指向下一级结构内存的起始地址Table2［0］，根据目的IP地址的17～24位获得数值L2_Base_Idx，将L2_Base_Idx值与上级Tbl_L1_Entry［L1_Base_Idx］中的Min和Max值进行比较，如果L2_Base_Idx不在Min和Max组成的闭区间内，返回步骤2;如果L2_Base_Idx在Min和Max组成的闭区间中，表明第二级空间中存在该路由。进一步检查Tbl_L2_Entry［L2_Base_Idx］表项中 Valid的有效性，如果Valid=0，表明该表项无效，返回步骤2;如果Valid=1，进一步判别Cont标志位，如果Cont=1，进入步骤5，否则进入步骤4。

步骤4根据Tbl_L2_Entry［L2_Base_Idx］表项的Info指针，找到路由信息Htbl_Entry，即可获得出接口Index和下一跳网关等信息，进入步骤7。

步骤5表明第3级中可能存在更长的路由表项，其中表项中L2_Entry域指向下一级结构内存的起始地址Tbl_L3_Entry［0］，根据目的IP地址的25～32为获得数值L3_Base_Idx，将L3_Base_Idx值与上一级Tbl_L2_Entry［L2_Base_Idx］中的Min和Max值进行比较，如果L3_Base_Idx不在Min和Max组成的闭区间内，返回步骤4;如L3_Base_Idx在Min和Max组成的闭区间内，进一步检查Tbl_L3_Entry［L3_Base_Idx］表项中 Valid的有效性，如果Valid=0，表明该表项无效，返回步骤4;如果Valid=1，进入步骤6。

步骤6根据Tbl_L2_Entry［L2_Base_Idx］表项的Info指针，找到路由信息Htbl_Entry，即可获得出接口Index和下一跳网关等信息，进入步骤7。

步骤7匹配到路由，退出。

步骤8没有匹配到路由，取默认路由或将该数据包丢弃，退出。

5 测试结果与分析

在多核平台中对该算法进行了测试。该CPU拥有10个核，核0运行Linux系统作为控制平面;其他9个核运行在数据平面，实现算法环境下数据实际转发功能的实现。平台外部配备2条8 GB的DDR3的内存，端口上外接2个万兆口(XG)。

实验中采用的路由表信息来自网络Protocol上的统计信息，其中长度为1 bit～16 bit，17 bit～24 bit，25 bit～32 bit，各占一定比例的实际前缀总数为1 ×103，1 ×104，1 ×105，1 ×106，5 ×106不同数量的路由，并从转发的数据的吞吐量、数据包平均延时、丢包率3个方面对算法进行测试。

为了评估本文IP地址查找算法的效率，本文使用随机和非随机两种策略产生IPv4测试地址。表1中列出了采用4种IP测试数据所得到的地址在5×106条路由条目下查找次数和平均查找次数。从测试结果可以看出，算法的平均查找次数介于1～2次之间。

表1 平均查找次数

在1 ×103，1 ×104，1 ×105，1 ×106，5 ×106条路由测试，在64 Btye长度 IP数据包下达到了双向10 GB/s的吞吐量，其测试特性如图4所示，仪表记录了数据包进入被测试设备最大、最小和平均延时时间，从图中的数据变化来看，路由条目虽然成级数增加，但是数据转发延时则变化并不明显，这是因为算法在路由查找的过程中平均查找次数控制在1～2次之间，克服了传统算法随着路由条目数增加，平均查找的次数随之增加而导致算法性能降低的问题。

图4 64 Byte数据不同路由条目下性能测试结果

在5×106条路由的情况下，进行了64 Btye，128 Btye，256 Btye，512 Btye，1 024 Btye 不同数据包长度的性能测试，测试结果如图5所示。latancy记录测试进端口到出端口的延时。

图5 5×106条路由条目下算法测试结果

在64 Btye长度的数据包测试中，在路由表中装载不同条目的路由表项，其测试结果显示算法在表项数目达到5×106条的情况下，达到双向10 GB/s的线速，并且维持较低的丢包率，包延时相对于其他情况下有所增加，但变化比较平稳，在容忍的范围内。同时5×106条路线下，算法在64 Btye长度的短包下达到线速。

测试分别对 1 ×103，1 ×104，1 ×105，1 ×106，5×106路由条目情况下内存使用情况进行统计，如图6所示。算法内存空间的优化前后的数据进行对比，优化后的算法在内存的消耗量上明显比没有进行优化时要少很多，相对于普通的分段路由查找机制，算法一定程度上节约了内存的开销。优化后的算法，在5×106大表项的情况下算法占用8．9 GB的内存空间，这是一般高端路由设备的硬件能够承受的。

图6 内存优化前后数据对比

为了测试算法与其他算法查找速度的对比，本文选择了常用的二进制Trie树、多比特Trie树［11］和二分哈希法［12］路由查找算法，64 Btye长度IP数据包在多核平台上进行 1 ×103，1×104，1×105，1×106，5×106条路由查找平均延时时间测试，测试结果如表2所示。

表2 不同算法的延时比较 μs

在表项较小的情况下4种算法查找平均延时相差不大，但是随着表项的增加二进制Trie树和多比特Trie树高度增加，以及二分哈希查找算法哈希冲突增加，算法平均匹配查找次数增加，延时也随之增加，本算法则随表项的增加查找延时变化不大，维持在 22 μs左右。

6 结束语

本文提出一种基于哈希表和多比特树相结合的路由查找机制，充分考虑到网络实际应用中路由前缀长度的分布情况、存储空间和每次路由查找平均匹配次数等综合因素，将IPv4地址分成3段:1 bit～16 bit，17 bit～24 bit，25 bit～32 bit，对于网络中前缀长度大多数分布在24 bit的路由表来说拥有非常高的查找效率，平均查找次数介于1～2次就可以查找最长匹配的路由表项，从而取得较快的转发速度。同时算法引入了哈希表用于解决算法在路由表项输出表项详细信息方面的不足，算法在内存空间上也进行了一定程度的优化，进一步压缩了算法在内存空间消耗量。算法通过多核平台进行验证，取得百万条路由环境下双向10 GB/s的速度，平均延时小于30 μs的测试性能，平均查找次数1～2次。

当前基于哈希表和多比特树相结合的路由查找机制已经在高端路由设备的IPv4路由转发中得到实际应用，后期将推广到IPv6的路由查找中，但由于IPv6地址长度有128 bit，其路由前缀长度分布有别于IPv4的情况，因此需要根据实际情况对地址的分段情况做出调整，以获得较高的查找效率和较优的内存消耗。

［1］ 王亚刚，杜慧敏，杨康平．使用Hash表和树位图的两级IPv6地址查找算法［J］．计算机科学，2010，39(9):36-39．

［2］ 汪志莉，沈富可．一种基于哈希表和Trie树的快速内容路由查找算法［J］．计算机应用与软件，2009，26(10):121-125．

［3］ 张 琦，金胤丞，李 苗，等．Trie树路由查找算法在网络处理器中的实现［J］．计算机工程，2014，40(1):98-102．

［4］ 华 泽，班建民，陆 悠．基于分段地址结构的快速路由查找算法［J］．计算机与数字工程，2007，37(10):8-11．

［5］ 杜 飞，董治国，苗 琳，等．基于无冲突哈希表和多比特树的两级IPv6路由查找算法［J］．计算机应用，2013，33(5):1194-1196．

［6］ Grama A，Atallah M J．Adaptive Data Structures for IP Lookups［J］．AIM Journal of Experimental Algorithms，2005，33(5):1194-1196．

［7］ Zheng K，Liu B．V6Gene:A ScalableIPv6 Prefix Generator for Route Look up Algorithm Benchmark［C］//Proceedings of AINA’06．Washington D．C．，USA:IEEE Press，2006:1254-1260．

［8］ Swartzlandere L Y．Priority Tries for IP Address Lookup［J］．IEEE Transactions on Computers，2010，59(6):784-794．

［9］ 陆笑天，李 曦，周学海．基于前驱查找的快速IP路由查找和更新方案［J］．计算机工程，2007，33(13):127-129．

［10］ 殷 科，邓亚平．基于RAM和TCAM存储结构的高速路由查找算法［J］．计算机工程与应用，2005，41(20):159-161．

［11］ 崔 宇，田志宏，张宏莉，等．基于前缀区间集合的IPv6路由查找算法［J］．通信学报，2013，34(6):29-37．

［12］ 杨玉梅，黎仁国．基于二分查找和Trie的IPv6路由查找算法［J］．兰州理工大学学报，2012，38(4):98-102．