路由驗證和路由查找是實現(xiàn)安全路由和高效轉(zhuǎn)發(fā)的關(guān)鍵技術(shù)，隨著網(wǎng)絡(luò)規(guī)模和網(wǎng)絡(luò)流量的持續(xù)增長以及大范圍路由異常事件的頻發(fā)，路由查找和路由驗證均面臨嚴(yán)峻的性能挑戰(zhàn)。我中心前瞻實驗室團(tuán)隊圍繞上述挑戰(zhàn)開展深入研究，提出一系列創(chuàng)新算法與機(jī)制，部分算法已在實際系統(tǒng)部署應(yīng)用。近日，相關(guān)的三篇論文分別被計算機(jī)網(wǎng)絡(luò)與系統(tǒng)領(lǐng)域的國際會議USENIX NSDI ?(CCF A) 2025、IEEE?INFOCOM?(CCF A) 2025和國際期刊IEEE/ACM Transactions on Networking?(CCF A) 錄用。
針對BGP路由驗證的性能挑戰(zhàn)，前瞻實驗室團(tuán)隊通過深入建模分析指出現(xiàn)有方案的性能瓶頸源自底層的塊驗證模型，然后提出一種新型的授權(quán)前綴驗證模型從根本上突破性能瓶頸，并基于該模型設(shè)計了一種基于樹比特位圖的高效路由起源驗證算法h2ROV，大幅提升驗證速度并有效降低存儲開銷。算法實驗結(jié)果表明，相比于業(yè)界最優(yōu)算法，h2ROV在IPv4場景下驗證速度提高了1.4倍，內(nèi)存開銷減少了69.9%。系統(tǒng)驗證結(jié)果表明，h2ROV對于路由消息處理流程的影響減少10.4% ～ 61.4%，對于BGP全網(wǎng)收斂時間的影響降低2.2% ～ 16.3%。相關(guān)研究成果被USENIX NSDI 2025錄用。
h2ROV基本原理與核心數(shù)據(jù)結(jié)構(gòu)
針對SDN流表查找的性能挑戰(zhàn)，前瞻實驗室團(tuán)隊聯(lián)合華為算法專家深入分析多維規(guī)則的內(nèi)在關(guān)聯(lián)，提出一種哈希元組劃分合并算法BTP，平衡各元組之間以及元組內(nèi)部哈希表內(nèi)的負(fù)載，有效減少哈希元組數(shù)以及規(guī)則合并引發(fā)的哈希沖突，從而提高查找與更新性能。實驗效果表明，相比經(jīng)典算法PSTSS和最新方法DT、TupleTree，BTP的查找性能分別可提高16.5倍,2.2倍,3.3倍。這一研究成果被IEEE?INFOCOM?2025 錄用。
BTP的工作原理
針對IPv6路由查找的性能挑戰(zhàn)，前瞻實驗室團(tuán)隊聯(lián)合華為算法專家通過分析不同網(wǎng)絡(luò)場景下IPv6規(guī)則的分布特點，提出一種基于啟發(fā)式二分搜索的高性能IPv6路由查找的方法HBS，并在此基礎(chǔ)上提出一種樹旋轉(zhuǎn)機(jī)制可針對IPv6前綴分布特點動態(tài)調(diào)整樹形，實現(xiàn)不同網(wǎng)絡(luò)場景下的自適應(yīng)高性能路由查找。實驗效果表明，相比經(jīng)典算法SBS、Tree Bitmap以及最新方法SAIL、Poptrie，HBS的查找性能最高可提升17.5倍、15.5倍、26.6倍和30.2倍。這一研究成果被IEEE/ACM Transactions on Networking錄用。
HBS基本原理
?樹旋轉(zhuǎn)方法基本原理
相關(guān)成果：
????[1]?Zedong Ni#, Yinbo Xu#, Hui Zou, Yanbiao Li*, Guang Cheng, and Gaogang Xie, “Improving RPKI Efficiency: h2ROV for Accelerating Validation Performance and Reducing Memory Overhead” to appear in the 22nd 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 44th IEEE International Conference on Computer Communications (INFOCOM' 25).
????[3]?Donghong Jiang, Yanbiao Li*, Yuxuan Chen, Jin Hu, Yi Huang and Gaogang Xie*, "Heuristic Binary Search: Adaptive and Fast IPv6 Route Lookup With Incremental Prefix Updates," in IEEE/ACM Transactions on Networking, doi: 10.1109/TNET.2024.3504244.