[發明專利]網絡交換機設備中的準確匹配哈希查找數據庫的方法及裝置

有效

• 申請號: 201310394776.1
• 申請日: 2013-08-30
• 公開（公告）號: CN104104604B
• 公開（公告）日: 2018-10-02
• 發明（設計）人: C·阿拉德;G·利維
• 申請（專利權）人: 馬維爾以色列(M.I.S.L.)有限公司
• 主分類號: H04L12/741
• 分類號: H04L12/741;G06F17/30
• 代理公司: 北京市金杜律師事務所 11256
• 代理人: 酆迅;辛鳴

1.一種用于在網絡設備中轉發包的方法，所述方法包括：

在哈希值生成器并且基于與包對應的查找關鍵字生成多個哈希值，至少包括至少通過向所述查找關鍵字應用第一哈希函數而生成第一哈希值、至少通過向所述查找關鍵字應用第二哈希函數而生成第二哈希值和至少通過向所述查找關鍵字應用第三哈希函數而生成第三哈希值，所述第三哈希函數不同于所述第一哈希函數和所述第二哈希函數；

使用所述第一哈希值和所述第二哈希值來在查找表中選擇包括用于所述查找關鍵字的偏移的條目；以及

使用所述第三哈希值和用于所述查找關鍵字的所述偏移來在轉發表中選擇與所述查找關鍵字對應的轉發條目；以及

使用選擇的所述轉發條目向所述網絡設備的一個或者多個端口轉發所述包。

2.根據權利要求1所述的方法，其中使用所述第一哈希值和所述第二哈希值來在所述查找表中選擇條目包括：

使用所述第一哈希值來確定所述查找表中的具有對應條目的位置，其中與所述查找表中所確定的位置對應的所述條目包括與所述第一哈希值關聯的多個沖突桶，以及

用所述第二哈希值從與所述第一哈希值關聯的所述多個沖突桶選擇沖突桶以確定所述偏移。

3.根據權利要求1所述的方法，其中使用所述第一哈希值和所述第二哈希值來在所述查找表中選擇條目包括：

使用所述第一哈希值來確定所述查找表中的具有對應條目的位置，其中與所述查找表中所確定的位置對應的所述條目包括與所述第一哈希值關聯的多個沖突桶；

使用所述第二哈希值搜索所述多個沖突桶以嘗試標識所述多個沖突桶之中與所述第二哈希值關聯的沖突桶；以及

在標識與所述第二哈希值關聯的所述沖突桶時，選擇標識的所述沖突桶以確定所述偏移，以及

在未標識與所述第二哈希值關聯的沖突桶時，使用默認偏移作為所述偏移。

4.根據權利要求2所述的方法，其中所述多個沖突桶之中的沖突桶包括相應簽名字段和相應偏移字段，并且其中確定所述偏移包括：

比較所述第二哈希值與所述多個沖突桶之中的至少一些沖突桶的相應簽名字段，

在所述第二哈希值與所述沖突桶中的一個沖突桶的簽名字段的值匹配時，將所述偏移設置成所述一個沖突桶的所述偏移字段的值，以及

在所述第二哈希值不與所述多個沖突桶的所述簽名字段的任何值匹配時，將所述偏移設置成預定偏移值。

5.根據權利要求1所述的方法，其中使用所述第三哈希值和用于所述查找關鍵字的所述偏移來在所述轉發表中選擇所述轉發條目包括：

使用所確定的偏移和所述第三哈希值來確定索引，其中所述索引標識所述轉發表中與所述轉發條目對應的位置；以及

使用所述索引從所述轉發表中取回所述轉發條目。

6.根據權利要求1所述的方法，其中：

所述轉發表中的條目包括用于存儲相應關鍵字的相應關鍵字字段和用于存儲與所述相應關鍵字分別關聯的相應轉發信息的相應信息字段；

所述方法還包括比較選擇的所述轉發條目的所述關鍵字字段的值與所述查找關鍵字；以及

向所述網絡設備的所述端口轉發所述包：如果所述關鍵字字段的所述值與所述查找關鍵字匹配，則基于選擇的所述轉發條目的信息字段來轉發所述包。

7.根據權利要求6所述的方法，其中：

所述網絡設備包括用于存儲無法被向所述轉發表中插入的查找關鍵字的內容可尋址存儲器(CAM)表；

所述方法還包括如果所述關鍵字字段的所述值不與所述查找關鍵字匹配，則：

使用所述查找關鍵字以搜索所述CAM表；并且

向所述端口轉發所述包包括：

如果在所述CAM表中發現用于所述查找關鍵字的匹配，則基于所述CAM表條目轉發所述包，以及

如果在所述CAM表中未發現用于所述查找關鍵字的匹配，則向所述網絡設備的多個端口以泛洪方式傳送所述包。

8.根據權利要求1所述的方法，還包括：

經由所述網絡設備的所述一個或多個端口傳輸所述包。