| 摘要 | 第1-5页 |
| ABSTRACT | 第5-6页 |
| 第一章 绪论 | 第6-13页 |
| ·Internet的发展概况 | 第6-7页 |
| ·路由器的发展演变 | 第7-9页 |
| ·第一代路由器:CPU结构 | 第7页 |
| ·第二代路由器:线路卡具有寻路转发能力 | 第7-8页 |
| ·第三代路由器:分布式处理和交叉连接型的交换结构 | 第8-9页 |
| ·高速路由查找算法的研究背景 | 第9-12页 |
| ·IPv4的地址结构和基于类的路由查找 | 第9-10页 |
| ·无类域间路由(CIDR)及CIDR下的路由查找 | 第10-11页 |
| ·IPv6的路由查找 | 第11页 |
| ·研究路由查找算法的目的 | 第11-12页 |
| ·本文内容的组织 | 第12-13页 |
| 第二章 基于Trie的路由查找算法 | 第13-31页 |
| ·路由查找算法性能的评估标准 | 第13-14页 |
| ·Radix Trie | 第14-15页 |
| ·Patricia Trie | 第15-16页 |
| ·路径压缩Trie | 第16页 |
| ·LC-Trie | 第16-17页 |
| ·多比特树(扩展树) | 第17-21页 |
| ·前缀扩展(Prefix Expansion) | 第17-18页 |
| ·多比特树的构造和查找方法 | 第18-19页 |
| ·受控前缀扩展(Controlled Prefix Expansion) | 第19-21页 |
| ·压缩转发表 | 第21-25页 |
| ·Leaf-Push | 第21页 |
| ·压缩转发表算法的预处理 | 第21页 |
| ·第一级的数据结构 | 第21-23页 |
| ·第一级的查找 | 第23-24页 |
| ·第二级和第三级的数据结构 | 第24-25页 |
| ·算法性能分析 | 第25页 |
| ·压缩树 | 第25-30页 |
| ·算法基本思想 | 第25页 |
| ·编码方案 | 第25-26页 |
| ·算法描述 | 第26-28页 |
| ·查找过程 | 第28-29页 |
| ·算法的改进-扩展压缩树算法 | 第29-30页 |
| ·性能分析 | 第30页 |
| ·本章小结 | 第30-31页 |
| 第三章 常用路由查找算法 | 第31-42页 |
| ·线性表算法 | 第31-33页 |
| ·基本方案 | 第31-32页 |
| ·算法性能评估 | 第32页 |
| ·算法改进 | 第32页 |
| ·转发表的更新 | 第32-33页 |
| ·基于前缀区间的算法 | 第33-35页 |
| ·基本方案 | 第33-35页 |
| ·方案改进 | 第35页 |
| ·性能分析 | 第35页 |
| ·基于前缀长度的二分查找算法 | 第35-38页 |
| ·基于前缀长度的查找 | 第35页 |
| ·基于前缀长度的二分查找 | 第35-36页 |
| ·加入标记 | 第36-37页 |
| ·回溯问题 | 第37页 |
| ·性能分析 | 第37-38页 |
| ·基于CAM的硬件查找算法 | 第38-40页 |
| ·CAM与TCAM | 第38页 |
| ·采用TCAM进行查找 | 第38-39页 |
| ·TCAM算法的性能分析 | 第39页 |
| ·TCAM表项管理方法 | 第39-40页 |
| ·各种算法性能比较 | 第40-42页 |
| 第四章 基于二分查找Trie的路由查找算法 | 第42-54页 |
| ·算法基本原理 | 第42-44页 |
| ·IPv4路由查找方案 | 第44-45页 |
| ·转发表的生成和查询 | 第44-45页 |
| ·回溯问题 | 第45页 |
| ·转发表的生成 | 第45-46页 |
| ·转发表的查找 | 第46-47页 |
| ·转发表的更新 | 第47-48页 |
| ·实验与性能分析 | 第48-50页 |
| ·查找速度 | 第48-49页 |
| ·转发表所需存储容量 | 第49页 |
| ·转发表更新 | 第49-50页 |
| ·IPv6路由查找的方案 | 第50-53页 |
| ·算法改进 | 第50-51页 |
| ·转发表的生成 | 第51页 |
| ·查找算法 | 第51-53页 |
| ·算法小结 | 第53-54页 |
| 结束语 | 第54-55页 |
| 致谢 | 第55-56页 |
| 参考文献 | 第56-57页 |