路由表的快速查找技术

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

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

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

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