随着Internet的迅猛发展,网络处理器的接口速率已经达到了2.5Gbps到10Gbps。这一速率要求网络处理器能快速地进行地址查找,所以说网络处理器中搜索引擎已经成为实现包快速转发的关键。 笔者结合网络处理器的本身架构,从网络处理器的整体性能和性价比出发,对多个网络处理器的搜索算法进行横向和纵向比较,如,PATRICIA树,内容可定址—CAM,缓存策略,二进制trie树,多分支Trie树和地址前缀长度的二分查找法等,然后提出了基于PATRICIA树的树形搜索引擎的设计原理和设计方法。树形搜索引擎支持精确的全匹配搜索(FM),也支持最长前缀搜索(LPM),还支持用于自定义树的搜索(SMT);它支持二进制patricia树结构,同时也支持多分支(multibit)的搜索方法;它支持缓存(Cache)策略搜索,也支持哈希(Hashing)辅助搜索;它还支持专门为trunking设计的二进制搜索(Binary Search)算法。 笔者结合网络处理器的整体框架和性能,提出了树形搜索引擎的实现方案,从三个主要执行模块阐述了搜索引擎的命令操作过程。 笔者更从工程的角度出发,提到了芯片验证(Verification)是设计实现的保证,所以论文从验证方法、验证流程、验证环境和验证结果四个方面,阐述了树形搜索引擎模块的验证。