用於產生和使用改進的樹形位圖數據結構的方法和裝置的製作方法

2023-09-22 02:32:50

專利名稱：用於產生和使用改進的樹形位圖數據結構的方法和裝置的製作方法
技術領域：
本發明特別涉及通信和計算機系統；並且本發明尤其涉及、但不限於，例如在路由器、包交換系統或者其他通信或計算機系統中，當確定最長前綴匹配時產生和使用改進的樹形位圖數據結構。
背景技術：
通信產業正迅速改變以適應新興技術和不斷增長的用戶需求。用戶對新應用和已有應用的改進性能的需求正促使通訊網絡和系統供應商採用具有更高速度和容量(例如，更寬的帶寬)的網絡和系統。在實現這些目標的努力中，一種很多通信供應者採用的普遍方法是採用包交換技術。越來越多地利用各種包技術，如IP(Internet Protocol，網際協議)，建立和擴充公共和私有的通訊網絡。
例如交換機或者路由器的網絡設備一般基於一個或多個標準接收、處理和前向轉發或丟棄包，這些標準包括包使用的協議的類型、包的地址(例如，源、目的地、群組)和被請求服務的類型或質量。此外，在每個包上一般執行一個或多個安全操作。但在這些操作可被執行前，在該包上一般必須執行包分類的操作。
IP轉發需要以網速進行最長匹配前綴計算。現在的IP版本IPv4，使用32位目的地地址，並且一個核心網際網路路由器能夠容納超過200,000個前綴。前綴一般用跟著一個』*』的位串(例如，01*)表示，以指示這些後面位的值不重要。對於目的地路由，在路由表中的每一個前綴條目一般包括一個前綴和下一個跳轉值。例如，假設資料庫只包括兩個前綴條目(01*--＞L1；0100*--＞L2)。如果路由器收到一個目的地地址從01000開始的包，那麼該地址和第一個前綴(01*)和第二個前綴(0100*)都匹配。因為第二個前綴是最長匹配，包應該被送到下一個跳轉L2。另一方面，一個目的地地址從01010開始的包，應該被送到下一個跳轉L1。下一個跳轉信息將一般指定在路由器上的一個輸出埠，並且可能指定一個數據鏈路地址。
圖1A舉例圖示了示為表10A中的節點1A-9A和二進位TRIE 10B中的節點1B-9B的一組前綴P1-9。二進位TRIE 10B中也示出了佔位符/空節點11B-18B，其代表不匹配節點(也就是說，不可能作為最長匹配前綴結果的節點)。例如，串1110000匹配前綴P1(1B)、P2(2B)和P5(5B)，其中最長的匹配前綴是P5(5B)。
在Eatherton等人於1999年8月10號申請、現正在審理中的美國專利申請09/371,907，」使用樹形位圖的數據結構和對一個資料庫中的數據快速分類的方法(Data Structure Using a Tree Bitmap and Method forRapid Classification of Data in a Database)」中描述了一種一般被稱為」樹形位圖」的已知方法，所述專利申請引用於此以供參考。樹形位圖是一種多位TRIE算法，它通過將節點分組成步組(sets of strides)來實現對二進位搜索TRIE的表達(representation)。步一般被定義為被分組在一起的二進位TRIE的樹級別的數目，或者定義為在單個的讀操作中訪問的一個樹中的級別的數目，代表一個樹或TRIE中的多個級別。圖1B用示了一個這樣將節點P1-P9(1B-9B)和空節點11B-18B(圖1A)分成步20-25的例子。在這個例子中，步的大小是三。
在一個已知的樹形位圖算法的實現中，一個特定的TRIE節點的所有子節點被連續存儲，這允許對所有子(children)只使用一個指針(指針指向子節點塊的開始)，因為每一個子節點能夠作為相對於該單個指針的偏移量被計算。這能減少所需指針的數目並減小TRIE節點的尺寸。
另外，每個TRIE節點有兩個位圖，一個用於所有在內部被存儲的前綴，一個用於外部指針。內部位圖具有一個為被存儲在這個節點中的每一個前綴設置的1位。這樣，對一個r位TRIE節點，長度小於r的可能前綴有(2r)-1個，因此，使用(2r)-1位圖。外部位圖包含一個位，該位用於所有可能的2r個子指針。一個TRIE節點具有固定的大小，並且只包含一個外部指針位圖、一個內部下一個跳轉信息位圖和一個指向子節點塊的獨立指針。與內部前綴相關的下一個跳轉被以與每一個TRIE節點相關聯的獨立數組形式存儲在該TRIE節點裡。為了存儲器分配目的，結果數組通常是普通節點大小的偶數倍(例如，對於16位下一個跳轉指針，和8位元組節點，一個結果節點被最多4個下一個跳轉指針需要，兩個結果節點被最多8個需要等等)。將下一個跳轉指針放到一個獨立的結果數組中，每個TRIE節點可能需要兩個存儲器訪問(一個給TRIE節點，一個為存儲的前綴提取(fetch)結果節點)。一般使用一種不訪問結果節點直到搜索結束的簡單延遲策略。然後訪問結果節點，該結果節點對應於包含一個有效前綴的路徑中碰到的最後的TRIE節點。這只是在除了每個TRIE節點所需的那個存儲器查詢(memory reference)之外，在末端加了一個單獨的存儲器查詢。
圖1C圖示了圖1A-B所示的前綴例子的一個樹形位圖實現的表達。如所示的，根節點30代表第一級別TRIE。子指針31將根節點30連接到包含第二級別步的子數組40。在級別3，有兩個子數組50和60，它們從子數組40分別通過子指針41和42被連接。
最長前綴匹配是通過從根節點開始被找到的。目的地地址的開始位(first bits)(對應於根節點的步，在這個例子中是3)被用於索引到在比如位置P上的根節點的外部位圖。如果一個1被定位在這個位置，那麼有一個有效子指針。這個1左邊、不包括這個1的1的數目(假設為I)被確定。因為指向子塊起始位置的指針(比如為C)和每一個TRIE節點的大小(比如為S)是已知的，所以指向子節點的指針能夠被計算為C+(I*S)。
在轉移到下一個子之前，檢查內部位圖以查看是否有一個對應於位置P的存儲的前綴。為了這樣做，設想從右邊開始逐位地移去P的位，並索引到內部位圖的相應位置，以尋找遇到的第一個1。例如，假設P是101，並且在根節點位圖中使用3位步。最右邊的位被首先移去，導致前綴10*。因為10*對應於內部位圖中的第六位位置，作檢查以確定在那個位置是否有個1。如果沒有，最右邊的兩個位被移去(導致前綴1*)。因為1*對應於內部位圖的第三個位置，作檢查以確定在那是否有個1。如果在那找到一個1，那麼搜索結束。如果在那沒有找到一個1，那麼前三位被移去，並且執行對一個條目的搜索，該條目對應於內部位圖的第一個條目中的*。
一旦已經確定一個匹配的被存儲的前綴存在於一個TRIE節點中，來自於與TRIE節點相關的結果節點、對應於下一個跳轉的信息不會被立即提取。而是，計數前綴位置之前的位的數量以指示該信息在結果數組中的位置。訪問結果數組對每個TRIE節點都將使用一個額外的存儲器查找。否則，在記憶被存儲的前綴位置和相應的父TRIE節點的同時，檢查子節點。此目的是記憶在搜索路經中包含被存儲的前綴的最後的TRIE節點T和相應的前綴位置。當搜索結束時(也就是說，遇到了一個在外部位圖的相應位置上設有一個0的TRIE節點)，對應於在已經計算出的位置上的T的結果數組被訪問以讀完下一個跳轉信息。
圖1D圖示了一個全部樹形位圖搜索的實現的偽碼。假設一個函數treeFunction，如果有最長匹配前綴的話，該函數能在一個特定的節點中通過查詢(consult)內部位圖，找到最長匹配前綴的位置。」LongestMatch」跟蹤指向迄今所見最長匹配的指針。當沒有子指針(也就是說，在節點的外部位圖中沒有位被設置)時循環結束，然後執行對LongestMatch所指的結果節點的延遲(lazy)訪問，以獲得最後的下一個跳轉。偽碼假設正被搜索的地址已經被分成步，並且stride[i]包含對應第i步的位。
使步保持不變，一種減少每一個隨機訪問的大小的方法是分裂內部和外部位圖，這有時被稱為分裂樹形位圖。這是通過在每一個TRIE節點中只放置外部位圖實現的。如果沒有存儲器分段(segmentation)，來自相同父的子TRIE節點和內部節點能夠在存儲器中被連續放置。如果存在存儲器分段，使內部節點分散在多個存儲體中是一個壞的設計。在被分段的存儲器的情況下，對TRIE節點的一個選擇是使指針指向子數組、內部節點和結果數組。
如圖1E所示的一種替換方法，使TRIE節點指向內部節點，並且內部節點指向結果數組。為了使這個最優化運作，每個子必須具有一個位，該位能指示父節點是否包含一個前綴，該前綴是迄今最長的匹配。如果在路徑中有一個前綴，搜尋引擎記錄內部節點的地點(從最後節點的數據結構中計算出來)，作為包含迄今最長匹配前綴。然後，當搜索結束時，相應的內部節點被訪問，然後對應於內部節點的結果節點被訪問。注意，核心算法延遲地訪問下一個跳轉信息；分裂樹形算法甚至延遲地訪問內部位圖。能這樣做是因為，任何時候只要前綴P被存儲在節點X中，匹配P的X的所有子能夠存儲一個位，該位表示父具有一個存儲的前綴。軟體索引(reference)實現使用這種優化來節省內部位圖處理；硬體實現使用它只是為了減小訪問的寬度大小(因為位圖處理在硬體中不是問題)。分裂樹形位圖的一個好處是，如果一個節點只包含路徑而沒有內部前綴，能夠使用一個空內部節點指針，並且在內部位圖上沒有空間被浪費。
用這種優化，外部和內部位圖分別在搜索節點和內部節點之間被分裂。以這種方式分裂位圖導致了減小的節點大小，這利於硬體實現。每一個搜索節點Sj有兩個指針一一個指向子，另一個指向內部節點，Ij。內部節點Ij保持一個指針指向葉數組LAj，對應於屬於這個節點的前綴。例如，圖1E圖示了搜索節點S1(111)、S2(112)和S3(113)，內部節點I1(121)、I2(115)和I3(114)，和葉數組LA1(122)、LA2(116)和LA3(123)，以及它們之間通過指針的互連。另外，葉數組LA1(122)、LA2(116)和LA3(123)分別包含葉節點L1(122A)、L2(116A)和L3(123A)。注意，以實線圖示的節點是在一個樹形位圖查找例子中被訪問的節點，這個例子在下文中描述。
現在，考慮查找繼續進行訪問搜索節點S1(111)、S2(112)和S3(113)的情況。如果parent_has_match標記設置在S3(113)中，這意味著，在在葉數組LA2(116)中的葉節點L2(116A)中的一個中有某個前綴，該前綴是當前的最長匹配。在這種情況下，內部節點I2(115)的地址被保存在查找上下文中。現在假設S3(113)不是這個查找擴展路徑。在葉數組LA3(123)中可能有某個前綴，該前綴為最長匹配前綴。因此，I3(114)首先被訪問，並且它的內部位圖被檢查來尋找最長匹配前綴。如果沒有找到最長匹配前綴，那麼地址已經被保存的內部節點I2(115)被提取，它的位圖被分析，並且對應最長匹配的葉節點L2(116A)被返回。上述訪問順序是S1(111)、S2(112)、S3(113)、I3(114)、I2(115)、L2(116A)。這個例子顯示有這樣的情況，即在最長匹配能夠被確定前，需要訪問兩個內部節點，並且分析兩個內部位圖。
在硬體實現中，存儲器訪問速度通常是和節點處理時間相對立的瓶頸。基於硬體的樹形位圖搜尋引擎的一般實施，使用多個存儲信道來存儲樹形位圖數據結構。在這種情況下，樹形位圖節點以這樣的方式在存儲信道中遍布，使得對於每一個查找，所被訪問的連續節點落在不同的存儲信道中。如果一個獨立的存儲信道能夠承受每秒」x」次訪問，那麼對於同時進行的多個查找，假如每個存儲信道每次查找最多被訪問一次，那麼就能夠實現平均每秒」x」次查找。如果這些信道中的任何一個在每次查找中被訪問兩次，那麼包轉發速度下降一半，因為那個特定的信道成為瓶頸。
因此，沿著任何從樹的根部到底部(bottom)的路徑的所有內部節點，都需要被存儲在不同的存儲信道中。因為兩個內部節點都需要被放置到不同的存儲信道中，所以當存儲信道的數目有限時，訪問兩個內部節點就出現了問題，並且哪兩個內部節點將被訪問取決於特定的樹形位圖和查找值。例如，參照圖1E，被訪問的內部節點可能是I3(114)和I2(115)，或者I3(114)和I1(121)，或者I2(115)和I1(121)。因此，在這個例子中，所有的七個節點S1(111)、S2(112)、S3(113)、I1(121)、I2(115)、I3(114)和L2(116)需要處於單獨的存儲器模塊中。當存儲器模塊少於7時就有問題了。
當確定最長前綴匹配時，需要用來產生和使用改進的樹形位圖數據結構的新方法和裝置，尤其是，但是不限於，減少存儲器訪問的次數和/或提供一個比以前的樹形位圖實現具有優勢的那些方法和裝置。

