基于Hash和Radix树的路由查找算法研究

李渊　阮军洲

（1中国电子科技集团第五十四研究所，河北　石家庄　050081）

（2解放军75660部队，广西　桂林　541002）

基于Hash和Radix树的路由查找算法研究

李渊1阮军洲2

（1中国电子科技集团第五十四研究所，河北石家庄050081）

（2解放军75660部队，广西桂林541002）

介绍了路由查找算法的研究背景和技术指标，对比了基于Radix树和Hash的路由查找算法，进而提出了一种基于Hash和Radix树相结合的路由查找算法，详细介绍了该算法的数据结构和实现步骤，同时给出了该算法基于FPGA的硬件实现模型并设计了对该模型的逻辑仿真结构，对逻辑仿真结构中的测试激励产生机制作了介绍。针对逻辑仿真波形进行了分析，结果显示该算法实现了8.6X106次查找/s。

Radix树路由查找Hash表逻辑仿真

1　引言

随着互联网的迅速发展，Internet的速度不断提高，网络流量不断增加，相应的路由表规模也不断扩大。网络容量的不断提高要求路由器能够每秒中内转发尽可能多的分组，而分组转发效率提高的重要一步就是路由查找算法的实现，即在路由表中查找最长前缀匹配路由。

目前，基于最长匹配原则的路由查找功能在硬件上通常采用外置TCAM或者DDR实现。该方法虽然满足了路由查找对匹配命中时间及路由表项数的要求，但是也带了功耗加大，成本增加等问题。尤其是在一些对功耗、电路板面积要求比较苛刻，甚至明确要求不能使用TCAM或DDR的场合（例如，卫星星上交换设备），该方法显然不能满足要求。因此，本文提出一种基于Hash和Radix的路由查找算法，该算法适用于在FPGA片内实现，同时又不占用太多FPGA资源，能够快速命中路由表项。

2　几种路由查找算法的介绍

2.1基于Radix树结构的查找算法

Radix树结构是每一个分支上都带有标号的二叉树，其左分支对应0，右分支对应1，然后沿着与待查IP地址匹配的分支逐比特查找。进行匹配查找时，首先从根节点开始查起，每次从待查IP地址中读取1比特，如果该比特为0则查询当前节点的左节点；为1则查询当前节点的右节点。按照此规则逐比特查询，直至遇到叶子节点或者当前节点无相应子节点时结束查询操作。对于Radix树结构，如果待查IP地址长度为W，最坏情况下需要读O（W）次存储器。在基本的Radix树结构中，即使某节点不是有效前缀，也需要分配空间来存储子结点指针，浪费了存储空间。因此，为了节省存储空间，同时减少内存访问次数，需要对Radix树进行压缩处理［1］。

2.2线性查找hash表算法

该算法对待查IP地址运用哈希技术和多路哈希表进行查找，从而找到最长匹配前缀。其数据结构如图1所示。

图1　hash表数据结构

该算法的查找过程如下：首先在数组中从后往前进行查找，即从长度最长32的元素开始，通过hash指针查找其对应的哈希表，若哈希表表项非空，则找到最长匹配前缀，查找结束；否则继续往前查找。直至查找结束时，哈希表表项中记录的就是能匹配上的最长前缀所对应的信息。

线性查找hash表算法采用并行查表设计，可在较短的时间内完成路由查找操作；但是对于每个前缀长度的查询都要通过哈希函数，而性能良好的哈希函数又很难找到，同时转发表更新时要增加一些前缀，这有可能降低哈希函数的性能，就要重新选择哈希函数，组织哈希表，且增加了更新的难度［1］。

3　路由查找算法描述

基于Hash和Radix的路由查找算法结合了Radix树结构的查找算法和hash表算法的优势，具有占用内存空间少和查表命中时间短等特点。该算法的具体查表过程如下：

①将待查目的IP地址的第一字节作为第一入口关键字，将待查目的IP地址的第一字节和第二字节进行组合作为第二入口关键字，将待查目的IP地址的第一字节、第二字节和第三字节进行组合作为第三入口关键字；同时送入一一对应的3个并行查找模块；以目的IP 192.168.1.3为例，其第一入口关键字、第二入口关键字和第三入口关键字分别为：

②3个入口关键字分别通过hash函数得到其所在hash桶中的索引地址，该索引地址存储着该入口关键字对应Radix树的入口地址；其中，第一入口关键字的索引地址为第一入口关键字的本身值；第二入口关键字的索引地址和第三入口关键字的索引地址均选用CRC-10算法计算获得，hash桶深度为8；其中，CRC-10的计算多项式为其中，为多项式因子。3个hash桶的结构如图2所示。

图2　Hash桶结构

③在得到3个入口关键字的Radix树的入口地址后，同时进入3个Radix树存储空间，分别对每个Radix树的每个节点进行访问，每个节点由前缀比特串、8位掩码，下一跳索引值、要比较的比特位序号、左子树指针和右子树指针构成；

