[發明專利]分布式ipv6路由查找方法和系統

有效

• 申請號: 201610829157.4
• 申請日: 2016-09-18
• 公開（公告）號: CN106656816B
• 公開（公告）日: 2019-09-24
• 發明（設計）人: 陳文龍;唐曉嵐;張沛;張銘書
• 申請（專利權）人: 首都師范大學
• 主分類號: H04L12/743
• 分類號: H04L12/743
• 代理公司: 北京清亦華知識產權代理事務所(普通合伙) 11201
• 代理人: 張大威

本發明公開了分布式ipv6路由查找方法和系統，該方法包括：構建前綴長度為32位和前綴長度為48位的多分支Trie樹；將所有前綴長度除了32位與48位的路由項以前綴長度劃分，并建立哈希表；當添加路由項時，判定添加路由項的前綴長度是否為32或48，若是，則將添加路由項添加到多分支Trie樹中的對應位置，若不是，則添加到哈希表中；當轉發報文時，根據報文分別在多分支Trie樹和哈希表中匹配結果轉發報文。本發明具有如下優點：將前綴長度為32位和48位的路由占的總數較大，使用多分支Trie樹極大的提高了查找速度；其它前綴長度的路由長度分布廣、總數較少，用基于前綴長度的算法實現查找，能極大地提高查找速度。

技術領域

本發明涉及互聯網路由路由技術領域，具體涉及一種分布式ipv6路由查找方法和系統。

背景技術

現有技術中，針對前16位種類少，且多以0x2001開頭，通過多層次，多階段逐步解決ipv6存儲空間過大的問題。例如在TSB中，將二叉樹、段表和路由桶技術相結合,提出一種多階段ipv6路由表查找算法。但由于ipv6的飛速發展，現有主干網中路由項數成指數增長，前16位分布變的廣泛，使得不僅僅只有0x2001需要段表，主干網中路由項數量的快速增長還使得路由桶技術不能適用，且ipv6存儲方案空間需求過大，查找時間過長。

發明內容

本發明旨在至少解決上述技術問題之一。

為此，本發明的一個目的在于提出一種分布式ipv6路由查找方法，以解決現有ipv6存儲方案空間需求過大，查找時間過長的問題。

為了實現上述目的，本發明的實施例公開了一種分布式ipv6路由查找方法，包括以下步驟：S110：構建前綴長度為32位和前綴長度為48位的多分支Trie樹；S120：將路由器中所有前綴長度除了32位與48位的路由項以前綴長度劃分，并建立哈希表；S130：當添加路由項時，判定所述添加路由項的前綴長度是否為32或48，若是，則將所述添加路由項添加到所述多分支Trie樹中的對應位置，若不是，則添加到所述哈希表中；S140：當轉發報文時，根據所述報文分別在所述多分支Trie樹和所述哈希表中匹配結果轉發報文。

根據本發明實施例的分布式ipv6路由查找方法，將前綴長度為32位和48位的路由占的總數較大，故使用多分支Trie樹，極大的提高了查找速度；其它前綴長度的路由長度分布廣，但總數較少，用基于前綴長度的算法實現查找，能極大地提高查找速度。

另外，根據本發明上述實施例的分布式ipv6路由查找方法，還可以具有如下附加的技術特征：

進一步地，所述步驟S140進一步包括：S141：當轉發報文時，從所述多分支Trie樹查找是否有匹配的路由項，若匹配，則記錄第一匹配路由項和第一匹配路由項的前綴長度；若沒有匹配的路由項，則進入步驟S142；S142：在所述哈希表中進行查找，若匹配，則記錄第二匹配路由項和第二匹配路由項的前綴長度；S143：如果所述報文在所述多分支Trie樹和所述哈希表中均無匹配項，則丟且所述報文；如果所述報文存在所述第一匹配路由項或所述第二匹配路由項，則以所述第一匹配路由項或所述第二匹配路由項轉發所述報文；如果所述報文存在所述第一匹配路由項和所述第二匹配路由項，則當第一匹配路由項的前綴長度大于第二匹配路由項的前綴長度時，以所述第一匹配路由項轉發所述報文；則當第一匹配路由項的前綴長度小于第二匹配路由項的前綴長度時，以所述第二匹配路由項轉發所述報文。

進一步地，使用二分查找法從所述哈希表中查找匹配項。

進一步地，在步驟S142中，所述哈希表中查找路由項的前綴長度為16位至64位。

為此，本發明的一個目的在于提出一種分布式ipv6路由查系統，以解決現有ipv6存儲方案空間需求過大，查找時間過長的問題。