路由器中的硬件IP路由表应用解析

　　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 ;

　　entryentry = entry ->hit_next;

　　}ELSE{ entryentry = 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 <= 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指针都不为空等四种情况。这里就不再讨论。