[發明專利]一種面向GPU加速IP查找的更新方法及系統

在審

• 申請號: 202011626256.5
• 申請日: 2020-12-30
• 公開（公告）號: CN112804153A
• 公開（公告）日: 2021-05-14
• 發明（設計）人: 李彥彪;謝高崗;姜東虹
• 申請（專利權）人: 中國科學院計算機網絡信息中心
• 主分類號: H04L12/741
• 分類號: H04L12/741;H04L29/12
• 代理公司: 北京億騰知識產權代理事務所(普通合伙) 11309
• 代理人: 陳霽

本發明涉及一種面向GPU加速IP查找的更新方法及系統，該方法包括：對于前綴刪除，查找目標前綴對應的節點，若該節點不存在或者不是一個前綴節點，則刪除結束；否則，刪除該節點保存的前綴信息，然后再消除該前綴對其他節點的影響；以及對于前綴插入，查找目標前綴對應的節點，如果目標前綴對應的節點存在則只需修改該節點的權值，然后從該節點開始葉推；如果目標前綴對應的節點不存在，就需要拆解原葉子線段構造新葉子線段；每拆解一個葉子線段，則構造出兩個新的葉子線段；不斷重復上述過程直到構造出目標前綴對應的線段；根據前綴刪除步驟或者前綴插入步驟的更新結果，將線索引化的葉子線段映射到GPU上執行。

技術領域

本發明涉及IP查找技術，特別涉及一種面向GPU加速IP查找的更新方法 及系統。

背景技術

IP查找是路由交換設備轉發數據包過程中的一項核心操作，其性能直接決 定了路由交換設備轉發數據包的吞吐率，進而影響整個網絡的通信效率。因此， 研究高性能IP查找引擎具有重要意義。隨著物理傳輸介質以及網絡接入技術 的發展，物理鏈路速度持續增長。通常來說，100Gbps的鏈路需要億次級查找 每秒的查找速度。但是，其他操作，比如路由更新導致的增、刪、改等操作， 也是在設計IP查找引擎的過程中一個非常關鍵的因素。因為這些操作也會與 查找操作競爭計算、存儲等資源，并因此影響查找的性能。尤其是在更新頻率 較高的場景，比如虛擬化路由器的多表更新聚合，OpenFlow的流表更新等，頻 繁的更新操作不僅會降低系統吞吐率，也會導致查找性能的不穩定。因此，對 于現代高性能IP查找引擎的設計，除了要追求查找速度之外，高效的更新機 制也是維持穩定高速查找不可或缺的。

隨著圖形處理單元(Graphic Processing Unit,GPU)發展成為一種通用 的高性能計算平臺，一些基于GPU加速的軟件路由器平臺陸續涌現出來，與此 同時也出現了一些基于GPU加速來對IP查找進行有針對性優化的算法，但這 些算法都缺乏一種高效的更新機制。原因是目前基于GPU加速的IP查找算法大 多是基于前綴樹的算法，而基于前綴樹算法的查找數據結構一般會維護一個存 儲著下一跳信息的連續數組，每次更新都會修改一片連續的數組區域，而多次 更新之間將要修改的數組區域可能產生重疊，從而導致不同更新之間會有部分 區域產生數據相關。這就給更新的完全并行化帶來一定的限制，導致更新操作 的并行不夠徹底，無法利用GPU強大的計算能力。另一方面，無法將更新完全 的并行化會制約算法在高頻更新的場景下的應用，以至于隨著更新頻率的增長， IP查找的速度會顯著下降。

發明內容

本發明的目的，在于解決現有基于GPU加速的IP查找算法無法將更新進行 完全并行化，從而導致更新速度不高甚至影響IP查找速度的問題。

為實現上述目的，一方面，本發明提供了一種面向GPU加速IP查找的更新 方法，該方法包括以下步驟：

對于前綴刪除，查找目標前綴對應的節點，若該節點不存在或者不是一個 前綴節點，則刪除結束；否則，刪除該節點保存的前綴信息，然后再消除該前 綴對其他節點的影響；以及

對于前綴插入，查找目標前綴對應的節點，如果目標前綴對應的節點存在 則只需修改該節點的權值，然后從該節點開始葉推；如果目標前綴對應的節點 不存在，就需要拆解原葉子線段構造新葉子線段；每拆解一個葉子線段，則構 造出兩個新的葉子線段；不斷重復上述過程直到構造出目標前綴對應的線段；

根據所述前綴刪除步驟或者前綴插入步驟的更新結果，將線索引化的葉子 線段映射到GPU上執行。

優選地，在所述前綴刪除步驟中，還包括對目標前綴節點控制域中的葉子 節點進行修改。

優選地，所述前綴節點是被刪前綴對應節點到根節點這條路徑上離被刪前 綴對應節點最近的那個前綴節點，如果存在這樣的前綴節點，就將其前綴信息 從被刪前綴節點開始葉推；否則，只需將被刪前綴影響的節點修改為無權值。