以路由缓存表项指针作标记的标记交换探析

刘永强

（江苏海洋大学，江苏连云港 222005）

随着IP 宽带应用需求的不断提高，对网络的带宽提出了更高要求，而路由器对IP 数据分组的转发速率是制约频带拓宽的关键因素。提高IP 数据分组的转发性能大致有如下的几种思路[1]：①将路由和转发分开；②用快速硬件对IP 分组进行报头处理、寻径和转发；③使用分布式网络接口；④以交换结构提高各接口之间的带宽。

无论从IP 路由器的体系结构上还是从实现技术上看，上述的几种研究思路，虽然能使IP 分组的转发速率有一定的提高，但始终未克服从路由表中查找路由（本文称之为表格路由）这个瓶颈，这与IP 地址的体系结构有关。IP 地址的分配虽然具有全局性，然而IP分组的路由是基于目的地址的，从IP 地址中可得到包括地址类型、网络地址、主机地址3 个信息，其不具备方向性，这些信息对路由器中的某个IP 数据分组来说就像置身迷宫，只能在一定的路由策略下通过多次的比较或查找以确定数据分组的去向，这使得主干网上的路由器不得不维护庞大的路由表和路由缓存表，而且对每个到达的IP 分组（即使是同一数据流或同一转发等价类）都需要在该路由缓存散列表[2]上进行一次查找，如果路由缓存没有命中，则需要做一次完整的更花时间的路由计算，再将结果加入到路由缓存中供下次利用，而高速缓存（包括联想存储器CAM 和TCAM——ternary CAM）因受容量的制约致使取得的性能改善很有限，这是IP 地址体系结构的先天不足。

1 MPLS 及IPLS 的引入

设计和实施一种不需要查找路由表，直接经计算即可得到路由（本文称之为计算路由）的地址体系结构目前条件尚不成熟。为减小IP 地址目前的这种结构体系对IP 分组转发速率的进一步提高所产生的影响，提出了将路由和转发分开，并在此基础上利用“一次路由，多次转发/交换”技术的多种方案。诸如MPLS（多协议标记交换）、IPLS（IP 分组标记交换）等，两者使主干网上路由器的数据分组的转发性能有了很大的提高，有望成为未来互联网新的技术平台。

MPLS 综合了IP 选路和ATM 交换的优点，实现基于IP 路由机制和ATM 交换机制的统一技术平台。但是这种基于ATM 的体制存在着如下缺陷[3]：①在网络边缘的节点上IP 分组与ATM 信元之间拆与装比较复杂，而且在传输速率非常高时，甚至难以实现；②FEC（转发等价类）标记与各种标记域的相互对应较难保证；③通信双方之间2 条不对称性的单向LSP（标记交换路径）没有有效地利用双向对称的ATM 交换通路的带宽；④MPLS 隧道的功能在ATM 上只有VPI 和VCI两级；⑤ATM 的信元标记归并可能会发生交织；⑥MPLS 使用动态IP 选路可能形成环路。总体上看，MPLS 是将IP 地址的最长前缀匹配改为标记的精确匹配。

为克服MPLS 的以上缺陷，使用基于IP 分组的标记交换（IPLS）构建宽带网络有明显的优势[3]。下面讨论标记交换中的标记问题。

2 标记的概念

几乎所有关于标记交换的资料中对标记没有准确的语意，只是给出了说明性的定义，比较倾向的描述是一种简短的，具有固定长度的，用以标识网络中一个“转发等价类（FEC）”的，只具有局部意义的标识符。由于其在标记交换中起到非常重要的作用，因此必须具有明确的语意，可以看作是FEC 的别名，或者是IP 地址的最长前缀匹配等，然而，具体到协议栈实现中究竟选取什么作标记需要仔细研究。实际上，IP 地址也是一种标记，用以标记互联网上的一台主机。

