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

摘要

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