④确定查找关键字：第一入口关键字对应的Radix树中的查找关键字为待查目的IP地址的第二字节；第二入口关键字对应的Radix树中的查找关键字为待查目的IP地址的第三字节；第三入口关键字对应的Radix树中的查找关键字为待查目的IP地址的第四字节；

⑤将查找关键字与节点的8位掩码进行与运算，将运算结果同前缀比特串进行比较，如二者相同则认为节点匹配，进入第⑥步；如二者不相同，则回退至前一个匹配节点，如果不存在匹配节点，则该待查目的IP没有匹配路由项，查找模块输出未匹配信号，结束本次查表，进入第⑦步；

⑥当节点匹配时，如果要比较的比特位序号为零，则此节点为最终的匹配节点，查找模块输出下一跳索引值，结束本次查表，进入第⑦步；如果要比较的比特位序号不为零，则提取查找关键字中要比较的比特位序号对应的比特值，当该比特值为0时，下一节点的访问地址为左子树指针，当该比特值为1时，下一节点的访问地址为右子树指针；访问下一节点时，返回第⑤步；

⑦当3个并行查找模块全部完成查表，并输出查表结果后，根据最长匹配的原则，按照第三入口关键字、第二入口关键字和第一入口关键字优先级顺序将最终的查表结果作为下一跳索引值，至此完成基于Hash和Radix树的路由查找。

4　路由查找算法硬件实现

在对基于Hash和Radix的路由查找算法进行算法分析后，使用可综合的Verilog HDL对该算法的硬件实现模型进行了RTL级的描述，其总体结构如图3所示。

图3　系统总体结构

5　仿真测试结果

为了验证算法的功能和性能，对该模型进行功能逻辑仿真。根据所要仿真测试的功能，采用modelsim软件搭建了仿真测试平台，该测试平台的总体结构如图4所示。其仿真过程为：测试激励产生器随机产生路由前缀、目的IP地址以及下一跳地址；CPU配置驱动器根据测试激励产生器产生的测试向量配置被测模块；测试向量驱动器将测试向量输入被测模块；被测模块的运行结果可以通过modelsim软件的打印输出窗口和波形窗口进行观察，如图5所示。

图4　仿真测试平台结构

图5　仿真波形结果

通过功能仿真，可观察到被测模块的输入输出波形正确，被测模块的结果输出符合期望的路由查找结果。图5为一次路由查找的过程：在该波形中，macth_enable=1，表示开始进行路由查找；当serach_over=1和match_ok=1时，表示一次查找完成，此时match_index输出查找结果，即下一跳地址。

通过对仿真结果的分析和理论估计，模型的工作频率为200 MHz，即时钟周期为5 ns，该路由查找模块达到的基本性能为：8.6X106次查找/s。在功能仿真中存储1000条路由前缀需要的存储容量少于2 Mbit。

6　结束语

与现有技术相比，本文提出的基于Hash和Radix树的路由查找算法占用存储器资源少，无需添加外设即可在FPGA片内实现基于最长匹配的路由查找算法；由于对目的IP地址进行了关键字划分并采用了并行查找方法，缩短了路由查找时间，极大的提高了路由查表性能；该算法适合于对低功耗，低成本和稳定性要求高的场合。

［1］CHAO J H.broadband packet switching technologies：a practical guide to atm switches and ip routers［M］.2001.

［2］李鸥，邬江兴，汪斌强，等.一种分段式高速IP路由查找方法［J］.通信学报，2001，22（5）：93-96.

［3］徐恪，徐明伟，吴建平，等.路由查找算法研究综述［J］.软件学报，2002，13（1）：42-50.

［4］刘亚林.动态快速路由查找算法［J］.中国工程科学，2002，4（7）：60-68.

［5］程耀林.FPGA的系统设计方法解析［J］.微型电脑应用，2007 （1）：48-51，68.

［6］夏宇闻.Verilog数字系统设计教程［M］.北京：北京航天航空出版社，2003.

Research on Router Lookup Algorithm Based on Hash and Radix Tree

LI Yuan1，RUAN Jun-zhou2
（1.The 54th Research Institute of CETC，Shijiazhuang Hebei 050081，China）
（2.Unit 75660，PLA，Guilin Guangxi 541002，China）

This paper introduces the research background and some technical parameters of the route lookup algorithm.Comparing the router lookup algorithm based on Radix tree with the router lookup algorithm based on Hash，a kind of router lookup algorithm is proposed，which combines together the router lookup algorithms based on Hash and Radix tree.The data structure and implementation steps of this algorithm are presented.The hardware implementation model based on FPGA is given and the structure of logical simulation for this model is designed.This paper introduces the test excitation generation mechanism.The analysis is performed for logical simulation waveform，and the result shows that this algorithm can realize 8.6X106 routing lookup/s.

Radix tree；router lookup；Hash table；logical simulation

TP391.4

A

1008-1739（2015）11-42-3

定稿日期：2015-05-12