路由查找算法研究与分析

郭润伟

摘要：随着互联网络链路速率的不断提高，路由查找已成为路由器报文转发的瓶颈。本文首先介绍和分析了路由器中广泛使用的各种典型IP 路由算法方法，并提出一种基于多分枝 trie树的改进路由查找算法。该算法保留了多分支trie树访存次数少，查询速度快的特点，并具有占用存储空间少，更新开销小等特点，对IPv4和IPv6地址都可以适用。

关键词：因特网；路由查找；最长前缀匹配；trie树

1引言

当前，因特网的规模、链路速度、带宽、流量等都呈指数级增长，这对路由器中IP 路由查找算法对大容量路由表处理的适应性以及报文转发查表的能力提出了更高要求。路由器是构成因特网的中间结点，其转发性能决定了因特网的整体性能。路由器的发展面临三个难题：交换结构、缓冲调度、报文处理。随着半导体技术和光交换技术的发展，分组交换可以在很高的速率下得到实现。因此，IP路由查找是实现高速分组转发的关键，其优劣直接影响了当前和未来因特网网络的整体性能[1]。本文首先对现有的典型IP 路由算法进行介绍，总结其优缺点，并基于此提出一种基于多分枝 trie树的路由查找算法。

2常用的路由查找算法分析

2.1 硬件算法

目前使用最多的硬件实现方法是使用CAM (Content AddressableMemory)内容可寻址存储器[2]，它是一种特殊的存储器件，用来实现路由表查找的一种硬件方法。CAM的最大特点是能够在一个硬件时钟周期内完成关键字的精确匹配查找。为了能够实现最长前缀匹配，一个CAM表存放一类定长的前缀集。IPV4下需要32个CAM。这种方法有一个明显的缺点，在对地址前缀长度具体分配没有准确的了解之前，为了能够保证存储N个前缀表项目，每个CAM都要有N个表项的空间，因此，CAM存储空间的利用率大大降低了。

另一种基于硬件的改进CAM算法是基于TCAM(三值CAM)的算法[3]。在进行搜索的时候，所有的TCAM 项都需要同时进行匹配，在有多个匹配项时，TCAM 规定在所有匹配的表项中选取地址最低的表项作为最后的结果。因此，为了能够进行最长前缀路由的查找，就需要保证在TCAM的低地址区域存储前缀路由项，而在高地址区域存储短前缀路由项。TCAM 具有速度快、实现简单的优点，但它也具有几个不足之处：(1)单位比特昂贵；(2)容量小；(3)并行匹配导致功耗很大；(4)更新复杂。

2.2 软件算法

2.2.1二进制trie树[4]

IP路由要求查找最长匹配的前缀地址，因此树形结构的路由查找算法将最长前缀匹配查找模型话为一棵二进制树的过程。用Trie 表示前缀并不存储在Trie 的结点中，而是用结点间的路径表示前缀，一般规定一个结点到其左子结点的路径表示前缀中的对应比特为0，结点到其右子结点的路径代表前缀中的对应比特为1。如图1所示就是二进制trie树结构来表示的地址前缀结构。

IPv4中地址长度为32，所以二进制trie树的深度为32层，前缀长度即子网掩码长度为L的网络路由会被存放在第L层的结点中。二进制trie树算法一次更新操作只需要首先查询定位并修改一个结点，开销较小，它的最大不足在于查找过程中要进行大量的存储访问，对于IPv4地址查找最多需要32次，IPv6地址为128次。

2.2.2 多分支trie树

直接用二进制trie树的方式来实现路由查找，查找一个比特即对二叉树向下遍历一个深度，这样会导致查找速度太慢。如果一次从目的IP中取出多个比特，就可以开有效的减少查找过程中的存储访问次数。多分支trie树的查找过程与二进制trie树的查找过程类似，在每次结点访问过程时，记录下到目前为止匹配上的最长地址前缀，直到到达叶子结点搜索过程结束。例如，如果每次检查地址的4个比特，那么IPv4地址查找最多只需要8次存储访问就可以了。图2是和前面图1中采用同样IP前缀表生成的多分支trie树结构图。

每次从目的IP中取出的比特长度K称为查找步长。由于存储树中的前缀长度各不相同，如果每次检查步长为K的比特数，则小于K或者不是K整数倍的前缀将无法与多分支trie树的某个结点匹配。解决的方法是将无法匹配的前缀扩展为同K相同或者和K的整数倍。例如，K=3时，可以将1*扩展为100*、101*、110*、和111*。这种采用扩展前缀进行查找多分支trie树的算法称为可控前缀扩展算法。

当然，这种地址前缀扩展的多分支trie树在减少访存次数的同时也带来了消耗存储空间增大以及更新复杂的问题。假设步长K=5，那么就有4/5的IP前缀需要扩展（假设IP前缀长度均匀分布），最大的扩展长度前缀都要进行扩展到24个，这样就消耗了大量的存储空间。此时要更新某个IP前缀，最多需要更新24个结点。

