唐丽梅 ，邢素霞 ，陈天华

（1.北京工商大学 计算机与信息工程学院，北京 100048；2.北京英瑞博系统技术有限公司，北京 100039）

随着网络的高速发展，Internet的网络传输量每几个月就增加一倍，这也给高速路由的设计带来了挑战，骨干网路由器接口速率已经达到Tb/s量级，IP路由查找操作已经成为路由器转发性能乃至Internet整体性能的主要瓶颈之一。因此提高路由查找速度的关键是采用快速的路由查找算法。

路由器IP路由查找面临巨大挑战，主要表现在：（1）实现最长前缀匹配的路由查找算法设计困难[1]；（2）路由表庞大，查找记录条目极多；（3）路由更新频繁，最高每秒更新条目达几万条；（4）接口速率越来越高，OC-768（40 Gb/s）以太网及更高标准要求。实现 100 Gb/s接口的线速转发，包转发率要达到150 Mb/s，每包处理时延小于 6.72 ns。

快速的路由查找技术一直是一个热门课题，近年来提出了不少路由查找算法，传统的基于软件的路由查找算法已经不能满足分组的线速转发，目前高性能核心路由器基本上都采用基于硬件的路由查找算法。路由查表实现的主要功能就是最长前缀匹配 （LongestPrefix Matching）。基于前缀值的二分搜索、页面压缩等基于树的搜索存储空间占用少，利用率高，但由于算法实现复杂，硬件实现上不合适。TCAM （Content Addressable Memory）[2]采用保存关键字掩码的方式来保存任意长度的关键字表项，并且使用并行比较，仅在一个时钟周期内就可以完成一次查表操作，能够实现高速查表。但是TCAM的路由表更新操作复杂、功耗大[6]、容量小且价格昂贵。……