论文部分内容阅读
随着网络技术的高速发展及网络应用的曰趋多样化,作为路由器的一项核心技术,IP查找在吞吐率、存储效率以及更新性能等诸多方面都面临着严峻的挑战.流水线技术的引入,使IP查找的吞吐率获得了显著提升.但是,不平衡的结构不仅会导致低存储效率和高更新开销,对查找性能以及多流水架构的负载均衡也会产生一定的影响.而目前针对流水线进行平衡优化的工作,又会带来一些不容忽视的新问题,制约了其在IPv6或者大规模数据集下的应用.鉴于此,本文提出了一种双向平衡的线性流水线结构—流水化的多步长拆分特里树(pipelined mult,i-bit split Trie,PMST).通过拆分前缀,旋转子树以及一系列平衡优化,PMST仅需要很少的流水级就能获得理想的平衡度,同时还能实现综合性能的提升.我们采用真实路由器中的IPv4/IPv6数据集以及按一定规则产生的大规模IPv6数据集对PMST进行了全面的实验评估.结果表明,与现有优秀成果相比,PMST在获得同等理想的平衡度时对流水级的需求下降了75%~85.7%.同时,在流水线延时、单次查找的平均访存、片上存储效率、更新开销以及多流水架构的负载均衡等方面PMST都表现出明显的优势.因此,PMST具有更高的综合性能和良好的可扩展性,能更好地适应目前和未来的应用需求.
With the rapid development of network technology and the increasingly diversified network applications, as a core technology of routers, IP lookups face severe challenges in many aspects such as throughput, storage efficiency and update performance etc. With the introduction of pipeline technology, So that IP lookup throughput rate has been significantly improved.However, the unbalanced structure will not only lead to low storage efficiency and high update overhead, the search performance and multi-flow architecture load balancing will also have an impact.At present, for the pipeline The work of balance optimization will bring some new problems that can not be ignored and restrict its application in IPv6 or large-scale datasets. In view of this, this paper presents a bidirectional balanced linear pipeline architecture - Pipelined multitrip (PMST). By splitting the prefix, rotating the subtree, and a series of balancing optimizations, PMST achieves the desired balance with minimal pipeline stages, But also to achieve a comprehensive performance improvement.We use the real router in the IPv4 / IPv6 data set and according to certain rules generated large-scale IPv6 data set on the PMST The results show that compared with the existing excellent results, the PMST has a 75% -85.7% decrease in the pipeline level when obtaining the same ideal balance degree.At the same time, in the pipeline delay, the average of one-time lookup PMST has obvious advantages in memory access, on-chip storage efficiency, update overhead and load balancing of multi-stream architecture, etc. Therefore, PMST has higher comprehensive performance and good scalability, can better adapt to current and future Application requirements.