[發明專利]一種基于Hash查找CAM的方法

有效

• 申請號: 201110276822.9
• 申請日: 2011-09-19
• 公開（公告）號: CN102364463A
• 公開（公告）日: 2012-02-29
• 發明（設計）人: 周恒釗
• 申請（專利權）人: 浪潮電子信息產業股份有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

?

技術領域

本發明涉及通信、高速網絡下的數據查找匹配或芯片設計技術領域,?具體地說是一種基于Hash查找CAM的方法。

背景技術

隨著通信技術的快速發展，一方面，在網絡中傳輸的數據帶寬越來越大。另一方面，?網絡中各種各樣的應用不斷變化和發展，現在的IP網絡需要為用戶提供更多服務類型和更???好的服務質量，要求路由器提供額外的處理機制來實現區分服務，報文分類，安全入侵監測，???防火墻訪問控制，虛擬專用網，快速路由查找，網絡地址轉化，等一些網絡關鍵技術。

為了適應網絡的數據流量越來越大的發展趨勢，保證網絡鏈路的通暢性，對路由器性能?提出了新的挑戰——如何快速路由。網絡技術的發展，這些關鍵網絡技術都涉及查找匹配問??題，而基于軟件的查找匹配效率低下，傳統的軟件實現的方法對于高速網絡的發展顯的力不?從心。

CAM芯片的快速查找匹配特性，使得CAM在網絡中得到廣泛的應用。CAM芯片的快速查???找匹配的特點，為網絡中很多關鍵的應用提供了新的解決方案?？梢杂肅AM來實現快速路由??查找，報文分類，區分服務，入侵監測等需要快速查找匹配的關鍵技術。

發明內容

本發明的目的是提供一種基于Hash查找CAM的方法。

本發明的目的是按以下方式實現的，本發明的通過Hash查找匹配原理，將其邏輯用硬件電路描述，待查數據寫入存儲體，?兩結構組合成為內容可尋址存儲體（Content?Addressable?Memory）。設計分為以下幾個功?能模塊：

1)總線；2)Hash函數查找表；3)Hash入口表；4)數據存儲體；5)匹配電路；6)RAM控制電路，其中：

總線1）是CAM與外部通信的通道。在CAM中總線分為請求總線和響應總線。請求總線是一條雙向多路復用總線，請求總線由命令總線和請求數據總線組成。命令總線處理輸入命令，請求總線是主要數據通道。所有對CAM的操作命令信號，還有輸入到CAM中的數據信號都通過請求總線進行傳輸。

?Hash函數查找表2）通過查找表的方式對Hash查找函數邏輯進行實現，哈希查找步驟為：設哈希表為HST[0~M-1]，哈希函數取H（key），解決沖突的方法為R（x）；第一步對給定k值，計算哈希地址?Di=H（k）；若HST為空，則查找失??；若HST=k，則查找成功；否則，執行第二步（處理沖突）。第二步重復計算處理沖突的下一個存儲地址?Dk=R（Dk-1），直到HST[Dk]為空，或HST[Dk]=k為止。若HST[Dk]=K，則查找成功，否則查找失敗。根據選擇的沖突處理方法，計算關鍵字key的下一個存儲地址。若下一個存儲地址仍被占用，則繼續執行第二步，直到找到能用的存儲地址為止。

Hash入口表3）中存放Key值經過Hash函數計算后的Hash_Key以及與之對應的數據表項入口值。

數據存儲體4）作為待查找的數據存放區，根據系統的數據格式確定該存儲體的數據寬度和數據深度，通過Hash_Key查找到對應于數據存儲體的地址后，系統通過RAM控制電路6）對該存儲體進行訪存，讀取數據表項中的數據。

讀取出表項中的數據后，通過匹配電路5）將待尋址的內容與表項數據進行比對，若匹配，則輸出匹配地址，拉高數據匹配標志。

查找程序流程如下：

1．根據輸入的查找數據進行hash計算得到Hash?key，用Hash?key去訪問Hash入口表。如果Hash入口表的內容為0，則跳到3；如果Hash入口表的內容不為0，則跳到2；

2．根據Hash入口表的內容，去訪問CAM數據項鏈表，并把查找數據同CAM數據項鏈表的數據一個一個比較(從鏈表頭到鏈表尾)。從鏈表頭開始比較，查找不成功，接著查找鏈表的下一項，直到鏈表尾為止，跳到3；查找成功(查找數據的值同CAM數據項鏈表中一項的值相同)則記錄下此項CAM地址，接著查找鏈表的下一項，如果也成功則比較CAM地址與此前記錄的CAM地址的大小，最終取CAM地址最小者，這樣查找一直到鏈表尾為止，跳到3；

3．查找成功，返回CAM地址和CAM命中的信息，跳到4；查找不成功，返回查找結束，返回CAM沒有命中的信息，跳到4；

4．操作結束，返回。

本發明的有益效果是：基于Hash查找算法的高效性，可快速查找出匹配數據，減小了數據查找時的比較次數，只需要一次即能找出數據，提高了查找效率，節約了系統時間，提高了數據通信的吞吐率。

附圖說明