[發明專利]數據存儲方法、查找方法及裝置

有效

• 申請號: 201210048605.9
• 申請日: 2012-02-28
• 公開（公告）號: CN102622434A
• 公開（公告）日: 2012-08-01
• 發明（設計）人: 劉恒;楊俊杰
• 申請（專利權）人: 成都市華為賽門鐵克科技有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京同立鈞成知識產權代理有限公司 11205
• 代理人: 劉芳

1.一種數據存儲方法，其特征在于，包括：

獲取待存儲到TCAM的關鍵字，并獲取所述關鍵字的位寬；

從TCAM的所有標準位寬中，選擇與所述關鍵字的位寬的差值最小的標準位寬為第一標準位寬；

若所述第一標準位寬大于等于所述關鍵字的位寬，將所述關鍵字存儲到TCAM中存儲位寬等于所述第一標準位寬的空間中，獲取所述關鍵字的存儲地址，并將所述關鍵字的存儲地址作為所述關鍵字在TCAM中的索引值；

若所述第一標準位寬小于所述關鍵字的位寬，將所述關鍵字切割成兩個關鍵字，分別為第一關鍵字和第二關鍵字；將所述第一關鍵字存儲到TCAM中存儲位寬等于所述第一標準位寬的空間中，獲取所述第一關鍵字的存儲地址作為所述第一關鍵字在TCAM中的索引值，所述第一標準位寬等于所述第一關鍵字的位寬；將所述第二關鍵字存儲到TCAM中存儲位寬等于第二標準位寬的空間中，獲取所述第一關鍵字的存儲地址作為所述第二關鍵字在TCAM中的索引值，所述第二標準位寬大于等于所述第二關鍵字的位寬且與所述第二關鍵字的位寬的差值最小；通過將所述第一關鍵字在TCAM中的索引值和所述第二關鍵字在TCAM的中索引值進行組合變換獲得所述關鍵字在TCAM中的索引值，其中，所述組合變換使得所述關鍵字在TCAM中的索引值與其它關鍵字在TCAM的索引值不產生沖突；

將所述關鍵字對應的關聯數據存儲于存儲器中，所述關聯數據在所述存儲器中的存儲地址與所述關鍵字在TCAM的索引值對應，所述關聯數據中包含有所述關鍵字的報文的處理信息。

2.根據權利要求1所述方法，其特征在于，在所述從TCAM的所有標準位寬中，選擇與所述關鍵字的位寬的差值最小的標準位寬為第一標準位寬之后，還包括：

若所有標準位寬中有兩個標準位寬與所述關鍵字的位寬的差值相等且最小，選擇其中位寬小的標準位寬為第一標準位寬。

3.根據權利要求1或2所述方法，其特征在于，所述獲取所述關鍵字的位寬，還包括：

對所述關鍵字進行壓縮；

查找所述TCAM中是否已存在與壓縮后的所述關鍵字相同的關鍵字；

若TCAM中存在與壓縮后的所述關鍵字相同的關鍵字，將壓縮前的所述關鍵字的位寬確定為待存儲的所述關鍵字的位寬；

若TCAM中不存在與壓縮后的所述關鍵字相同的關鍵字，將壓縮后的所述關鍵字的位寬確定為待存儲的所述關鍵字的位寬。

4.一種數據查找方法，其特征在于，包括：

從報文中提取出待查找的關鍵字，并獲取所述關鍵字的位寬；

從TCAM的所有標準位寬中選擇與所述關鍵字的位寬的差值最小的標準位寬為第一標準位寬；

若所述第一標準位寬大于等于所述關鍵字的位寬，在TCAM中位寬等于第一標準位寬的空間中查找所述關鍵字，獲取所述關鍵字的存儲地址并將所述關鍵字的存儲地址作為所述關鍵字在TCAM中的索引值；

若所述第一標準位寬小于所述關鍵字的位寬，將所述關鍵字切割成兩個關鍵字，分別為第一關鍵字和第二關鍵字；在TCAM中位寬等于第一標準位寬的空間中查找所述第一關鍵字，并將所述第一關鍵字的存儲地址作為所述第一關鍵字在TCAM中的索引值；在TCAM中位寬等于第二標準位寬的空間中查找所述第二關鍵字，獲取所述第二關鍵字的存儲地址并將所述第二關鍵字的存儲地址作為所述第二關鍵字在TCAM中的索引值，其中，所述第一標準位寬等于所述第一關鍵字的位寬，所述第二標準位寬大于等于所述第二關鍵字的位寬且與所述第二關鍵字的位寬的差值最小；通過將所述第一關鍵字在TCAM中的索引值和所述第二關鍵字在TCAM的中索引值進行組合變換獲得所述關鍵字在TCAM中的索引值，其中，所述組合變換使得所述關鍵字在TCAM中的索引值與其它關鍵字在TCAM的索引值不產生沖突；

根據所述關鍵字在TCAM的索引值，確定與所述關鍵字對應的關聯數據在存儲器中的存儲地址，根據所述關聯數據在存儲器中的存儲地址讀取出所述關聯數據，所述關聯數據中包含有所述關鍵字的報文的處理信息。

5.根據權利要求4所述方法，其特征在于，在所述從TCAM的所有標準位寬中選擇與所述關鍵字的位寬的差值最小的標準位寬為第一標準位寬之后，還包括：

若所有標準位寬中有兩個標準位寬與所述關鍵字的位寬的差值相等且最小，選擇其中位寬小的標準位寬為第一標準位寬。