| 摘要 | 第5-7页 |
| Abstract | 第7-9页 |
| 第1章 绪论 | 第21-43页 |
| 1.1 研究背景与动机 | 第21-24页 |
| 1.1.1 互联网的起源与发展 | 第21-22页 |
| 1.1.2 高性能网络数据包处理 | 第22-24页 |
| 1.1.3 本文研究动机 | 第24页 |
| 1.2 研究目标及意义 | 第24-25页 |
| 1.2.1 面向未来——顺应网络发展大势 | 第24-25页 |
| 1.2.2 提升性能——实现高效数据交换 | 第25页 |
| 1.2.3 灵活应变——保障柔性系统扩展 | 第25页 |
| 1.3 研究内容及关键技术挑战 | 第25-37页 |
| 1.3.1 本文主要研究点 | 第25-30页 |
| 1.3.2 剖析问题本质——广义加权多模式匹配 | 第30页 |
| 1.3.3 差异化分析及本文研究思路 | 第30-35页 |
| 1.3.4 拟解决的关键技术挑战 | 第35-37页 |
| 1.4 本文主要工作及创新点 | 第37-41页 |
| 1.4.1 本文主要工作 | 第37-40页 |
| 1.4.2 本文主要创新点 | 第40-41页 |
| 1.5 本文组织结构 | 第41-43页 |
| 第2章 文献综述及研究现状分析 | 第43-67页 |
| 2.1 IP地址查找技术 | 第43-52页 |
| 2.1.1 基于三态内容可寻址存储器的IP查找 | 第43-44页 |
| 2.1.2 基于哈希的IP查找 | 第44-46页 |
| 2.1.3 基于前缀树的IP查找 | 第46-49页 |
| 2.1.4 并行处理技术 | 第49-51页 |
| 2.1.5 小结 | 第51-52页 |
| 2.2 面向虚拟化路由器的多表查找技术 | 第52-55页 |
| 2.2.1 基于隔离存储的多表查找 | 第52页 |
| 2.2.2 基于树融合的多表查找 | 第52-53页 |
| 2.2.3 基于表融合的多表查找 | 第53-54页 |
| 2.2.4 小结 | 第54-55页 |
| 2.3 面向软件定义网络的流表查找技术 | 第55-61页 |
| 2.3.1 基于层次化前缀树的多域规则匹配算法 | 第55-56页 |
| 2.3.2 基于规则空间分解的多域规则匹配算法 | 第56-57页 |
| 2.3.3 基于降维或空间投影的多域规则匹配算法 | 第57-59页 |
| 2.3.4 多域规则匹配的软、硬件加速技术 | 第59页 |
| 2.3.5 OpenFlow的流表查找算法与架构 | 第59-60页 |
| 2.3.6 OpenFlow交换机的原型实现与优化 | 第60页 |
| 2.3.7 小结 | 第60-61页 |
| 2.4 面向命名数据网络的名字查找技术 | 第61-67页 |
| 2.4.1 基于名字的转发 | 第61页 |
| 2.4.2 基于哈希表的名字查找技术 | 第61-62页 |
| 2.4.3 基于布鲁姆过滤器的名字查找技术 | 第62-63页 |
| 2.4.4 基于前缀树的名字查找技术 | 第63-64页 |
| 2.4.5 针对应用场景优化的表设计 | 第64-65页 |
| 2.4.6 名字查找的并行处理加速 | 第65-66页 |
| 2.4.7 小结 | 第66-67页 |
| 第3章 一种基于前缀拆分的并行路由查找模型 | 第67-89页 |
| 3.1 引言 | 第67-68页 |
| 3.2 相关工作简介 | 第68-71页 |
| 3.2.1 叶推算法和多步长优化 | 第68-69页 |
| 3.2.2 存储压缩技术 | 第69-70页 |
| 3.2.3 前缀树融合算法 | 第70-71页 |
| 3.3 拆分查找模型 | 第71-77页 |
| 3.3.1 拆分的核心思想 | 第71-73页 |
| 3.3.2 模型假设 | 第73页 |
| 3.3.3 模型定义 | 第73-74页 |
| 3.3.4 模型等价性证明 | 第74-75页 |
| 3.3.5 改进拆分模型的查找优化 | 第75-77页 |
| 3.4 基于前缀树的拆分模型实现 | 第77-82页 |
| 3.4.1 单步长拆分前缀树(Unibit Split Trie,UST) | 第77-78页 |
| 3.4.2 片外哈希表 | 第78-79页 |
| 3.4.3 扩展叶推算法 | 第79-81页 |
| 3.4.4 多步长优化 | 第81页 |
| 3.4.5 拆分前缀树的更新 | 第81-82页 |
| 3.5 实验评估 | 第82-88页 |
| 3.5.1 实验部署 | 第82-83页 |
| 3.5.2 单表查找的性能评估 | 第83-87页 |
| 3.5.3 多表查找的性能评估 | 第87-88页 |
| 3.6 本章小结 | 第88-89页 |
| 第4章 面向高性能IP查找的双向平衡流水线结构 | 第89-108页 |
| 4.1 引言 | 第89-90页 |
| 4.2 背景及相关工作介绍 | 第90-93页 |
| 4.3 流水化的多步长拆分前缀树(PMST) | 第93-101页 |
| 4.3.1 拆分前缀建单步长拆分前缀树(Uni-bit Split Trie,UST) | 第93-94页 |
| 4.3.2 联合最优步长计算及流水化的多步长拆分前缀树(PMST) | 第94-96页 |
| 4.3.3 旋转子树打造平衡基点 | 第96-97页 |
| 4.3.4 平衡度的形式化描述及优化策略 | 第97-99页 |
| 4.3.5 基于PMST的双向多流水架构 | 第99-101页 |
| 4.4 实验评估 | 第101-106页 |
| 4.4.1 存储平衡度 | 第102-103页 |
| 4.4.2 查找性能 | 第103-105页 |
| 4.4.3 存储效率 | 第105-106页 |
| 4.4.4 更新性能 | 第106页 |
| 4.5 本章小结 | 第106-108页 |
| 第5章 一种面向GPU加速IP查找的高效更新机制 | 第108-127页 |
| 5.1 引言 | 第108-110页 |
| 5.2 相关工作 | 第110-111页 |
| 5.2.1 DIR-24-8算法 | 第110页 |
| 5.2.2 GALE | 第110-111页 |
| 5.2.3 线段树及前缀的线段表示 | 第111页 |
| 5.3 线索化线段树 | 第111-119页 |
| 5.3.1 前缀线段树 | 第111-113页 |
| 5.3.2 叶推线段树 | 第113-114页 |
| 5.3.3 线索化线段树及更新算法 | 第114-117页 |
| 5.3.4 线索化线段整合重组 | 第117-119页 |
| 5.4 系统实现 | 第119-122页 |
| 5.4.1 系统架构 | 第119-120页 |
| 5.4.2 查找算法 | 第120-121页 |
| 5.4.3 更新机制 | 第121-122页 |
| 5.5 实验评估 | 第122-126页 |
| 5.5.1 实验部署 | 第122-123页 |
| 5.5.2 线下更新访存开销 | 第123-124页 |
| 5.5.3 线上更新访存开销 | 第124-125页 |
| 5.5.4 综合系统性能 | 第125-126页 |
| 5.6 本章小结 | 第126-127页 |
| 第6章 一种基于GPU加速的多步长前缀树结构 | 第127-155页 |
| 6.1 引言 | 第127-128页 |
| 6.2 背景知识和相关工作 | 第128-130页 |
| 6.2.1 多步长前缀树 | 第128-129页 |
| 6.2.2 CUDA并行编程模型及优化策略 | 第129-130页 |
| 6.2.3 GPU加速的IP查找引擎 | 第130页 |
| 6.3 GPU加速的多步长前缀树(GAMT) | 第130-136页 |
| 6.3.1 编码方案 | 第130-131页 |
| 6.3.2 查找算法 | 第131-132页 |
| 6.3.3 更新机制 | 第132-134页 |
| 6.3.4 总体系统架构 | 第134-136页 |
| 6.4 性能优化 | 第136-144页 |
| 6.4.1 GPU上O(1)的查找算法最快吗? | 第136-137页 |
| 6.4.2 面向GPU访存优化的多步长前缀树 | 第137-140页 |
| 6.4.3 “懒惰”删除 | 第140-141页 |
| 6.4.4 多流流水线 | 第141-144页 |
| 6.5 实验评估 | 第144-153页 |
| 6.5.1 实验方案 | 第144-146页 |
| 6.5.2 查找性能 | 第146-149页 |
| 6.5.3 更新开销 | 第149-150页 |
| 6.5.4 可扩展性及综合性能 | 第150-153页 |
| 6.6 本章小结 | 第153-155页 |
| 第7章 TailTrie:一种面向GPU加速虚拟化路由器的高效可扩展查找结构 | 第155-176页 |
| 7.1 引言及相关工作 | 第155-157页 |
| 7.2 TailTrie核心结构及算法 | 第157-161页 |
| 7.2.1 融合树结构的压缩 | 第157-158页 |
| 7.2.2 下一跳数组的压缩 | 第158-159页 |
| 7.2.3 TailTrie的查找算法 | 第159-161页 |
| 7.3 系统实现及优化 | 第161-169页 |
| 7.3.1 基于GPU的包处理 | 第161页 |
| 7.3.2 总体系统架构 | 第161-162页 |
| 7.3.3 线上TailTrie的查找优化 | 第162-165页 |
| 7.3.4 线下TailTrie的更新及优化 | 第165-168页 |
| 7.3.5 理论分析 | 第168-169页 |
| 7.4 实验评估 | 第169-175页 |
| 7.4.1 实验方案 | 第169-170页 |
| 7.4.2 存储可扩展性 | 第170-173页 |
| 7.4.3 查找性能 | 第173-174页 |
| 7.4.4 更新开销 | 第174-175页 |
| 7.5 本章小结 | 第175-176页 |
| 第8章 迭代哈希:一种时空高效可扩展的多域规则匹配算法 | 第176-199页 |
| 8.1 引言 | 第176-177页 |
| 8.2 多域规则匹配的迭代降维理论 | 第177-181页 |
| 8.2.1 多域规则匹配的数学模型 | 第177-178页 |
| 8.2.2 规则投影及相关理论 | 第178-180页 |
| 8.2.3 迭代降维处理及相关理论 | 第180-181页 |
| 8.3 基于迭代哈希表的多域规则匹配 | 第181-190页 |
| 8.3.1 基于多步长前缀树的前缀规则匹配 | 第182-184页 |
| 8.3.2 基于规则数组的区间规则匹配 | 第184-185页 |
| 8.3.3 二元哈希的转化 | 第185-186页 |
| 8.3.4 迭代哈希表的构建 | 第186-188页 |
| 8.3.5 基于迭代哈希的规则匹配算法 | 第188-189页 |
| 8.3.6 基于流水线的查找架构 | 第189-190页 |
| 8.4 实验评估 | 第190-197页 |
| 8.4.1 实验数据和实验方案 | 第190-192页 |
| 8.4.2 二元哈希转换的可行性 | 第192-193页 |
| 8.4.3 规则前缀树的树高对迭代哈希表性能的影响 | 第193-194页 |
| 8.4.4 存储效率 | 第194-195页 |
| 8.4.5 查找性能 | 第195-197页 |
| 8.5 本章小结 | 第197-199页 |
| 第9章 FPGA加速NDN名字查找:主要挑战及一种可扩展的解决方案 | 第199-220页 |
| 9.1 引言 | 第199-201页 |
| 9.2 相关工作介绍 | 第201-203页 |
| 9.2.1 基于FPGA实现的IP查找流水线 | 第201页 |
| 9.2.2 基于GPU加速的多对齐迁移数组 | 第201-203页 |
| 9.3 问题分析 | 第203-206页 |
| 9.3.1 从IP前缀树到名字前缀树 | 第203-204页 |
| 9.3.2 从GPU到FPGA,从数据并行到流水线加速 | 第204-205页 |
| 9.3.3 FPGA加速名字查找的主要挑战 | 第205-206页 |
| 9.4 层次化对齐迁移数组 | 第206-210页 |
| 9.4.1 分层处理——创造流水线映射基础 | 第206页 |
| 9.4.2 多点探测——突破MATA存储、更新瓶颈 | 第206-207页 |
| 9.4.3 并行验证——提升处理性能 | 第207-208页 |
| 9.4.4 HATA的查找算法 | 第208-210页 |
| 9.5 系统实现及优化 | 第210-215页 |
| 9.5.1 ATA的数组单元设计 | 第210-211页 |
| 9.5.2 迁移边的定位和验证 | 第211-212页 |
| 9.5.3 流水线映射 | 第212-214页 |
| 9.5.4 总体架构 | 第214-215页 |
| 9.6 实验评估 | 第215-219页 |
| 9.6.1 存储效率和可扩展性 | 第215-217页 |
| 9.6.2 查找性能的对比 | 第217-218页 |
| 9.6.3 层数阈值对查找吞吐率的影响 | 第218页 |
| 9.6.4 HATA在真实设备上的性能评估 | 第218-219页 |
| 9.7 本章小结 | 第219-220页 |
| 结论 | 第220-225页 |
| 参考文献 | 第225-246页 |
| 致谢 | 第246-248页 |
| 附录A 攻读学位期间完成的论文 | 第248-250页 |
| 附录B 攻读学位期间参与的科研项目 | 第250页 |
