一種前綴匹配的方法、裝置和系統的製作方法
2023-06-03 00:49:51 3
專利名稱：一種前綴匹配的方法、裝置和系統的製作方法
技術領域：
本發明涉及通信技術領域，尤其涉及一種前綴匹配的方法、裝置和系統。
背景技術：
路由器在轉發IP報文時，需要根據IP報文的目的地址去查詢存儲於 TCAM(ternary content addres sable memory,三重內容可尋址存儲器)中的路由表，在 TCAM中存儲的路由表中，存儲的是IP位址的前若干位，即前綴；路由器在查詢路由表時採 用最長前綴匹配規則，即選擇與IP報文目的地址匹配位數最多的前綴所對應的埠進行 轉發。隨著網絡規模的擴大和IPv6 (Internet Protocol version 6，下一代網際網路協 議)的廣泛使用，路由器需要支持的IPv6前綴的數目越來越多。但發明人發現，在現有技 術中，對於IPv6前綴存儲存在浪費存儲空間，路由器成本較高的問題。
發明內容
一方面，本發明實施例提供了一種前綴匹配的方法，在一定程度上節約了存儲器 的空間，降低了路由器的成本。為達到上述目的，本發明實施例採用如下技術方案一種前綴匹配的方法，包括按照前綴長度是否超過設定的前綴長度閾值將前綴分別存放到不同的存儲區域 內；在所述不同的存儲區域內同時查詢匹配的前綴，並將各自的查詢結果發送給外部 比較電路；所述外部比較電路對所述查詢結果進行比較，得到最終匹配結果。一方面，本發明實施例提供了一種前綴匹配的裝置，在一定程度上節約了存儲器 的空間，降低了路由器的成本。為達到上述目的，本發明實施例採用如下技術方案一種前綴匹配的裝置，包括存儲模塊，用於存儲前綴，包含多個存儲區域；分配模塊，用於將前綴按照前綴長度是否超過前綴長度閾值分別存放到所述存儲 模塊的不同的存儲區域內；查詢模塊，用於在所述存儲模塊的不同的存儲區域內查詢匹配的前綴，並將查詢 結果發送給外部比較電路；外部比較電路，用於對所述查詢模塊的查詢結果進行比較，得到最終匹配結果。另一方面，本發明實施例提供了一種前綴匹配的系統，在一定程度上節約了存儲 器的空間，降低了路由器的成本。為達到上述目的，本發明實施例採用如下技術方案
一種前綴匹配的系統，包括所述第一存儲區域，用於存放長度超過前綴長度閾值的前綴；所述第二存儲區域，用於存放長度小於或等於前綴長度閾值的前綴；外部比較電路，用於接收在所述不同的存儲區域查詢的查詢結果，並進行比較，得 到最終匹配結果。本發明實施例基於IPv6前綴長短不一的特點，通過設定前綴長度閾值，按照前綴 長度的不同將前綴存放在不同的存儲區域內，較長的前綴分配較大的存儲空間，較短的前 綴分配較小的存儲空間，從而與現有技術相比，在一定程度上節約了存儲器的空間，降低了 路由器的成本。
為了更清楚地說明本發明實施例的技術方案，下面將對實施例描述中所需要使用 的附圖作以簡單地介紹，顯而易見地，下面描述中的附圖僅僅是本發明的一些實施例，對於 本領域普通技術人員來講，在不付出創造性勞動性的前提下，還可以根據這些附圖獲得其 他的附圖。圖1為本發明實施例提供的實現前綴匹配方法的流程圖；圖2為本發明實施例提供的實現前綴匹配的裝置的結構圖；圖3為本發明實施例提供的查詢模塊的結構圖；圖4為本發明實施例提供的實現前綴匹配的系統示意圖。
具體實施例方式下面將結合本發明實施例中的附圖，對本發明實施例中的技術方案進行清楚、完 整地描述，顯然，所描述的實施例僅僅是本發明一部分實施例，而不是全部的實施例。基於 本發明中的實施例，本領域普通技術人員在沒有作出創造性勞動前提下所獲得的所有其他 實施例，都屬於本發明保護的範圍。為了解決現有前綴匹配技術浪費存儲器資源、路由器成本過高的問題。本發明實 施例提供了一種前綴匹配的方法。如圖1所示，本發明實施例提供的前綴匹配的方法，包括101、設定前綴長度閾值；IPv6前綴長短不一，為了將IPv6的前綴按長度進行分類，需要設定一個前綴長度 閾值，本發明實施例中，前綴長度閾值可以為64bit ；102、按照前綴長度是否超過設定的前綴長度閾值將前綴分別存放不同的存儲區 域內。對要存儲的前綴進行判斷，若其長度大於64bit，則將其存儲進第一存儲區域，每 個前綴分配128bit的存儲空間；若其長度小於64bit，則將其存儲進第二存儲區域，每個前綴分配64bit的存儲空 間；由於大多數IPv6的前綴長度都不大於64bit，因此只有較少的IPv6前綴被存儲進 第一存儲區域內；大多數的IPv6前綴則被存儲進第二存儲區域，每個前綴佔用64bit的空間，與現有技術相比，節省了存儲空間，降低了路由器成本；103、在所述不同的存儲區域內同時查詢匹配的前綴，並將各自的查詢結果發送給 外部比較電路；本發明實施例提供的查詢前綴的方法具體為同時向第一存儲區域和第二存儲區域發送查詢請求；各存儲區域在收到所述查詢請求後，分別對自身存儲的前綴進行查詢；查詢後，各存儲區域分別將各自的查詢結果發送給外部比較電路。104、所述外部比較電路接收到所述查詢結果後，對其進行比較，得到最終匹配結 果；所述外部比較電路對查詢結果比較，得到最終匹配結果的方法具體為若在所述第一存儲區域能找到匹配的前綴，則將所述前綴確定為最終匹配的結 果；若所述第一存儲區域未能找到匹配的前綴，則將所述第二存儲區域匹配的前綴確定為 最終匹配結果；若在上述兩存儲區域均未找到匹配的前綴，則查詢失敗。上述本發明實施例所提供的技術方案，通過設定前綴長度閾值，按照前綴長度的 不同將前綴存放在不同的存儲區域內，較長的前綴分配較大的存儲空間，較短的前綴分配 較小的存儲空間，按照本發明實施例提供的查詢方法，能夠實現前綴的匹配，與現有技術相 比，本發明節約了存儲器的空間，降低了路由器的成本。在本發明實施例中，只設定了一個前綴長度閾值，在實際應用中，可將本發明技術 方案進行推廣以進一步節省存儲空間，根據需要設定多個前綴長度閾值，即將IPv6的前綴 按照其長度不同，分別存放於多個不同的存儲區域內；在查詢時，可按照上述查詢方法在多 個存儲區域內查詢，並由外部比較電路對所述多個存儲區域內的查詢結果進行比較。上述推廣過程與本發明實施例及其類似，在此不再過多贅述。如圖2所示，本發明實施例提供的實現前綴匹配的裝置，包括存儲模塊201，用於存儲前綴，包含多個存儲區域；分配模塊202，用於將前綴按照前綴長度是否超過前綴長度閾值分別存放到所述 存儲模塊201的不同的存儲區域內；查詢模塊203，用於在所述存儲模塊201的不同的存儲區域內查詢匹配的前綴；並 將查詢的結果發送給外部比較電路；外部比較電路204，用於對查詢模塊203的查詢結果進行比較，得到最終匹配結果.如圖3所示，在本發明實施例中，所述查詢模塊203包括請求發送單元301，用於向存儲模塊201的各存儲區域發送查詢請求；查詢單元302，用於在存儲模塊201中各存儲區域的前綴中查詢匹配的前綴；發送單元303，用於將查詢單元302的查詢結果發送給外部比較電路204。本發明實施例提供的實現前綴匹配的裝置，分配模塊202按照前綴長度的不同將 其分別存儲於存儲模塊201中的不同存儲區域中去，通過查詢模塊203對存儲模塊201中 的不同存儲區域分別進行查詢，並將查詢結果發送給外部比較電路204，由所述外部比較電 路204對查詢結果進行比較，實現了對存儲在各存儲區域內前綴的匹配，與現有技術相比， 在一定程度上節約了存儲器的空間，降低了路由器的成本。
如圖4所示，本發明實施例提供一種實現前綴匹配的系統， 包括兩個並行連接的存儲區域41a和41b和外部比較電路204，其中第一存儲區域41a 中存放長度超過前綴長度閾值的前綴，第二存儲區域41b中存放長度小於或等於前綴長度 閾值的前綴；外部比較電路204，用於接收在所述不同的存儲區域查詢的查詢結果，並進行比 較，得到最終匹配結果。所述實現前綴匹配的系統，還包括分配模塊202，用於將前綴按照前綴長度是否超過前綴長度閾值分別存放到所述 不同的存儲區域內；查詢模塊203，用於在所述不同的存儲區域內查詢匹配的前綴，並將查詢結果發送 給外部比較電路204。如圖3所示所述查詢模塊203包括請求發送單元301，用於向所述不同的存儲區域同時發送查詢請求；查詢單元302，用於在所述不同的存儲區域存儲的前綴中查詢匹配的前綴；發送單元303，用於將查詢單元的查詢結果發送給所述外部比較電路204。所述外部比較電路204，用於接收各存儲區域的查詢結果，並進行比較，得到最終 匹配結果；具體為若在第一存儲區域41a能找到匹配的前綴，則將所述前綴確定為最終匹 配的結果；若在第一存儲區域41a未能找到匹配的前綴，則將第二存儲區域41b匹配的前綴 確定為最終匹配結果；若均未找到匹配的前綴，則查詢失敗。在上述本發明實施例提供的實現前綴匹配的系統，將前綴按照長度的不同存放在 不同的存儲區域41內，並按照一定的連接方式和查詢模塊203，實現了前綴的匹配，與現有 技術相比，節約了存儲器的空間，降低了成本。本發明實施例提供的實現前綴匹配的系統可以應用到路由器當中，在路由器中， 將IP位址的前綴按照前綴長度是否超過前綴長度閾值進行分類，並將其分別存放到所述 實現前綴匹配的系統中的不同存儲區域內；當路由器轉發IP報文時，先獲取IP報文的目的地址，然後將所述目的地址與所述 不同存儲區域內的前綴進行匹配，並對匹配的結果進行比較，最終找出相匹配的前綴，將所 述IP報文從所述前綴所對應的埠轉發出去。在本發明實施例提供的路由器中，由於將前綴按照前綴長度是否超過前綴長度閾 值分別存放到不同的存儲區域內，較長的前綴分配較大的存儲空間，較短的前綴分配較小 的存儲空間，從而與現有的路由器相比，節約了存儲器的空間，降低了路由器的成本。另外，本發明實施例還可以進一步推廣，不限於IPv6前綴查詢，在需要執行前綴 匹配操作的系統中，均可以將前綴按長度分為兩個或者多個部分，並分別存放在不同的存 儲區域內，在查詢時查詢兩個部分或者多個部分，根據兩個部分或者多個部分的查詢結果 判決得到最終的匹配結果，從而節約了存儲器的存儲空間，降低了成本，並且查詢接口的帶 寬保持不變。本領域普通技術人員可以理解實現上述實施例方法中的全部或部分步驟可以 通過程序來指令相關的硬體完成，所述的程序可以存儲於計算機可讀存儲介質中，如ROM/ RAM、磁碟或光碟等。
以上所述，僅為本發明的具體實施方式
，但本發明的保護範圍並不局限於此，任何 熟悉本技術領域的技術人員在本發明揭露的技術範圍內，可輕易想到的變化或替換，都應 涵蓋在本發明的保護範圍之內。因此，本發明的保護範圍應以權利要求所述的保護範圍為準。
權利要求
一種前綴匹配的方法，其特徵在於，包括按照前綴長度是否超過設定的前綴長度閾值將前綴分別存放到不同的存儲區域內；在所述不同的存儲區域內同時查詢匹配的前綴，並將各自的查詢結果發送給外部比較電路；所述外部比較電路對所述查詢結果進行比較，得到最終匹配結果。
2.根據權利要求1所述的前綴匹配的方法，其特徵在於，所述按照前綴長度是否超過 設定的前綴長度閾值將前綴分別存放到不同的存儲區域內包括將長度超過前綴長度閾值的前綴存放於第一存儲區域，將長度小於或等於前綴長度閾 值的前綴存放於第二存儲區域。
3.根據權利要求1所述的前綴匹配的方法，其特徵在於，所述在所述不同的存儲區域 內同時查詢匹配的前綴，並將各自的查詢結果發送給外部比較電路包括向所述不同的存儲區域同時發送查詢請求；所述不同的存儲區域接收到查詢請求後，在所述不同的存儲區域存儲的前綴中查詢匹 配的前綴；將各自的查詢結果發送給外部比較電路。
4.根據權利要求1或2所述的前綴匹配的方法，其特徵在於，所述外部比較電路對所述 查詢結果進行比較，得到最終匹配結果的步驟包括若在第一存儲區域能找到匹配的前綴，則將所述前綴確定為最終匹配的結果；若在第 一存儲區域未能找到匹配的前綴，則將第二存儲區域匹配的前綴確定為最終匹配結果；若 均未找到匹配的前綴，則查詢失敗。
5.一種前綴匹配的裝置，其特徵在於，包括 存儲模塊，用於存儲前綴，包含多個存儲區域；分配模塊，用於將前綴按照前綴長度是否超過前綴長度閾值分別存放到所述存儲模塊 的不同的存儲區域內；查詢模塊，用於在所述存儲模塊的不同的存儲區域內查詢匹配的前綴，並將查詢結果 發送給外部比較電路；外部比較電路，用於對所述查詢模塊的查詢結果進行比較，得到最終匹配結果。
6.根據權利要求5所述的前綴匹配的裝置，其特徵在於，所述查詢模塊包括 請求發送單元，用於向所述不同的存儲區域同時發送查詢請求；查詢單元，用於在所述不同的存儲區域存儲的前綴中查詢匹配的前綴； 發送單元，用於將查詢單元的查詢結果發送給外部比較電路。
7.一種前綴匹配的系統，其特徵在於，包括兩個並行連接的存儲區域和外部比較電路；所述第一存儲區域，用於存放長度超過前綴長度閾值的前綴； 所述第二存儲區域，用於存放長度小於或等於前綴長度閾值的前綴； 外部比較電路，用於接收在所述不同的存儲區域查詢的查詢結果，並進行比較，得到最 終匹配結果。
8.根據權利要求7所述的系統，其特徵在於，還包括分配模塊，用於將前綴按照前綴長度是否超過前綴長度閾值分別存放到所述不同的存儲區域內；查詢模塊，用於在所述不同的存儲區域內查詢匹配的前綴，並將查詢結果發送給外部 比較電路。
9.根據權利要求8所述的系統，其特徵在於，所述查詢模塊包括請求發送單元，用於 向所述不同的存儲區域同時發送查詢請求；查詢單元，用於在所述不同的存儲區域存儲的 前綴中查詢匹配的前綴；發送單元，用於將查詢單元的查詢結果發送給所述外部比較電路。
全文摘要
本發明實施例提供了一種實現前綴匹配的方法，包括按照前綴長度是否超過設定的前綴長度閾值將前綴分別存放到不同的存儲區域內；在所述不同的存儲區域內同時查詢匹配的前綴，並將各自的查詢結果發送給外部比較電路；所述外部比較電路對所述查詢結果進行比較。本發明實施方式還提供一種實現前綴匹配的裝置和系統。本發明實施例基於IPv6前綴長短不一的特點，通過設定前綴長度閾值，按照前綴長度的不同將前綴存放在不同的存儲區域內，較長的前綴分配較大的存儲空間，較短的前綴分配較小的存儲空間，從而節約了存儲器的空間。
文檔編號H04L12/56GK101848133SQ20091011939
公開日2010年9月29日 申請日期2009年3月25日 優先權日2009年3月25日
發明者梁軍 申請人:華為技術有限公司