[發明專利]一種路由查找方法和路由器

有效

• 申請號: 201410009315.2
• 申請日: 2014-01-09
• 公開（公告）號: CN104780100B
• 公開（公告）日: 2019-06-04
• 發明（設計）人: 陸曉慶;沈曉峰
• 申請（專利權）人: 中興通訊股份有限公司
• 主分類號: H04L12/741
• 分類號: H04L12/741
• 代理公司: 北京安信方達知識產權代理有限公司 11262
• 代理人: 田紅娟;龍洪

本發明提出了一種路由查找方法和路由器，配置路由表和滑翔地址表；路由表至少包括一級滑翔多分支樹結構塊TRIEBLOCK，每一級滑翔TRIEBLOCK包括16個滑翔多分支樹結構TRIE成員，每一個滑翔TRIE成員包括滑翔TRIE類型、滑翔地址/滑翔地址索引、滑翔地址長度、路由索引和下一級TRIEBLOCK索引；滑翔地址表包括滑翔地址和對應的滑翔地址索引；該方法包括：在第k級滑翔TRIEBLOCK中，查找互聯網協議IP地址中第（4k?3）到4k位地址對應的滑翔TRIE成員；其中，k為大于等于1的整數；當查找到的滑翔TRIE成員的滑翔TRIE類型表示該滑翔TRIE成員無下一級滑翔TRIEBLOCK，且無滑翔地址信息，且查找到的滑翔TRIE成員的路由索引有效時，根據查找到的滑翔TRIE成員的路由索引獲取下一級路由信息。本發明能夠加快路由查找速度。

技術領域

本發明涉及互聯網協議(IP，Internet Protocol)通信領域，尤指一種路由查找方法和路由器。

背景技術

傳統的路由查找算法，主要分為硬件查找和軟件查找。硬件查找一般采用三態內容尋址存儲器(TCAM，Ternary Content Addressable Memory)進行查找，TCAM具有查找速度快、操作簡單的優點，但其成本高、功耗大、路由更新復雜。對于中低端路由器而言，實現成本較高，因此中低端路由器一般采用軟件查找方法，軟件查找方法主要有線性查找法、二叉樹查找法、哈希表查找法、多分支樹結構(TRIE)查找法等，例如，互聯網協議第6版(IPV6，Internet Protocol Version 6)地址的長度為128位，按照32位來劃分，可分為 4段。參見圖1，采用哈希表查找法和TRIE4查找法相結合進行路由查找的方法如下：

配置路由表使其包括哈希表項和對應的TRIE鏈，根據IPV6地址對應的掩碼的長度將哈希表項的哈希值分成4類，TRIE鏈最多包括8級多分支樹結構塊TRIEBLOCK，每一級TRIEBLOCK包括16個TRIE成員，每個TRIE 成員包括下一跳路由索引和下一級TRIEBLOCK索引。該方法包括：

步驟100、采用哈希算法計算IPV6地址的哈希值。當IPV6地址對應的掩碼的長度為1到32之間時，可以取其默認哈希值為0；當IPV6地址對應的掩碼的長度為33到64之間時，可以取IPV6地址的前32位地址做哈希計算；當IPV6地址對應的掩碼的長度為65到96之間時，可以取IPV6地址的前64位地址做哈希計算；當IPV6地址對應的掩碼的長度為97到128之間時，可以取IPV6地址的前96位地址做哈希計算。

步驟101、查找計算得到的哈希值對應的TRIE鏈，對于查找到的TRIE 鏈，逐級在TRIEBLOCK中查找IPV6地址對應的4位地址對應的下一跳路由索引和下一級TRIEBLOCK索引。當下一級TRIEBLOCK索引有效時，根據下一級TRIEBLOCK索引跳到下一級TRIEBLOCK，當下一級TRIEBLOCK 索引無效時，根據下一跳路由索引獲取路由信息。

現有的路由查找方法查找速度慢，占用內存大，在數據流較大時影響報文的轉發性能。

發明內容

為了解決上述問題，本發明提出了一種路由查找方法和路由器，能夠加快查找速度。

為了達到上述目的，本發明提出了一種路由查找方法，配置路由表和滑翔地址表；

所述路由表至少包括一級滑翔多分支樹結構塊TRIEBLOCK，每一級滑翔TRIEBLOCK包括16個滑翔多分支樹結構TRIE成員，每一個滑翔TRIE 成員包括滑翔TRIE類型、滑翔地址/滑翔地址索引、滑翔地址長度、路由索引和下一級TRIEBLOCK索引；所述滑翔地址表包括滑翔地址和對應的滑翔地址索引；

該方法包括：

在第k級滑翔TRIEBLOCK中，查找互聯網協議IP地址中第(4k-3)到 4k位地址對應的滑翔TRIE成員；其中，k為大于等于1的整數；