查找資料庫中顯性定義記錄表項優先級的方法
2023-12-07 21:51:41
專利名稱：查找資料庫中顯性定義記錄表項優先級的方法
技術領域：
本發明涉及資料庫查找和網絡通信技術領域，特別是涉及一種在查找資料庫中顯性定義記錄表項優先級的方法。
背景技術：
隨著網絡應用對網絡帶寬需求的不斷增加，特別是在線音頻、視頻節目的普及，IPV6的步步推廣，3G、4G手機網絡的發展，以及人們對網絡安全的需求，導致各種數據查找不斷增加，高速查找搜索晶片TCAM被廣泛地使用在數據查找，數據通信系統中。TCAM (Ternary Content Addressable Memory)即「三態內容尋址存儲器」是目前廣泛使用的查找晶片。TCAM中每個bit位有三種狀態，除掉「O」和「I」外，還有一個「don’tcare」狀態，所以稱為「三態」，它是通過掩碼來實現的。 由於固有的電路架構原因，TCAM查找晶片只能提供最長匹配查找(LPM，LongestPrefix Matching,精確匹配部分必須放置在don’t care部分之前)。TCAM需要保證前綴較長的記錄表項保存在前綴較短的記錄表項之前，即TCAM的低地址存貯前綴較長的記錄表項，高地址存儲前綴較短的記錄表項。TCAM這種電路架構隱性定義了各個記錄表項的優先級關係，即地址越高，優先級越低，記錄表項的存忙地址和記錄表項的優先級綁定；使得TCAM資料庫維護算法複雜，特別是記錄表項的添加和刪除部分。針對TCAM的資料庫維護更新算法，目前主要有下面幾種I、順序移動法所有前綴記錄按照長度組成前綴塊，按照前綴由長到短從TCAM的低地址空間開始順序排列，空閒記錄集中放在TCAM的高地址。當需要增加一個新記錄時，將已有記錄中長度小於該記錄的條目依次向後移動一個位置，然後將要新記錄添加到騰出的位置處。顯然，這種方式記錄移動關聯性太大，效率極低，最差的情況複雜度為O(N)，其中N是TCAM中保存的記錄個數。2、帶預留記錄的順序移動法相對於順序移動法，該算法的改進在於把空閒記錄分散到每個前綴記錄塊裡。若添加的記錄對應的集合存在空閒記錄時，直接寫入，其它記錄不須移動；當不存在空閒記錄時，只須從相鄰的記錄集合中借用一個空閒地址即可寫入。但是在刪除記錄時，要把該集合中刪除記錄以下的記錄都向上移動一個位置，以保持空閒記錄的連續性。該算法只是減少了平均表項移動次數，但在最壞情況下，如預置的空閒記錄出現連續滿狀態時，算法複雜度顯然仍是O (N)。3、選擇移動法結合TCAM工作原理分析，路由前綴查找只需要保證不同長度記錄的順序關係，而對於相同長度的記錄則可以不用嚴格要求，由此提出了選擇移動法，TCAM中記錄結構與順序移動法一致，在添加新記錄時，只需要將每個前綴塊的第一個記錄移到最後一個位置即可，表項的移動次數大大減少。該算法複雜度為O(W)，其中W為前綴塊的個數。
4、帶預留記錄的選擇移動法該算法將預留記錄的思想運用到選擇移動法。當需要添加新記錄時，如果預置空閒記錄非滿，直接寫入；若空閒記錄已滿，但相鄰前綴塊存在空閒地址，也直接寫人；否則，才按照選擇移動法的添加方式進行，直到騰出空閒地址寫入新記錄。刪除記錄操作跟預留記錄法的相同。因為只有在空閒記錄非空的情況下，才會有記錄選擇移動，使得該算法的平均移動次數進一步降低。不管上面哪種算法，複雜度都很高，可能需要移動記錄，佔用TCAM的查找時間，降低查找帶寬，從而降低系統性能，影響數據通信速度。
發明內容
為了解決上述方法中TCAM查找晶片中記錄表項地址和優先級綁定，資料庫更新維護複雜，佔用大量TCAM查找時間，降低TCAM的查找速度，從而降低整個系統查找速度，影響系統性能的問題，本發明提出了一種在查找資料庫中顯性定義記錄表項優先級的方法， 其特徵在於，包括以下步驟SI :系統劃分查找資料庫優先級，給每條記錄表項分配優先級標籤，每條記錄表項都分配一個優先級標籤，不同優先級用不同數字表示；S2 :系統把記錄表項和其優先級標籤一同提交給查找晶片；S3 :查找晶片把記錄表項和其優先級標籤貯存到內部存貯單元中。作為上述技術方案的優選，所述方法還包括以下步驟S4:系統執行鍵值查找時，系統提交鍵值及查找指令給查找晶片，查找晶片得到鍵值及查找指令；S5 :查找晶片啟動內部查找電路，對內部存貯單元的記錄表項並發查找；S6 :查找晶片把所有匹配記錄表項的優先級標籤發送給優先級比較電路；S7 :優先級標籤符合要求的記錄表項作為最終查找結果，返回給系統。本發明的在查找資料庫中顯性定義記錄表項優先級的方法，由於每條記錄表項都有獨立的優先級標籤，優先級和存貯地址分開，從而記錄表項可以隨意地存貯在查找晶片存忙單元中；記錄表項的「don』 t care」位可以處於記錄表項中任意位置,避免記錄表項的前綴排序問題。這些都極大地釋放了記錄表項維護算法需要的時間，提升了系統性能。
為了更清楚地說明本發明實施例或現有技術中的技術方案，下面將對實施例或現有技術描述中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附圖僅僅是本發明的一些實施例，對於本領域普通技術人員來講，在不付出創造性勞動性的前提下，還可以根據這些附圖獲得其他的附圖。圖I為本發明一個實施例的在查找資料庫中顯性定義記錄表項優先級的方法的流程示意圖；圖2為本發明另一個實施例的在查找資料庫中顯性定義記錄表項優先級的方法的流程示意圖；圖3為本發明實施例的顯性定義優先級標籤查找晶片邏輯示意圖。
具體實施例方式下面將結合本發明的附圖，對本發明的技術方案進行清楚、完整地描述，顯然，所描述的實施例僅僅是本發明一部分實施例，而不是全部的實施例。基於本發明中的實施例，本領域普通技術人員在沒有作出創造性勞動前提下所獲得的所有其他實施例，都屬於本發明保護的範圍。本發明的一個實施例的一種在查找資料庫中顯性定義記錄表項優先級的方法，如圖I所示，包括以下步驟SI :系統劃分查找資料庫優先級，給每條記錄表項分配優先級標籤，每條記錄表項都分配一個優先級標籤，不同優先級用不同數字表示；S2 :系統把記錄表項和其優先級標籤一同提交給查找晶片； S3 :查找晶片把記錄表項和其優先級標籤貯存到內部存貯單元中。在本發明的一個實施例中，如圖2所示，所述方法包括以下步驟SI :系統劃分查找資料庫優先級，給每條記錄表項分配優先級標籤，每條記錄表項都分配一個優先級標籤，不同優先級用不同數字表示；S2 :系統把記錄表項和其優先級標籤一同提交給查找晶片；S3 :查找晶片把記錄表項和其優先級標籤貯存到內部存貯單元中；S4:系統執行鍵值查找時，系統提交鍵值及查找指令給查找晶片，查找晶片得到鍵值及查找指令；S5 :查找晶片啟動內部查找電路，對內部存貯單元的記錄表項並發查找；S6 :查找晶片把所有匹配記錄表項的優先級標籤發送給優先級比較電路；S7 :優先級標籤符合要求的記錄表項作為最終查找結果，返回給系統。本發明上述實施例所述的方法的有益效果可以通過附圖3所示的顯性定義記錄表項優先級標籤的查找晶片結構示意圖來說明，(以16bit記錄表項數據，4bit優先級標籤為例，優先級數字不同代表不同優先級，本例中數字越小，優先級越高，優先級最高作為結果)Entry:記錄表項Key:查找鍵值Pri :優先級標籤Match Index :最終查找結果EntryO, Entryl都是16bit精確匹配數據;分別定義4bit優先級為「0000」，「0011」，存放在查找晶片任意地址；Entry M, Entry M+1 是 12bit 精確匹配,4bit don’t cares 數據；分別定義 4bit優先級為「0100」，「0101」，存放在查找晶片任意地址。記錄N,記錄N+1為8bit精確匹配，8bit don』 t care數據；分別定義4bit優先級為「 1001」，「1100」，存放在任意地址。當晶片啟動查找時，Key A會同時和所有Entry比較；其中Entryl,Entry M+1,Entry N都匹配,它們的優先級標籤Pri進入優先級比較電路；
最終，因為Entryl的優先級數字最小,優先級最高，Entryl成為匹配記錄.當有新的Entry L需要加入時，只需要給Entry L分配一個優先級，就可以把Entry L存放在任意空閒地址，不需要排序移動現在已經存儲的Entry,極大地減少了Entry更新時間。本發明上述實施例的在查找資料庫中顯性定義記錄表項優先級的方法，由於每條記錄表項都有獨立的優先級標籤，優先級和存貯地址分開，從而記錄表項可以隨意地存貯在查找晶片存忙單元中；記錄表項的「don』 t care」位可以處於記錄表項中任意位置,避免記錄表項的前綴排序問題。這些都極大地釋放了記錄表項維護算法需要的時間，提升系統性能。以上所述，僅為本發明的具體實施方式
，但本發明的保護範圍並不局限於此，任何熟悉本技術領域的技術人員在本發明揭露的技術範圍內，可輕易想到變化或替換，都應涵 蓋在本發明的保護範圍之內。因此，本發明的保護範圍應所述以權利要求的保護範圍為準。
權利要求
1.一種在查找資料庫中顯性定義記錄表項優先級的方法，其特徵在於，包括以下步驟 Si:系統劃分查找資料庫優先級，給每條記錄表項分配優先級標籤，每條記錄表項都分配一個優先級標籤，不同優先級用不同數字表示； 52:系統把記錄表項和其優先級標籤一同提交給查找晶片； 53:查找晶片把記錄表項和其優先級標籤貯存到內部存貯單元中。
2.如權利要求I所述的在查找資料庫中顯性定義記錄表項優先級的方法，其特徵在於，所述方法還包括以下步驟 S4:系統執行鍵值查找時，系統提交鍵值及查找指令給查找晶片，查找晶片得到鍵值及查找指令； 55:查找晶片啟動內部查找電路，對內部存貯單元的記錄表項並發查找； 56:查找晶片把所有匹配記錄表項的優先級標籤發送給優先級比較電路； 57:優先級標籤符合要求的記錄表項作為最終查找結果，返回給系統。
全文摘要
本發明提供了一種在查找資料庫中顯性定義記錄表項優先級的方法，包括以下步驟S1系統劃分查找資料庫優先級，給每條記錄表項分配優先級標籤，每條記錄表項都分配一個優先級標籤，不同優先級用不同數字表示；S2系統把記錄表項和其優先級標籤一同提交給查找晶片；S3查找晶片把記錄表項和其優先級標籤貯存到內部存貯單元中，由於每條記錄表項都有獨立的優先級標籤，從而記錄表項可以隨意地存貯在查找晶片存貯單元中，極大地釋放了記錄表項維護算法需要的時間，提升系統性能。
文檔編號G06F17/30GK102819617SQ20121033263
公開日2012年12月12日 申請日期2012年9月11日 優先權日2012年9月11日
發明者謝國敏 申請人:蘇州雄立科技有限公司