一种无回溯的最长前缀匹配搜索算法

摘要

研究网络处理器中的搜索算法,提出一种基于Patricia树的无同溯搜索算法,并进行仿真和评估分析.该算法被用于中科院计算所的网络处理器的搜索引擎的设计中,该搜索引擎可以运行在155.9 MHz的XC2VP30 FPGA上,占用421个LUT,当频率为100 MHz时,每秒可以执行约7 000 000次搜索操作,实现了资源消耗和性能的折中.