从本质上看，交换是指交换节点根据数据分组携带的标记，按照某种设定的输入输出关系，对分组进行处理的过程，以求在源与目的之间建立一条数据通道。可见，输入输出关系的高效利用是关键所在，这种关系的建立则可以采用各种有效的路由算法，与分组的处理是分离的。交换机与路由器中的这种输入输出关系建立方法可以不同，可使用的协议有许多，如路由信息协议（RIP）、内部网关路由协议（IGRP）、开放式最短路径优先协议（OSPF）、外部网关协议（EGP）和边界网关协议（BGP）等。

3 以路由缓存表项入口指针作标记

对于主干网节点上的一个待发送的数据分组，IP层大致完成如下过程：①从传输层或数据链路层接收数据分组并进行一定的处理；②在所连接的网络中使用一定的路由算法选择数据包传输的下一跳；③把数据分组交予数据链路层的驱动程序。其中第②步根据IP 地址经过一定的计算，然后到庞大的路由表中进行检索，以得到该数据分组的下一跳，这一步十分费时，是路由器的瓶颈。

上面提到的“一次路由，多次转发/交换”思想将在很大程度上缓解路由器路由选择的压力，然而这一思想要求路由器保持活跃的路由结果，缓冲将是比较可行的解决方案，而记录路由结果有2 种选择：①记录数据流的输出硬件端口（如网卡地址）；②记录路由缓冲表项的入口指针。显然，由于路由器需要收集许多管理数据，选择记录路由缓冲表项的入口指针是对路由的最好保持。

本文提出以路由缓冲表项的入口指针（Entry Pointer of Route Cache，EPRC）作IPLS 的标记，该入口指针可以是物理或逻辑地址，一般为逻辑地址。

3.1 选取EPRC 作标记的出发点

宽带IP 网络要求路由器有高速的数据分组转发性能。一般来说，标记越简洁、越能表现路由信息，那么使用的转发规范也就越简单，由此而获得的数据分组转发性能就越好，所以，使用路由缓冲表项的入口指针作标记是较为合适的选择。使用含混或“曲线”的标记在高速数据分组转发中很难想象有多好的性能表现。

3.2 IP 数据分组转发性能的提高

选取EPRC 作标记既继承了IP 路由的灵活性，又为高速的交换提供了可能。在已建好的连接上转发数据分组时，根据其携带的标记将直接得到所需的路由信息。对内存的访问只需一次，按10 ns 的访存时间计算，理想情况下每秒可进行100 M 次路由/交换，假设数据分组的载荷平均为200 个字节，在网络线路接口能达到较高的吞吐率的情况下，则总带宽为160 Gbps，若考虑使用高速Cache、多体存储器和更高速的内存，则得到的总带宽将大于上面的数字，完全能满足大多数主干网交换节点的需要。

3.3 EPRC 的应用限制

以路由缓存表项的入口指针作标记这一点在端节点与路由器或各路由器之间达成共识后，新的路由表项除标记和原有的内容外，还可包括服务类型、服务质量（QoS）、标记堆栈指示和标记操作等信息，其内容的多寡依据路由器提供的服务需要而定，跟标记无关，所以这种标记可应用于多种网络协议，目前基本上没有应用上的限制。至于担心建立连接会损失一定的时间，这是不必要的，比如打电话需拨号是再正常不过的，况且大多数应用都是面向连接的，而且更关心的是网络的数据传输速度。

4 标记在IP 网络中的承载

为增强EPRC 的兼容性，采用对IPv4 数据分组的选项[4]（Options）进行扩展。

在IPv4 中，IP 选项类型组成如图1 所示，其定义见表1。

图1 IP 选项类型组成

表1 选项类型定义

如上所述，选项类型为0 和2 的已被使用，可利用保留的类型，即class=1。由于EPRC 在IP 数据分组的传输中需要将该选项复制到所有的分片中，故复制位应置为1，即二进制形如[101xxxxx]b，将此标记置于IP选项中，实际的路由缓存表项入口指针可选用4 个字节32 位整数，可容纳4 G 项，可满足一定规模的骨干路由器需要。

