论文部分内容阅读
随着Internet规模的急剧膨胀,路由器的体系结构、转发速度和交换网络的容量已成为网络发展的瓶颈。本文结合国家863项目“可扩展到T比特的高性能IPv4/v6路由器基础平台及实验系统”,较深入的研究了高速路由器路由查找算法及其实现技术。在对现有路由查找算法分析比较的基础上,本文重点研究了基于TCAM的路由查找技术,提出了基于TCAM的二级路由查找方案;对基于流分类的哈希查找进行了分析,提出了多哈希随机检测快速选择更新算法。本文所做的工作如下: 1、提出了评价路由查找算法的标准,指出了现有路由查找算法的问题,对现有路由查找算法及新兴发展方向进行了较为全面的分类分析比较,为T比特路由器转发引擎的研究设计提出了新的课题和思路。 2、设计了一种由TCAM和SRAM分别完成搜索和读结果的查表流水线。该方案引入一种全新的TCAM表项配置与管理方法来支持IPv4/v6双协议栈下的路由查找。与传统的由TCAM串行完成搜索和读结果两个过程的路由查表方案相比,该方法可将路由查表时间从十多个周期减少到仅为2或4个周期,大大提高了转发引擎性能。实测结果表明,在数据速率高达10Gbps时,该方案下的转发引擎能线速转发包长40字节以上的IP数据包。 3、根据TCAM的特性,提出了一种基于TCAM的二级路由查找方案。该方案由一种基于比特选择的hash分类机制实现,大大节省了查表的功耗,消除了基于TCAM的路由查找功率消耗大的特点,提高了系统的稳定性,具有重要的实用价值。 4、对现有路由表项更新算法进行了分析和比较,在分析了基于流分类的哈希查找算法的随机性的基础上,提出了一种支持IPv4/IPv6双协议栈的路由表项更新算法——多哈希随机检测快速选择更新算法,分析了该算法的性能并给出了实验结果。该算法在T比特路由器上已得到实现,取得了较好的效果。