基于TCAM和多核处理器的高速路由查找转发引擎设计

论文摘要

近年来,随着Internet的迅速普及,使用Internet的人数、连接到Internet上的主机数量和数据流量呈现指数式的增长。另一方面,各种新的多媒体业务也不断涌现。因此Internet的容量正在成为一种稀缺资源。为了适应Internet应用的迅速发展,提供更好的服务质量,必须提高网络的容量。随着光纤技术的发展和T比特级交换技术的发展有效的解决了链路带宽、路由器的吞吐量问题,而路由器的转发效率就成为制约网络性能提高的主要瓶颈。如何提高路由器的查找转发效率已经成为众多专家学者和公司研发工作人员研究的重点。而提高转发效率的关键又在于如何提高路由查找速度和采用更先进的、更合理的路由架构。本论文在综合了国内外近年来在路由查找算法及实现和路由器发展架构的基础上,提出了第六代路由器架构的概念,并利用TCAM和多核处理器实现了一种高效的路由查表转发引擎。本文所做的主要工作如下:总结了IP地址结构的变化历程,介绍了现有的一些常用的高速路由表查询算法,对它们进行了详细的研究和比较。分析了路由架构的发展历程,在第五代基于NP实现的高速路由器基础上提出了第六代,即基于多核处理器来实现的更高性能的高端路由器的体系架构。应用TCAM和多核处理器实现了一种高性能的路由转发引擎架构。介绍了一种基于TCAM和FPGA实现的路由查表结构。从功耗、成本、性能方面综合考虑,实现了一种高性能路由查表结构。

论文目录

• 中文摘要
• ABSTRACT
• 符号说明
• 第一章 绪论
• 1.1 课题研究背景
• 1.2 路由查找算法的研究现状
• 1.3 路由器发展现状和研究中存在的问题
• 1.4 本文的主要工作
• 1.5 本文的组织结构及安排
• 第二章 路由查找技术
• 2.1 地址结构的发展变化
• 2.1.1 基于类的地址结构
• 2.1.2 无类域间路由
• 2.1.3 IPV6地址结构
• 2.2 查找技术面临的问题
• 2.2.1 链路速率飞速发展
• 2.2.2 路由表增长迅速
• 2.2.3 最长前缀匹配复杂
• 2.3 路由查找的一些概念和典型算法
• 2.3.1 路由表
• 2.3.2 地址前缀匹配
• 2.3.3 传统的路由查找算法
• 2.3.4 基于多分支Trie树（Multibit Trie）的查找算法
• 2.3.5 基于地址区间的二分查找算法
• 2.3.6 基于CAM/TCAM的硬件路由查找算法
• 2.3.6.1 CAM的实现方法
• 2.3.6.2 TCAM的原理和结构
• 2.3.6.3 采用TCAM的路由查找方案
• 2.3.6.4 TCAM表项更新算法研究
• 2.4 本章小结
• 第二章 路由器的体系结构发展简介
• 3.1 路由器基本体系结构
• 3.2 数据转发引擎的发展
• 3.2.1 第一代路由器 CPU结构
• 3.2.2 第二代路由器 多处理器共享总线结构
• 3.2.3 第三代路由器 分布式交换结构
• 3.2.4 第四代路由器 基于ASIC的分布式交换结构
• 3.2.5 第五代路由器 基于网络处理器的分布式交换结构
• 3.2.6 第六代路由器 基于多核处理器的分布式交换结构
• 3.2.6.1 高端路由器对多核处理器的需求
• 3.2.6.2 一种典型的多核处理器—XLR732介绍
• 3.3 本章小结
• 第四章 基于TCAM和多核处理器的查找转发引擎的实现
• 4.1 高速接口转发平面设计
• 4.1.1 高速转发引擎的管理流
• 4.1.2 高速转发引擎的监控流
• 4.1.3 高速转发引擎的业务流
• 4.2 高速查表引擎
• 4.2.1 TCAM路由方案的拟定
• 4.2.2 FPGA算法+TCAM+DDRII SDRAM方案的硬件实现
• 4.2.2.1 算法查找引擎单元
• 4.2.2.2 时钟单元
• 4.2.2.3 电源单元
• 4.2.3 查找引擎功能的具体实现
• 4.3 本章小结
• 第五章 总结与展望
• 5.1 论文小结
• 5.2 展望
• 参考文献
• 致谢
• 攻读硕士期间参与的工程项目和发表的论文
• 学位论文评阅及答辩情况表