IP 选项的定义如图2 所示，详见Linux 源代码(v2.6.28.10)srcincludelinuxip.h。

图2 IP 选项

路由缓存项的结构在内核源代码srcin clude et oute.h中的定义如图3所示。

图3 路由缓存项定义

EPRC 在网络层而非链路层实现，只需修改部分的路由软件，无须增加硬件设备。EPRC 在IPv6 中同样有合适的承载。

5 标记的分配、分发与操作

使用EPRC 作标记，路由缓存表项的分配就是标记的分配，在路由器采用数据流驱动的方式。标记的分发采用下游按需分发，在路由缓存表项分配完成后，将得到的入口指针由ICMP 携带告知上游节点并登记保存，待数据分组发送时将该标记装配进IP 数据分组的选项里一并转发出去。

以Linux（内核版本v2.6.28.10）为例，IP 数据分组在网络层的处理流程[2，5]如下。当数据帧到达网络设备时，将产生一个中断，中断程序调用驱动层的net_rx()，继而产生软中断进入net_rx_action()，如发现这个数据帧是IP 分组，则调用IP 协议层ip_rcv()，IP 数据分组在经过netfilter 模块处理后，进而调用ip_rcv_finish()，在该函数内，将调用IP 接口函数ip_route_input()执行实际的路由算法。其中入参5 个：skb (IP 包缓冲区)、iph-〉daddr(IP 包目的地址)、iph-〉saddr(IP 包源地址)、iph-〉tos(服务类型)和dev(输入的网络设备)。当函数返回0 时，说明成功找到路由。路由查询结果放在skb-〉dst 中，其指向路由缓存中的一个结点。之后通过调用skb-〉dst-〉input(skb)来对该IP 数据包进行处理。由于这里的input 是路由缓存结点中的一个函数指针，根据数据包的流向进行处理，如果这个路由项表示转发的，那么这个指针实际上指向的是ip_forward()，而如果是传送给本地的，那么指向的是ip_local_deliver(),该函数将这个IP 包进一步传给上层协议层处理，ip_forward()则将这个IP 包从网络设备发送出去。

路由缓存结构关系如图4 所示。

图4 路由缓存结构关系图

涉及的主要数据结构包括如下几点：struct rt_hash_bucket rt_hash_table、struct rtable、struct dst_en try和变量rt_hash_mask。EPRC的保存可采用在结构rtable中新增对应的指针，形如struct rtable*eprc，初始化为null。

无论是数据分组输入还是输出，当搜索路由缓存失败，则执行路由算法查找路由表并将表项保存到路由缓存中，利用函数rt_intern_hash()将创建的缓存项添加到哈希缓存头部。此后，利用ICMP 携带该缓存路由表项指针以长整型反向回传到上一跳（数据分组初始发起者无上一跳）并保存，放到对应的路由缓存项的指针eprc 中。

当有IP 数据分组输入时，解析IP 的选项，如果携带有ERPC，则直接从路由缓存项中读取，即可进入数据分组的下一处理环节。为安全起见，将增加审核环节，即需比对对应的源地址和目的地址等相关信息，以免使用过期的eprc。

当有IP 数据分组需要输出时，在搜索路由缓存项成功返回后，如果保存有下一跳的eprc，则其组装进IP分组的选项内一并转发出去。

如涉及标记的操作压栈、弹栈、合并和转换等可沿用MPLS 的方法[6]。

6 结束语

在非计算路由中，要获取数据包的下一跳信息，就必须对路由缓存所在的存储器进行至少1 次读取，表格路由中获取路由信息最直接、最快捷的方法是以EPRC 作为标记。标记交换中以EPRC 作为标记处理单播的通信是可以胜任的，对多播和组播还有待进一步研究。