PMST:一种面向高性能IP查找的双向平衡流水线结构

摘要：

随着网络技术的高速发展及网络应用的日趋多样化,作为路由器的一项核心技术,IP查找在吞吐率、存储效率以及更新性能等诸多方面都面临着严峻的挑战.流水线技术的引入,使IP查找的吞吐率获得了显著提升.但是,不平衡的结构不仅会导致低存储效率和高更新开销,对查找性能以及多流水架构的负载均衡也会产生一定的影响.而目前针对流水线进行平衡优化的工作,又会带来一些不容忽视的新问题,制约了其在IPv6或者大规模数据集下的应用.鉴于此,本文提出了一种双向平衡的线性流水线结构—流水化的多步长拆分特里树(pipelined multi-bit split Trie,PMST).通过拆分前缀,旋转子树以及一系列平衡优化,PMST仅需要很少的流水级就能获得理想的平衡度,同时还能实现综合性能的提升.我们采用真实路由器中的IPv4/IPv6数据集以及按一定规则产生的大规模IPv6数据集对PMST进行了全面的实验评估.结果表明,与现有优秀成果相比,PMST在获得同等理想的平衡度时对流水级的需求下降了75％～85.7％.同时,在流水线延时、单次查找的平均访存、片上存储效率、更新开销以及多流水架构的负载均衡等方面PMST都表现出明显的优势.因此,PMST具有更高的综合性能和良好的可扩展性,能更好地适应目前和未来的应用需求.

关键词：包转发、流水线、架构、算法、存储高效、平衡、特里树

所属期刊栏目：45

分类号：TP393;P435.2;TN432

资助基金：国家重点基础研究发展计划（973计划）;国家自然科学基金;国家自然科学基金;湖南省研究生科研创新项目

在线出版日期：2015-08-14（万方平台首次上网日期，不代表论文的发表时间）

页码：934-952