文献[5]中列举了多分支trie树算法取不同步长时的实际运行性能比较。当步长K较大时，多分支trie树的深度相对较小，因此查找性能较好，但是需要耗费较多的存储空间。当步长K较小时，多分支trie树的深度相对较大，查找性能较差，但是存储空间需求较小。可见，对于多分支trie树来说，查找速度和存储容量是一对互相矛盾的性能指标。

3路由查找算法的衡量标准及性能提高方法

在评价一种地址查找算法的优劣时，必须综合考虑以下性能[6]：

3.1查找速度。一般所使用的指标是每秒查找分组数。考虑到各种方案在测试时所使用硬件不同、测试条件的不同会对测试结果产生很大影响，所以使用一次查找、特别是最差情况下一次查找需要进行的存储器访问次数作为衡量速度的标准更为合理。

3.2所需存储器的大小。实施方案所需的存储器应尽可能的小，在一定的空间中存储尽可能多的路由前缀，以便于硬件实现和满足不断增长的前缀数目的需要。

3.3路由表更新的开销。包括路由表周期更新开销和表项插入、删除操作开销两部分。路由信息的变化所引起的查找性能的下降应尽可能的小。

提高路由查找速度的主要途径有3个[7]：（1）减少存储器访问次数；（2）减小转发表的存储空间；（3）采用硬件流水并行处理。只采用一种方法或者算法所得到的查找性能受到一定的限制，既使能够取得很快的查找速度，往往也存在转发表更新困难或者扩展性差等问题。所以很多算法都是把这3个方向上的改进结合起来的结果。

4一种改进的多分支trie树算法

我们提出一种多分支trie树改进算法。在多分支trie树结构基础上，不需要进行前缀扩展。假设检查步长为K的比特数，为解决小于K或者不是K整数倍的前缀将无法与多分支trie树的某个结点匹配问题，把小于K或者不是K整数倍的前缀挂载到K的整数倍结点上，以整数倍结点为根结点，组成一个大的中间结点。即，中间结点之间采用多分支步长查询，中间结点的内部使用二进制trie树来表示。

图3列举了步长K=3时，某个中间结点的表示方法。前缀100110是K的整数倍结点，即中间结点。1001100，1001101，

10011010都不是K的整数倍结点，把他们挂载在100110的中间结点上。图4是使用前面的IP前缀表生成的结构图。

在路由查询时，使用步长为K访问中间结点，找到中间结点后，以步长为1访问中间结点内部。一个长度为N的前缀，所需要的访存次数为N/K的结果加上N/K的余数。以步长K为3为例，假设前缀长度N为11，那么访存次数为3+2=5次。最坏情况下，IPv4地址前缀最长为32，访存次数为10+2=12次，仅比原来的多分支trie树的10次访存多2次，而又远少于二进制trie树的32次访存，这就保留了原来多分支trie树查询速度快的优点。

同时，普通的多分支trie树，对于前缀长不是整数倍的结点，要进行前缀扩充，最多扩充为2K-1个，占用了大量的存储空间，而本算法于没有对前缀进行扩展，占用空间小；而且更新结点不需要涉及到其他结点，和二进制trie树路由表更新的开销其实是一样小的。

5结束语

本文在分析传统路由算法的基础上，提出了一种基于多分支trie树的路由查找算法。该保留了多分支trie树访存次数少，查询速度快的特性，并具有占用存储空间不大，更新开销小的特点，对IPv4和IPv6地址都可以使用。由于使用硬件实现往往能使得路由查找算法性能得到数量级的提升，接下来的工作可以在硬件实现技术上进行研究。

参考文献:

[1]Marc Friedman,AlonLevy,Todd Millstein. NavigationalPlans for Data Integration[C].Proc of t he 16t h National Confon Artificial Intelligence (AAAI'99)[C].1999.6:72-73.

[2]A MCAULEY,P FRANCIS.Fast Routing Table Lookup using CAMs[J].Proc.IEEE INFOCOM 1993,Vol3,pp1382 - 1391,San Francisco,USA.

[3]吴彤,杨嗣超,诸鸿文.路由表快速查找算法[J],通信技术,No4,2000:52-59.

[4]刘永锋,杨宗凯.高速路由器中基于树型结构路由查找算法的研究与实现[J].计算机工程与科学.vol.26,No1,2004:77-80.

[5]徐格,吴建平,徐明伟等.高等计算机网络-体系结构、协议机制、算法设计与路由器技术[M],机械工业出版社,北京,2006:522-544.

[6]谭明锋,高蕾,龚正虎,IP路由查找算法研究概述[J].计算机工程与科学.vol,28,No6,2006:87-91.

[7]徐宇锋,李乐民.快速路由查找算法及其实现,通信技术[J],No7,2001:48-52.