快速的IP路由查找算法

下一代路由器的一个主要设计问题是IP查找机制。对于每一个接受的信息包，路由器在地址查找过程中需执行一次最长前缀匹配操作，以此决定下一个转发站点。目前，这一过程由软件完成并且已成为路由器性能的一个主要瓶颈。因此，我建议使用一种快速的IP查找机制，其中的转发表足够小可存储在SRAM（静态随机存储器）中，并且费用非常低。通过管道技术它也能用硬件来实现。通过使用我们建议的方法，一个大的、拥有45000路由前缀的路由表可以被压缩成大小大约为430千字节的转发表。在最坏的情况下，一次查询的存储器访问的次数是三次。当通过管道技术实现时，所建议的机制能达到每次存储器访问完成一次路由查询。对于目前10纳秒的静态随机存储器，这个机制提供大约每秒1亿次的路由查询。此外，查询速度可以通过存储器访问速度的加速线性提升。

A Fast IP Routing Searching Scheme