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

PMST:a balanced bidirectional pipeline architecture to highperformance IP lookup

作　　者：李彦彪[1] 张大方[1] 黄昆[2] 何大成[1] 曾彬 

机构地区：[1]湖南大学信息科学与工程学院,长沙410082 [2]中国科学院计算技术研究所,北京100190 [3]中国移动通信集团湖南公司,长沙410015

出　　处：《中国科学：信息科学》2015年第7期934-952,共19页Scientia Sinica(Informationis)

基　　金：国家重点基础研究发展计划(973计划)(批准号:2012CB315805);国家自然科学基金(批准号:61173167;61100171);湖南省研究生科研创新项目(批准号:CX2014B150)资助

摘　　要：随着网络技术的高速发展及网络应用的日趋多样化，作为路由器的一项核心技术，IP查找在吞吐率、存储效率以及更新性能等诸多方面都面临着严峻的挑战．流水线技术的引入，使IP查找的吞吐率获得了显著提升．但是，不平衡的结构不仅会导致低存储效率和高更新开销，对查找性能以及多流水架构的负载均衡也会产生一定的影响．而目前针对流水线进行平衡优化的工作，又会带来一些不容忽视的新问题，制约了其在IPv6或者大规模数据集下的应用．鉴于此，本文提出了一种双向平衡的线性流水线结构流水化的多步长拆分特里树（pipelined multi-bit split Trie，PMST）．通过拆分前缀，旋转子树以及一系列平衡优化，PMST仅需要很少的流水级就能获得理想的平衡度．同时还能实现综合性能的提升．我们采用真实路由器中的IPv4／IPv6数据集以及按一定规则产生的大规模IPv6数据集对PMST进行了全面的实验评估．结果表明，与现有优秀成果相比，PMST在获得同等理想的平衡度时对流水级的需求下降了75％-85．7％．同时，在流水线延时、单次查找的平均访存、片上存储效率、更新开销以及多流水架构的负载均衡等方面PMST都表现出明显的优势．因此，PMST具有更高的综合性能和良好的可扩展性，能更好地适应目前和未来的应用需求．With the rapid development of network technology and the growing diversity of network applications, IP lookup, as a core function of routers, has been confronted with serious challenges, ranging from throughput, memory efficiency and update performance. Benefiting from the pipeline technology, the throughput of IP lookup has been improved significantly. However, unbalanced structure will not only lead to low memory efficiency and high update overhead, but also influence the lookup performance and the load balance of multi-pipeline architec- tures. While existing solutions to balance optimizing would bring some indispensable new problems, impending their applications in IPv6 or large-scale routing tables. In view of this, this paper proposes a balanced bidirectional pipeline architecture--pipelined multi-bit split tree （PMST）. After splitting prefixes, reversing a sub-tree and a series of optimizations, PMST can achieve a desirable balance degree at the cost of only a few stages. What is more, PMST also realizes significant improvements on comprehensive performance. Large IPv6 routing data sets generated in some manner, as well as real-world IPv4/v6 routing data sets, are used to evaluate the performance of PMST comprehensively. According to the experimental results, when achieving a desirable balance degree, the number of stages cost in PMST decreases by 75% - 85.7% in comparison to existing solutions. Meanwhile, the superiorities of PMST on pipeline latency, average memory accesses per lookup, on-chip memory efficiency, update overhead and the load balance of multi-pipeline architecture are also significant. Therefore, PMST has higher comprehensive performance and better scalability, which can better meet current and future demands.

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

分 类 号：TN915.05[电子电信—通信与信息系统]