發明內容
公開了在確定一個最長的前綴匹配時，例如在路由器、包交換系統，或者其他通信或計算機系統、設備或系統中，用來產生和使用改進的樹形位圖數據結構的方法和裝置。一個實施例包括一個數據結構。數據結構包括，第一搜索節點，第一子數組，其具有第一內部節點和第二搜索節點；和第一葉數組，其具有多個第一葉數組條目。第一搜索節點包括一個指向第一子數組的指針。第一內部節點包括一個指向第一葉數組的指針。第二搜索節點包括一個指向多個第一葉數組條目中的一個的指針。


所附的權利要求詳細地闡明了本發明的特徵。從下面結合附圖的詳細描述中，本發明和它的優點可以被最好的理解。這些附圖是圖1A-E是已知的樹形位圖系統的框圖或其他圖示；圖2A是一個實施例中使用的改進的樹形位圖數據結構的框圖；圖2B是一個實施例中使用的改進的樹形位圖數據結構的框圖；圖3A是一個實施例中使用的，通過使用樹形位圖執行一個最長前綴匹配操作的進程的框圖；圖3B-C圖示了一個實施例中使用的，從一個樹形位圖中增加和刪除節點的進程的偽碼的框圖；圖4是一個實施例的框圖，該實施例產生和/或使用一個樹形位圖數據結構來確定一個最長前綴匹配；圖5是一個實施例的框圖，該實施例產生和/或使用一個樹形位圖數據結構來確定一個最長前綴匹配；圖6A圖示了一個實施例中使用的搜索要求和結果消息格式；圖6B圖示了一個實施例中使用的節點數據單元的一個格式；圖6C圖示了一個實施例中使用的進程，該進程用來確定一個樹形位圖數據結構的一個實施例中的下一個相關節點或單元的地址；圖7圖示了一個實施例中使用的進程，該進程用來從一個收到的包或其他信息中摘錄數據，將這些數據轉送到一個樹形位圖系統，並且根據從樹形位圖系統接收到的結果來處理收到的包或其他信息；和圖8A-D圖示了一個實施例中使用的進程，該進程用來執行一個樹形位圖最長前綴或者其他查找操作。
具體實施例方式
公開了當確定一個最長前綴匹配時，例如在路由器、包交換系統或者其他通信或計算機組件、設備或系統中，用來產生和使用改進的樹形位圖數據結構的方法和裝置。這裡所描述的實施例包括了各種元件或限制，其中沒有一個元件或限制被認為是關鍵性的元件或限制。每一項權利要求獨立完整地陳述本發明的一個方案。此外，所描述的一些實施例包括，但不限於，系統、網絡、集成電路晶片、嵌入式處理器、ASIC(ApplicationSpecific Integrated Circuit，特定用途集成電路)、方法和包含指令的計算機可讀介質。以下描述的實施例實現了在本發明範圍和原則內的不同方案和構造，其中圖說明了示例性的非限制性的構造。
術語「包」使用在這裡指所有類型的包或者任何其它單位的信息或數據，包括，但不限於，固定長度的信元、可變長度的包，其中每一個可以或不可以分為更小的包或信元。術語「包」使用在這裡也指包本身或包指示，例如，但不限於，包或包報頭的全部或部分、數據結構值、指針或索引，或者包的任何其他部分或標識。而且，這些包可以包含一種或多種類型的信息，包括，但不限於，語音、數據、視頻和音頻信息。在這裡術語「項目」用來指包或者任何其它單位或段的信息或數據。
術語「系統」在這裡通用於描述任何數目的組件、元件、子系統、設備、包交換元件、包交換機、路由器、網絡、計算機和/或通信設備或機構、或其組件的組合。術語「計算機」在這裡通用於描述任何數目的計算機，包括，但不限於，個人電腦、嵌入式處理器和系統、控制邏輯、ASIC、晶片、工作站、大型機等。術語「設備」在這裡通用於描述任何類型的機構，包括計算機或系統或其組成部分。術語「任務」和「過程」在這裡通用於描述任何類型的運行的程序，包括，但不限於，計算機進程、任務、線程、執行應用程式、作業系統、用戶進程、設備驅動程序、本地碼、機器或其他語言等，並且可以是交互的和/或非交互的、本地和/或遠程執行的、在前臺和/或後臺執行的、在用戶和/或作業系統地址空間內執行的、一個例程庫和/或獨立的應用程式，並且不限於任何特定存儲器分區技術。圖中所示的步驟、連接和信號與信息的處理，包括，但不限於，任何框圖、流程圖和消息隊列表，在保持在本發明範圍和原則內的其他實施例中，可以以相同或不同的串行或並行次序和/或由不同組件和/或進程、線程等，和/或通過不同的連接並結合其他功能來執行。
此外，術語「網絡」和「通信機制」在這裡通用於描述一個或多個網絡、通信媒體或通信系統，包括，但不限於，網際網路，私有或公共電話，蜂窩狀的、無線的、衛星的、電纜的、局域、城域的和/或廣域的網絡，通過電纜的電連接、總線等等，以及例如消息傳送、進程間通信、共享存儲器等的內部通信機構。
術語「存儲機構」包括任何類型的存儲器、存儲設備或其他用於以任何形式保存指令或數據的機構。「計算機可讀介質」是一個可擴展的術語，包括了任何存儲器、存儲設備、存儲機構、和包括了例如網絡接口卡及其緩存的接口和設備的其他存儲和信令機構，以及任何通信設備和所接收和傳送的信號，和計算機化的系統能夠解釋、接收和/或傳送的其它當前和發展中的技術。術語「存儲器」包括任何隨機訪問存儲器(RAM)、只讀存儲器(ROM)、快閃記憶體、集成電路和/或其他存儲器組件或元件。術語「存儲設備」包括任何固態存儲介質、盤驅動器、磁碟、網絡化的服務、磁帶驅動器和其他存儲設備。存儲器和存儲設備可以存儲由處理器和/或控制邏輯執行的計算機可執行指令，和由處理器和/或控制邏輯操縱的數據。術語「數據結構」是一個可擴展的術語，指任何數據元素、變量、數據結構、資料庫、和/或能應用於數據以方便解釋該數據或對其執行操作的一個或多個或一個組織的體系(scheme)，例如，但不限於，存儲器位置或設備、集合、隊列、樹結構、堆棧、列表、連結列表、數組、表格、指針等。一個數據機構一般保存在存儲機構中。術語「關聯存儲器」指的是所有類型的公知的或開發出來的關聯存儲器，包括但不局限於二進位(binary)和三進位(ternary)內容可尋址存儲器、哈希(hash)表、TRIE和其他數據結構等等。
術語「一個實施例」在這裡用來指一個特定的實施例，其中每次提到「一個實施例」可能指的是不同的實施例，在這裡描述關聯特性、元件和/或限制時，重複使用該術語並不導致每個實施例必須包括的一套累積的關聯特性、元件和/或限制，雖然某個實施例一般可以包括所有這些特性、元件和/或限制。此外，短語「用於xxx的裝置」一般包括包含了用於執行xxx的計算機可執行指令的計算機可讀介質。
此外，術語「第一」、「第二」等在這裡通常用來代表不同單元(如，第一元件、第二元件)。在這裡使用這些術語不一定意味一個排序，如一個單元或事件比另一個發生或到來得更早，而是提供一個區別特定單元的機制。此外，短語「基於x」和「響應於x」用來表示最小的一組項目x，從它衍生或引起了某些事物，其中「x」是可延伸的，並且不一定描述在其上執行操作等等的一個完整列表的項目。另外，短語「耦合到」用來表示兩個元件或設備之間的一定程度的直接或間接連接，而耦合設備修改或不修改被耦合的信號或通信的信息。術語「子集」用來表示包括了一個集合中元素的全部、少於全部的組。此外，術語「或」在這裡用來表示連續項目中的一個或多個，包括全部，的交替選擇。
本發明公開了當確定一個最長前綴匹配時，例如在路由器、包交換系統中，用來產生和使用改進的樹形位圖數據結構的方法和裝置。一個實施例組織樹形位圖，使得在一個查找操作中必須被訪問的內部節點數最少。在TRIE或搜索節點的每一個中都包括一個指向父的葉或結果數組中的最佳匹配條目的指針，這允許對這個結果的直接訪問而不用必須分析相應的內部節點。而且，一個實施例將一個特定級別的內部節點存儲為其子數組中的第一個單元。此外，一個實施例使用通用搜尋引擎，該引擎能夠同時遍歷多個樹形位圖或其他數據結構，並且執行完整搜索、部分搜索，並且重新開始部分搜索，例如在收到在其上搜索的額外數據後。
一個實施例包括對樹形位圖數據結構以及相關的查找和更新方案的改進。這些一般改善了查找性能，並且可能節約存儲器訪問以用於某些硬體實施例。一個實施例以這樣的方式組織樹形位圖，使得每次查找最多需要一個內部節點訪問。例如，一個實施例修改樹形位圖結構，以避免必須以S1、S2、S3、I3、I2和L2的順序(也就是說，前面描述的涉及圖1E的順序)訪問內部節點I2。在這個例子中並且也參照圖1E，匹配葉節點L2(116A)在分析I2(115)中的內部位圖後被確定。對這個訪問順序的分析，使得觀察到了對每一個通過節點S3(113)的查找，隨後的對I2(115)的內部位圖分析總是產生相同的匹配葉節點L2(116)。這樣，在一個實施例中，一個新的樹形位圖數據結構和相關的查找和更新方案，被用來避免以這個典型的查找順序在I2(115)對內部位圖分析。
一個實施例使用數據結構，該數據結構包括，第一搜索節點；第一子數組，包括第一內部節點和第二搜索節點；和第一葉數組，包括多個第一葉數組條目。一般，第一搜索節點包括一個指向第一子數組的指針，第一內部節點包括一個指向第一葉數組的指針；並且第二搜索節點包括一個指向第一葉數組多個條目中的一個的指針。
在一個實施例中，第一內部節點是第一子數組的第一單元。在一個實施例中，第一內部節點的指針和第二搜索節點的指針指示不同的第一葉數組條目。在一個實施例中，數據結構還包括第二子數組，其中，第二搜索節點包括一個指向第二子數組的指針。在一個實施例中，數據結構還包括第二葉數組，該數組包括多個第二葉數組條目，其中，第二子數組包括第二內部節點，該第二內部節點包括一個指向第二葉數組的指針。在一個實施例中，第二內部節點是第二子數組的第一單元。在一個實施例中，第二子數組包括第三搜索或結束節點，其中，第二搜索或結束節點包括一個指向多個第二葉數組條目中的一個的指針。在一個實施例中，第二內部節點的指針和第三搜索或結束節點的指針，指示不同的第二葉數組條目。在一個實施例中，第一搜索節點代表第一長度的步，第二搜索節點代表第二長度的步，其中，第一長度和第二長度是不同的。在一個實施例中，第一搜索節點包括第一長度的第一提示符，第二搜索節點包括第二長度的第二提示符。
一個實施例遍歷代表多個前綴的樹形數據結構，多個前綴被區分成具有大於一的許多樹級別的多個步，多個步中的每一步用樹形位圖表示，並且子路徑的指出用擴展位圖表示。在一個實施例中，在樹形數據結構中位於當前級別的搜索節點被接收。響應確定一個新的最佳匹配是否存在，當前最佳匹配標識符被更新。在確定匹配的下一級別節點是否存在中，索引到當前級別的擴展位圖。在一個實施例中，這個遍歷被重複，直到匹配的下一級別節點確實存在，然後用當前級別的搜索節點指出的內部節點被提取，並且基於當前最佳匹配標識符或者基於當前級別搜索節點中指向葉節點的指針，搜索結果被識別。在一個實施例中，響應確定搜索節點不存在於當前級別，索引到一個結束節點以識別搜索結果。在一個實施例中，基於在結束節點中的指針，當前最佳匹配標識符被更新。
一個實施例，基於一個輸入搜索數據串，遍歷一個存儲在一個或多個計算機可讀介質中的樹形數據結構。一般，一個部分完成的樹形遍歷的搜索進程上下文被接收，其中搜索進程上下文一般包括下一個節點地址或者某個其他節點提示符。樹形數據結構的遍歷，從這個節點輸入串的下一部分重新開始。一個實施例將一般包括下一個節點地址的查找請求分配給多個存儲設備中的一個。查找結果從多個存儲設備中的一個設備中被接收，查找結果包括一個搜索節點。響應確定一個新的最佳匹配是否存在，當前最佳匹配標識符被更新。索引到搜索節點的當前級別擴展位圖，以確定匹配的下一個級別的節點是否存在。下一個節點地址的新值被產生，作為對搜索進程上下文的新值。
在一個實施例中，搜索進程上下文還包括一個最佳匹配提示，和所使用的輸入搜索數據串的長度。在一個實施例中，最佳匹配提示包括一個匹配標記和一個葉節點指針。在一個實施例中，多個樹形數據結構被存儲在計算機可讀介質中，並且這些樹形數據能夠被同時遍歷。
基於輸入數據串、用來遍歷一個或多個樹形數據結構的節點的一種實施例裝置，包括樹形位圖下一個地址機構，該機構用來確定一個或多個樹形數據結構中的一個特定的樹形數據結構的下一個節點的存儲地址，下一個節點對應輸入數據串的一部分，多個存儲設備，這些設備用來存儲一個或多個樹形數據結構，並且用來響應於提取請求、返回下一個節點；和一個存儲器管理器，被耦合到樹形位圖下一個地址機構和多個存儲設備，用來將提取請求分送給多個存儲設備中的一個。一般，一個或多個樹形數據結構中的每一個，包括第一搜索節點，第一子數組包括第一內部節點和第二搜索節點，並且第一葉數組包括多個第一葉數組條目。在一個實施例中，第一搜索節點包括一個指向第一子數組的指針，第一內部節點包括一個指向第一葉數組的指針；並且第二搜索節點包括一個指向多個第一葉數組條目中的一個條目的指針。
在一個實施例中，一個或多個樹形數據結構包括具有至少兩個不同樹的節點。在一個實施例中，樹形位圖下一個地址還確定多個存儲設備中的一個，並為存儲器管理器提供多個存儲設備中的一個設備的提示。在一個實施例中，下一個節點包括多個存儲設備中具體的一個設備的提示，在那裡，存儲器管理器將提取請求分配給多個存儲設備中的那個具體的設備。在一個實施例中，多個存儲設備包括第一類型的第一存儲設備和第二類型的第二存儲設備，其中第一類型和第二類型是不同的。在一個實施例中，第一存儲類型為樹形數據結構中的每一個存儲第一級別的節點。
圖2A圖示了這樣的一個實施例，其具有搜索節點S1(211)、S2(212)和S3(213)，內部節點I1(221)、I2(224)和I3(214)，和葉數組LA1(222)、LA2(215)和LA3(223)，葉節點L1(222A-B)、L2(215A-B)和L3(223A-B)以及它們之間通過指針的互連。注意，以實線圖示的節點是在下文中要描述的、在一個樹形位圖查找例子中被訪問的節點。同樣，如圖2A所示，指針220、230和240從它們各自的搜索節點212、213和225直接指向了父節點的葉節點222A、215A和223B(對應最佳匹配條目)。同樣，注意圖2A只顯示了一個路徑，而其他路徑的搜索節點將指向在葉數組(222，215，223)中的不同的葉節點(222A-B、215A-B、223A-B)。在一個實施例中，在控制時間(例如，當樹形位圖正在被編程時)，已知葉L2(215A)包含的是對應節點S3(213)的最長匹配。所以，通過直接將指向葉節點L2(215A)的指針存儲在節點S3(213)中，那麼在上述的訪問順序中，在訪問葉節點L2(215)之前，將不必訪問I2(224)。
在一個實施例中，搜索節點S1(211)、S2(212)、S3(213)和S4(225)每一個在它們相應的父節點葉數組中都包含一個指向最佳匹配葉的parent_best_leaf_pointer(210，220，230和240)。示出了具有指向葉數組LA1(222)中葉節點L1(222A)的指針220的搜索節點S2(212)，具有指向葉數組LA2(215)中葉節點L2(215A)的指針230的搜索節點S3(213)，具有指向葉數組LA3(223)中葉節點L3(23B)的指針240的搜索節點S4(225)。在一個實施例中，一個零或空parent_best_leaf_pointer標識出在父節點中沒有更新的、這樣的最長匹配前綴。
在某些實施例中，使節點的大小最小化是非常重要的。在一個實施例中，通過釋放搜索節點中的內部節點指針，以及通過將該內部節點設置為子數組中的第一個節點，從前面的樹形位圖實現(implementation)中提取搜索節點中的空間。然後，內部節點能夠通過搜索節點中的子指針被訪問，並且搜索節點的節點結構中被釋放了的內部節點指針空間(來自前面的實現)被用來存儲指向父節點葉數組中的最佳匹配葉節點的指針。參照例子，S3中的內部節點指針235(也就是，S3-＞I3)，用連結S3-＞L2(230)替代，其中L2是級別2中對應S3(213)的最長匹配。
圖2B圖示了一種新的樹形位圖數據結構的一個實施例。如所示的，內部節點被設置為搜索節點的子數組中的第一個單元。因此子和內部節點使用同一指針被訪問。例如，內部節點I1(261)是子數組260的第一個單元，內部節點I2(281)是子數組280的第一個單元。
更詳細地說，搜索節點S1(250)包括一個指向子數組260的指針256，子數組260包括內部節點I1(261)和子單元265。內部節點I1(261)包括一個指向可以包括零或更多單元的葉數組LA1(270)的指針267，在這個例子中，葉數組LA1(270)包括單元葉節點L1(271)，該節點是搜索節點S2(262)的最佳葉父節點結果。注意，子單元265包括搜索節點S2(262)，其包括直接指向葉節點L1271的指針268。注意，為了便於讀者理解，在子單元265和葉數組LA1(270)中使用了一串圓點，以表示在子單元265中更多可能的搜索節點和指向葉數組LA1(270)中條目的指針。搜索節點S2(262)還包括指向子數組280的指針266，該子數組280包括內部節點I2(281)和包括結束節點E3(282)的子單元285。內部節點I2(281)包括指向葉數組LA2(290)的指針277。結束節點E3(282)包括直接指向葉節點L2(291)的指針288，葉節點L2(291)是結束節點E3(282)的最佳葉父節點結果。
以概括術語描述一個實施例，只有當Sk不是一個特定查找的擴展前綴時，搜索節點Sk的內部節點Ik才被訪問。如果Sk是擴展前綴，那麼Ik永遠不需要被訪問。換句話說，在一個實施例中，永遠沒有Ik和Sk+1在同一個查找中都需要被訪問的情況。因此，Ik和Sk+1一般可以都放在同一存儲器模塊中。在一個實施例中，如果」parent_has_match」標記被設置在下一個級別的搜索節點Sk+1中，內部節點地址Ik在查找中被記憶。在新的方案中，如果Sk+1中的」parent_best_leaf_pointer」是非零，它直接指向是最長匹配前綴的、在級別」k」的葉節點。在一個實施例中，上述節點結構改變能夠應用於除內部節點和葉節點之外的所有樹形位圖節點。
圖3A圖示了在一個實施例中所使用的、在一個樹形位圖上執行查找的進程。進程從進程塊300開始，並繼續進行到進程塊302，在那裡搜索從在級別k＝0的根節點開始。然後，在進程塊304中，current_best_leaf被初始化為zero＝0(例如，迄今沒有匹配)，parent_best_leaf_pointer被初始化為zero＝0(例如，迄今沒有匹配)。
接著，如進程塊306中所確定的，如果當前節點是搜索節點Sk(例如，不是結束節點Ek)，那麼如進程塊308中所確定的，如果Sk中的parent_best_leaf_pointer是非零，那麼在進程塊310中，current_best_leaf被設置為parent_best_leaf_pointer的值。
接著，在進程塊312中，使用取決於步的來自查找關鍵字的接著的幾個位，索引到Sk的」擴展位圖」。如果如進程塊314中所確定的，Sk是擴展前綴，那麼在進程塊316中，計算在子數組中的下一級別節點的地址(一般包括一個考慮內部節點Ik是子數組中的第一個節點的調節)。接著，在進程塊318中，在級別k+1的節點被提取，並且進程返回到進程塊306。
否則，Sk不是擴展前綴(如進程塊314中所確定的)，那麼，在進程塊320中，內部節點Ik被提取，其中Ik是Sk的子數組中的第一個單元。如果如進程塊322中所確定的，通過分析內部位圖在Ik中有最長匹配前綴，那麼，在進程塊324中，結果從級別k的葉節點被提取，並且如進程塊338所提示的，進程結束。否則，在進程塊326中，使用保存的current_best_leaf直接訪問對應迄今的最長前綴的葉來提取結果，並且如進程塊338所提示的，進程結束。
否則，在進程塊306中，當前節點被確定為一個結束節點，並且進程繼續進行到進程塊330。如果，如進程塊330中所確定的，如果Ek中的parent_best_leaI_pointer是非零的，那麼在進程塊332中current_best_leaf被設置為parent_best_leaf_pointer的值。
接著，如進程塊334中所確定的，如果在Ek中有一個最長匹配前綴，那麼在進程塊336中，結果從在級別k的葉節點被提取，並且如進程塊338所指示的，進程結束。否則，在進程塊326中，使用保存的current_best_leaf直接訪問對應迄今最長前綴的葉節點，結果被提取，並且如進程塊338所提示的，進程結束。
圖3B圖示了一個實施例中使用的進程，以在一個葉節點被加入時，當向一個樹形位圖數據結構中插入前綴時更新parent_best_leaf_pointer。假設Pk是在級別k被插入的前綴。假設Sk是對應的搜索節點。假設Setk+1是Sk的子數組中從Pk派生的那些節點的集合。換句話說，Pk是Setk+1中的所有搜索節點的前綴。在一個實施例中，Setk+1是所有節點的集合，在這些節點中當Pk被插入時，需要設置」parent_has_match」標記。
在軟體的一個實施例中，下面的附加變量連同」parent_best_leaf_pointer」一起被保存在每一個搜索節點中。注意，在一個實施例中，這些只在控制軟體節點結構中需要，在硬體結構中不需要。Bestleaf_offset(Sk+1)基本上是用在它的葉數組中parent_best_leaf(Sk+1)所指葉的偏移量。」bestleaf_length」是用parent_best_leaf(Sk+1)指向的前綴的長度。
下面是對圖3B中所圖示的偽碼中所使用的術語/函數/變量的定義。Children_array(Sk)是搜索節點Sk的子數組指針。Bestleaf_offset(Sk+1)是搜索節點Sk+1的純軟體」bestleaf_offset」變量的值。Parent_best_leaf(Sk+1)是在搜索節點Sk+1中新引進的」parent_best_leaf_pointer」的值。Bestleaf_length(Sk+1)是搜索節點Sk+1的純軟體」bestleaf_length」變量的值。當在一個已經存在的葉數組中插入一個新的前綴時，New_leaf_array_base(Pk)是在樹形位圖中位置的地址，並且整個葉數組連同被插入的前綴Pk被拷貝到該位置。
基本上，如圖3B圖示的偽碼中所描述的，前綴的實際插入與在前的實現同樣進行，加入了更新在下一級別搜索節點中的parent_best_leaf_pointer，而不是更新parent_has_match標記。對於處於一致的狀態、所有parent_best_leaf_pointer都指向正確的葉的樹形位圖數據結構來說，圖3B中圖示的偽碼示出了在一個前綴插入後，所有的parent_best_leaf_pointer是怎樣又被變到一致狀態的。
另外，當一個新的搜索節點Sk+1被插入到Sk的子數組中時(例如，當樹的新支被創建作為前綴插入的結果時)，parent_best_leaf(Sk+1)需要被確定。本質上，在Sk的葉數組Lk中、是對應Sk+1的最長前綴的葉節點的偏移量是通過分析Sk的內部節點Ik中的內部位圖被確定的。
另外，當一個前綴被刪除時，parent_best_leaf_pointer必須被更新。假設Pk是在級別k被刪除的前綴。假設Sk是對應的搜索節點。假設Setk+1是Sk的子數組中那些節點的集合，對於這些節點來說Pk是最佳葉。圖3C圖示了在一個實施例中被用以更新在前綴被刪除的搜索節點的子節點中的parent_best_leaf_pointer的進程。
圖4圖示了用來實現樹形位圖數據結構的系統400的一個實施例，該系統，例如但是不限於計算機或通信系統。在一個實施例中，系統400使用這樣的一個樹形位圖數據結構來根據本發明確定最長前綴匹配。在一個實施例中，系統400使用樹形位圖數據結構通過接404編程另一個設備，例如遍歷引擎500(圖5)。
在一個實施例中，系統400包括處理器401、存儲器402、存儲設備403和可選接404，它們一般通過一個或多個通信機構409(為了說明目的示為總線)耦合。系統400的各種實施例可以包括或多或少的單元。系統400的操作一般被處理器401控制，通過使用存儲器402和存儲設備403以執行一個或多個排定的任務或進程。存儲器402是一種計算機可讀介質，並且一般包括隨機存儲器(RAM)、只讀存儲器(ROM)、快閃記憶體、集成電路、和/或其他存儲組件。存儲器402一般存儲將要被處理器401執行的計算機可執行指令，和/或被處理器401操縱、用來實現本發明的功能的數據。存儲設備403是另一種類型的計算機可讀介質，並且一般包括固態的存儲介質、磁碟驅動器、磁碟、網絡服務、磁帶驅動器和其他存儲設備。存儲設備403一般存儲將要被處理器401執行的計算機可執行指令，和/或被處理器401操縱、用來實現本發明的功能的數據。
圖5圖示了用來遍歷等級(hierarchal)數據結構的一個實施例的框圖，該數據結構，包括，但是不限於樹形位圖或者其他樹形數據結構。一個請求設備501，例如一個處理器或其他控制邏輯，產生被遍歷引擎500接收的查找請求，並且將該請求存儲在請求緩衝器512中。因為遍歷引擎能夠被用來同時在多個和甚至獨立的樹形位圖和/或其他數據結構上執行搜索，所以維護處理器502用一個或多個樹形位圖和/或其他數據結構編程遍歷引擎500。在一個實施例中，請求設備501和/或維護處理器與系統400(圖4)通信。在一個實施例中，請求設備501和/或維護處理器502被包含在遍歷引擎500中。
在一個實施例中，遍歷引擎500包括請求緩衝器512，用來接收和緩衝搜索請求；一個存儲器管理器520，用來控制對存儲設備和控制器521-529、以及對SRAM和控制器530的讀和寫操作，結果被發到樹形位圖下一個地址邏輯514或輸出隊列535。輸出隊列535將搜索結果傳送到請求設備501。樹形位圖下一個地址邏輯514處理從請求緩衝器512接收到的搜索請求和從存儲設備和控制器521-529以及從SRAM和控制器530接收到的中間結果，並且可能確定下一個節點的存儲器地址，並將存儲器讀請求發送給存儲器管理器520。
被遍歷引擎500接收或產生的搜索請求可以包括一個完整的或部分的串，基於該串找到最長匹配前綴或其他結果。例如，在一個實施例中，遍歷引擎500包括基於一個查找串的第一個部分搜索、返回結果、然後基於結果和查找串的額外部分從它停止搜索的地方繼續該搜索的能力。此外，在一個實施例中，遍歷引擎500將繼續在數據結構中搜索，直到接收到一個結果、用盡了搜索數據、或者遇到一個停止節點(在下面進一步描述)。
在一個實施例中所使用的搜索請求的格式在圖6A中示出。初始搜索請求601包括一個指示初始(與繼續的相對)搜索請求的搜索類型域和一個包括要匹配的信息的搜索數據域。被繼續的搜索請求602，包括一個指示繼續的搜索的搜索類型域，一個指示從哪裡重新開始該搜索的開始地址域，一個包括該查找串額外部分的搜索數據域，一個迄今有效葉標記和指向迄今最佳葉的指針的域，其中這個標記指示指向迄今最佳葉的指針的域是否填充相應的指針(在搜索的前面部分被確定)。
圖6A還圖示了一個實施例所使用的搜索響應(search response)的格式。響應(繼續的搜索(continuing search))結果603，包括一個搜索結果類型域、一個下一個節點地址域、一個迄今有效葉標記、一個指向迄今最佳葉的指針的域和所使用的搜索數據的長度。響應(葉訪問)結果604包括一個搜索結果類型域和最後所得到的葉節點數據域。
維護處理器502(圖5)，通過提交請求到更新控制器539，能夠裝入並提取一個或多個樹形位圖或其他數據結構，該更新控制器539發送更新請求到存儲器管理器520，並且能夠接收來自存儲設備和控制器521-529以及來自SRAM和控制530的信息。
圖6B圖示了一個實施例中所使用的節點或數據結構單元(element)的格式。搜索/結束/停止節點611包括一個節點類型域、一個指示當前節點中使用的步的大小的子數組集群(cluster)大小，這樣數據結構能夠使用可變長度的步和節點。搜索/結束/停止節點611還包括擴展位圖、子(例如子數組)指針域、迄今最佳葉指針、內部節點存在標記和錯誤糾正碼域。內部節點612包括節點類型域、葉數組指針域、迄今最佳葉指針域、內部位圖域和錯誤糾正碼域。葉節點613包括節點類型域、相關的返回數據域和錯誤糾正碼域。跳轉節點614包括節點類型域、被比較的數據域、被比較的長度域、迄今最佳葉域、子(例如子數組)指針域和錯誤糾正碼域。
返回圖5，搜索請求，例如，但是不限於在這裡所描述的那些，被請求緩衝器512接收。如果節點的存儲器地址基於接收到的搜索請求很容易被得到，那麼請求被直接發送到存儲器管理器520。否則，搜索請求被發送到樹形位圖下一個地址邏輯514，在那裡存儲器地址被計算。注意，該樹形位圖下一個地址邏輯514也接收存儲器讀結果並計算下一個節點的存儲器地址，或者發送存儲器讀結果(例如，節點)到輸出隊列535。
圖6C圖示了一個實施例中所使用的、計算或確定下一個地址(例如，在數據結構中相關的下一個節點或者單元的地址)的進程。進程從進程塊650開始，並且繼續進行到進程塊652，在那裡提取查找串的下一部分的當前步長和子位圖。注意，在一個實施例中，條目的步長在每一個條目間可以改變。而且，一個實施例支持子數組的可變大小，這個大小被子數組集群(cluster)大小識別。接著，在進程塊654中，計數在條目的子位圖中直到匹配查找串的位置的1的數量。這樣，這個計數識別哪個單元是感興趣的下一個。在進程塊656中，基於子指針加上指針域寬度乘以該計數，計算下一個地址。然後，在進程塊658中，包括所確定的下一個地址、要使用的存儲體和存儲信道的查找請求被發送到存儲器管理器，並且如進程塊659所指示的，進程結束。
由請求設備501(圖5)和遍歷引擎500的進程，在圖7和圖8A-D中通過流程圖被進一步描述，現在我們就轉到這些圖。
圖7圖示了在一個實施例中由請求設備501(圖5)使用的進程。進程從進程塊700開始，並且繼續進行到進程塊702，在那裡包或者其他信息被接收。接著，在進程塊704中，存儲器搜索請求，例如初始搜索請求601(圖6A)，被發送到遍歷引擎500(圖5)。接著，在進程塊706中，結果從遍歷引擎500被接收。如進程塊708所確定的，如果搜索沒有結束(例如，在搜索請求中有更多位需要提供給遍歷引擎，例如對於圖6A中被繼續的搜索請求602)，進程返回到進程塊704以產生和傳送搜索請求。否則，在進程塊710中，基於所接收的結果處理包或其他信息。對於這個搜索，如進程塊712所指示的，進程結束。
圖8A-D圖示了在一個實施例中所使用的、用以遍歷樹形位圖或其他數據結構的進程。進程從進程塊800開始，並且繼續進行到進程塊802，在那裡初始或被繼續的搜索請求被接收。接著，如進程塊804所確定的，如果第一個存儲器訪問將要在SRAM和控制器530中被執行，那麼SRAM查找地址在進程塊806中被確定，並且在進程塊808中該存儲器訪問(也就是，查找)請求被發送到SRAM控制器用來執行存儲器訪問。否則，或者經由連接器8A(111)繼續，在進程塊810中，基於能夠服務該請求的對存儲設備的某種分配方案，查找請求被轉發給外部存儲設備中的一個。在一個實施例中，一個或多個樹形位圖或其他數據結構中的每一個，在外部存儲器中的每一個中被複製。在一個實施例中，某些樹形位圖或其他數據結構填充外部存儲器的子集。
接著，在進程塊812中，查找結果被接收。如果，如進程塊814中所確定的，查找結果包括一個跳轉節點，那麼進程通過連接器8B(816)繼續進行到圖8B中的連接器8B(830)。否則，如果，如進程塊818中所確定的，查找結果包括一個內部節點，那麼進程通過連接器8C(820)繼續進行到圖8C中的連接器8C(850)。否則，如果如進程塊822中所確定的，查找結果包括一個葉節點，那麼在進程塊824中，查找的返回值在進程塊824中被發送，並且如進程塊826中所指出的，進程結束。否則，進程通過連接器8D(828)繼續進行到圖8D中的連接器8D(870)。
轉到圖8B，進程通過連接器8B(830)或8E(840)繼續。從連接器8B(830)開始，如進程塊832中所確定的，如果有一個對應於當前節點的最佳葉，那麼在進程塊834中這個最佳葉被作為在搜索中發現的迄今當前最佳葉存儲。接著，如進程塊836中所確定的，跳轉節點中提供的跳轉位匹配查找串的緊接著的數據位，那麼，在進程塊838中，跳轉節點中指定的地址被用作下一個地址值，並且進程通過連接器8A(839)返回到圖8A中的連接器8A(811)。跳轉節點允許搜索數據串與可能對應一個或多個TRIE的程序串做比較，因此，可以被用以節省存儲器訪問和查找時間。當在查找串中有不改變的長串時，例如在IPv6查找中，這個跳轉節點特徵尤其有用。
否則，或者從連接器8E(840)繼續，如果在進程塊842中最佳匹配已經被確定，那麼這個最佳匹配值被用作下一個地址，進程通過連接器8A(847)繼續進行到圖8A中的連接器8A(811)。否則，最佳匹配結果沒有被定位，並且在進程塊844中沒有匹配結果被發送，那麼如在進程塊845中所指示的，這個搜索的進程結束。
轉到圖8C，從連接器8C(850)開始，如進程塊852中所確定的，如果有一個對應於當前節點的最佳葉，那麼在進程塊854中這個最佳葉被作為搜索中發現的迄今當前最佳葉存儲。接著，如進程塊856中所確定的，如果偏移量位標記在樹形位圖中被設置(也就是說，樹形位圖將要被分析)，那麼，在進程塊858中，葉節點的地址被計算，並且進程通過連接器8A(859)繼續進行到圖8A中的連接器8A(811)。否則，進程通過連接器8E(857)繼續進行到圖8B中的連接器8E(840)。
轉到圖8D，從連接器8D(870)開始，如進程塊872中所確定的，如果有一個對應於當前節點的最佳葉，那麼在進程塊873中這個最佳葉被作為搜索中發現的迄今當前最佳葉存儲。接著，如進程塊874中所確定的，如果在外部位圖中相應位沒有被設置(例如，沒有這個查找的外部查找)，那麼進程繼續進行到進程塊876。如果子節點不是內部節點，那麼如在進程塊880中所確定的，如果有查找串的匹配，那麼在進程塊881中下一個地址被設置給最佳地址，並且進程通過連接器8A(883)繼續進行到圖8A中的8A(811)。否則，在進程塊882中，不匹配結果在進程塊882中被發送，如在進程塊883中所指示的，進程結束。否則，如果在進程塊876中一個內部節點被確定，那麼在進程塊878中，下一個地址被設置為子指針的值，並且進程通過連接器8A(879)繼續進行到圖8A中的連接器8A(811)。
否則，子節點的下一個地址在進程塊884中被計算。如在進程塊886中所確定的，如果當前節點是一個結束節點(例如，指示一個停止遍歷標識(indication))，那麼在進程塊888中搜索狀態被返回或發送，並且如在進程塊889中所指示的，進程結束。否則，進程通過連接器8A(887)繼續進行到圖8A中的連接器8A(811)。
考慮到我們的發明的原理可以被應用到很多可能的實施例中，在這裡參照圖/圖形所描述的實施例及其方面只是圖示性的而不應該作為對本發明的範圍的限制。對於例子和對本領域的技術人員將顯然的，許多進程塊操作能夠被重新排序，在其他操作之前、之後或者實質上與其他操作同時地被執行。同樣，數據結構的許多不同的形式能夠被用於多種實施例中。這裡所描述的本發明，考慮了所有可以落在下面的權利要求和其等價物的範圍內的這樣的實施例。
權利要求
1.一種計算機可讀介質，在其上存儲有數據結構，數據結構包括第一搜索節點；第一子數組，包括第一內部節點和第二搜索節點；和第一葉數組，包括多個第一葉數組條目；其中，第一搜索節點，包括一個指向第一子數組的指針；其中，第一內部節點，包括一個指向第一葉數組的指針；並且其中，第二搜索節點，包括一個指向多個第一葉數組條目中的一個的指針。
2.權利要求1中的計算機可讀介質，其中，第一內部節點是第一子數組的第一個單元。
3.權利要求1中的計算機可讀介質，其中，第一內部節點的指針和第二搜索節點的指針指示不同的所述第一葉數組條目。
4.權利要求1中的計算機可讀介質，包括第二子數組；並且其中，第二搜索節點包括一個指向第二子數組的指針。
5.權利要求4中的計算機可讀介質，包括第二葉數組，該數組包括多個第二葉數組條目；並且其中，第二子數組包括第二內部節點，該第二內部節點包括一個指向第二葉數組的指針。
6.權利要求5中的計算機可讀介質，其中，第二內部節點是第二子數組的第一單元。
7.權利要求6中的計算機可讀介質，其中，第二子數組包括第三搜索或結束節點，其中，所述第三搜索或結束節點包括一個指向多個第二葉數組條目中的一個的指針。
8.權利要求7中的計算機可讀介質，其中，第二內部節點的指針和第三搜索或結束節點的指針，指示不同的所述第二葉數組條目。
9.權利要求1中的計算機可讀介質，其中，第一搜索節點代表第一長度的步，第二搜索節點代表第二長度的步，其中，第一長度和第二長度是不同的。
10.權利要求9中的計算機可讀介質，其中，第一搜索節點包括第一長度的第一指示符，第二搜索節點包括第二長度的第二指示符。
11.一種使用樹形數據結構執行的方法，該數據結構代表多個前綴，前綴被區分為大於一的多個樹級別的多個步，多個步中的每一步用樹形位圖表示，子路徑的標識用擴展位圖表示，該方法包括(a)提取樹形數據結構中當前級別的一個搜索節點；(b)響應於確定一個新的最佳匹配是否存在，更新當前最佳匹配標識符；(c)索引到當前級別擴展位圖，以確定匹配的下一級別節點是否存在；(d)響應於所述確定匹配的下一級別節點存在，重複步驟(a)、(b)和(c)，使得當前級別是基於所述索引到當前級別擴展位圖而識別的下一級別，以確定用搜索節點指示的內部節點中的偏移量；和(e)響應所述確定匹配的下一級別節點不存在，執行步驟包括提取一個用當前級別搜索節點指示的內部節點；和基於當前最佳匹配標識符、或者基於在當前級別搜索節點中到葉節點的指針識別搜索結果。
12.權利要求11中的方法，包括響應於確定搜索節點不存在於當前級別，索引到一個結束節點以識別搜索結果。
13.權利要求12中的方法，包括基於結果節點中的指針，更新當前最佳匹配識別符。
14.一種裝置，用於基於一個樹形數據結構來確定搜索結果，該樹形數據結構代表多個前綴，多個前綴被區分為大於一的多個樹級別的多個步，多個步中的每一步用樹形位圖表示，子路徑的標識用擴展位圖表示，該裝置包括用來提取在樹形數據結構中當前級別的搜索節點的裝置；用來響應於確定一個新的最佳匹配是否存在，更新當前最佳匹配標識符的裝置；用來索引到當前級別擴展位圖，以確定匹配的下一級別節點是否存在的裝置；用來索引到當前級別擴展位圖，以確定用搜索節點指示的內部節點中的偏移量的裝置；用來提取用當前級別搜索節點指示的內部節點的裝置；和用來基於當前最佳匹配標識符、或者基於當前級別搜索節點中指向葉節點的指針來識別搜索結果的裝置。
15.權利要求14中的裝置，包括用來索引到一個結束節點以識別搜索結果的裝置。
16.權利要求15中的裝置，包括用來基於結束節點中的指針更新當前最佳匹配識別符的裝置。
17.一種計算機可讀介質，包含用來執行步驟的計算機可執行指令，執行步驟是通過使用一個樹形數據結構，該數據結構代表多個前綴，多個前綴被區分為大於一的多個樹級別的多個步，多個步中的每一步用樹形位圖表示，子路徑的標識用擴展位圖表示，所述步驟包括(a)提取樹形數據結構中當前級別的一個搜索節點；(b)響應於確定一個新的最佳匹配是否存在，更新當前最佳匹配標識符；(c)索引到當前級別擴展位圖，以確定匹配的下一級別節點是否存在；(d)響應於所述確定匹配的下一級別節點存在，重複步驟(a)、(b)和(c)，使得當前級別是基於所述索引到當前級別擴展位圖而識別的下一級別，以確定用搜索節點指示的內部節點中的偏移量；和(e)響應所述確定匹配的下一級別節點不存在，執行步驟包括提取用當前級別搜索節點指示的內部節點；和基於當前最佳匹配標識符、或者基於在當前級別搜索節點中到葉節點的指針識別搜索結果。
18.權利要求17中的計算機可讀介質，具有用來執行步驟的計算機可執行指令，步驟包括響應於確定搜索節點不存在於當前級別，索引到一個結束節點以識別搜索結果。
19.權利要求18中的計算機可讀介質，具有用來執行步驟的計算機可執行指令，步驟包括基於結束節點中的指針更新當前最佳匹配識別符。
20.一種基於一個輸入搜索數據串、用來遍歷存儲在一個或多個計算機可讀介質中的樹形數據結構的方法，該方法包括對輸入搜索數據串的多個部分中的每一部分都執行一套步驟，這套步驟包括(a)接收一個部分完成的樹遍歷的搜索進程上下文，搜索進程上下文包括下一個節點地址；(b)重新開始所述對樹形數據結構的遍歷，包括重複執行步驟(i)到(iv)，用來遍歷對應輸入串的多個部分中的下一個的樹形數據結構(i)將包括下一個節點地址的查找請求分送到多個存儲設備中的一個；(ii)從所述多個存儲設備中的一個中接收查找結果，查找結果包括一個搜索節點；(iii)響應確定一個新的最佳匹配是否存在，更新當前最佳匹配標識符；(iv)索引到搜索節點的當前級別擴展位圖，以確定一個匹配的下一級別節點是否存在；(v)產生下一個節點地址的新值；和(c)產生搜索進程上下文的新值。
21.權利要求20中的方法，其中，搜索進程上下文包括一個最佳匹配標識，和所使用的輸入搜索數據串的長度。
22.權利要求21中的方法，其中，最佳匹配標識包括一個匹配標記和一個葉指針。
23.權利要求20中的方法，其中，一個或多個計算機可讀介質包括多個不同的樹形數據結構；並且其中，對多個輸入搜索數據串中的每一個都執行步驟(a)、(b)和(c)，該多個輸入搜索數據串中的每一個對應多個不同樹形數據結構中的每一個。
24.一種計算機可讀介質，包含用於執行一種方法的計算機可執行指令，該方法用來基於一個輸入搜索數據串、遍歷一個樹形數據結構，該方法包括對輸入搜索數據串的多個部分中的每一個執行一套步驟，這套步驟包括(a)接收一個部分完成的樹遍歷的搜索進程上下文，搜索進程上下文包括下一個節點地址；(b)重新開始所述對樹形數據結構的遍歷，包括對應下一個輸入串的多個部分，重複執行用來遍歷樹形數據結構的步驟(i)到(iv)(i)將包括下一個節點地址的查找請求分送到多個存儲設備中的一個；(ii)從所述多個存儲設備中的一個中接收查找結果，查找結果包括一個搜索節點；(iii)響應確定一個新的最佳匹配是否存在，更新當前最佳匹配標識符；(iv)索引到搜索節點的當前級別擴展位圖，以確定一個匹配的下一級別節點是否存在；(v)產生下一個節點地址的新值；和(c)產生搜索進程上下文的新值。
25.權利要求24中的計算機可讀介質，其中，搜索進程上下文包括一個最佳匹配提示，和所使用的輸入搜索數據串的長度。
26.權利要求25中的計算機可讀介質，其中，最佳匹配提示包括一個匹配標記和一個葉指針。
27.權利要求24中的計算機可讀介質，其中，對多個輸入搜索數據串中的每一個都執行步驟(a)、(b)和(c)，該多個輸入搜索數據串中的每一個對應多個不同樹形數據結構中的每一個。
28.一種基於輸入搜索數據串，用來遍歷一個或多個樹形數據結構的節點的裝置，該裝置包括樹形位圖下一個地址機構，該機構用來確定所述的一個或多個樹形數據結構中特定的一個樹形數據結構的下一個節點的存儲器地址，下一個節點對應於輸入數據串的一部分；多個存儲設備，用來存儲所述的一個或多個樹形數據結構，以及用來響應於提取請求、返回所述下一個節點；和存儲器管理器，被耦合到樹形位圖下一個地址機構和多個存儲設備，用來將提取請求分送給多個存儲設備中的一個；其中，所述的一個或多個樹形數據結構中的每一個，都包括第一搜索節點；第一子數組，包括第一內部節點和第二搜索節點；和第一時數組，包括多個第一葉數組條目；其中，第一搜索節點包括一個指向第一子數組的指針；其中，第一內部節點包括一個指向第一葉數組的指針；並且其中，第二搜索節點包括一個指向多個第一葉數組條目中的一個的指針。
29.權利要求28中的裝置，其中，所述的一個或多個樹形數據結構包括至少兩個不同的樹的節點。
30.權利要求28中的裝置，其中，樹形位圖下一個地址還確定多個存儲設備中的所述一個，並且為存儲器管理器提供多個存儲設備中的所述一個的標識。
31.權利要求30中的裝置，其中，下一個節點包括多個存儲設備中特定的一個的標識，其中，存儲器管理器將提取請求分送給多個存儲設備中特定的一個。
32.權利要求28中的裝置，其中，多個存儲設備包括第一類型的第一存儲設備和第二類型的第二存儲設備，其中，第一類型和第二類型是不同的。
33.權利要求32中的裝置，其中，第一存儲器類型為樹形數據結構的每一個存儲第一級別的節點。
34.一種基於輸入搜索數據串，用來遍歷存儲在一個或多個計算機可讀介質中的一個樹形數據結構的裝置，該裝置包括用來接收一個部分完成的樹遍歷的搜索進程上下文的裝置，該搜索進程上下文包括下一個節點地址；和用來重新開始對樹形數據結構的所述遍歷的裝置；用來將包括下一個節點地址的查找請求分送給多個存儲設備中的一個的裝置；用來從多個存儲設備中的所述一個中接收查找結果的裝置，該查找結果包括一個搜索節點；用來響應確定一個新的最佳匹配是否存在，更新當前最佳匹配標識符的裝置；用來索引到搜索節點的當前級別擴展位圖，以確定一個匹配的下一級別節點是否存在的裝置；用來產生下一個節點地址的新值的裝置；和用來產生搜索進程上下文的新值的裝置。
35.權利要求34中的裝置，其中，搜索進程上下文包括一個最佳匹配標識，和所使用的輸入搜索數據串的長度。
36.權利要求35中的裝置，其中，最佳匹配標識包括一個匹配標記和一個葉指針。
全文摘要
公開了用來在例如路由器、包交換系統中，在確定最長前綴匹配時，產生和使用一種改進的樹形位圖數據結構的方法和裝置。一個實現組織樹形位圖，以最小化在一個查找操作過程中必須被訪問的內部節點的數量。在TRIE或搜索節點的每一個中都包含有一個指向葉或結果數組中迄今最佳匹配條目的指針，這允許對這個結果的直接訪問而不用必須分析相應的內部節點。而且，一個實現將特定級別的內部節點存儲為在它的子數組中的第一個單元。此外，一個實現使用能夠同時遍歷多個樹形位圖或其他數據結構的通用搜尋引擎，並且執行完全搜索、部分搜索和例如在接收到要搜索的額外數據後重新開始部分搜索。
文檔編號G06F17/30GK1462004SQ0312292
公開日2003年12月17日 申請日期2003年4月24日 優先權日2002年5月31日
發明者維賈伊·蘭加拉詹, 達利特·沙吉, 威廉·N·伊瑟頓 申請人:思科技術公司