网络树形搜索引擎的设计及其验证

论文摘要

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

论文目录

• 第一章 绪言
• 1.1 研究背景及意义
• 1.1.1 什么是网络处理器
• 1.1.2 什么是搜索引擎
• 1.2 研究方法及过程
• 第二章 网络处理器及其树形搜索引擎介绍
• 2.1 网络处理器介绍
• 2.1.1 网络处理器模块框图
• 2.1.2 网络处理器数据流程
• 2.1.3 内嵌处理单元EPC
• 2.2 搜索引擎比较
• 2.2.1 PATRICIA树
• 2.2.2 精确匹配的改进算法
• 2.2.3 二进制trie树（binary Trie）
• 2.2.4 路径压缩trie树（Path-Compressed Trie）
• 2.2.5 多分支Trie树（Multibit Trie）
• 2.2.6 地址前缀长度的二分查找法
• 2.2.7 缓存策略
• 2.2.8 内容可定址——CAM（Content-Addressable Memory）
• 2.2.9 树形搜索引擎
• 第三章 树形搜索引擎工作原理及其设计
• 3.1 树形搜索引擎的工作原理
• 3.2 树形搜索引擎的搜索过程
• 3.3 树形数据结构（DT，PSCB，Leaf和LUDef）
• 3.3.1 直接表格DT（Direct Table）
• 3.3.2 模式搜索控制单元PSCB（Pattern Search Control Block）
• 3.3.3 叶子Leaf
• 3.3.4 查找定义表（LUDefTable）
• 3.4 搜索算法
• 3.4.1 全匹配搜索FM（Full Match）
• 3.4.2 最长前缀匹配LPM（Longest Prefix Match）
• 3.4.3 软件管理搜索SMT
• 3.5 性能加强点（Cascase/Cache，Hash，Binary Search）
• 3.5.1 级联（Cascade）／Cache
• 3.5.2 哈希（Hash）
• 3.5.3 二进制搜索（binary search）
• 第四章 树形搜索引擎设计实现
• 4.1 概述
• 4.2 接口波形
• 4.3 内部模块实现
• 4.3.1 FMLPM模块
• 4.3.2 FMSMT模块
• 4.3.3 MISC模块
• 第五章 树形搜索引擎的验证及其验证结果
• 5.1 验证方法
• 5.2 验证流程
• 5.3 验证环境
• 5.3.1 验证平台概述
• enqueuer）'>5.3.2 命令输入模块（cmd_enqueuer）
• 5.3.3 DDI响应模块
• 5.3.4 CPEI激励模块
• 5.3.5 CPDI激励模块
• 5.3.6 控制存储器仲裁模块CSA（Control Store Arbiter）
• Stim'>5.3.7 线程分配模块Dispatcher_Stim
• Snooper'>5.3.8 结果检查模块TSE_Snooper
• 5.4 验证结果
• 第六章 总结
• 6.1 项目总结
• 6.2 个人总结
• 参考文献
• 致谢