交换式路由技术

　　虽然计算机工业在近几年引入了越来越高速的共享式总线，从ISA到EISA直至现在的PCI。但是这仍然跟不上网络发展的步子。首先,共享总线不可避免内部冲突；第二，共享总线的负载效应使得高速总线的设计难度太大。

　　1．单级交换结构

　　交换结构的引入逐步克服了共享总线的以上缺点。从技术上,目前使用较多的交换结构有共享内存和Crossbar两种。而Crossbar的结构由于其简单性得到了更多的青睐和更广泛的采用。

　　共享内存结构是通过共享输入输出端口的缓冲器，从而减少了对总存储空间的需求。分组的交换是通过指针调用来实现的，这提高了交换容量。但它的速度受限于内存的访问速度。

　　Crossbar结构可以同时提供多个数据通路。一个Crossbar结构由N×N交叉矩阵构成。当交叉点（X，Y）闭合时，数据就从X输入端输出到Y输出端。交叉点的打开与闭合是由调度器来控制的。因此，Crossbar结构的速度要取决于调度器的速度。调度器是Crossbar交换结构的核心，它在每个调度时隙内收集各输入端口有关数据包队列的信息，经过一定的调度算法得到输入端口和输出端口之间的一个匹配，提供输入端口到输出端口的通路。

　　Crossbar结构可以支持高带宽的原因主要有两个:第一,线路卡到交换结构的物理连接现在简化为点到点连接,这使得该连接可以运行在非常高的速率。半导体厂商目前已经可以用传统CMOS技术制造出1Gbit/s速度的点对点串行收发芯片,并且可以在今后几年里把速度进一步提高到4～10Gbit/s的水平。第二个原因是它的结构可以支持多个连接同时以最大速度传输数据,这一点极大的提高了整个系统的吞吐量。只要同时闭合多个交叉节点，多个不同的端口就可以同时传输数据。从这个意义上，我们称所有的Crossbar在内部是无阻塞的,因为它可以支持所有端口同时以最大速率传输(或称为交换)数据。

　　数据包通过Crossbar的时候,可以是以定长单元的形式(通过数据包的定长分割),也可以不进行分割直接进行变长交换。一般高性能的Crossbar交换结构都采用了定长交换的方式,在数据包进入Crossbar以前把它分割为固定长度的cells,等这些cells通过交换结构以后再按照原样把它组织成原来的变长包(packet)。

　　交叉开关和共享内存都能够达到比较高的吞吐率。共享内存的特点是实现简单，能达到比较高的吞吐率,但是其可扩展性比较差,当线路接口卡数量较多时,性能将受到一定的影响。而交叉开关能够达到比较高的速率,扩展性好,但是需要设计完善的调度算法并用高速硬件实现调度器。随着人们对交叉开关调度算法研究的深入,已经设计并实现了许多性能良好、实现简单的调度算法。因此,目前高性能路由器都趋向于使用交叉开关作为交换结构。

　　但是交叉开关和共享内存结构仍属于单级交换结构范畴。当考虑大型系统时，单级交换结构有两个基本问题。第一、对于小规模系统，每端口成本还算合理，但随着规模的扩大，其成本涨得也特快。第二、所有的单级交换结构在技术上受限于其尺寸与速度。一旦达到这些极限，单级交换机无法再增加端口或提升线路速率。正因为如此，可扩展的交换系统必须采用多级结构。

　　2. 多级交换结构

　　多级交换结构是由多个交换单元互联起来的，每个交换单元具有一整套输入输出，与普通交换机类似，提供输入输出的连接。通过互联多个小的交换单元，就可以制造一个大型的、可扩展的交换结构。多级结构之间的不同取决于交换单元之间是如何互联的。典型的结构包括Benes网、Butterfly网、Clos网等形式。

　　Benes网使用方形交换单元（即：输入输出端口数相同）进行多级互联。一般来说，3级N部Benes网的每一级均可以用N个输入/输出端口和N个交换单元来构造（如图4所示）。这个格形结构在每个输入端和每个输出端之间形成N个可能的通路。Benes输出可以扩展至任意奇数级。

　　虽然对于小型系统单级结构的设计相对简单，成本也相对低，但是它不能满足下一代Internet扩展的需要。多级结构在操作上较复杂，但是可以扩展到成百上千个端口，这对于下一代Internet核心路由系统是绝对必要的。在多级拓扑结构中，Benes结构是最佳选择，因为它的系统复杂程度最低，性能好且满足可扩展的要求。

路由表的快速查找技术

　　随着Internet上计算机数量的急剧增长,同时用户对带宽的需求的不断增加,使得路由表的快速查找成为目前最需迫切解决的问题。传统的基于软件的路由查找策略，如树或哈希算法，其执行过程都是相当慢的，而且与路由表的大小相关联。所以，这些方法只能用于比较小的、性能较低的包转发应用。

　　使用路由表压缩技术，将路由表按特定的分布规律压缩后存放在处理器的高速缓存中，这样可以大大提高查询速度。但是数据结构的高度优化和压缩使得路由表的更新需要花费更多的寄存器访问和处理器周期。当路由表增大时，这个值还会增加。在路由表更新时，输入的数据包必须被缓存或丢弃，降低了路由器的性能。

　　另外，基于软件查找和更新路由表的不确定性增加了包传输时的抖动，因此必须进行包的缓存，在高速率时还会造成丢包。因此，为了适应网络的发展，理想的包转发方案必须能够不但保证线速的数据转发速率，并且要提供足够大的路由表来满足下一代的路由设备的需要（在边界位置应达到512K）。同时它还要能够以很小的更新时延来处理长时间的突发路由表更新。尽管通常路由表的更新为每秒几百次，但瞬间突发更新则可能会高出很多。

　　要解决这个问题，目前来看最为有效的办法是采用专门的协处理器结合内容寻址寄存器CAM（Content addressable memory）解决方法以及cache解决方法来完成快速路由查找或更新。但是核心路由器需要的转发表非常大，因此对于核心路由器，cache只是一种辅助的方法，需要有足够大的cache能把整个转发表放进去，并且仍然需要快速算法，还可以将逻辑控制器和存储器集成于单一器件中，以缩短存储器的访问时间。