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

有效

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

本發明的各實施例涉及網絡交換機設備中的準確匹配哈希查找數據庫。在一種用于在網絡設備中轉發包的方法中，基于查找關鍵字生成多個哈希值。多個哈希值至少包括使用第一哈希函數生成的第一哈希值、使用第二哈希函數生成的第二哈希值和使用第三哈希函數生成的第三哈希值。第三哈希函數不同于第一哈希函數和第二哈希函數。使用第一哈希值和第二哈希值搜索查找表以確定用于查找關鍵字的偏移。然后，使用第三哈希值和為查找關鍵字確定的偏移搜索轉發表以選擇與查找關鍵字對應的轉發條目。基于選擇的轉發條目向網絡設備的一個或者多個端口轉發包。

相關申請的交叉引用

本申請要求對通過完全引用將其公開內容明確地結合于此、于 2013年4月4日提交、名稱為″Exact Match Hash Algorithm For Very Large Table in Switches″的第61/808，323號美國臨時申請的優先權。

技術領域

本公開內容總體上涉及網絡設備，并且更具體地涉及網絡設備中的哈希查找表。

背景技術

這里提供的背景描述是出于總體上呈現公開內容的背景的目的。當前具名的發明人的工作在背景技術這一節中描述的程度上以及該描述的可能在提交時未以其他方式符合現有技術的方面既未被明示地也未被暗示地承認為針對本公開內容的現有技術。

網絡設備(比如網絡交換機、路由器、邊緣設備等)經常運用如下查找表，這些查找表存儲與由網絡設備處理的包關聯的各種信息，并且網絡設備在查找表中執行查找以用于在網絡設備處理包期間做出各種處理判決。例如，可以執行查找操作以用于包分類、轉發判決、服務質量分類、策略控制列表應用和一般由網絡設備執行的其他處理操作。一般而言，根據與包關聯的或者為包生成的關鍵字執行對于包的查找。關鍵字例如被用來搜索表，并且從由表中的由關鍵字標識的條目取回與包相關的信息(例如，用于包的轉發信息)。

使用內容可尋址存儲器(CAM)來實施一些查找表。基于CAM 的表一般允許通常在單個比較循環中比較向表提供的關鍵字與表的所有條目，并且返回指示哪些條目與關鍵字匹配的結果。然而，尤其在運用大規模查找表時，基于CAM的表一般在面積和功率消耗方面成本高。

查找表的備選實現方式利用基于哈希的方案，在該方案中，將哈希函數應用于關鍵字以確定哈希表中的其中存儲關鍵字和與關鍵字關聯的信息(例如，轉發信息)的位置。盡管哈希表與CAM實現方式相比一般更小并且更高效，但是哈希表在哈希函數為向哈希函數提供的兩個或者更多不同關鍵字生成相同哈希值時表現固有沖突，并且作為結果，無法向哈希表中插入向哈希表提供的一些關鍵字。因此，即使關鍵字可以與條目匹配，對于向哈希表提供的一些關鍵字的查找操作仍然不會產生匹配。因此，難以在運用哈希表時實現準確匹配查找性能。

發明內容

在一個實施例中，一種用于在網絡設備中轉發包的方法包括在哈希值生成器并且基于與包對應的查找關鍵字生成多個哈希值，至少包括使用第一哈希函數生成第一哈希值、使用第二哈希函數生成第二哈希值和使用第三哈希函數生成第三哈希值，第三哈希函數不同于第一哈希函數和第二哈希函數。該方法也包括使用第一哈希值和第二哈希值搜索查找表以確定用于查找關鍵字的偏移，以及使用第三哈希值和為查找關鍵字確定的偏移搜索轉發表以選擇與查找關鍵字對應的轉發條目。該方法還包括基于選擇的轉發條目向網絡設備的一個或者多個端口轉發包。