论文部分内容阅读
Internet骨干链路速度的不断提高，要求Internet核心路由器必须以10Gbps或者更高的速度处理IP最长前缀匹配(LongestPrefixMatch，LPM)，这一问题已成为Internet核心路由器的主要性能瓶颈之一。IPv6地址的出现要求最长前缀匹配的查找长度从IPv4的32比特增加到128比特，使IP路由查找更加困难。
本文介绍了一个支持高速查找和快速增量更新的的IPv6路由查找算法TrieC，以及算法基于多核多线程体系结构IntelIXP2800网络处理器(NetworkProcessorUnit，NPU)上的高效实现。
TrieC算法利用改进的压缩前缀扩展(ModifiedCompactPrefixExpansion，MCPE)技术构造固定高度为5的IPv6TrieC查找树，在减少搜索次数提高查找性能的同时，消除了由传统前缀扩展引入的冗余信息存储。通过仔细研究分析算法设计和实现之间的关系，TrieC将网络处理器的体系结构特征融入了算法设计之中。
根据IPv4地址前缀分布特征、IPv6地址分配特点和现有IPv6路由表的统计特性，本文采用了三组不同前缀分布特征、每组各包含200K、300K和400K三个不同规模的共计九个IPv6路由表，对TrieC算法在IXP2800网络处理器上进行了性能模拟。实验表明TrieC算法可以在IntelIXP2800网络处理器上支持OC-192线速的IPv6路由查找，此外算法接近线性的加速比表明TrieC还可以获得更高的查找速度。
基于多核多线程体系结构的NPU编程是一项具有挑战性的工作，本文通过研究并行算法设计和体系结构映射之间的关系，在网络处理器上高效地实现了TrieC算法。本文详细讨论了在这种多核多线程体系结构上设计实现网络处理程序和算法的六个关键问题：内存空间压缩、指令选择、数据分配、任务切分、长延迟隐藏和线程同步，并以TrieC算法实现为例提供了在网络处理器上设计高性能算法和应用程序、有效开发NPU体系结构特性以克服算法实现中的性能瓶颈、以及在多核多线程体系结构上开发线程级并行性(ThreadLevelParallelism,TLP)的一些指导方法。虽然这些指导方法基于IntelIXP2800NPU，但是这些方法同样适用于其它类似的NPU。