路由器中的硬件IP路由表查找技术

为了实现有效的插入和删除，我们还要在路由表的数据结构中再另外添加几个域 ：parent指针(指向本结点的父结点)，路由信息(routeinfo)等。它们的用途是在路由表的查找过程中，特别是在指针的回溯(pointer reversal)中，可以大大的节省查找时间。由于IP路由的插入和删除比较复杂。我们只是粗略得说明一下。

IP路由的插入：

/*　插入算法开始 */

/* 先用上面提到的查找算法找出best-match */

best_match = search ( new_entry );

/* 确定需要加入的路由中没有被best-match包括的那几位 */

for ( count = first_unmatched_bit ; count <= sizeof ( new_entry) ;

count+= sizeof ( address_part ) {

/* 创建新的结点 */

create new node ;

/* 将该结点连入best_match的hit_next */

link node into hit branch of best_match ;

}

/*　插入算法结束 */

IP路由的删除要分几种情况讨论 。如 best_match 是叶子结点 ，best_match的hit_next指针为空, best_match的miss_next指针为空 和hit_next指针和miss_next指针都不为空等四种情况。这里就不再讨论。

3.路由表查找的硬件实现：

图3就是对应与上面提及的路由表结构的IP路由表查找的硬件实现(简称为路由卡)的系统框图。

在路由卡中，主要有IP地址，状态机，路由信息，Memory，译码器，掩码器，比较器，地址寄存器组成。IP地址用于保存所要查找的目标地址。状态器用于控制IP路由表的查找。路由信息就是我们所要查找的信息。它的工作原理是这样的：

当路由器从某一个网络适配器中接受到一个需要转发的数据包后，在需要进行IP路由表的查找时，把IP包的目的地址送到IP地址寄存器中，同时给状态机发一个指令。状态接到这一指令后，从Memory中读出路由表的相应的表项，并和IP地址寄存器中的相应几位经译码器，掩码器后，进行比较，把比较的结果反馈给状态机。再由状态机来控制下一轮的比较。当比较结束后，把比较的结果放在路由信息寄存器中，供路由器(如转发引擎)读取。同时状态机在特定的某一端口设置标志，来通知CPU查找是否已经结束或还在进行当中。下面对其性能进行分析。

4.性能分析

由于路由表项中，地址掩码的引入，使得路由结构变得非常灵活。但相应的，由此产生的内存的开销也相当的大。这是性能和硬件开销一对矛盾的必然体现。

该路由卡原型的实现是利用微机上的ISA总线，采用存取时间为70ns 的SRAM存储器(所需容量为6*123k*8bit)。除了使用ISA总线上提供的总线外，本身还带了33M的晶振。对某一路由表项的查找，最多只需32步查找。

在最坏情况下，共需32次查找，查找时间为：

32* 1 /(33*106) ≈ 9.7 * 10 -7秒

此时每秒可查找 1/(9.7 * 10 -7)≈ 1.03 * 106次

虽然该路由卡是基于ISA总线，但平均来说，该路由卡的查找速率为每秒8百万次。这也从另一方面说明该路由卡的设计是可行的。

针对网络流量的增加，及对路由器性能要求的提高，本文从硬件的角度对IP路由查找算法用硬件实现做了一系列的分析，并提出了相应的便于用硬件实现的IP路由表的数据结构。同时对该路由卡的性能进行了分析。

同时也该看到：为了更快的提高路由表的查找速率，基于ISA总线是不可能满足要求的。由此，使用FPGA芯片不可避免。由于VHDL语言固有的灵活性和可编程性，可以更为灵活和高效的实现路由查找。所以，使用FPGA芯片来实现路由查找，是未来的趋势。