Internet的迅速发展给我们的生活带来了巨大的变化。随之而来的是网络流量的迅速增长。网络流量的增长对于Internet上的路由器来说是一个很大的挑战，非凡是核心路由器。它需要高速有效的包调度.转发和路由策略。本文针对路由器的路由查找，提出了一种高效的.便于用硬件实现的技术。
1. 路由器的体系结构
图1给出了一般路由器的逻辑体系结构。它主要由下面几部分组成 ：路由引擎、转发引擎、 路由表、网络适配器和相关的逻辑电路等。转发引擎负责把从一个网络适配器来的数据包转发到另一个网络适配器出去。ip协议，包括对路由表的查找，构成了转发引擎中最主要的部分。由于每个通过路由器并需要其转发的数据包都要对路由表进行查找，所以路由表的查找效率如何往往决定了整个路由器的性能。路由引擎则包括了高层协议，非凡是路由协议，它负责对路由表的更新。由于路由引擎不涉及通过路由器的数据通路，故它可用通用的CPU代替。
2．硬件路由表的数据结构设计
一般路由器中路由表的每一项至少有这样的信息：目标地址、网络隐码、下一跳地址。假如对每一个IP地址都要一个表项，那么需要占用很大的2323*4字节的存储器，而且其中必定有很多的表项没有被使用，这就会造成极大的资源浪费。
为了用硬件实现路由表的查找，查找算法需要满足如下的条件：
1） 实时的实现路由表的查找；
2） 有效的实现路由表的插入和删除；
3） 提供有效的最长前缀匹配；
4） 具有良好的可扩展性；
5） 支持广播和组播；
6） 有效的对Memory进行利用；
7） 硬件上轻易实现，并具有良好的性能 。
我们考虑，假如在对路由表的查找中，把子网隐码和IP地址结合起来，对IP地址进行相应的分段，并把它们相连。这样在路由表的表项中，只有IP地址的一部分及其相应的隐码部分，可以实现良好的可扩展性，只要对Memory进行有效的治理，可以灵活的动态的实现对路由的插入和删除。鉴于此，我们设计该表的结构（如下面的表一所示 ）：
它的思想是：把32位IPv4地址主要分成4部分，每部分8位。在该结构中，Address-part[0-4]是IP地址中的一部分，Mask-part[0-4]是相应的掩码部分。Hit-next[0-4]是需要查找的目标IP地址与掩码部分相与后，与Address-part一致时所要查找的下一路由项所在地址的指针。,Miss-hit[0-4]则是相互不一致时，下一路由项所在地址的指针。Shift位则用于判定是否需要对IP地址中的下8位进行查找和判定。它只有在当前的8位IP地址与目标地址中相应的8位一致时，才会被置位。Stop位用于判定是否还需进行查找。它在IP地址查找结束时被置位，或没有比当前项所对应的IP地址更长的路由表项时被置位。
图2就是一个表1的例子 ：
在该例子中，每一方框中上面一行表示相应的IP地址部分和隐码部分。下面一行表示相关的隐码部分的二进制表示。 相应的查找算法如下：
／＊查找算法开始 */
search = TRUE ;
WHILE ( search ) {
masked_key = key & ( entry -mask_part ) ;
result = ( entry -address_part ) = = masked_key
IF ( result = = TRUE ) {
best_match = entry ;
entry = entry -hit_next;
}ELSE{
entry = entry -miss_next;
IF ( entry -stop = = TRUE ) search = FALSE;
}
}
RETURN best_match ；
／＊查找算法结束 */
为了实现有效的插入和删除，我们还要在路由表的数据结构中再另外添加几个域 ：parent指针（指向本结点的父结点），路由信息（routeinfo）等。它们的用途是在路由表的查找过程中，非凡是在指针的回溯（pointer reversal）中，可以大大的节省查找时间。由于IP路由的插入和删除比较复杂。我们只是粗略得说明一下。
IP路由的插入：
/*插入算法开始 */
/* 先用上面提到的查找算法找出best-match */
best_match = search ( new_entry );
/* 确定需要加入的路由中没有被best-match包括的那几位 */
for ( count = first_unmatched_bit ; count
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芯片来实现路由查找，是未来的趋势。
