[發明專利]鍵值分組方法

在審

• 申請號: 201210187221.5
• 申請日: 2012-06-08
• 公開（公告）號: CN103473237A
• 公開（公告）日: 2013-12-25
• 發明（設計）人: 林彥竹;張建杰;熊冰
• 申請（專利權）人: 蘇州雄立科技有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京市振邦律師事務所 11389
• 代理人: 何自力

技術領域

本發明屬于網絡技術領域，特別是涉及一種網絡查找中的鍵值分組方法。

背景技術

現有的基于查找引擎(例如TCAM)的網絡查找中，對于查找引擎里存儲規則中的重復出現部分，一直缺乏有效的方法實現對重復出現部分的復用，以節省查找引擎的存儲空間。另外，對于網絡中所要實現的超長表項的查找，也同樣缺乏有效的對超長表項的分解，以完成超長表項的查找。

在網絡處理器(交換機，路由器等對數據報文進行處理的設備)對報文處理的過程中，需要用查找引擎以完成各種查找，查找引擎會返回查找到的規則表項地址以讀取關聯數據或者直接返回關聯數據，然后網絡處理器會根據返回的關聯數據決定對該數據包文如何處理。

在查找引擎所存儲的規則表項中，存在著多個規則表項同時都包含了同樣的部分，如果不對該部分數據進行復用，查找引擎里要花費很大的空間以完成對這些表項的存儲，特別是隨著ipv6地址逐步取代ipv4地址，這個問題越來越突出。

另外，對于超長的表項查找，目前也缺乏有效的表項拆分手段以完成拆分表項查找結果的合并。

如果規則表項中所重復的部分是完全精確匹配(要查找的)的，目前已有技術方案可以對該問題提供方法(Netlogic公司所申請的一項美國專利，專利號：US7,694,068?B1，專利名稱：RE-ENTRANT?PROCESSING?IN?A?CONTENT?ADDRESSABLE?MEMORY)，該專利本來的目的是為了節省網絡處理器與查找引擎之間的帶寬，但客觀上也可用來提供精確匹配重復部分的重復利用。根據該專利所提供的方法，可以對表項進行拆分，然后先對表項的重復出現部分進行查找，再將查找返回的結果與后面要查找的部分重新組成一個新的表項以完成后續的查找。這樣查找引擎里只需要存儲一次該重復部分，就可以代表所有含有該重復部分的表項。另外，對于超長查找表項中的重復出現部分，如果所重復部分是完全精確匹配的，也可以通過2次或多次查找完成。

現有技術只能完成對重復部分為精確匹配的重復部分表項共享，否則對重復部分的查找會遇到多重匹配的問題，例如：將規則A拆分為{a0，a1}，規則B拆分為{a0，b1}，規則C拆分為{c0，c1}，其中規則A和規則B中的a0部分復用，如果在進行表項查找的時候a0，c0同時與查找鍵值的相應部分匹配(由于a0，c0不為精確匹配，因此可能發生多重匹配)，則初始查找到的結果為兩個，無法只將一個結果返回以完成后續查找。這樣就無法完成查找引擎存儲空間上的節省。

同樣地，對于超長表項的拆分仍然會遇到多重匹配從而無法完成后續查找的問題。

發明內容

為了至少解決上述問題之一，本發明提出了一種查找引擎的把規則拆分后的鍵值分組方法，包括以下步驟：

首先，將查找引擎從物理上劃分為不同的查找單元，在查找引擎進行查找的時候，每個查找單元都可以獨立的輸出匹配優先級最高的規則；

其次，在將查找規則拆分成的鍵值寫入搜索引擎時，將互相之間會發生多重匹配的拆分鍵值寫入不同的查找單元中，這樣在查找時即使發生了多重匹配，各個查找單元仍然可以保留這些發生了多重匹配的各個結果；

最后，將保留的這些結果與其他拆分鍵值匹配的結果進行合并及優先級比較。

優選地，查找單元所存放的數據包括數據段，掩碼段，起始標志位，組編號和后續標志位，其中所述數據段和掩碼段共同表示被拆分后的鍵值，起始標志位用于標示該鍵值是否為起始鍵值，組編號用于標示鍵值之間的關聯，相同的組編號表示這兩條鍵值的關聯，后續標志位用于標示該鍵值是否有后續鍵值。

優選地，查找單元所存放的數據包括數據段，掩碼段，起始段和結束段，其中所述數據段和掩碼段共同表示被拆分后的鍵值，所述起始段為0時表示該段鍵值為起始鍵值，所述結束段為0時表示該段鍵值為結束鍵值，當每個鍵值的起始段與上一鍵值的結束段相等表示他們屬于同一條規則拆分后的鍵值。

附圖說明

本發明的上述和/或附加的方面和優點從結合下面附圖對實施例的描述中將變得明顯和容易理解。

圖1本發明實施例的查找規則拆分示意圖；

圖2本發明實施例的鍵值匹配電路示意圖；

圖3本發明實施例的一種寫入查找單元的數據格式示意圖；

圖4本發明實施例的利用圖3的數據格式對拆分鍵值編組的關聯示意圖；

圖5本發明實施例的另一種寫入查找單元的數據格式示意圖；

圖6本發明實施例的利用圖5的數據格式對拆分鍵值編組的關聯示意圖；