Abstract:
This paper studies search algorithms designed for network processor, and presents a new non-backtracking longest prefix match algorithm based on Patricia tree. The algorithm is simulated and evaluated, which is used in the searching engine design of a network processor designed by Institute of Computing Technology, Chinese Academy of Sciences. The searching engine can run at a speed of 155.9 MHz, and occupies 421 LUTs when implemented in a XC2VP30 FPGA. It can finish 7 000 000 search operations when running at a speed of 100 MHz.
Key words:
search algorithm,
longest prefix match,
Patricia tree,
searching engine
摘要： 研究网络处理器中的搜索算法，提出一种基于Patricia树的无回溯搜索算法，并进行仿真和评估分析。该算法被用于中科院计算所的网络处理器的搜索引擎的设计中，该搜索引擎可以运行在155.9 MHz的XC2VP30 FPGA上，占用421个LUT，当频率为100 MHz时，每秒可以执行约7 000 000次搜索操作，实现了资源消耗和性能的折中。
关键词:
搜索算法,
最长前缀匹配,
Patricia树,
搜索引擎
CLC Number:
ZHANG Fei-fei; LI Hua-wei; HAN Yin-he;. Non-backtracking Longest Prefix Match Search Algorithm[J]. Computer Engineering, 2008, 34(10): 52-54.
张飞飞;李华伟;韩银和;. 一种无回溯的最长前缀匹配搜索算法[J]. 计算机工程, 2008, 34(10): 52-54.