一種實現無回溯的最長前綴匹配搜索的方法和裝置的製作方法
2023-09-22 02:23:25
專利名稱:一種實現無回溯的最長前綴匹配搜索的方法和裝置的製作方法
技術領域：
本發明涉及網絡通訊領域中的模式匹配，特別涉及一種實現無回溯的最長前綴匹配搜索的方法和裝置。
背景技術：
IP數據包的轉發是路由器、交換機等網絡設備的基本功能之一。在進行IP數據包轉發時，需要根據數據包的目標地址進行搜索，以確定該數據包的轉發埠。最常見的搜索操作是在路由表中查找與對應的目標地址具有最長前綴匹配表項。由於路由表的規模通常都很大，對它們的檢索是一件非常費時的工作。
目前存在兩種版本的IP，即IP版本4(IPv4)和IP版本6(IPv6)。IPv4的地址長度為32位，而IPv6的地址長度則為128位。一個32位的IPv4目的地址提供40億個可能的路由，而一個網際網路路由器通常存儲40億個可能的路由中的5萬個路由。隨著互連網的發展和IPv6的普及，路由器中所存儲的路由數量也需要相應增加。
在現有的IPv4協議中，IP的地址空間分為A、B和C三類IP位址。每個IP位址空間分為網絡地址和主機地址。然而，將IP位址空間劃分為不同的類減少了可用IP位址的數量，浪費了大量可用的地址。為了提高IP位址空間利用率，現有技術中引入了無級域間路由(CIDR)。但無級域間路由增加了存儲在路由器中的路由數量。這是由於無級域間路由需要採用最長前綴匹配搜索來取代完全匹配搜索，以獲得相應的下一跳而尋找匹配的網絡地址。
實現採用最長前綴匹配搜索的技術主要有以下方法基於TCAM(三態內容尋址存儲器)器件的方法，這種方法的特點是使用特殊的存儲器件TCAM來實現最長前綴匹配，雖然能實現很好的查找性能，但由於TCAM器件成本很高，一般只適用於規模較小的查找表中。另外一種是基於二進位樹數據結構的方法搜索方法，這種方法將輸入的關鍵字與二進位樹的逐位匹配，直到找到葉子結點為止。對於一個32位的IPv4地址，需要32次搜索才能找到與關鍵字匹配的表項的入口。第三種方法是採用路徑壓縮的二進位樹，採用這種結構可以減少完成一次搜索所需的匹配次數。
採用基於路徑壓縮的二進位樹的方法進行搜索的存儲空間開銷較小，搜索效率也較高，而且這種方法的擴展性也很好。在當前的網絡處理中，通常採用採用這種結構。但採用這種方法實現最長匹配搜索時，由於搜索時無法確定當前結點的子樹中是否有最優的結果，所以在搜索時必須保存搜索過程中訪問到的節點，以便在葉子結點處找不到最優結果時回退到先前訪問的結點，即回溯以獲得正確的搜索結果，這會使存儲搜索結構的存儲開銷增加，同時還會因回溯而降低搜索的效率。
發明內容本發明的目的本發明的目的是克服現有方法在實現最長匹配搜索時，由於回溯而造成的存儲開銷增加，搜索效率降低的缺陷，從而提供一種可用於實現最長前綴匹配搜索的方法和實現裝置，以提高搜索的效率。
為了實現上述目的，本發明提供了一種實現無回溯的最長前綴匹配搜索的裝置，包括第一選擇器10、第二選擇器11、第三選擇器12、第一加法器14、第二加法器15、第一或門16、第二或門17、第三或門18、多路選擇器19、解碼器20、掩碼生成單元21和比較部件22；還包括輸入信息寄存器組1、樹結點寄存器組2、樹結點讀取部件4、葉索引表讀取部件5、比較結果寄存器6、葉結點信息寄存器組7、搜索結果寄存器組8和控制信號生成部件9；其中，所述的輸入信息寄存器組1與所述的多路選擇器19、第一選擇器10、第二加法器15連接；所述的樹結點寄存器組2分別與所述的第一選擇器10、第一加法器14、第二加法器15、樹結點讀取部件4和解碼器20電連接；所述的第一選擇器10還連接到第一加法器14上，所述的第一加法器14則與所述的多路選擇器19連接；所述的樹結點讀取部件4與多路選擇器19和外部的存儲器3電連接，所述的存儲器3還與所述的葉索引表讀取部件5電連接，所述的葉索引表讀取部件5與所述的第二加法器15、葉結點信息寄存器組7電連接；所述解碼器20分別與所述的第一或門16、第二或門17、第三或門18和掩碼生成單元21電連接，所述的第三或門18與所述的多路選擇器19連接，所述的第一或門16與所述的比較結果寄存器6電連接，所述的掩碼生成單元21還與葉結點信息寄存器組7、比較部件22相連，所述的比較部件22分別與所述的輸入信息寄存器組1、比較結果寄存器6、第二選擇器11和第三選擇器12電連接，所述的葉結點信息寄存器組7分別與第二選擇器11、第三選擇器12電連接，所述的第二選擇器11、第三選擇器12分別連接到所述的搜索結果寄存器組8上。
上述技術方案中，所述的輸入信息寄存器組1由葉索引表始址寄存器、搜索樹根結點地址寄存器、輸入關鍵字寄存器組成。
上述技術方案中，所述的樹結點寄存器組2由類型寄存器、待測位寄存器、下一中間結點地址寄存器以及葉結點索引寄存器組成。
上述技術方案中，所述的葉結點信息寄存器組7由關鍵字寄存器、前綴長度寄存器、數據信息大小寄存器和數據信息指針寄存器組成。
上述技術方案中，所述的搜索結果寄存器組8由搜索信息大小寄存器和搜索信息指針寄存器組成。
一種實現無回溯的最長前綴匹配搜索的方法，包括以下步驟步驟100、將搜索需要的參數寫入到輸入信息寄存器組1中，發出啟動信號，啟動一個查找過程；步驟200、樹結點讀寫部件4根據輸入信息寄存器組1中的搜索樹根結點地址寄存器和輸入關鍵字寄存器中的信息讀取外接的存儲器3，將相應的樹結點信息存入到樹結點寄存器組2中，並置比較結果寄存器6為0，執行下一步；步驟300、判斷樹結點寄存器組2中的類型域的值，如果類型域的值為「00」，則置完成信號為1，並根據比較結果寄存器6的值產生搜索成功與失敗信號，執行步驟900；若類型域的值為其他值，則執行下一步；步驟400、如果樹結點寄存器組2中的類型域的值為「01」或者「11」，執行下一步；否則，樹結點寄存器組2中的類型域為「10」，執行步驟900；步驟500、將樹結點寄存器組2中的葉結點索引域中的值與輸入信息寄存器組1中的葉索引表始址寄存器的值相加，相加後的結果送葉索引表讀取部件5，葉索引表讀寫部件5根據相加的結果對存儲器3進行讀取，將相應的葉結點信息寫入到葉結點信息寄存器組7中後，執行下一步；步驟600、將葉結點信息寄存器組7中的前綴長度域的值送到掩碼生成單元21中，生成的掩碼與輸入信息寄存器組1的輸入關鍵字寄存器所發出的輸入關鍵字相與，結果送到比較部件，與葉子信息寄存器7中的關鍵字域中的值作比較；步驟700、判斷比較的結果，若比較成功，結果送比較結果寄存器6，並將葉結點信息寄存器組7中的數據信息大小和數據信息指針域分別送到搜索結果寄存器組8的對應寄存器中；若比較失敗，不進行任何操作；步驟800、對樹結點寄存器組2中的類型域的值進行判斷，若該值為「11」，執行步驟下一步；否則置完成信號為1，根據比較結果寄存器的值產生搜索成功與失敗信號，轉步驟1000；步驟900、根據樹結點寄存器組2的下一待測位域取出輸入信息寄存器組1中的輸入關鍵字域對應位，若該位為1，則將樹結點寄存器組2的下一中間結點地址域的值加1，得到下一個中間結點地址；否則將樹結點寄存器組2的下一中間結點地址域的值作為下一中間結點地址，把該地址輸入到樹結點讀寫部件4；樹結點讀寫部件4讀取存儲器3，將相應的樹結點存入到樹結點寄存器組2中，重新執行步驟300；步驟1000、外部設備檢測到完成信號，檢查搜索輸出結果，若為1，則查找成功，讀取輸出的數據信息大小和數據信息指針寄存器，獲得搜索結果；否則，搜索失敗。
上述技術方案中，採用路徑壓縮的二進位樹來存儲搜索結構和葉索引表來存放葉結點信息。
在所述的二進位樹中，有包含兩個樹結點結構的中間結點，所述的兩個樹結點存放在連續的存儲空間中；所述樹結點結構由類型、待測位、下一中間結點地址和葉結點索引四個域組成。
所述的葉索引表是一個線性表，它的每個元素是一個葉結點結構；所述葉結點結構存放所述二進位樹的葉結點信息，所述葉結點結構由關鍵字、前綴長度、數據信息指針和數據信息大小四個域組成。
本發明的優點在於1、本發明採用了一種新的無回溯的路徑壓縮的二進位樹的結構及搜索方法，可提高搜索效率並降低存儲空間消耗。
2、本發明採用的葉子索引的機制，可減少實現查找的存儲空間開銷。
圖1為本發明的實現無回溯的最長前綴匹配搜索裝置的示意圖；圖2為一種應用本發明的實現無回溯的最長前綴匹配搜索裝置的網絡處理器的結構圖；圖3為在一個實施例中所採用的二叉樹的示意 圖4為本發明的實現無回溯的最長前綴匹配搜索方法的流程圖。
圖面說明1 輸入信息寄存器組 2 樹結點寄存器組 3 存儲器4 樹結點讀取部件 5 葉索引表讀取部件 6 比較結果寄存器7 葉結點信息寄存器組 8 搜索結果寄存器組 9 控制信號生成部件10 第一選擇器 11 第二選擇器 12 第三選擇器14 第一加法器 15 第二加法器 16 第一或門17 第二或門 18 第三或門 19 多路選擇器20 解碼器 21 掩碼生成單元 22 比較部件31 控制微處理器 32 數據總線 33 搜索裝置具體實施方式
下面結合附圖和具體實施方式
對本發明的實現無回溯的最長前綴匹配搜索的方法和裝置作進一步說明。
在對本發明的實現無回溯的最長前綴匹配搜索的方法進行說明前，首先對本發明中所涉及到的數據結構進行說明。
在本發明中所採用的二進位搜索樹中包含以下數據結構中間結點(IN)、樹結點(TN)、葉結點索引表(LIT)和葉結點(LN)。
中間結點(IN)是實現搜索樹內部結點的結構，如表1所示，它包含了兩個樹結點結構，結點1(TN1)和結點2(TN2)，它們存放在連續的存儲空間中，分別用於表示該結點的左右兩棵子樹。
表1樹結點(TN)是中間結點(IN)的基本組成部分。如表2所示，一個樹結點包含了類型(Type)、待測位(TB)、下一中間結點地址(NIA)和葉結點索引(LI)幾個域。其中，類型(Type)域表明了該樹結點的類型。在本方法中，樹結點分為四類空樹結點、連接葉結點的樹結點、連接中間結點的樹結點和連接葉及中間結點的樹結點。類型域的長度為兩位，表3給出了各個結點類型的定義和成立條件；待測位(TB)域表明關鍵字中待測試的位的位置；下一中間結點地址保存了連接在該樹結點上的中間結點的地址；而葉結點索引則存儲了連接在該樹結點上的葉子結點在葉結點索引表中的索引值。
表2
表3葉結點是實現查找樹的葉子結點的結構，如表4所示，它包含關鍵字(Key)、前綴長度(PL)、數據信息指針(DP)和數據信息大小(DS)四個域。其中，關鍵字和前綴長度域存儲了該葉子中關鍵字，用於在查找時與輸入的關鍵字比較；數據信息指針域和數據信息大小域分別保存了與該葉子結點對應的數據信息在存儲器中的地址及其大小，這兩個域將作為搜索結果返回，控制處理器可以根據它們從存儲器中讀出對應的數據信息。
表4葉結點索引表(LIT)是一個線性表，它的每個元素是一個葉結點結構。如表5所示，該表是一個保存8個32位的IPv4路由表項的葉結點索引表的示例，其中，0至7號前綴分別與0至7號數據一一對應。例如，在編號為0的葉結點索引表項中，一個32位的IP位址，它的前綴長度為16位，因此，該IP位址中關鍵字為32位IP位址的前16位，即「1.1.x.x」中的「1.1」為關鍵字。
表5如圖4所示，為一個搜索二叉樹的示意圖。在該示意圖中，樹結點的類型(Type)域是用二進位表示的，待測位(TB)和葉子索引是用十進位表示的。以其中的根結點為例，根結點本身是一個樹結點數據結構，由該結點的類型值10可以看出，根結點只與一個中間結點相連，待測位的值為6表示進行搜索時，需根據輸入關鍵字的第6位決定下一步訪問根節點的左子樹還是右子樹，若關鍵字的第6位為1在根節點的右子樹中查找，否則在根節點的左子樹中查找。沒有葉結點與根結點連接，因此葉結點索引值為空。在與根結點連接的中間結點上有兩個樹結點，左側的樹結點的類型值為11，表示該結點與一個葉結點和一個中間結點連接。待測位的值14表示進行搜索時，需根據輸入關鍵字的第14位決定下一步訪問當前節點的左子樹還是右子樹，若關鍵字的第14位為1，在當前節點的右子樹中查找，否則在當前節點的左子樹中查找，葉結點索引值7表示與結點相連接的葉結點在葉結點索引表中的第7項，假設所述的葉結點索引表就是表5，則與樹結點連接的葉結點為1.x.x.x/8。圖中其他結點的含義相類似，不再一一說明。
無回溯的最長前綴匹配搜索在網絡技術中有廣泛的應用，在本實施例中，以網絡處理器為例，對本發明的應用於網絡處理器的實現無回溯的最長前綴匹配搜索裝置進行說明。
如圖2所示，一個網絡處理器由控制微處理器31、數據總線32、搜索裝置33和存儲器3組成，其中控制微處理器31通過數據總線32與搜索裝置33相連，控制微處理器31和搜索裝置33都和存儲器3相連。搜索裝置33即為本發明的實現無回溯的最長前綴匹配搜索裝置，它作為網絡處理器中的查找加速電路存在。數據總線32在控制微處理器31和搜索裝置33之間傳遞數據和讀寫控制信號，控制微處理器31通過該部件向搜索裝置33的寄存器寫入數據或者從搜索裝置33中間查找結果後讀出。存儲器3存儲了查找所需的各種數據結構，它可以被控制微處理器31和搜索裝置33訪問。
下面對本發明的實現無回溯的最長前綴匹配搜索裝置進行詳細說明。如圖1所示，本發明的實現無回溯的最長前綴匹配搜索裝置包括輸入信息寄存器組1、樹結點寄存器組2、樹結點讀取部件4、葉索引表讀取部件5、比較結果寄存器6、葉結點信息寄存器組7、搜索結果寄存器組8和控制信號生成部件9。其中，輸入信息寄存器組1與多路選擇器19、第一選擇器10、第二加法器15連接；樹結點寄存器組2分別與第一選擇器10、第一加法器14、第二加法器15、樹結點讀取部件4和解碼器20電連接；第一選擇器10還連接到第一加法器14上，第一加法器14則與多路選擇器19連接；樹結點讀取部件4與多路選擇器19和外部的存儲器3電連接，存儲器3還與葉索引表讀取部件5電連接，葉索引表讀取部件5與第二加法器15、葉結點信息寄存器組7電連接；所述解碼器20分別與第一或門16、第二或門17、第三或門18和掩碼生成單元21電連接，所述的第三或門18與所述的多路選擇器19連接，所述的第一或門16與比較結果寄存器6電連接，所述的掩碼生成單元21還與葉結點信息寄存器組7、比較部件22相連，所述的比較部件22分別與輸入信息寄存器組1、比較結果寄存器6、第二選擇器和第三選擇器12電連接，所述的葉結點信息寄存器組7分別與第二選擇器11、第三選擇器12電連接，所述的第二選擇器11、第三選擇器12分別連接到搜索結果寄存器組8上。
輸入信息寄存器組1由多個寄存器組成，包括葉索引表始址寄存器、搜索樹根結點地址寄存器、輸入關鍵字寄存器。輸入信息寄存器組1從與本發明裝置連接的控制微處理器31輸入參數，該參數包括搜索樹根結點地址、葉結點索引表起始地址、輸入關鍵字和啟動信號。其中，搜索樹的根結點在存儲器3中的地址存儲在搜索樹根結點地址寄存器中，葉結點索引表的起始地址存儲在葉索引表始址寄存器，輸入關鍵字存儲在輸入關鍵字寄存器。
樹結點讀取部件4從與本發明的裝置相連接的存儲器3中讀取樹結點的信息。
樹結點寄存器組2保存了樹結點讀取部件4從存儲器3中讀入的樹結點，搜索電路利用該寄存器組決定進行查找時的各項操作，該寄存器組包含了類型寄存器(Type)、待測位(TB)寄存器、下一中間結點地址寄存器(NIA)以及葉結點索引(LI)寄存器四個寄存器，它們與樹結點的幾個域一一對應，樹結點四個域中的信息保存在對應的四個寄存器中。
葉索引表讀取部件5根據輸入的輸入信息寄存器組1中的葉索引表始址寄存器和樹結點寄存器組2的LI寄存器讀取葉索引表，將存儲器3中的葉結點信息寫入到葉結點信息寄存器組7中。
比較結果寄存器6存放了搜索過程中葉子結點中的關鍵字與輸入關鍵字的比較結果，同時還用於在搜索結束時產生搜索成功與失敗信號(OK/KO)。
葉結點信息寄存器組7包含關鍵字寄存器(Key)、前綴長度(PL)寄存器、數據信息大小寄存器(DS)和數據信息指針寄存器(DP)四個寄存器，分別用於存放葉結點的四個域中的相應信息。
搜索結果寄存器組8包括搜索信息大小寄存器和搜索信息指針寄存器兩個寄存器，分別存放作為搜索結果的信息的大小及其在存儲器中的存儲位置。
控制信號生成部件9用於生成各種內部的控制信號。
本發明裝置的輸出結果發送到控制微處理器31上，輸出結果具體包括搜索成功信號(OK/KO)、搜索完成信號(Finish)、搜索結果(搜索信息指針(DP)和搜索信息大小(DS))等。
上述的輸入信息寄存器組1中的輸入關鍵字寄存器和葉子信息寄存器組7中的Key域寄存器可根據需要可設置為不同的值，一般可取128位至256位之間，為簡化硬體電路，其餘的全部內部寄存器應所處的網絡處理器的字長一致，例如，在32位長的機器中，內部搜索裝置的寄存器均為32位長。
利用本發明的實現無回溯的最長前綴匹配搜索裝置可實現無回溯的最長前綴匹配搜索，其方法如下步驟100、控制微處理器31將搜索需要的各種輸入參數寫入到輸入信息寄存器組中，發出啟動信號，啟動一個查找過程；
步驟20、樹結點讀寫部件4根據輸入信息寄存器組1中的搜索樹根結點地址寄存器和輸入關鍵字寄存器中的信息讀取存儲器3，將相應的樹結點存入到樹結點寄存器組2中，置比較結果寄存器6為0，執行步驟300；步驟300、判斷樹結點寄存器組2中的類型域(Type)的值，如果類型域的值為「00」，則置完成(Finish)信號為1，並根據比較結果寄存器6的值產生搜索成功與失敗信號(OK/KO)，執行步驟900；若類型域的值為其他值，則執行下一步；步驟400、如果樹結點寄存器組2中的類型域(Type)的值為「01」或者「11」，執行下一步；否則，樹結點寄存器組2中的類型域(Type)為「10」，執行步驟900；步驟500、將樹結點寄存器組2中的葉結點索引域(LI)中的值與輸入信息寄存器組1中的葉索引表始址寄存器的值相加，相加後的結果送葉索引表讀取部件5；葉索引表讀寫部件5對存儲器3進行讀取，將相應的葉結點信息寫入到葉結點信息寄存器組7中後，執行下一步；步驟600、將葉結點信息寄存器組7中的前綴長度域(PL)的值送到掩碼生成單元中，生成的掩碼與輸入信息寄存器組1的輸入關鍵字寄存器所發出的輸入關鍵字相與，結果送到比較部件，與葉子信息寄存器7中的關鍵字域(Key)中的值作比較；步驟700、判斷比較的結果，若比較成功，結果送比較結果寄存器6，並將葉結點信息寄存器組中的數據信息大小(DS)和數據信息指針域(DP)分別送到搜索結果寄存器組8的對應寄存器中；若比較失敗，不進行任何操作。
步驟800、對樹結點寄存器組2中的類型域(Type)的值進行判斷，若該值為「11」，執行步驟900；否則置完成(Finish)信號為1，根據比較結果寄存器的值產生搜索成功與失敗信號(OK/KO)，轉步驟1000；步驟900、根據樹結點寄存器組2的下一待測位域(TB)取出輸入信息寄存器組1中的輸入關鍵字域對應位，若該位為1，則將樹結點寄存器組2的NIA域加1，得到下一個中間結點地址；否則樹結點寄存器組2的NIA域作為下一中間結點地址。將該地址輸入到樹結點讀寫部件4；樹結點讀寫部件4讀取存儲器3，將相應的樹結點存入到樹結點寄存器組2中，重新執行步驟300；步驟1000、控制微處理器1檢測到完成信號，檢查搜索輸出結果(OK/KO)，若為1，則查找成功，讀取輸出的數據信息大小(DS)和數據信息指針(DP)寄存器，獲得搜索結果；否則搜索失敗。
下面以一個具體的實例，對無回溯的最長前綴匹配搜索過程進行說明。假設在圖4的樹中，搜索一個IPv4的地址1.1.0.5，所採用的葉結點索引表如表5所示，具體實現如下步驟a、控制微處理器31將樹和葉結點索引表的信息以及關鍵字(1.1.0.5)寫入到搜索裝置33的輸入寄存器中，啟動搜索過程；步驟b、搜索裝置33讀入根結點，根結點的類型為「10」，關鍵字1.1.0.5的第6位(指二進位位)為0，因此讀入根節點的左子結點；步驟c、根結點的左子結點的類型值為「11」，TB域的值為14，葉子索引域為7，根據該索引值(7)和索引表的起始地址從表5中讀入該葉子結點，其中的前綴為1.x.x.x(Key)/8(PL)，根據前綴長度8得到掩碼255.0.0.0。將掩碼分別與關鍵字和前綴相與後作比較，二者相等，比較成功，因此將葉結點寄存器組的DP和DS域(即索引值為7的葉結點的地址和大小)送到結果寄存器組中。由於該節點的類型為「11「，TB域為14，而輸入關鍵字1.1.0.5的第14位為0，因此還需要讀入該樹結點的左孩子結點。
步驟d、在步驟300中讀入的結點的類型域為「10」，TB域為15，輸入關鍵字(1.1.0.5)的第15位為1，故讀入其右孩子結點。
步驟e、新讀入的右孩子結點的類型域為「11」，TB域為23，其葉子索引域的值為0，根據該索引值(0)和索引表的起始地址從表5中讀入該葉子結點，其中的前綴為1.1.x.x(Key)/16(PL)，根據前綴長度16得到掩碼255.255.0.0。將掩碼分別與關鍵字和前綴相與後再比較，二者相等，即比較成功，所以將葉結點寄存器組的DP和DS域(即索引值為0的葉結點的地址和數據的大小)送到結果寄存器組中。由於該節點的類型為「11」，TB域為23，而輸入關鍵字(1.1.0.5)的第23位為0，故讀入該樹結點的左孩子結點。
步驟f、本次讀入的結點類型為「01」，其葉子索引域的值為4，根據該索引值(4)和索引表的起始地址從表5中讀入索引值為4的葉子結點，其中的前綴為1.1.2.x(Key)/24(PL)，根據前綴長度24得到掩碼255.255.255.0。將掩碼分別與關鍵字和前綴相與後再比較，二者不等，即比較失敗，不進行任何操作。由於該結點的類型域為「01」，即搜索結束，此時比較結果寄存器的值為1，故置比較完成標誌和比較成功標誌為1。此時，搜索完成，搜索結果為搜索成功，得到的數據為索引值為0的葉結點中的數據。
權利要求
1.一種實現無回溯的最長前綴匹配搜索的裝置，其特徵在於，包括第一選擇器(10)、第二選擇器(11)、第三選擇器(12)、第一加法器(14)、第二加法器(15)、第一或門(16)、第二或門(17)、第三或門(18)、多路選擇器(19)、解碼器(20)、掩碼生成單元(21)和比較部件(22)；還包括輸入信息寄存器組(1)、樹結點寄存器組(2)、樹結點讀取部件(4)、葉索引表讀取部件(5)、比較結果寄存器(6)、葉結點信息寄存器組(7)、搜索結果寄存器組(8)和控制信號生成部件(9)；其中，所述的輸入信息寄存器組(1)與所述的多路選擇器(19)、第一選擇器(10)、第二加法器(15)連接；所述的樹結點寄存器組(2)分別與所述的第一選擇器(10)、第一加法器(14)、第二加法器(15)、樹結點讀取部件(4)和解碼器(20)電連接；所述的第一選擇器(10)還連接到第一加法器(14)上，所述的第一加法器(14)則與所述的多路選擇器(19)連接；所述的樹結點讀取部件(4)與多路選擇器(19)和外部的存儲器(3)電連接，所述的存儲器(3)還與所述的葉索引表讀取部件(5)電連接，所述的葉索引表讀取部件(5)與所述的第二加法器(15)、葉結點信息寄存器組(7)電連接；所述解碼器(20)分別與所述的第一或門(16)、第二或門(17)、第三或門(18)和掩碼生成單元(21)電連接，所述的第三或門(18)與所述的多路選擇器(19)連接，所述的第一或門(16)與所述的比較結果寄存器(6)電連接，所述的掩碼生成單元(21)還與葉結點信息寄存器組(7)、比較部件(22)相連，所述的比較部件(22)分別與所述的輸入信息寄存器組(1)、比較結果寄存器(6)、第二選擇器(11)和第三選擇器(12)電連接，所述的葉結點信息寄存器組(7)分別與第二選擇器(11)、第三選擇器(12)電連接，所述的第二選擇器(11)、第三選擇器(12)分別連接到所述的搜索結果寄存器組(8)上。
2.根據權利要求
1所述的實現無回溯的最長前綴匹配搜索的裝置，其特徵在於，所述的輸入信息寄存器組(1)包括葉索引表始址寄存器、搜索樹根結點地址寄存器和輸入關鍵字寄存器。
3.根據權利要求
1所述的實現無回溯的最長前綴匹配搜索的裝置，其特徵在於，所述的樹結點寄存器組(2)由類型寄存器、待測位寄存器、下一中間結點地址寄存器以及葉結點索引寄存器組成。
4.根據權利要求
1所述的實現無回溯的最長前綴匹配搜索的裝置，其特徵在於，所述的葉結點信息寄存器組(7)由關鍵字寄存器、前綴長度寄存器、數據信息大小寄存器和數據信息指針寄存器組成。
5.根據權利要求
1所述的實現無回溯的最長前綴匹配搜索的裝置，其特徵在於，所述的搜索結果寄存器組(8)由搜索信息大小寄存器和搜索信息指針寄存器組成。
6.一種應用權利要求
1、2、3、4或5所述的搜索裝置進行無回溯的最長前綴匹配搜索的方法，包括以下步驟步驟100)、將搜索需要的參數寫入到輸入信息寄存器組(1)中，發出啟動信號，啟動一個查找過程；步驟200)、樹結點讀寫部件(4)根據輸入信息寄存器組(1)中的搜索樹根結點地址寄存器和輸入關鍵字寄存器中的信息讀取外接的存儲器(3)，將相應的樹結點信息存入到樹結點寄存器組(2)中，並置比較結果寄存器(6)為0，執行下一步；步驟300)、判斷樹結點寄存器組(2)中的類型域的值，如果類型域的值為「00」，則置完成信號為1，並根據比較結果寄存器(6)的值產生搜索成功與失敗信號，執行步驟900；若類型域的值為其他值，則執行下一步；步驟400)、如果樹結點寄存器組(2)中的類型域的值為「01」或者「11」，執行下一步；否則，樹結點寄存器組(2)中的類型域為「10」，執行步驟900；步驟500)、將樹結點寄存器組(2)中的葉結點索引域中的值與輸入信息寄存器組(1)中的葉索引表始址寄存器的值相加，相加後的結果送葉索引表讀取部件(5)，葉索引表讀寫部件(5)根據相加的結果對存儲器(3)進行讀取，將相應的葉結點信息寫入到葉結點信息寄存器組(7)中後，執行下一步；步驟600)、將葉結點信息寄存器組(7)中的前綴長度域的值送到掩碼生成單元(21)中，生成的掩碼與輸入信息寄存器組(1)的輸入關鍵字寄存器所發出的輸入關鍵字相與，結果送到比較部件，與葉子信息寄存器(7)中的關鍵字域中的值作比較；步驟700)、判斷比較的結果，若比較成功，結果送比較結果寄存器(6)，並將葉結點信息寄存器組(7)中的數據信息大小和數據信息指針域分別送到搜索結果寄存器組(8)的對應寄存器中；若比較失敗，不進行任何操作；步驟800)、對樹結點寄存器組(2)中的類型域的值進行判斷，若該值為「11」，執行步驟下一步；否則置完成信號為1，根據比較結果寄存器的值產生搜索成功與失敗信號，轉步驟1000；步驟900)、根據樹結點寄存器組2的下一待測位域取出輸入信息寄存器組(1)中的輸入關鍵字域對應位，若該位為1，則將樹結點寄存器組(2)的下一中間結點地址域的值加1，得到下一個中間結點地址；否則將樹結點寄存器組(2)的下一中間結點地址域的值作為下一中間結點地址，把該地址輸入到樹結點讀寫部件(4)；樹結點讀寫部件(4)讀取存儲器(3)，將相應的樹結點存入到樹結點寄存器組(2)中，重新執行步驟300；步驟1000)、外部設備檢測到完成信號，檢查搜索輸出結果，若為1，則查找成功，讀取輸出的數據信息大小和數據信息指針寄存器，獲得搜索結果；否則，搜索失敗。
7.根據權利要求
6所述的實現無回溯的最長前綴匹配搜索的方法，其特徵在於，採用路徑壓縮的二進位樹來存儲搜索結構和葉索引表來存放葉結點信息。
8.根據權利要求
7所述的實現無回溯的最長前綴匹配搜索的方法，其特徵在於，在所述的二進位樹中，有包含兩個樹結點結構的中間結點，所述的兩個樹結點存放在連續的存儲空間中；所述樹結點結構由類型、待測位、下一中間結點地址和葉結點索引四個域組成。
9.根據權利要求
7所述的實現無回溯的最長前綴匹配搜索的方法，其特徵在於，所述的葉索引表是一個線性表，它的每個元素是一個葉結點結構；所述葉結點結構存放所述二進位樹的葉結點信息，所述葉結點結構由關鍵字、前綴長度、數據信息指針和數據信息大小四個域組成。
專利摘要
本發明公開了一種實現無回溯的最長前綴匹配搜索的裝置，包括第一選擇器、第二選擇器、第三選擇器、第一加法器、第二加法器、第一或門、第二或門、第三或門、多路選擇器、解碼器、掩碼生成單元和比較部件，還包括輸入信息寄存器組、樹結點寄存器組、樹結點讀取部件、葉索引表讀取部件、比較結果寄存器、葉結點信息寄存器組、搜索結果寄存器組和控制信號生成部件。本發明還公開了一種實現無回溯的最長前綴匹配搜索的方法。本發明採用的無回溯的路徑壓縮的二進位樹的結構及搜索方法，可提高搜索效率並降低存儲空間消耗；本發明採用葉子索引的機制，可減少實現查找的存儲空間開銷。
文檔編號G06F17/30GK1996953SQ200610165449
公開日2007年7月11日 申請日期2006年12月20日
發明者張飛飛, 鄢貴海, 付斌章, 李華偉, 韓銀和, 劉彤, 雷韶華 申請人:中國科學院計算技術研究所導出引文BiBTeX, EndNote, RefMan