论文部分内容阅读
研究表明,Internet持续迅猛的发展对支撑起其数据转发平面功能的两种关键技术——路由查找和分组分类提出了越来越高的性能要求,并对其实现构成了巨大的挑战。本论文系统的调研和分析了这两类技术的共同特点与相关数据分布特征,给出了合并课题研究的可行性分析与相关的算法设计理论指导。在此基础上,分别针对超高吞吐量性能和各种新型应用的需求,如对嵌入式环境应用的支持、对IPv6的良好扩展性以及对多核并行网络处理器架构的支持等,提出了一系列新颖的高性能算法和相应的实现方案,并给出了完备的性能评价:1.提出了一种基于三态内容可寻址存储器(TCAM)的高性能路由查找算法T-DPRLA,该算法根据一系列启发式规则将路由表分布式的存放在多个并行设置的TCAM芯片中,通过引入高效的自适应任务量均衡机制,仅需少量的冗余存储就能提供多倍且稳定的查找性能加速比。理论分析表明,采用现有的技术,该方案即可满足相当于160Gbps甚至更高的线速转发需求。2.提出了一种基于TCAM的分组分类算法DPPC-RE,它充分的利用了并题研究的优势,在继承分布式并行提高吞吐量的思想的基础上,采用TCAM本身来做范围编码解决其范围匹配问题;同时巧妙的利用范围编码和分组分类匹配任务之间的不相关性,提出了一种自适应任务量均衡的机制,实现了稳定的高吞吐量。3.将对相关数据的系统调研分析以及多项启发式原理巧妙的运用到算法设计中,结合CAM技术和基于Trie算法各自的优势,分别提出了一种可供嵌入式环境使用的高性能路由查找方案CCAM-OBC和一种基于变步长位图压缩Trie技术、适合IPv6环境下使用的路由查找算法DVSBC-PC,都在较小存储容量需求的前提下,实现较高的吞吐量,均能满足当前的高端运用需求。4.根据对分类问题的深入理解,以及结合当前多核并行网络处理器架构,提出了一种基于规则集去耦分存的高性能分组分类算法PPCvRP。该算法不但能有效提高传统软件算法的性能,而且有着确定的性能和需求估算公式。