[發明專利]實現最長掩碼匹配的方法及裝置

無效

• 申請號: 201310544159.5
• 申請日: 2013-11-06
• 公開（公告）號: CN103581023A
• 公開（公告）日: 2014-02-12
• 發明（設計）人: 廖繼平;李占斌;何志川;孫偉
• 申請（專利權）人: 盛科網絡（蘇州）有限公司
• 主分類號: H04L12/743
• 分類號: H04L12/743;H04L12/745;H04L12/747
• 代理公司: 蘇州慧通知識產權代理事務所(普通合伙) 32239
• 代理人: 安紀平

技術領域

本發明涉及最長掩碼匹配算法領域，尤其是涉及一種將哈希表查找與TCAM表查找相結合實現最長掩碼匹配的方法及裝置。

背景技術

最長掩碼匹配(LPM)表示了在IP路由查找中普遍應用的原則，即精確匹配。LPM本身并沒有規定使用何種算法實現，所有實現了相同輸出結果的思想都可以認為是LPM。在路由查找過程中路由的條目常是以192.168.10.0/24或者192.168.10.0/32這樣的形式出現，/后表示的是該路由的掩碼，掩碼包含的是需要關心的內容，未包含的是無需關心的內容，掩碼越大路由越精確，在IP相同但是掩碼長度不同的情況下選取路由掩碼更長的條目。上例中如果報文的目的IP地址是192.168.10.0時應該選取/32掩碼的路由條目，如果報文的目的IP地址是192.168.10.10時則只能選取/24掩碼的路由條目了(因為/24的條目最后8位不關心)。

目前的交換機通用方式是使用三態內容尋址存儲器(TCAM)來實現LPM，TCAM的表項始終是按照一個順序，從上往下查詢并逐條匹配，如果匹配成功就立刻停止查詢。如果TCAM表中，只有一條表項是匹配的，那就只能是一個結果；如果存在多條表項匹配，那就只能是優先級高的匹配成功，而優先級低的就不會被匹配了。于是只要將IP掩碼大的放在TCAM表項的上部，就能保證LPM。但是由于TCAM占用面積大，能耗高，價格昂貴，所以在交換機中都盡量避免或減少TCAM的使用。

現有的交換機及路由器在存儲和讀取數據時，也普遍采用哈希算法，同樣可以實現最長掩碼匹配。哈希算法一種高效的查找算法，是將一組關鍵詞(或者叫鍵值)，通過哈希函數映射到一個連續的空間上，而這個連續的空間則被稱之為哈希表，其中該一組關鍵詞包括至少一個關鍵詞。一般的哈希算法包含三個要素：關鍵詞key、哈希函數hash_function和位置position。key是指需要確定位置的關鍵詞，通過采用哈希函數對key進行哈希算法獲得存儲位置position信息，上述三者之間的關系可以簡單的表示如下：Potion＝hash_function(key)。但是由于哈希算法較TCAM表查找的方式，在軟件復雜度上大幅度提高，同時還導致芯片的讀寫次數大量增加，從而無法實現芯片高速轉發的要求。

發明內容

本發明的目的在于克服現有技術的缺陷，提供一種實現最長掩碼匹配的方法及裝置，將TCAM表與哈希表相結合，實現對目的IP地址快速準確地查找。

為實現上述目的，本發明提出如下技術方案：一種實現最長掩碼匹配的方法，將需查詢的目的IP地址首先在TCAM表中查找匹配，若匹配到第一中間信息或同時匹配得到第一中間信息和第一最終結果，則將所述目的IP地址在第一級哈希表中繼續查找匹配，若匹配得到第二中間信息或同時得到第二中間信息和第二最終結果，則將所述目的IP地址在第二級哈希表中進行最后的查找匹配。

優選地，將IP地址的前兩個字節劃分為第一部分，后兩個字節分別劃分為第二部分和第三部分，所述第一部分、第二部分和第三部分分別存放在所述TCAM表、第一級哈希表和第二級哈希表中。

所述目的IP地址的前兩個字節在所述TCAM表中進行查找匹配，后兩個字節分別在所述第一級哈希表和第二級哈希表中進行查找。

所述目的IP地址的前兩個字節在所述TCAM表中進行查找匹配后，若未匹配到，則將所述目的IP地址丟棄；若匹配僅得到第一最終結果，則將所述第一最終結果丟棄或直接轉發出去。

所述目的IP地址在第一級哈希表中進行查找后，若未匹配到，則將所述第一最終結果轉發出去或丟棄；若匹配僅得到第二最終結果，則將所述第二最終結果丟棄或直接轉發出去。

所述目的IP地址的最后一個字節在所述第二級哈希表中查找后，若未匹配到，則將所述第二最終結果丟棄或直接轉發出去；若匹配到第三最終結果，則將所述第三最終結果丟棄或直接轉發出去。

本發明還揭示了一種實現最長掩碼匹配的裝置，包括第一匹配裝置、第二匹配裝置和第三匹配裝置，所述第一匹配裝置中設置TCAM表，所述第二匹配裝置和第三匹配裝置中分別設置有第一哈希表和第二哈希表，所述TCAM表、第一哈希表和第二哈希表中存放復數個IP地址。

優選地，所述IP地址的前兩個字節存放在所述TCAM表中，所述IP地址的后兩個字節分別存放在所述第一哈希表和第二哈希表中。

本發明的有益效果是：本發明將TCAM表查找與哈希表查找相結合，在大幅度減少TCAM表使用量的同時，有效控制了軟件的復雜度及芯片的讀寫次數，滿足芯片高速轉發的需求。