路由验证和路由查找是实现安全路由和高效转发的关键技术，随着网络规模和网络流量的持续增长以及大范围路由异常事件的频发，路由查找和路由验证均面临严峻的性能挑战。我中心前瞻实验室团队围绕上述挑战开展深入研究，提出一系列创新算法与机制，部分算法已在实际系统部署应用。近日，相关的三篇论文分别被计算机网络与系统领域的国际会议USENIX NSDI  (CCF A) 2025、IEEE INFOCOM (CCF A) 2025和国际期刊IEEE/ACM Transactions on Networking (CCF A) 录用。

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

h²ROV基本原理与核心数据结构

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

BTP的工作原理

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

HBS基本原理

 树旋转方法基本原理

相关成果：

    [1] Zedong Ni^#, Yinbo Xu^#, Hui Zou, Yanbiao Li*, Guang Cheng, and Gaogang Xie, “Improving RPKI Efficiency: h²ROV for Accelerating Validation Performance and Reducing Memory Overhead” to appear in the 22^nd USENIX Symposium on Networked Systems Design and Implementation (NSDI' 25) .

    [2] Neng Ren, Yanbiao Li*, Chunyang Zhang, Jin Hu, Linbo Guo, and Gaogang Xie*, “A Balanced Tuple P2artitioning Method for Packet Classification with High-Performance and Scalability” to appear in the 44^th IEEE International Conference on Computer Communications (INFOCOM' 25).