随着Internet的不断发展,路由查找速度已经成为制约核心路由器性能的主要瓶颈。减少访问存储器的次数是提高路由查找速度的有效途径之一。由于片外存储器价格较片内存储器低很多,本文利用多片片外存储器,采用基于并行流水线的查找方式对IP地址进行最长前缀匹配,以达到访问一次存储器的时间完成一次路由查找。本文首先介绍了国内外现有的部分研究成果,并在剖析多分支trie算法的基础上,采用分段查找及前缀扩展技术,给出了一种适合FPGA实现的路由查找算法。算法采用多表结构,将查找过程分为了四级,然后根据四块存储器独立工作的特性,采用流水线的方式进行了并行化设计,从而可以保证访问一次存储器完成一次数据包的查找。设计表的结构时,为了保证占用的空间小,本文给出了一个动态规划算法用于求解四个目标层的值。本文提出的设计结构支持动态更新,并且更新单元数少。测试结果表明,在同等规模的前缀集下,相比DIR-24-8-BASIC方法在空间上具有显著优势。最后,给出了算法实现的FPGA设计结构,实验结果显示算法可以达到15Mpps的查找速度。