高性能路由验证和路由查找研究获进展

路由验证和路由查找是实现安全路由和高效转发的关键技术。随着网络规模和网络流量的持续增长以及大范围路由异常事件频发，路由查找和路由验证面临严峻的性能挑战。中国科学院计算机网络信息中心前瞻实验室团队围绕上述挑战开展研究，提出一系列创新算法与机制，部分算法已在实际系统部署应用。

针对BGP路由验证的性能挑战，该团队通过深入建模分析提出现有方案的性能瓶颈源自底层的块验证模型，提出从根本上突破性能瓶颈的新型授权前缀验证模型，并基于这一模型设计了基于树比特位图的高效路由起源验证算法h²ROV。h²ROV能够提升验证速度并有效降低存储开销。算法实验结果显示，相比于业界最优算法，h²ROV在IPv4场景下验证速度提高了1.4倍，内存开销减少了69.9%。系统验证结果表明，h²ROV对于路由消息处理流程的影响减少10.4%~61.4%，对于BGP全网收敛时间的影响降低2.2%~16.3%。相关成果被USENIX NSDI 2025录用。

针对SDN流表查找的性能挑战，该团队联合华为算法专家深入分析多维规则的内在关联，提出哈希元组划分合并算法BTP，平衡各元组之间以及元组内部哈希表内的负载，有效减少哈希元组数以及规则合并引发的哈希冲突，从而提高查找与更新性能。实验效果显示，相比经典算法PSTSS和最新方法DT、TupleTree，BTP的查找性能可分别提高16.5倍、2.2倍、3.3倍。相关成果被IEEE INFOCOM 2025录用。

针对IPv6路由查找的性能挑战，该团队联合华为算法专家通过分析不同网络场景下IPv6规则的分布特点，提出基于启发式二分搜索的高性能IPv6路由查找的方法HBS，并在此基础上提出树旋转机制可针对IPv6前缀分布特点动态调整树形，实现不同网络场景下的自适应高性能路由查找。实验效果表明，相比经典算法SBS、Tree Bitmap以及最新方法SAIL、Poptrie，HBS的查找性能最高可提升17.5倍、15.5倍、26.6倍和30.2倍。相关成果被IEEE/ACM Transactions on Networking录用。

研究工作得到国家重点研发计划和国家自然科学基金的支持。

高性能路由验证和路由查找研究获进展