最長匹配地址查詢的方法和裝置的製作方法

2023-05-22 16:42:51 3

專利名稱：最長匹配地址查詢的方法和裝置的製作方法
技術領域：
網際網路是由路由器連接的一組網絡。路由器維護表示每個可能的目的網絡，即接收的數據包應被轉發到的下一跳的路由表。下一跳可以是另一個路由器或最終的目的地。
背景技術：
在路由器中的埠接收的網際協議(「IP」)數據包包括一個IP目的地址。該IP目的地址是該IP數據包的最終目的地。目前，存在兩種版本的IP，IP版本4(「IPv4」)和IP版本6(「IPv6」)。IPv4提供包含在用來存儲IP目的地址的數據包中IP首部中的32位欄位。根據存儲在IP首部中的IP目的地址，如果目的地在本地網，路由器轉發接收到的與下一跳路由器或最終目的地相連的數據包。
一個32位的IPv4目的地址提供40億個可能的路由。一個互連網路由器通常存儲40億個可能的路由中的5萬個路由。然而，存儲的路由數量會隨著互連網的發展和IPv6的普及而增加。
起初，IP位址空間分為A，B和C三類IP位址。每個IP位址空間分為網絡地址和主機地址。A類可容納126個網絡，每個網絡可包含16,000,000臺主機。B類可容納16382個網絡，每個網絡可包含64,000臺主機，以及C類可容納2,000,000個網絡，每個網絡可包含256臺主機。然而，將IP位址空間劃分為不同的類減少了可用IP位址的數量。C類只允許每個網絡最多256臺主機對於大多數組織來說太少了。因此，大多數組織分配到一個B類地址，多達64,000個主機地址，這些地址即使該組織用不了也不能由其它組織使用。具有B類IP位址的組織的主機都在16位最高有效位(「MSBs」)中存儲相同的網絡地址，例如27.32.xx.xx。
引入無級域間路由(「CIDR」)以便釋放未使用的IP主機地址。剩餘的未使用網絡分配給規模不同的組織。一個需要500個地址的組織得到500個連續的地址。例如，一個組織可以分配到以128.32.xx為起始的500個可用地址。自從引入了無級域間路由，增加了存儲在路由器中的路由數量。無級域間路由需要最長前綴匹配來尋找相應路由來代替為找到相應的IP目的地址的下一跳而尋找匹配的網絡地址。例如，因為128.32.4.xx可能已經分配給其它需要不同下一跳的組織，所以在B類IP位址的16MSB，例如128.xx.xx之後，不再停止尋找。
一種用來查詢關鍵字最長前綴匹配的方法是使用二叉樹搜索。二叉樹搜索與輸入的32位逐位匹配到32層，需要32次搜索才能找到與32位關鍵字匹配的入口。另一種搜索匹配的方法是使用Patricia樹。如果二叉樹沒有入口的葉子，Patricia樹減少所需的搜索次數。
Brodnick等人於1998年5月11日提交的題為「快速路由查詢的方法和系統」，序號為PCT/SE98/00854的PCT申請中描述了有效地搜索與IP目的地址有關的下一跳的另一種方法。Brodnick描述的方法通過不再存儲重複路由來減少所存儲的下一跳的數量。通過減少下一跳的數量，減小了對內存的需求，因此路由查詢表可以存儲在快速超高速緩衝存儲器中。
Brodnick等人將二叉樹劃分為三層。將二叉樹劃分為三層使搜索次數減少到三。第一層中的索引入口表示搜索是否可以利用從入口獲得的路由在第一層結束，或者該搜索必須利用IP目的地址另外的部分將繼續到下一層。
圖1A說明了表示二叉樹第一層的現有技術的64K(65536)位表。64K位表30代表在深度16層的二叉樹的葉子或節點44，每個節點44對應一位。位表被劃分為長度為16的位屏蔽。在64K位表中共有212＝4096個位屏蔽。圖1A中顯示了一個位屏蔽。如果有子樹或路由索引存儲在與節點44對應的指針數組中，則位表30中的一位賦置為「1」。如果該節點與前一節點44共享路由入口，則位表30中的一位賦置為「0」。
圖1B說明了在超高速緩衝存儲器中實現查詢表的當前技術。查詢表包括碼字數組36，基索引數組34和映射表40。圖1B中還顯示了32位IP位址38。針對位表30(圖1A)中的每個位屏蔽，將碼字46存儲在碼字數組36中。碼字46包括一個6位的值46a和一個10位的位移46b。針對碼字數組36的數組中的每四個碼字46，將基索引42存儲在基索引數組34中。
碼字數組36，基索引數組34和映射表40用來在指針數組(未顯示)中選擇指針。指針存儲一個路由索引或一個索引以便執行進一步的搜索。
通過在碼字數組36中選擇碼字46和在基索引數組34中選擇基索引42來在指針數組中選擇一組指針。利用IP位址38的前12位50來選擇碼字46。利用IP位址38的前10位來選擇基索引42。利用映射表32在一組指針中選擇正確的指針。
所選碼字36中10位的值46b作為到映射表32的索引。映射表32將一個位屏蔽中的位數映射到4位的位移。該位移指定在指針數組中所選的一組指針中的指針。10位的值46b選擇映射表32中的行，並且IP位址52的位1916選擇4位的位移54。
這樣，搜索指針需要下面的超高速緩衝存儲器訪問(1)讀取16位碼字46；(2)讀取16位基地址42；(3)從映射表32中讀取4位位移54；(4)從指針索引讀取指針，其中指針索引是基地址42，碼字位移46a和4位位移54之和。
二叉樹的每一層需要同樣的存儲器訪問。這樣，3層的搜索需要訪問存儲器12次。

發明內容
David A.Brown提交的代理案編號2037.2004-001，題為「長匹配地址查詢的方法和裝置」描述了用來執行多層搜索符合關鍵字的值的查詢表。能夠存儲在查詢表中的路由索引的數量由查詢表中存儲單元的數量來限制。
根據本發明的原理，給出包括第一查詢單元和第二查詢單元的查詢表。第一查詢單元接收關鍵字並且通過第一單元中的多層搜索提供第一結果。第二查詢單元接收關鍵字並且通過第二單元中的多層搜索提供第二結果。第一查詢單元和第二查詢單元二者都並行地接收關鍵字，但根據第一結果和第二結果，只有一個單元提供只存儲在一個查詢單元中的關鍵字的最終結果。
根據存儲在查詢表中的最終結果的總數將最終結果分配到表中。關鍵字可以是IP位址，最終結果是IP位址的路由索引。
由關鍵字索引的第一查詢單元中的第一存儲單元存儲最終結果，由關鍵字索引的第二查詢單元中的第二存儲單元存儲最終結果存儲在第一查詢單元的指示。第一查詢單元和第二查詢單元都包括多個映射程序層並且每一個映射程序層包括用於存儲結果的存儲單元。
在一個實施例中，把與存儲在第一查詢單元中的多個映射程序層的任何一層中的單元中的關鍵詞對應的最終結果轉發到第二查詢單元，並由第一查詢單元提供。
在另一個實施例中，由存儲最終結果的查詢單元提供與該關鍵字對應的最終結果。


圖1A示出代表二叉樹第一層的現有技術的位表；圖1B示出在超高速緩衝存儲器中實現的現有技術的查詢表；圖2A示出根據本發明原理的最長匹配前綴查詢表；圖2B示出存儲在圖2A所示的查詢表中的路由索引的二叉樹表示；圖3示出根據本發明原理的40位關鍵字的最長匹配前綴查詢表；圖4示出能夠存儲在圖2A所示的直接映射的映射程序的映射程序入口的類型；圖5示出對應圖2B所示的映射程序層2 112b中的節點的映射程序；圖6A是子樹的二叉樹表示；圖6B示出對應圖6A所示的子樹底層中的節點的圖5所示的數據欄位中存儲的密集子樹描述符。
圖7示出圖5所示的ptr欄位；圖8示出圖5所示的映射程序地址邏輯；圖9是說明搜索最長匹配的步驟的流程圖；圖10A示出提供深度擴展的實施例；
圖10B示出圖10A所示的實施例中的一個查詢表；圖10C示出通過提供深度擴展來增加可用於存儲值的映射程序入口數量的另一個實施例；圖10D示出圖10C所示的實施例中的副查詢表；圖11A-B示出在圖10A和10C所示查詢表中的映射程序入口中圖2B所示路由索引的二叉樹表示中節點分配的二叉樹表示。
圖12是說明在圖10A和10C所示的查詢表中的映射程序入口中分配值的方法的流程圖；圖13是說明搜索與圖10C所示的查詢表中一個映射程序入口中存儲的搜索關鍵字對應的值的方法的流程圖；圖14是說明搜索與圖10A所示的查詢表中一個映射程序入口中存儲的搜索關鍵字對應的值的方法的流程圖；圖15示出由第一映射程序層索引的第二映射程序層中稀疏子樹和密集子樹的二叉樹表示；圖16A-C示出在圖5所示子樹入口和圖4所示子樹入口中數據欄位和指針欄位的修改以便在子樹入口中允許存儲多個稀疏子樹描述符；圖17示出圖8所示位移邏輯中稀疏模式子樹邏輯以選擇稀疏居住子樹中節點的塊位移；圖18示出圖17中位移邏輯中所示的稀疏模式邏輯；圖19A-D示出在稀疏居住子樹中為節點選擇塊位移；圖20是說明圖8所示指針邏輯中稀疏模式基本選擇邏輯的方框圖；圖21示出在子樹存儲器中存儲的密集子樹描述符和稀疏子樹描述符；圖22是說明向為稀疏居住子樹和密集居住子樹中的節點存儲路由的子樹映射程序中的映射程序入口提供映射程序地址的方法的流程圖；圖23示出將要加到查詢表的新路由的二叉樹表示；圖24示出更新處理器存儲器中存儲的路由；圖25示出查詢表中存儲的圖23所示的新路由；圖26是說明向圖25所示查詢表中增加新路由的步驟的流程圖。
本發明前面所述的及其它目的，特徵和優點將通過下面參考本發明實施例的具體描述更加顯而易見，不同附圖中的相同部分用同一參考符號表示。附圖不必放大，強調只起說明本發明原理的作用。
具體實施例方式
下面描述本發明的優選實施例。密集模式圖2A示出根據本發明原理的最長匹配前綴查詢表100。查詢表100提供對應關鍵字104的路由索引102。路由索引102用來訪問對應IP目的地址的下一跳。在圖2A所示的實施例中，關鍵字104為32位，但是關鍵字104不必限制在32位。查詢表100包括3個映射程序106a-c。每個映射程序106a-c包括獨立的地址存儲器。對應關鍵字104的路由索引102或預設路由索引存儲在映射程序106a-c之一的一個單元中。如果需要搜索多個映射程序，來自每個映射程序的映射程序輸出110a-c存儲在延遲存儲器150a-c中，直到所有映射程序106a-c已訪問了關鍵字。
多路復用器108選擇轉發到多路復用器108輸入端中的一個映射程序輸出110a-c作為路由索引102。根據映射程序輸出110a-c的最高有效位(「MSB」)來選擇映射程序輸出110a-c。僅當映射程序輸出110a-c包括路由索引102時，將映射程序輸出110a-c的MSB置為「1」。
圖2B說明了圖2A所示的查詢表100中映射程序106a-c中存儲的入口的二叉樹表示。結合圖2A來描述圖2B。32位關鍵字104可以表示為32層二叉樹。二叉樹實現需要32次搜索，以便按位向下搜索到32層。為減少搜索次數，將32層的二叉樹分為每個映射程序層112a-c對應一個映射程序106a-c(圖2A)的3個映射程序層112a-c。映射程序層1 112a包括32層二叉樹的前16層。然而，為簡單起見，圖2B中只顯示了16層中的5層。映射程序層2 112b包括32層二叉樹接下來的8層，圖2B顯示了8層中的3層。映射程序層3包括32層二叉樹的最後8層，圖1B顯示了8層中的3層。每個映射程序層112a-c包括多個節點。將32層這樣分配，使映射程序層1 112a中包括16層(關鍵字104的16MSB)，映射程序層2 112b中包括8層以及映射程序層3中包括8層對當前存儲器技術顯然是最適宜的；然而，本發明不受這種配置的限制。
取代對關鍵字104的前16位進行16次分別的逐位搜索，而是將與關鍵字104的前16位有關的路由索引102存儲在映射程序106a中(圖2A)。映射程序106a(圖2A)直接由關鍵字104的前16位MSBs索引。根據前一個映射程序106a是否存儲了用於訪問與關鍵字104有關的下一跳信息的路由索引102來搜索接下來的映射程序106b。
如圖2B所示，映射程序層1 112a所示的節點或葉子包括分別標為r0和r1的兩個路由114，116，以及分別標為s0和s1的指向映射程序層2 112b中1304和13023的兩個指針。對應每個路由114，116的路由索引102存儲在L1映射程序106a中。另外，為子樹索引1304存儲L2映射程序106b的地址指針120，為子樹索引13023存儲L2映射106b的地址指針(未示出)。在映射程序106a中的映射程序入口1404中為子樹索引1304存儲的地址指針120表示為了尋找與關鍵字104有關的路由索引102所需的下一層的搜索。
樹中任何節點的值可以通過跟蹤從根114開始的路徑來確定。所示二叉樹中的每個節點有兩個子節點，右子節點和左子節點。如果父節點為「1」，選擇右子節點。如果父節點為「0」，選擇左子節點。跟蹤從根114到節點116的路徑，對於所有MSB置為「010」的關鍵字，r1作為路由索引102存儲在L1映射程序106a中。跟蹤從根114到s0節點1304的路徑，對於所有MSBs置為「00011」的關鍵字，s0存儲在L1映射程序106a中。
L1映射106a是直接映射的映射程序並且存儲映射程序層1 112a的底層的每個底層節點或葉子的路由索引102。映射程序層1 112a的底層是32層二叉樹的第16層。第16層有64K個節點。但是，為了說明的目的，所示映射程序層1 112a的底層作為32層二叉樹的第五層顯示。L1映射程序106a所示的路由索引102對應映射程序層1 112a的第五層節點1301-13032。跟蹤從根節點114到第五層節點1301，1302，1303的路徑，路由索引102為r0。因此r0存儲在L1映射程序106a的位置1401，1402，1403中；即在索引00000，00001和00010。節點1304存儲子樹索引s0，因此s0存儲在L1映射程序106a中地址為00011的位置1404。類似地，第五層節點1305-1308的路由索引102是r0，因此r0存儲在L1映射程序106a中地址為00100，00101，00110和00111的位置1405，1406，1407，1408。對應第五層節點1309-13012的路由索引102是r1，因此r1存儲在L1映射程序106a中地址為01000和01001的位置1409，14010。
在L1映射程序106a的每個位置存儲直接分配給第五層節點3001-30032或通過第五層節點3001-32的父節點分配或指向下一個映射程序106b-c的地址指針的路由索引102。映射程序層3 106c包括在32層二叉樹底層的節點138的主節點h0和在節點140的主節點h1。對主節點的搜索需要搜索關鍵字104的所有位。如圖2A所示，h0的路由索引102存儲在L3映射程序106c中的位置1464中。與L1映射程序106a不同，L2映射程序106b和L3映射程序106c不是直接映射。
在映射程序106b和106c中，不為每個可能的輸入而存儲路由索引102。僅當節點的路由索引102與映射程序106b-c中存儲的前一個路由索引102不同時才存儲路由索引102。請看映射程序層2 112b中所示的第一子樹A中的第三層節點，節點1321和節點1322的路由索引102是r0，因此r0對應的路由索引存儲在L2映射程序106b中的節點1321和節點1322對應的位置1421中。節點1322的子樹索引存儲在位置1422中。與第三層節點1324和第三層節點1325和1326有關的路由索引102為r0，與存儲前一個節點1322的s0不同，r0存儲在L2映射程序106b中的下一個位置1423。因為節點1327不與前一節點1326共享同一路由，所以對應節點1327的路由r2存儲在L2映射程序106b中的位置1424中。為下一個第三層的節點1327存儲子樹索引s3，因此，s3存儲在L2映射程序106b中的位置1425中。由於僅當與前一節點的路由不同時才存儲路由索引，因此減少了用於存儲路由索引102所需的內存。如圖所示，只需要L2映射程序106b中的5個位置來存儲映射層2 112b中第一子樹A的8個第三層節點1321-8對應的路由索引。對於非直接映射106b、106c將在後面結合圖5詳細描述。
圖3說明了根據本發明原理的對應40位關鍵字210的最長匹配前綴查詢表200。在一個實施例中，40位關鍵字包括8位前綴和32位IP位址。8位前綴可以是與32位IP位址有關的虛擬專用網(「VPN」)的標識符。查詢表200包括4個映射程序106a-d。如結合圖2A所描述過的，映射程序106a是直接映射的映射程序。映射程序106b-d是間接映射。映射程序106a存儲路由索引102或對應40位關鍵字210的16個MSB的L2映射程序106b的子樹索引。這樣，L1映射程序具有64K個可能的位置，第一映射程序層112a(圖2B)的64K個節點中的每一個節點對應一個位置。存儲在L1映射程序106a中對應位置的L1映射程序入口數據220a轉發到管道208和L2間接映射程序106b。如果L1映射程序入口數據220a表明下一層的搜索需要利用關鍵字210b接下來的8位，那麼根據關鍵字210b接下來的8位和L1映射程序入口數據220a在L2間接映射程序106b中執行搜索。
第二層搜索的結果提供在轉發到管道208和L3間接映射程序106c的L2映射程序入口數據220b上。根據關鍵字210c接下來的8位和L2映射程序入口數據220b，在L3間接映射程序106c中執行第三層搜索。
搜索結果提供在轉發到管道208和L4間接映射程序106d的L3映射程序入口數據220c上。L3映射程序入口數據220c根據關鍵字210d的最後8位和L3映射程序入口數據220c來確定是否在L4間接映射程序106d中執行第四層搜索。
第四層的搜索結果提供在L4映射程序入口數據220d上。與關鍵字210的最長匹配前綴有關的路由索引102隻存儲在映射106a-d其中一個的一個位置。因此，轉發到管道208的路由索引102隻包含在映射程序入口數據220a-d之一中。如果在映射程序106a-d的其中一個中找到路由索引102，例如在106b中，則不需要對餘下的映射程序106c-d進行搜索和訪問。管道208包括用來選擇映射程序入口數據220a-d之一中包含的路由索引102的多路復用器108(圖2A)。例如，映射程序入口數據220a-d的MSB能夠提供是否包含路由索引的指示。
通過將管道208與映射程序106a-d結合使用，可以並行執行對具有不同關鍵字210的最長匹配前綴表200的多重搜索。管道208通過存儲與40位關鍵字210有關的每個映射程序106a-d的映射程序入口數據220a-d，允許並行執行40位查詢表200的多重搜索，直到映射106a-d的每個搜索都已完成，如果必要，尋找對應40位關鍵字210的路由索引。因此，對應所接收的IP位址的路由索引的搜索請求通過對直接映射的映射程序106a執行一次內存訪問來發送給查詢表200。對應於另一個關鍵字的路由索引的後繼搜索可以在直接映射的映射程序106a的下一個內存訪問循環時發送給查詢表200。
圖4說明了能夠存儲在圖3所示的直接映射的映射程序106a中的映射程序入口的類型。圖2B所示的二叉樹中任何節點對應的映射程序入口能夠存儲非入口300，路由入口302或子樹入口描述符304。映射程序入口300，302，304中每一種類型包括一個子樹標記306。子樹標記306的狀態表示映射程序入口是否為子樹入口描述符304。如果子樹標記306置為「1」，映射程序入口是子樹描述符304並且包括子樹索引312。子樹索引312是下一個非直接映射的映射程序106b-d中存儲的子樹入口描述符304的地址。子樹入口將在後面結合圖4進行描述。如果子樹標記306為「0」，將檢查非入口標記314來確定映射程序入口是非入口300還是路由入口302。如果非入口標記314是「0」，該入口則是非入口300。如果非入口標記314為「1」，該入口則是路由入口302，並且在路由索引欄位310存儲中與關鍵字104有關的路由索引102(圖3)。多路復用器108(圖2A)利用子樹標記306來選擇包括路由索引102(圖3)的映射程序入口數據220a-d。
圖5說明了對應圖2B所示的映射層2 112b中的節點的映射程序106b。映射106b包括子樹內存400，映射程序地址邏輯402和子樹映射程序418。把由存儲在映射程序106a中的關鍵字210a的第一部分選擇的子樹索引312轉發到子樹內存400。子樹內存400包括由子樹索引312選擇的子樹入口404。子樹入口404包括數據欄位406和指針欄位408。
返回圖2B，子樹入口404對應映射程序層2 112b所示的一個子樹的底層。如果映射程序層2 112b有8層，每個子樹(未示出)的底層具有最多256條路由，每個節點一個路由。
繼續到圖5，子樹入口404提供對與子樹底層上的每個節點對應的256個可能的路由索引102(圖3)的訪問。路由索引102(圖3)存儲在子樹映射程序418中。為提供對256個可能的路由索引的訪問，密集子樹描述符存儲在數據欄位406中。數據欄位406有256位寬，為在子樹底層的每個節點提供一位。數據欄位將在後面結合圖6A和圖6B詳細描述。指針欄位408有256位寬，允許存儲16個16位指針，每個指針存儲子樹映射程序418中16個相鄰映射程序入口的基地址，以便提供對256個路由索引的訪問。因此，指針欄位408可以為子樹底層中的每個節點間接地提供到子樹映射程序418中的映射程序入口的指針。將結合圖6詳細描述指針欄位408。
把存儲在數據欄位406的密集子樹描述符中的子樹數據412和存儲在指針欄位408中的子樹指針414轉發到映射程序地址邏輯402。映射程序地址邏輯402還接收關鍵字210b的下一部分(接下來的8位)。
映射程序地址邏輯402根據與子樹有關的關鍵字212b接下來的8位，子樹數據412和子樹指針414來確定與子樹底層中的節點有關的映射程序入口的映射程序地址416。映射程序地址416在子樹映射程序418中選擇映射程序入口。子樹映射程序418包括直接映射的映射程序106a的與結合圖4所述類型相同的映射程序入口。映射程序數據入口220b的內容確定是否需要後繼搜索。如果映射程序入口數據220b包括表明在下一個映射層112c(圖2B)還有另一個子樹入口404的子樹索引312(圖4)，則需要後繼搜索。
關鍵字210b的第二部分選擇所選子樹底層中的節點。子樹指針414選擇與子樹中的節點有關的基地址，子樹數據412選擇與基地址有關的映射入口模塊中的位移。映射程序地址邏輯402將結合圖7在後面描述。
圖6A是子樹的二叉樹表示。所示子樹包括5層。該子樹包括三個路由索引r1，r2和r3以及兩個子樹索引s0和s1。子樹底層上有32個節點5001-50032。下面的表1顯示了與底層中的每個節點5001-50032有關的路由索引或子樹索引。
子樹位 路由/子樹00000r000001r000010r000011r000100r100101r100110r000111r001000r201001s001010r201011r201100r201110r201111r21xxxxr3表1圖6說明了對應圖6A所示的子樹底層中的節點的圖5所示的數據欄位406中存儲的密集子樹描述符。數據欄位406包括32位，圖6A所示的子樹底層中的每個節點500對應一位。位5021-50232在數據欄位406中是這樣分配的如果要使用前一個節點的路由索引，那麼數據欄位中的一位設定為『0』，如果使用存儲在子樹映射程序418(圖5)中的下一個路由索引，那麼設定『1』遞增到下一個映射入口地址。除非指定了路由，否則數據欄位402中的第一位選擇存儲在映射程序入口5041中的預設路由r0。這樣，由於沒有指定的路由，把位5021設定為『0』來選擇預設路由。為接下來三個節點5002-5004選擇映射程序入口5041中存儲的預設路由r0，因此，在數據欄位406中的對應位5022-5024被設定為「0」，以使用5021使用的前一個路由索引。在節點5005存在路由改變。
節點5006共享用於映射程序入口5042中存儲的節點5005的路由r1。因此位5025是『1』表示路由改變，以便在子樹映射程序418(圖5)中選擇映射程序入口5042。位5026是『0』表示把5025中存儲的路由索引用於該節點。不為節點5007提供路由，因此，存在著路由變化，並且在位5027中存儲『1』來表示需要在子樹映射程序418(圖5)中的映射程序入口5043存儲預設路由r0。
節點5008與前一個節點5007共享同一個路由，在子樹映射程序418(圖5)中不需要新的映射程序入口。對應節點5008的位5028設定為「0」。節點5009與前一個節點5008具有不同的路由，因此在子樹映射程序418(圖5)中需要新的映射程序入口。對應節點5009的位5029設定為「1」，並且將存儲r2的映射程序入口5044添加到下一個相鄰存儲單元中的子樹映射程序418(圖5)。
節點50010與前一個節點5009具有不同的路由，在子樹映射程序418(圖5)中需要新的路由入口。對應節點50010的位50210設定為「1」，並且將存儲s0的映射程序入口5045添加到下一個相鄰存儲單元中的子樹映射程序418(圖5)。
節點50011與前一個節點50010具有不同的路由，在子樹映射程序418(圖5)中需要新的映射程序入口。對應節點50011的位50211設定為「1」，並且將存儲r2的映射程序入口5046添加到下一個相鄰存儲單元中的子樹映射程序418(圖5)。
節點50012和50013共享與前一個節點50011相同的路由，在子樹映射程序418(圖5)中不需要新的映射程序入口。在數據欄位406中把對應於節點50012的位50212和對應於節點50013的位50213設定為『0』。
節點50014與前一個節點50013具有不同的路由，在子樹映射程序418(圖5)中需要新的映射程序入口。數據欄位406中對應節點50014的位50214設定為『1』，並且把存儲s1的映射程序入口5047添加到下一個相鄰存儲單元中的子樹映射程序418(圖5)。節點50015與前一個節點50014具有不同的路由，在子樹映射程序418(圖5)中需要新的映射程序入口。數據欄位406中對應節點50015的位50215設定為『1』，並且將存儲r2的映射程序入口5048添加到下一個相鄰存儲單元中的子樹映射程序418(圖5)。節點50016與前一個節點50015共享同一個路由，在子樹映射程序418(圖5)中不需要新的映射程序入口。
節點50017與前一個節點50016具有不同的路由，在子樹映射程序418(圖5)中需要新的映射程序入口。將數據欄位406中對應節點50017的位50217設定為『1』，並且將存儲r3的映射程序入口5049添加到下一個相鄰存儲單元中的子樹映射418(圖5)。
節點50018-50032全部與前一個節點50017共享相同的路由，在子樹映射程序418(圖5)中不需要新的映射程序入口。將對應的位50218-50232設定為『0』。這樣就需要9個映射程序入口5041-9來存儲32個節點5001-50032的路由入口302(圖4)或子樹入口304(圖4)。
通過計算在數據欄位406中存儲的密集子樹描述符中存儲的『1』的數量在子樹映射程序418(圖5)中索引與節點5001-50032對應的映射程序入口5041-5049。例如，為尋找對應節點50028的映射程序入口5041-5049，計算數據欄位406的位5021-50228中存儲『1』的數量。『1』的數量是8，並且對應的映射程序入口是從預設路由開始的第八個位置，即映射程序入口5049。
僅當路由發生變化時才存儲映射程序入口的方法減少了子樹映射程序418(圖5)中每個子樹映射程序入口5041-5049的數量。
圖7說明了圖5所示的指針欄位408。指針欄位408包括用於存儲子樹映射程序418(圖5)中幾組16個相鄰映射程序入口位置5041-50416組(圖6B)的基地址的塊基地址欄位6001，6002。在16個相鄰映射程序入口的組6021，6022的子樹映射程序418(圖5)中分配內存。8層的子樹可以具有多達256個不同路由，需要16個組6021，6022來存儲所有256個路由。根據子樹的路由數量來確定所需組602的數量。通過從塊基地址的空閒列表中(未顯示)刪除塊基地址6021，6022來將組602分配給特定的子樹。為內存提供地址空閒列表的方法是已知的技術。
通過分配16個映射程序入口5041-16的內存塊，由於所分配的16個位置是相鄰的，所以子樹映射程序418(圖5)中的內存易於管理。
圖8說明了圖5所示的映射程序地址邏輯402。映射程序地址邏輯402包括位移邏輯700，指針邏輯702和加法器邏輯704。位移邏輯700包括節點選擇邏輯706和「1」計數邏輯708。指針邏輯包括基地址選擇邏輯710。
節點選擇邏輯706選擇在子樹數據412中對應8位關鍵字210b的節點500(圖6B)。相應的節點數通過節點選擇718轉發到『1』計數邏輯708。『1』計數邏輯708累計子樹數據欄位406中存儲的『1』的數量，直到與所選節點500對應的位。『1』的數量通過塊選擇712轉發到指針邏輯702並且通過塊位移714轉發到加法器邏輯704。
需要8位寬的計數欄位的256位子樹數據欄位406中最大可存儲256個「1」。8位計數欄位分為兩個欄位，提供塊選擇712的4個MSB和提供塊位移714的4個最低有效位(「LSB」)。
例如，如果8位的關鍵字210b為『01000100』，為選擇節點數68並且共有27個「1」存儲在子樹數據42的前68位，計數結果為IC Hex(0001 1100)，MSB(0001)；即塊選擇714選擇塊6021(圖6)和LSB(1100)；即基塊位移選擇映射程序入口50411(圖6)，即塊5021中的第12個入口。
基地址選擇邏輯710根據從位移邏輯700轉發的塊選擇712從子樹指針414中選擇基地址716。加法器邏輯704將從位移邏輯700轉發的塊位移714累加到基地址716，並且提供映射程序地址416。映射程序地址416是映射程序106b-d中映射程序入口504(圖6B)的索引。
圖9是根據本發明原理用於在查詢表200中搜索關鍵字210(圖3)的最長匹配前綴的步驟的流程圖。
在步驟800中，把關鍵字210a(圖3)的第一部分作為索引轉發到映射程序106a。處理過程繼續到步驟802。
在步驟802中，由關鍵字210a(圖3)的第一部分索引的第一層映射程序中的映射程序入口504(圖6B)中存儲的映射程序入口數據220a(圖3)確定是否需要繼續對下一層進行搜索。如果需要，處理過程繼續到步驟804。否則，第一層映射程序中索引的映射程序入口504(圖6B)中的路由入口302(圖4)存儲該關鍵字的最長前綴路由並且處理過程繼續到步驟808。
在步驟804，搜索下一層映射程序106b-d。下一層映射程序的索引取決於前一層映射程序中索引的映射程序入口504(圖6B)中子樹入口描述符304(圖4)中存儲的子樹索引312和關鍵字210b-d的下一部分。處理過程繼續到步驟806。
在步驟806中，下一層映射程序中的索引映射程序入口504(圖6B)存儲該關鍵字對應的最長前綴路由索引或表示需要進一步搜索的子樹索引。如果需要進一步搜索，處理過程繼續到步驟804。否則，處理過程繼續到步驟808。
在步驟808，把映射程序106a-d之一中的一個映射程序入口504(圖6B)中存儲的路由索引102(圖3)作為路由索引102(圖3)從查詢表200轉發。處理過程結束。深度擴展能夠存儲在圖3所示查詢表200中的路由索引102(圖3)的數量受子樹映射程序418(圖5)中可用映射程序入口504(圖6B)的數量的限制。例如，如果每個子樹映射程序418(圖5)包括128K個映射程序入口並且在查詢表中有兩個子樹映射程序418(圖5)，那麼查詢表200中最多可以存儲256K個路由索引102(圖3)。具有128K個映射程序入口的子樹映射程序418(圖5)需要一個17位的索引。具有512K個映射程序入口的子樹映射程序418(圖5)需要一個19位的索引。查詢表200中2個512K的子樹映射程序418(圖5)為32位IPv4目的地址的40億個可能的路由索引102(圖3)中1百萬個提供了存儲空間。
通過提供多個查詢表200可以增加用於存儲路由索引102(圖3)的映射程序入口504(圖6B)的數量。可以在多個查詢表中並行地搜索與查詢表200之一中的子樹映射程序418(圖5)中的映射程序入口504(圖6B)中存儲的搜索關鍵字對應的值。
圖10A說明了深度擴展的實施例。示出兩個查詢表，一個為主查詢表200a，另一個為副查詢表200b。但是，查詢表的數量不只限於所示的兩個，可以增加一個以上的副查詢表200b。
以相同的搜索關鍵字210並行搜索查詢表200a-d中的每一個。對應於搜索關鍵字210的路由索引102(圖3)存儲在查詢表200a-d之一中的子樹映射程序418(圖5)中，或查詢表200a和200b二者中的直接映射程序106a中。在完成對查詢表200a和200b的並行搜索後，找到最終路由索引900。
圖10B說明了圖10A所示實施例中的查詢表200a中的一個。查詢表200a-b中的每一個包括映射程序106a-d和已經結合圖3針對查詢表200描述過的管道208，以及驅動器邏輯902。查詢表200a為與搜索關鍵字對應的路由索引在映射程序106a-d中執行多層搜索。每一層的搜索結果通過映射程序入口數據220a-d轉發到管道208。管道208再將搜索結果904轉發到驅動器邏輯902。每個查詢表200a-b中映射程序106a中的映射程序入口504(圖6B)存儲子樹入口304(圖4)，但只有主查詢表200a的映射程序106a存儲路由入口302(圖4)。副查詢表200b中映射程序106a中的映射程序入口504(圖6B)代替路由入口302存儲非入口300(圖4)。將映射程序106a中的路由索引集中在一個查詢表避免了為提供最終路由索引900的查詢表的選擇過程。這導致了副查詢表200b中不能用於存儲路由索引而只允許存儲相同查詢表的64K內存配置成主查詢表或結合圖3所述的副查詢表。在另一個實施例中，可以提供沒有映射程序106a的副查詢設備。如果路由索引102(圖3)存儲在映射程序106a中的路由入口302(圖4)，那麼搜索在主查詢表200a中的映射程序106a中結束。
如圖10A所示，主查詢表200a和副查詢表200b共享最終路由索引900。存儲了最終路由索引900的查詢表200a，200b提供路由索引102(圖3)。如果每個查詢表200a，200b是獨立的設備，共享最終路由索引900減小了每個設備的外部引腳數量。只有查詢表200a，200b中的一個隨時驅動最終路由索引。
為避免兩個查詢表200a，200b中存儲與搜索關鍵字210有關的路由索引而會使兩個查詢表同時驅動最終路由索引900的錯誤狀態，每個查詢表200a，200b存儲一個設備代碼。3位的設備代碼允許擴展的查詢表包括8個設備。
驅動器邏輯902確定搜索結果904是否包括路由索引102(圖3)。如果包括，查詢表200a中的驅動器邏輯902發出試圖通過總線請求信號(未示出)驅動最終路由索引900的信號。如果兩個或更多的查詢表200a，200b同時發出試圖驅動路由索引信號的信號，那麼由具有最低設備代碼的查詢表200a，200b中提供路由索引。通過使用總線請求信號來解決總線衝突的方法是熟知的技術。
圖10C說明了用來提供深度擴展以增加可用於存儲與搜索關鍵字210對應的值的映射程序入口數量的另一個實施例。在圖10C所示的實施例中，提供兩個查詢表200c-d來存儲值，主表200c和副表200d。但是查詢表的數量不只限於所示的兩個，可以通過加入更多的副表200d來增加映射程序入口的數量。在查詢表200c-d中並行執行對與搜索關鍵字[390]210對應的查詢表200c-d之一中的映射程序入口中所存儲的值的搜索。
圖10D說明了圖10C所示的實施例中的副表200d。每個查詢表包括結合圖3針對查詢表200描述的映射程序106a-d。每個查詢表200c-d中映射程序106a中的映射程序入口存儲子樹入口304(圖4)。每個查詢表200c-d將映射程序106a中映射程序入口504(圖6B)裡存儲的子樹入口描述符304(圖4)中存儲的子樹索引312轉發到下一個映射程序106b-d。但是，路由索引102(圖3)只存儲在主查詢表200c的映射程序106a中。無入口存儲在副查詢表200d中的映射程序106a中以避免在一個以上的查詢表200b，200d中存儲與該關鍵字對應的路由索引。
副查詢表200d中的多層搜索結果904轉發到最終索引邏輯1004。最終索引邏輯1004將多層搜索結果904或從主查詢表200c轉發來的輸入結果1000a作為輸出結果1002a轉發。如果路由索引102(圖3)包括在多層搜索結果904中，那麼將多層搜索的結果作為輸出結果1002a轉發。如果路由索引102(圖3)包括在輸入結果1000a中，那麼將輸入結果1000a作為輸出結果1002a轉發。如果路由索引102(圖3)既不包括在輸入結果1000a，也不包括在多層搜索結果904中，那麼將多層搜索結果904作為輸出結果1002a轉發。
如圖10C所示，主查詢表200c和副查詢表200d通過標有輸入結果1000a的公共總線相連。路由索引102(圖3)只通過輸出結果1002a從副查詢表200d轉發。如果有一個以上的副查詢表200d，最後一個副查詢表提供擴展查詢表的路由索引102(圖3)。本實施例可以避免實現結合圖10A所述的多驅動器最終路由索引900的出現，但需要更多用於輸入結果1000a的設備外部引腳。
圖11A-B說明了在查詢表200a-b(圖10A)或200c-d(圖10C)中分配圖2B所示路由的二叉樹表示。
圖11A說明了主查詢表200a(圖10A)或200c(圖10C)中存儲的路由的二叉樹表示。主查詢表200a中不包括圖2B所示路由的二叉樹表示中所示的子樹B。節點1301-13022和13024-32在結合圖3所述的查詢表200a中的映射程序106a中編碼。如果存儲在主查詢表200a中，那麼在那裡索引子樹B的節點用「X」圖形化地表示為已修剪子樹。在主查詢表200a中對應節點13023的映射程序入口504(圖6B)不再存儲指向子樹B的子樹索引312(圖4)。取而代之的是非入口300(圖4)存儲在主查詢表200a中對應節點13023的映射程序入口504(圖6B)中，以表示對應節點13023的映射程序入口存儲在另一個副查詢表200b的子樹映射程序418(圖5)中。
圖11B說明了存儲在副查詢表200b(圖10A)或200d(圖10C)中子樹映射程序418(圖5)中的映射程序入口504(圖6B)的路由的二叉樹表示。與圖2B所示二叉樹表示不同，存儲在副查詢表200b中的路由的二叉樹表示不包括子樹A。因此，節點1301-1303和1305-13032以如結合圖2B所述的那樣進行編碼。對應副查詢表200b中節點1304的映射程序入口504(圖6B)不再存儲指向子樹A的子樹索引312(圖4)。取而代之的是對應副查詢表200b中節點1304的映射程序入口存儲非入口300(圖4)以表示對應節點1304的映射程序入口存儲在另一個查詢表中。子樹A對應的子樹索引和主機138(圖11A)對應的路由索引存儲在主查詢表200a中，並且子樹B對應的子樹索引和主機140(圖11A)對應的路由索引存儲在副查詢表200b中。副查詢表200b，200d只存儲子樹的結果；就是說，副查詢表200b，200d不存儲第一層映射程序106a中的結果。
參考圖11A和圖11B，利用關鍵字210a的第一部分對主映射程序層1 1102a(圖3)或副映射程序層1 1104a中任何節點1309-13012的搜索產生了主查詢表200a，200c中映射程序106a中映射程序入口504(圖6B)中路由入口302(圖4)中存儲的r1 116以及副查詢表200b，200d中映射程序106a中映射程序入口504(圖6B)中存儲的非入口300(圖4)。主查詢表200a，200c中存儲的路由入口302(圖4)通過輸入結果1000a轉發到副查詢表200b，200d並且通過輸出結果1002a由副查詢表200b，200d轉發。
利用關鍵字210a的第一部分對節點1304的搜索產生了主查詢表200a中映射程序106a的映射程序入口504(圖6B)中子樹入口描述符304(圖4)中存儲的子樹A的子樹索引312(圖4)。子樹索引312轉發到主查詢表200a中的映射程序106b來繼續對主查詢表200a中存儲的路由入口302(圖4)進行搜索。
利用關鍵字210的第一部分對節點13023的搜索產生主查詢表200a中映射程序106a的映射程序入口504(圖6B)中存儲的非入口300(圖4)以及副查詢表200b中映射程序106a的映射程序入口504(圖6B)中存儲子的樹入口描述符304(圖4)。因此，繼續利用關鍵字210b的下一部分在副查詢表200b的映射程序106b中搜索路由入口302(圖4)。
圖12是說明圖10A所示查詢表200a-b中映射程序入口504(圖6B)中存儲的路由入口302(圖4)的分配方法的流程圖。同樣的方法用於圖10C所示的查詢表200c-d。在查詢表200a-b中存儲之前，最初由處理器(未示出)在存儲器中存儲映射程序入口中要存儲的路由入口302(圖4)。
當路由入口302(圖4)存儲在存儲器中時，計算每個查詢表200a-b(圖10A)中要存儲的路由入口302(圖4)的數量。映射程序層1 1104a(圖11B)的路由入口302(圖4)存儲在查詢表200a的映射程序106a中。映射程序層1 1104a(圖11B)的子樹入口304(圖4)存儲在每個查詢表200a-200b的映射程序106a中。
在步驟1200中，為確定如何在查詢表200a-b(圖10A)中分配路由入口302(圖4)，需要計算每個查詢表200a-200b(圖10A)中映射程序106a的每個子樹入口304(圖4)中要存儲的路由入口302(圖4)的數量。當確定了存儲路由入口302(圖4)所需的映射程序入口504(圖6B)的總數之後，處理過程繼續到步驟1202。
在步驟1202中，將要存儲的子樹的映射程序入口504(圖6B)的總數除以查詢表200a-b(圖10A)的數量以確定存儲在每個查詢表200a-b(圖10A)中的路由入口302(圖4)的數量。處理過程繼續到步驟1204。
在步驟1204中，在所選查詢表200a-b中子樹映射程序418(圖5)的映射程序入口504(圖6B)中存儲路由入口302(圖4)。處理過程繼續到步驟1206。
在步驟1206中，如果在所選查詢表200a-b中子樹映射程序418(圖5)的映射程序入口504(圖6B)中存儲的路由入口的數量小於1/n，其中n表示可用查詢表200a-b(圖10A)的數量，那麼處理過程繼續到步驟1024。否則，所選查詢表200a-b已經存儲了映射程序入口總數的1/n，並且處理過程繼續到步驟1208。
在步驟1208中，所選查詢表200a-b存儲映射程序入口總數的1/n，因為相應子樹的路由索引不存儲在當前所選的查詢表中，所以任何剩餘子樹節點的非入口300(圖4)存儲在所選擇的查詢表200a-b中。處理過程繼續到步驟1210。
在步驟1210中，如果已經存儲了全部路由入口，處理過程結束。否則，處理過程繼續到步驟1212。
在步驟1212中，選擇下一個查詢表200a-b(圖10A)。處理過程繼續到步驟1204。
在搜索對應於IP位址的路由索引之前，在查詢表200a-b(圖10A)中分配路由入口。搜索是在查詢表200a-b(圖10A)中的每一個中並行執行的。用查詢表200a-b(圖10A)中的一個來描述實現對每個查詢表並行搜索的方法。
圖13是說明利用搜索關鍵字搜索與圖10C所示的查詢表200c-d中的任何一個存儲的搜索關鍵字對應值的方法的流程圖。
在步驟1300中，查詢表200c-d(圖10C)中的每一個接收搜索關鍵字210。查詢表200c-d中的每一個中的映射程序106a搜索於關鍵字210a的第一部分對應的值。處理過程繼續到步驟1302。
在步驟1302中，讀取映射程序106a中映射程序入口504(圖6B)中存儲的入口。主查詢表200c中的映射程序入口504(圖6B)可以存儲非入口300(圖4)，路由入口302(圖4)或子樹入口描述符304(圖4)。副查詢表200d中的映射程序入口504可以存儲非入口300(圖4)和子樹入口描述符304(圖4)。如果相應的查詢表200中的映射程序入口存儲路由入口302(圖4)，該入口則是有效值，不需要進一步搜索查詢表200c-d中的後繼映射程序106b-d，處理過程繼續到步驟1310。否則，處理過程繼續到步驟1304。
在步驟1304中，如果入口存儲了子樹入口描述符304(圖4)，那麼需要進一步搜索查詢表200c-d並且處理過程繼續到步驟1306。否則，該入口存儲非入口，表示不需要進一步的搜索，處理過程繼續到步驟1310。
在步驟1306中，在所選子樹中繼續搜索。根據關鍵字210b-d的下一部分和從上一層的搜索得到的子樹索引312(圖4)來搜索下一層映射程序106b-d(圖3)。處理過程繼續到步驟1308。
在步驟1308中，根據從當前層映射程序106b-d中搜索得到的映射程序入口來確定是否繼續執行搜索。如果映射程序入口504(圖6B)存儲了子樹入口描述符304(圖4)，搜索繼續到下一層映射程序106b-d並且處理過程繼續到步驟1306。如果映射程序入口504(圖6B)沒有存儲子樹入口描述符304(圖4)，則不需要作進一步搜索，處理過程繼續到步驟1310。
在步驟1310中，把搜索結果與從另一個查詢表接收的輸入結果作比較。例如，如果查詢表是副查詢表200d，那麼把從主查詢表200c中搜索產生的輸入結果通過輸入結果1000a轉發到查詢表200d，並且與副查詢表200d的搜索結果作比較。處理過程繼續到步驟1312。
在步驟1312中，如果輸入結果1000a與當前查詢表200d中的搜索結果不同，處理過程繼續到步驟1314。如果輸入結果1000a與當前查詢表200d中的搜索結果相同，在分開的查詢表200c-d中的映射程序入口504(圖6B)中已經存儲這兩個有效的結果。不應該相同的關鍵字210來存儲兩個有效結果，處理過程繼續到步驟1316。
在步驟1314中，檢查輸入結果1000a來確定它是否有效。如果輸入結果1000a是路由入口302(圖4)，那麼它是有效的。如果輸入結果1000a是非入口300(圖4)或子樹入口描述符304(圖4)，那麼它是無效的。子樹入口描述符304(圖4)，路由入口302(圖4)和非入口300(圖4)已經結合圖4描述過了。如果輸入結果1000a無效，處理過程繼續到步驟1318。否則，處理過程繼續到步驟1320。
在步驟1318中，輸入結果1000a有效，而從當前查詢表200d中搜索得到的結果無效。輸入結果1000a通過輸出結果1002a從當前查詢表200d轉發。如果當前查詢表200d是最後一個查詢表，那麼輸入結果1000a作為路由索引102(圖3)轉發，或者作為輸入結果1000a轉發到下一個查詢表。處理過程結束。
在步驟1316中，在不同的查詢表中存儲關鍵字的兩個有效的結果值。在查詢表200c-d中存儲路由入口期間發生錯誤時，生成錯誤代碼以便能夠糾錯。處理過程結束。
在步驟1320中，來自當前查詢表200d的搜索結果和輸入結果1000a都無效。即使無效，也將當前查詢表200d的搜索結果作為輸入結果1000a轉發到下一個查詢表。處理過程結束。
圖14是說明搜索與圖10A所示的查詢表200a-b之一中存儲的搜索關鍵字對應的值的方法的流程圖。
在步驟1340中，在兩個查詢表200a-b中的第一層映射程序106a搜索與關鍵字210a的第一部分對應的值。處理過程繼續到步驟1342。
在步驟1342中，如果利用關鍵字210a的第一部分搜索第一層映射程序106a後找到了有效的結果值，則處理過程繼續到步驟1352。否則，處理過程繼續到步驟1344。
在步驟1344中，如果利用關鍵字210a的第一部分搜索第一層映射程序106a得到的值是子樹入口描述符304(圖4)，處理過程繼續到步驟1346。否則，當前查詢表中不存儲關鍵字的有效值，處理過程結束。
在步驟1346中，繼續在以搜索上一層映射程序期間找到的子樹入口描述符304(圖4)中標識的子樹中搜索有效值。根據關鍵字210b-c的下一部分和從搜索下一層得到的子樹選擇在下一層映射程序中搜索一個值。處理過程繼續到步驟1348。
在步驟1348中，搜索結果確定是否需要對下一層進行搜索。從當前搜索得到的入口可以存儲路由入口302，非入口300(圖4)或子樹入口描述符304(圖4)。如果入口存儲了子樹入口描述符304(圖4)，則需要進一步的搜索並且處理過程繼續到步驟1346。如果入口沒有存儲子樹入口描述符304(圖4)，處理過程繼續到步驟1350。
在步驟1350中，如果入口存儲了路由索引102(圖3)，處理過程繼續到步驟1352。否則，將入口存儲在另一個查詢表中。處理過程結束。
在步驟1352中，與該關鍵字對應的有效值存儲在當前查詢表中。有效值作為對應於該關鍵字的路由索引102(圖3)轉發。處理過程結束。稀疏模式返回圖5，子樹入口404對多達256個可能的路由索引中的每一個提供訪問，256個節點字樹中每個節點一個。路由索引存儲在子樹映射程序418(圖5)中的映射程序入口5041-504n中。根據子樹入口404中數據欄位406中存儲的密集子樹描述符和指針欄位408中存儲的子樹指針確定在子樹映射程序418(圖5)中映射程序入口504(圖6B)的映射程序地址416。密集子樹描述符的格式已經結合圖6A-6B描述過了。密集子樹描述符為256個節點的子樹中每個節點存儲一個節點位502(圖6B)。但是，所有子樹針對256個節點中的每一個具有不同的路由索引，例如，一個子樹可能只有一個路由索引。
圖15說明了由第一映射程序層112a中的子樹入口304索引的第二層映射程序層112b中稀疏子樹A和密集子樹B的二叉樹表示。映射程序106a中s1的子樹入口描述符304(圖4)存儲子樹A的子樹入口404的子樹索引312。映射程序106a中s0的子樹入口描述符304(圖4)存儲子樹B的子樹入口404的子樹索引312。
密集集中子樹B有11個路由索引；即，r6-r16和6個子樹入口；即，s2-s7。與存儲路由入口302(圖4)的映射程序入口504(圖6B)和子樹B的子樹入口304(圖4)對應的映射程序地址416在密集子樹描述符中的編碼已經結合圖6B描述過了。
稀疏集中子樹存儲兩個路由索引；即r1和r2。如果它們存儲在密集子樹描述符中，那麼整個子樹入口404用來提供映射程序入口504(圖6B)的三個映射程序地址416；即，r0，r1和r2。
查詢表200中存儲的路由數量可以通過對多個稀疏子樹描述符的其中一個稀疏子樹描述符編碼以及對子樹入口404中密集子樹描述符中的密集集中子樹描述符編碼來增加。
密集集中子樹有16個或更多個映射程序入口504(圖6B)，子樹入口404中的數據欄位406存儲結合圖6A-6B所述的密集子樹描述符。稀疏集中子樹有15個或更少個映射程序入口504(圖6B)；子樹入口404中的數據欄位存儲了多個稀疏子樹描述符。通過提供在稀疏子樹描述符中存儲稀疏集中子樹的能力，子樹存儲器400可以存儲更多的子樹並且查詢表200中可以存儲更多的路由入口。
圖16A-C說明了對圖5所示子樹入口404中數據欄位406和指針欄位408以及圖4所示子樹入口描述符304(圖4)的更改，以便允許在子樹入口404中存儲多個稀疏子樹描述符。
轉到圖16A，以稀疏模式配置的子樹入口404中的數據欄位406包括多個稀疏子樹描述符14001-1400n來代替結合圖6B所述的子樹的每個節點對應一位的密集子樹描述符。每個稀疏子樹描述符14001-1400n包括一個節點描述符14021-1402n。一個節點描述符14001-1402n是代表子樹中完全已編碼路由的一個9位值。節點描述符14021-1402n描述了子樹中一個節點或多個節點。
轉到圖16B，為支持存儲稀疏子樹描述符，在子樹入口404的指針欄位408增加模式欄位1404。指針欄位408還存儲塊基地址6001和塊基地址6002，每個塊包括16個為每個子樹入口404提供總共32個映射程序地址416的已分配映射程序地址416。模式欄位1404存儲模式值。模式欄位1404中存儲的模式值表示子樹入口404中存儲的稀疏子樹描述符14001-1400n的數量和每個稀疏子樹描述符14001-1400n中存儲的節點描述符14021-1402n的數量。表2說明了每個模式對應的子樹入口404的配置。

表2參見表2，例如，如果設置子樹入口404中指針欄位408的模式欄位1404中存儲的模式值為「4」，那么子樹入口404中的每個稀疏子樹描述符1400存儲5到7個節點描述符14021-1402n。每個節點描述符14021-1402n存儲9位。通過每個稀疏子樹描述符14001-1400n的節點描述符14021-1402n的數量乘以9(每個節點描述符14021-1402n的位數)來計算存儲在稀疏子樹描述符1400中的總位數。計算模式4的每個稀疏子樹描述符1400的位數後，具有7個節點描述符1402的稀疏子樹描述符1400存儲63位(7個節點描述符×9位＝63)。
數據欄位406中的位數除以稀疏子樹描述符14001-1400n的位數可以計算出每個子樹入口404的稀疏子樹描述符1400的數量。對於模式4，數據欄位406中的位數為256並且稀疏子樹描述符中的位數為63。因此稀疏子樹描述符14001-1400n的數量為4(int(256/63)＝4)。
每個子樹的節點數乘以每個子樹入口404的子樹數量可以得到每個子樹入口404的節點描述符14021-1402n的總數。計算模式4，如果在稀疏子樹描述符14001-1400n中存儲了7個節點描述符14021-1402n，那麼每個子樹入口404的節點描述符1402的數量為28(7×4＝28)，並且如果每個子樹描述符14001-1400n有5個節點描述符1402，則結果為20(5×4＝20)。
表2中的映射程序入口列表示子樹入口404使用了多少子樹映射程序418(圖5)中的映射程序入口504(圖6B)。通過將每個子樹的節點加1並通過乘以稀疏子樹描述符中的子樹數量來計算映射程序值。每個子樹節點加1是因為需要比每個子樹節點數量多1個映射程序入口，以便存儲子樹的預設入口。
參見表2中模式4的一行，如果每個稀疏子樹描述符1400有7個節點描述符1402，那麼每個子樹入口404需要32((7+1)×4＝32)個映射程序入口，並且如果每個稀疏子樹描述符1400有5個節點描述符1402，那麼每個稀疏子樹描述符1400需要24((5+1)×4＝24)個節點描述符1402。因為在16個塊遞增中分配了子樹映射程序418(圖5)中的映射程序地址416，所以選擇每個子樹節點的數量和每個子樹入口404的子樹數量，以便每個子樹入口404的節點描述符的最大數量不超過30。通過在指針欄位408中存儲兩個塊基地址6001，6002來提供32個映射程序地址416。
轉到圖16C，子樹存儲器400中的每個子樹入口404可以配置成如結合圖6B所述的密集模式或稀疏模式。通過提供表示子樹入口404是否以密集模式或稀疏模式編碼的標誌，將結合圖4所述的子樹映射程序418(圖5)中存儲的密集模式的子樹入口描述符304(圖4)修改為稀疏模式。類型欄位1406提供指示符。
類型欄位1406的狀態表示子樹入口404是按密集模式還是按稀疏模式配置。如果子樹入口404以稀疏模式配置，那麼稀疏子樹描述符選擇欄位1408中存儲的值和子樹索引312用於選擇稀疏子樹描述符1400。稀疏子樹描述符選擇1408將結合圖16在後面作詳細描述。
圖17說明了用於提供塊位移714來選擇稀疏集中子樹的節點的映射程序入口504(圖6B)的圖8所示的位移邏輯700中稀疏模式邏輯1502。稀疏模式邏輯1502根據子樹入口404中稀疏子樹描述符1400存儲的節點描述符1402來提供塊位移714。位移邏輯700還包括密集模式邏輯1500。密集模式邏輯1500包括節點選擇706和用來提供密集集中子樹中用於路由的塊位移714的「1」計數邏輯708。密集模式邏輯1500已經結合圖8描述過了。
如果類型欄位1406的狀態表示子樹入口404以稀疏模式配置，那麼來自子樹入口404的子樹數據412轉發到稀疏模式邏輯1502。結合圖18描述稀疏模式子樹邏輯1502。
圖18說明了圖17中位移邏輯700所示的稀疏模式邏輯1502。稀疏模式邏輯1502包括子樹選擇邏輯1600，多路復用器1602，內容可編址存儲器(「CAM」)1606以及轉換邏輯1604。所選子樹入口404中的數據欄位406中存儲的稀疏子樹描述符14001-1400n通過子樹數據412轉發到位移邏輯700。位移邏輯700將稀疏子樹描述符14001-1400n轉發到稀疏模式邏輯1502中的多路復用器1602。由子樹選擇邏輯1600生成的選擇1614來選擇子樹數據412中的一個稀疏子樹描述符14001。
子樹選擇邏輯1600根據從前一個映射程序層選擇的映射程序入口轉發的稀疏子樹描述符選擇1408的狀態和所選子樹入口404中的指針欄位408中存儲的模式1404生成選擇1614，以便選擇稀疏子樹描述符14001。表3說明了所選稀疏子樹描述符14001和從多路復用器1602通過所選擇的稀疏子樹描述符1610從對應模式4的子樹入口404的多路復用器1602轉發的相應的子樹數據位412。參見表2中模式4的一行，在模式4中，子樹入口404可以存儲4個稀疏子樹描述符。這4個稀疏子樹描述符中的每一個可以以子樹入口404的模式4存儲。這4個稀疏子樹描述符1400中的每一個有63位並且可以存儲7到5個節點描述符1402。因此，這4個稀疏子樹描述符1400中的每一個從63位的邊界開始。第一個稀疏子樹描述符14001存儲在數據欄位406的位620，第二個稀疏子樹描述符14002存儲在數據欄位406的位12563，第三個稀疏子樹描述符14003存儲在數據欄位406的位188126以及第四個稀疏子樹描述符14004存儲在數據欄位406的位251189。稀疏子樹描述符選擇1408選擇數據欄位406中的相應位。例如，看表3，如果稀疏子樹描述符選擇1408是「0001」，那麼選擇第二個稀疏子樹描述符14002並且通過多路復用器1602將256位子樹數據412的位12563從所選擇的稀疏子樹描述符1610轉發到轉換邏輯1604。

表3子樹存儲器400中的每個子樹入口404可以配置成稀疏模式或密集模式。以稀疏模式配置的每個子樹入口404可以配置為能夠通過模式1404存儲每個稀疏子樹描述符1400的不同數量的節點描述符1402。以稀疏模式配置的子樹入口404中所有稀疏子樹描述符1400存儲每個稀疏子樹描述符1400相同數量的節點描述符1402。
可以對節點描述符1402編碼以表示子樹中的多個節點。節點描述符1402表示的多個8位節點通過屏蔽8位中的一些位來識別。為取代利用每個節點描述符1402存儲屏蔽位，使用9位節點描述符1402對節點描述符1402表示的8位寬的節點進行完全編碼。使用運行比特長度編碼來以9位寬的節點描述符1402對8位寬的節點編碼。運行比特長度編碼可以識別8位節點中的哪些位被屏蔽了。
轉換邏輯1604將所選稀疏子樹描述符1400中存儲的9位寬的節點描述符14021-1402n轉換為包括置為「X」位(任意值)的8位CAM值1612並且將8位CAM值1612裝載到CAM 1606。表4顯示了通過轉換邏輯1604將9位節點描述符1402轉換為8位CAM值1612的例子。

表49位代碼列說明了節點描述符1402中存儲的值。看表4的第一行，節點描述符1402中存儲的9位代碼為「101100100」並且對應的8位值「101100XX」存儲在CAM 1606中。轉換邏輯1604通過在9位代碼中從右到左搜索第一個為「1」的位來轉換9位代碼。在9位代碼從右到左的位中，前兩位為「0」，第三位為「1」。由於在第一個「1」的右邊有兩個「0」，因此轉換邏輯1604將「100」轉換為兩個任意位(「XX」)。第一個「1」被忽略，餘下的位直接複製到8位值的後幾位。
在表4中的第二行，節點描述符1402存儲的9位代碼為「100100000」。轉換邏輯1604通過在9位代碼中從右到左搜索第一個為「1」的位來轉換9位代碼。第5位存儲「1」。9位代碼被轉換為其5位最低有效位(「LSBS」)設置為「任意值」(「X」)的8位值。通過使用9位運行比特長度編碼存儲節點描述符1402，使每個節點描述符1402所需的位數最少，因此增加了可以存儲在查詢表200中的節點描述符1402的數量。
在9位節點描述符1402轉換為8位值之後，轉換邏輯1604將8位值載入CAM 1606。8位值以與所選稀疏子樹描述符1400中存儲的節點描述符1402相同的順序載入CAM 1606，即，從最短到最長的匹配。CAM 1606提供用來存儲每個稀疏子樹描述符1400的最大編號節點描述符1402的存儲空間。因此，CAM 1606為8位寬16個入口深，以便能提供15個入口來存儲模式5的稀疏子樹描述符1400的節點描述符1402的最大編號以及預設的映射程序地址。CAM 1606具有三進位功能和內置的多匹配分解器。相對於提供真正的內容地址存儲器，小容量的CAM 1606可以利用邏輯門來實現，即，CAM 1606可以通過仿真CAM的硬體電路來實現。
稀疏子樹描述符1400中存儲的節點描述符1402的數量確定了存儲稀疏子樹描述符1400的子樹入口404。在特定模式範圍內存儲節點描述符1402的稀疏子樹描述符1400存儲在相同的子樹入口404中。為每個子樹的預設路由計算預設映射程序地址。預設的8位值永久地存儲在CAM1606的第一單元以計算預設的映射程序地址。
在所選稀疏子樹1400對應的8位值載入CAM 1606之後，利用關鍵字210b的下一部分搜索CAM 1606。選定與關鍵字210b的下一部分中最大位數匹配的CAM 1606中的入口。從搜索CAM得到的匹配地址作為塊位移714轉發。塊位移714用來確定與子樹映射程序418(圖5)中所存儲路由對應的映射程序入口的映射程序地址416。
圖19A-D說明了對稀疏集中子樹1700中一個節點的塊位移714的選擇。圖17A用圖形表示了稀疏集中子樹1700中的路由。子樹1700中的節點對應三個路由r0，r1和r2之一，r0是子樹1700的預設路由。以稀疏子樹描述符1400中的節點描述符14021和14022編碼r1，r2兩個路由。預設路由r0的值永久保存在CAM 1606中的第一入口1702中。參見表2，具有兩個節點描述符1402的稀疏子樹描述符1400存儲在模式欄位1404為「1」的子樹入口404中。
在子樹1700中，r2對應所有與10xxxxxx匹配的節點，r1對應所有與010xxxxx匹配的節點。為了最小化用來描述稀疏子樹描述符1400中每個路由的每個節點描述符14021，14022所需的位數，使用運行比特長度編碼對節點描述符14021，14022進行編碼。用於編碼的方法比用於對節點進行完全編碼所用位數多1位。在第一個「X」(「任意值」)的位置插入「1」並且其餘X位編碼為「0」。這樣，路由10xxxxxx被翻譯為10100000，路由010xxxxx被翻譯為010100000。
圖19B說明了節點描述符14021和14022在稀疏子樹描述符1400中的存儲。因為有兩個節點描述符14021和14022存儲在稀疏子樹描述符1400中，所以節點描述符14021和14022存儲在模式欄位1404設置為「1」的子樹入口404中。因為r1需要與前三位匹配，而r2需要與前兩位匹配，所以子樹的最長匹配為r1。節點14021和14022按從最短到最長的匹配順序存儲在稀疏子樹描述符1400中，其中r2的節點描述符14021存儲在第一位，r1的節點描述符14022存儲在下一位。
圖19C說明了節點描述符14022向8位屏蔽值1706的轉換。在從左到右的節點描述符位17081-17089中，第一個「1」存儲在位17086，它標誌著8位被屏蔽值1706的屏蔽位的結束。執行下面的位轉換來實現節點描述符14022向8位被屏蔽值1706的轉換。存儲在節點描述符17081位的「0」轉換為「X」並且存儲在8位被屏蔽值17101位。存儲在節點描述符17082位的「0」轉換為「X」並且存儲在8位被屏蔽值17102位。存儲在節點描述符17083位的「0」轉換為「X」並且存儲在8位被屏蔽值17103位。存儲在節點描述符17084位的「0」轉換為「X」並且存儲在8位被屏蔽值17104位。存儲在節點描述符17085位的「0」轉換為「X」並且存儲在8位被屏蔽值17105位。存儲在節點描述符17086位的「1」被忽略。存儲在節點描述符17087位的「0」存儲在8位被屏蔽值17106位。存儲在節點描述符17088位的「1」存儲在8位被屏蔽值17107位。存儲在節點描述符17089位的「0」存儲在8位被屏蔽值17108位。
圖19D說明了存儲CAM 1606中的節點描述符14021和14022以及所選擇的稀疏子樹描述符1400的子樹映射程序418(圖5)中存儲的對應的映射程序入口5041-5043。將所選擇的子樹描述符1400中存儲的9位節點描述符14021和14022轉換到轉換邏輯1604(圖18)中，並且載入CAM 1606。CAM 1606中第一個入口1702是圖19A中子樹1700所示的r0的預設入口。第二個入口1704從所選擇的稀疏子樹描述符1400中存儲的第一節點描述符14021轉換。第二個入口1704是為r2轉換的最短匹配。把所選擇的子樹描述符1400中存儲的第二節點描述符14022從010100000轉換為010XXXXX並且存儲在CAM 1606的第三入口1706中。
對CAM 1606的搜索產生塊位移714(圖18)。塊位移714用來確定子樹映射程序418(圖5)中存儲的映射程序入口5041-5043的映射程序地址416。利用存儲最長匹配的入口1702，1704，1706的關鍵字210b的第二部分來搜索CAM 1606。根據所選擇的子樹入口404中的指針欄位408中存儲的塊基地址6001，6001之一將CAM 1606提供的塊位移714與子樹基地址結合。
圖20是說明圖8所示指針邏輯702中稀疏模式基選擇邏輯1800的方框圖。指針邏輯702選擇用於計算子樹映射程序418(圖5)中映射程序入口504(圖6B)的映射程序地址416的基地址716。指針邏輯702包括密集模式基選擇邏輯710和稀疏模式基選擇邏輯1800，根據從上一層映射程序層轉發的子樹入口描述符304(圖4)中存儲的類型1406的狀態來選擇其一。如前所述，類型1406的狀態表示是否將子樹配置為密集模式。
如果子樹入口404存儲了多個稀疏子樹描述符1400，稀疏模式基選擇邏輯1800計算稀疏子樹描述符1400的基地址716。稀疏模式基選擇邏輯1800利用模式欄位1404中存儲的模式值1608和子樹入口404中塊基地址域6001，6002中存儲的子樹指針414以及上一層映射程序層轉發的子樹入口描述符304(圖4)中存儲的稀疏子樹描述符選擇1408來計算基地址716。基地址716的計算如下基地址(稀疏子樹描述符)＝塊基地址+基位移其中，基位移＝((1+節點/子樹)×稀疏子樹描述符選擇)例如，為查找以稀疏模式4配置的子樹入口404中2號子樹的起始基地址716，首先計算基位移。2號子樹對應的稀疏子樹描述符選擇1408為「1」並且節點/子樹數為7(見表2)。基位移為8((1+7)×1)。每個塊基地址6001，6002是分配給子樹入口404的16個映射程序地址塊的基地址。2號子樹對應的基位移是小於16的8，因此2號子樹的塊基地址是塊基地址6001並且稀疏子樹描述符的基地址716是塊基地址6001+8。表5說明了以模式4配置的子樹入口404中四個子樹的每個子樹基地址。

表5
圖21說明了存儲在子樹存儲器400中的密集子樹描述符和稀疏子樹描述符。結合圖15來描述圖21。子樹B(圖21)的密集子樹描述符存儲在子樹入口4041的數據欄位4061。子樹A(圖21)的稀疏子樹描述符14001存儲在子樹入口4042的數據欄位4062。密集子樹描述符存儲結合圖6B描述過的子樹B底層中每個節點的節點位。稀疏模式描述符14001包括對應結合圖19B描述過的路由r4和r5的節點描述符14021和14022。子樹索引312選擇子樹入口4041，4042。
s0(圖15)的映射程序106a中映射程序入口504(圖6B)中子樹入口描述符304(圖4)存儲的子樹索引312選擇子樹入口4041。s1(圖15)的映射程序106a中映射程序入口504(圖6B)中子樹入口描述符304(圖4)存儲的子樹索引312選擇子樹入口4042。因此，子樹存儲器400可以存儲稀疏子樹和密集子樹對應的子樹入口4041，4042。
圖22是說明用來向存儲稀疏集中子樹和密集集中子樹中的節點的路由的子樹映射程序418(圖5)中的映射程序入口504(圖6B)提供映射程序地址416(圖5)的方法的流程圖。任何子樹入口404都可以存儲多個稀疏子樹描述符或一個密集子樹描述符。根據路由在二叉樹中的如何分布，可以對稀疏子樹描述符和密集子樹描述符進行任意組合。靈活地混合和匹配在子樹存儲器400中子樹入口404中的稀疏模式和密集子樹描述符可以更好地利用子樹存儲器400。
在步驟1900中，從在上一映射程序層中選擇的子樹入口描述符304(圖4)中存儲的類型1406的狀態來確定所選擇的子樹入口404的配置。如果子樹入口404的類型配置為稀疏模式，處理過程繼續到步驟1902。否則，處理過程繼續到步驟1914。
在步驟1902中，子樹入口404的配置是稀疏模式。以稀疏模式配置的子樹入口404存儲多個稀疏子樹描述符1400。根據模式欄位1404的狀態確定子樹入口404中存儲的稀疏子樹描述符1400的數量。位移邏輯700中的稀疏模式邏輯1502根據從上一映射程序層轉發的子樹入口描述符304(圖4)中存儲的稀疏子樹描述符選擇1408和前面結合圖14描述過的模式欄位1404的內容來從子樹入口404中選擇稀疏子樹描述符1400。處理過程繼續到步驟1904。
在步驟1904，所選擇的稀疏子樹描述符1400中的節點描述符1402中存儲的9位編碼值被轉換為8位值並且按從最短到最長匹配的順序存儲在CAM 1606中。處理過程繼續到步驟1906。
在步驟1906中，利用關鍵字210b的下一部分在CAM 1606中搜索存儲最長匹配的CAM入口。處理過程繼續到步驟1908。
在步驟1908中，把存儲關鍵字210b下一部分的最長匹配的CAM 1606中的位置的地址作為塊位移714轉發。塊位移714用來計算子樹映射程序418(圖5)中映射程序入口504(圖6B)的映射程序地址416(圖5B)。處理過程繼續到步驟1910。
在步驟1910中，根據從上一映射程序層轉發的子樹入口描述符304(圖4)中存儲的稀疏子樹描述符選擇1408和所選擇的子樹入口404中存儲的模式欄位1404的內容來計算所選稀疏子樹描述符1400對應的基地址716。處理過程繼續到步驟1912。
在步驟1912中，通過在加法器邏輯704(圖8)中將塊位移714和基地址716相加來計算映射程序地址416。通過子樹映射程序418(圖5)中的映射程序地址416識別的映射程序入口504存儲路由入口302(圖4)或子樹入口描述符304(圖4)。如果映射程序入口504(圖6B)存儲路由入口302(圖4)，那麼搜索結束。如果映射程序入口504(圖6B)存儲子樹入口描述符304(圖4)，那麼繼續在下一映射程序層搜索對應關鍵字210b的值。
在步驟1914中，子樹入口404以密集模式配置並且在數據欄位406中存儲一個密集子樹描述符。通過統計前面結合圖6B描述過的子樹入口404中數據欄位406中存儲的密集子樹描述符中「1」的數量來計算塊位移714。處理過程繼續到步驟1916。
在步驟1916中，子樹入口404在子樹入口404中的指針欄位408存儲16個塊基地址600。前面結合圖8描述過的指針邏輯702中的密集模式基選擇邏輯710選擇塊基指針600中的一個。處理過程繼續到步驟1912。遞增更新圖23說明了在查詢表200中添加新路由的二叉樹表示。二叉樹說明了查詢表200中存儲的對應映射程序層1 2000，映射程序層2 2002和映射程序層3 2004的路由。映射程序層2 2002存儲子樹A和B的路由。映射程序層3 2004存儲子樹A1，A2，B1和B2的路由。s5表示子樹映射程序418(圖5)中存儲的子樹入口描述符304(圖4)。s5對應的子樹入口描述符304(圖4)存儲指向子樹B2的指針，子樹B2允許繼續在映射程序層3 2004搜索關鍵字210的最長匹配路由。
因為子樹B22006隻有兩個路由，r6和h1，所以它是稀疏子樹。因此，節點r6和h1對應的節點描述符1402(圖16A)存儲在已經結合圖14A描述過的稀疏子樹描述符1400中。因為在稀疏子樹描述符1400中存儲了兩個節點描述符1402，所以子樹B22006對應的稀疏子樹描述符1400存儲在子樹存儲器400中模式欄位1404設置為「1」的子樹入口404中。
子樹B2』2008所示的新節點h2添加到查詢表200中。因為子樹B22006的新增路由使稀疏子樹描述符1400中存儲的節點描述符1402的數量從2增加到3，所以新路由h1不能直接添加到查詢表的子樹B22006中。向稀疏子樹描述符1400增加節點描述符1402需要在模式欄位1404設置為「2」的子樹入口404中分配新的稀疏子樹描述符1400。因此，增加路由h1需要用子樹B2』2008代替子樹B22006。
圖24說明了處理器存儲器2400中存儲的更新路由。查詢表200中存儲的二叉樹的拷貝也存儲在與查詢表200分離的處理器存儲器2400中。存儲子樹B22006的路由複製到處理器存儲器2400的子樹B2』2008並且向子樹B2』2008增加新路由h2。
路由更新程序2402生成一系列路由更新指令2404，以便將子樹B2』2008添加到查詢表200中並且將路由更新2404轉發到表更新程序2406。表更新程序2406生成路由更新2402對應的表更新2410並且轉發更新周期2412，以便利用路由更新2404來更新查詢表200。更新周期2412將路由更新寫入子樹存儲器400(圖5)中相應的存儲器位置和子樹映射程序418中(圖5)。
返回圖23，更新周期2412包括用來分配一部分子樹映射程序418(圖5)以存儲映射程序入口504(圖6B)中新子樹B2』2008對應的路由的指令。子樹B2』2008包括路由h1和r6以及新路由h2的映射程序入口504(圖6B)中存儲的路由入口。在子樹B2』2008的路由入口存儲在子樹映射程序418(圖5)中的映射程序入口504(圖6B)後，產生了這些路由對應的節點描述符1402並且存儲在稀疏子樹描述符1400中。稀疏子樹描述符1400存儲在子樹入口404。子樹入口404的模式1404與稀疏子樹描述符1400中存儲的節點描述符1402的數量有關。
在子樹B2』2008的稀疏子樹描述符1400存儲在查詢表200的子樹存儲器400的子樹入口404中之後，s5代表的子樹入口描述符304(圖4)由指向子樹B22006改為指向子樹B2』2008。當把子樹B2』2008添加到查詢表時，可以通過s5訪問子樹B22006中存儲的路由r6和h1。在子樹B2』2008存儲到查詢表中後，s5改為指向子樹B2』2008並且可以訪問路由h1和r6和新路由h2。因此，當把新路由h2添加到查詢表200中時，可以在子樹B22006中繼續搜索對應於路由h1和r6的路由索引。
圖25說明了查詢表200中子樹映射程序418b中的映射程序入口504c4中存儲的圖23所示的新路由h2。結合圖24所示的二叉樹表示來描述圖25。
映射程序層2 2002中的子樹B有3個路由；即r3，s4和s5。因為子樹B的路由少於16個，所以它是稀疏子樹。子樹B r3，s4和s5的節點描述符1402a1-1402a3存儲在子樹存儲器400a中子樹入口404a中的稀疏子樹描述符1400a1中。子樹映射程序418a中存儲子樹B中每個路由對應的映射程序入口504a2-504a4。子樹映射程序418a中的映射程序入口504a1存儲子樹B的預設路由。每個映射程序入口504a2-504a4存儲該節點的路由入口302(圖4)或子樹入口描述符304(圖4)。504a3中存儲路由s4的子樹入口描述符304(圖4)，504a4中存儲s5的子樹入口描述符304(圖4)。映射程序入口504a4中存儲的s5為子樹存儲器400b提供子樹索引312b，以便開始下一層搜索；即對映射程序層3 2004的搜索。
子樹B2有兩個路由，即h1和r6，所以它也是稀疏子樹。節點描述符1402b1-1402b2存儲在子樹存儲器400b中的子樹入口404b中的稀疏子樹描述符1400b1中。子樹B2的每個路由存儲在映射程序入口504b2-504b3中並且子樹B2的預設路由存儲在映射程序入口504b1中。
為在子樹B22006中搜索路由h1，將保存了用來存儲路由s5的節點描述符1402的稀疏子樹描述符1400a的子樹入口404a的地址通過子樹索引312a轉發到子樹存儲器400a。所選擇的子樹入口404a中存儲的數據欄位406和指針欄位408通過子樹數據412a和子樹指針414a轉發到映射程序地址邏輯402a。映射程序地址邏輯402a生成存儲了s5的子樹入口的映射程序入口504a4的映射程序地址416a。映射程序地址416a取決於子樹數據412a，子樹指針414a和關鍵字210b的下一部分。把s5的子樹入口通過子樹索引312b轉發到子樹存儲器400b。
子樹存儲器400b存儲子樹B22006的節點描述符1402b2，1402b1。子樹B2的稀疏子樹描述符1400b1存儲在子樹入口404b中。子樹入口404b中存儲的數據欄位406和指針欄位408通過子樹數據412b和子樹指針414b轉發到映射程序地址邏輯402b。映射程序地址邏輯402b生成存儲了h1的路由入口的映射程序入口504b3的映射程序地址416b。映射程序地址416b取決於子樹數據412b，子樹指針414b和關鍵字210c的下一部分確定。
為向子樹B22006添加路由h2，分配子樹映射程序418b中一組前面未使用過的映射程序602c，以便存儲保存了子樹B2』2008的路由r6，h1和h2的映射程序入口504c2-504c4。映射程序入口504c1存儲子樹B2』2008的預設入口；即，映射程序入口504b1中存儲的相同的值。映射程序入口504c2存儲路由r6的路由入口；即，映射程序入口504b2中存儲的相同的值。映射程序入口504c3存儲路由h1的路由入口；即，映射程序入口504b3中存儲的相同的值。映射程序入口504c4存儲路由h2的路由入口。當寫入映射程序入口504c1-4塊時，可以通過子樹映射程序418a中的504a4中為路由s5存儲的子樹入口來訪問映射程序入口504b1-504b3中存儲的路由入口。
在子樹映射程序418b中已存儲了子樹B2』2008的映射程序入口504c1-4後，把稀疏子樹描述符1400c1添加到子樹存儲器400b。節點描述符1402c1-3的數量少於16，因此，節點描述符1402c1-3存儲在稀疏子樹描述符1400c1中。子樹描述符14001在子樹存儲器400b中的位置取決於與稀疏子樹描述符1400c1有關的節點描述符1402c1-3的熟練。通過在子樹B22006中增加一個新路由，要為稀疏子樹描述符1400c1存儲的節點描述符1402c1-1402c3的數量從2增加到3。稀疏子樹描述符1400c1存儲在每個稀疏子樹描述符含有3個節點描述符的子樹入口404c中，並且將模式欄位1404設置為「2」。如果有可用空間或分配了新模式3的子樹入口，那麼稀疏子樹描述符1400c1存儲在當前模式3的子樹入口404c中。子樹B2』2008中路由的節點描述符存儲在模式3的子樹入口404c中稀疏子樹描述符1400c1中的節點描述符1402c1-3中。
把稀疏子樹描述符1400c1和節點描述符1402c1-3存儲到子樹存儲器400b後，可以訪問子樹B2』2008。為提供對子樹B2』2008的訪問，修改子樹入口504a4在索引子樹入口404c中索引稀疏子樹描述符1400b1而不是在子樹入口404b中索引稀疏子樹描述符1400c1。可以訪問映射程序入口504c4中存儲的路由h2的路由入口和相應映射程序入口504c2和504c3中分別存儲的路由r6和h1。
由於不能再訪問映射程序入口504b1-504b3，所以將它們釋放並放置在空閒列表(未示出)中等待以後分配。另外，也不能再訪問稀疏子樹描述符1400b1。因此，稀疏子樹描述符1400b1被釋放並放置在空閒列表(未顯示)中等待以後分配。
已經描述了向稀疏子樹中增加路由。也可以通過在新分配的子樹入口404中存儲新的密集子樹描述符以及在子樹映射程序418中存儲對應的映射程序入口，並且將映射程序入口504a4中存儲的子樹入口改為索引新分配的子樹入口404來向密集子樹中增加路由。
圖26是說明在圖25所示查詢表200中執行增加路由的遞增更新步驟的流程圖。
在步驟2200中，計算每個子樹的路由數量以確定路由更新產生稀疏子樹還是密集子樹。如果路由更新後為密集子樹，處理過程繼續到步驟2218。如果路由更新後為稀疏子樹，處理過程繼續到步驟2202。
在步驟2202中，子樹是稀疏的，因此確定為稀疏子樹模式。處理過程繼續到步驟2204。
在步驟2204中，搜索子樹映射程序418(圖5)中存儲的部分填充的子樹入口404的列表以確定是否可將新的稀疏子樹描述符1400c1存儲在前面分配的子樹入口404中。例如，可將4個稀疏子樹描述符1400c1-1400c4存儲在模式4的子樹入口404中。如果只存儲了3個，子樹入口404被部分填充並且存儲在部分填充的子樹入口404的列表中。如果有可用的部分填充的子樹入口404，處理過程繼續到步驟2208。否則，處理過程繼續到步驟2206。
在步驟2206中，分配新的子樹入口404c以便存儲稀疏子樹描述符1400c1，並且在為新分配的子樹入口404c中的稀疏子樹描述符1400c1中存儲的節點描述符1402c1-1402c3存儲映射程序入口504(圖6B)的子樹映射程序中分配映射程序入口504c1-504c4。把指向子樹映射程序418(圖5)中分配的映射程序入口504c1-504c4塊的指針存儲在新子樹入口404c的指針欄位408中。處理過程繼續到步驟2208。
在步驟2208中，從子樹入口404c中指針欄位408中存儲的指針和子樹入口404c中模式欄位1404中存儲的模式來確定稀疏子樹描述符1400c1的子樹映射程序中第一個映射程序入口504c1的位置。處理過程繼續到步驟2210。
在步驟2210中，將稀疏子樹的路由入口存儲在子樹映射程序418b中的映射程序入口504c1-504c4中。處理過程繼續到步驟2212。
在步驟2212中，把存儲節點描述符1402c1-1402c3的稀疏子樹描述符1400c1存儲在子樹入口404c中。處理過程繼續到步驟2214。
在步驟2214中，映射程序入口504a4中存儲的子樹入口描述符304(圖4)被修改為索引子樹入口404c中存儲的新稀疏子樹描述符1400c1。現在可以訪問映射程序入口504c4中存儲的h2的路由入口。處理過程繼續到步驟2216。
在步驟2216中，不能再訪問映射程序入口504b1-504b3和稀疏子樹描述符1400b。將映射程序入口504b1-504b3放置在子樹映射程序418b的映射程序入口504(圖6B)的空閒列表中並且分配用來存儲其它路由。在部分填充的子樹入口的列表中更新子樹入口404b中的第一個可用位置。處理過程結束。
在步驟2218中，從處理器存儲器2400(圖24)中存儲的空閒子樹入口404的列表分配一個新的子樹入口404。分配新的子樹入口404用來存儲新的密集子樹描述符。分配子樹映射程序418b中的映射程序入口組504(圖6B)用於存儲這些路由。指向若干塊已分配的映射程序入口504(圖6B)的指針存儲在子樹入口404(圖5)中的指針欄位408(圖7)中。處理過程繼續到步驟2220。
在步驟2220中，如前面結合圖6A-B描述的，將新的密集子樹描述符寫入新子樹入口404中的數據欄位406。處理過程繼續到步驟2222。
在步驟2222中，把密集子樹的路由入口存儲在由子樹入口404中的指針欄位408中存儲的指針所識別的子樹映射程序418(圖5)中的映射程序入口504(圖6B)中。處理過程繼續到步驟2224。
在步驟2224中，修改映射程序入口504a4中存儲的子樹入口描述符304(圖4)以指向新的子樹入口404c中存儲的新密集子樹描述符。現在可以訪問映射程序入口504c4中存儲的h2的路由入口。處理過程繼續到步驟2226。
在步驟2226中，把由舊子樹入口404中的指針欄位408中存儲的指針指向的映射程序入口504(圖6B)返回到處理器存儲器2400(圖24)中存儲的映射程序入口的空閒列表。舊的子樹入口404b添加到處理器存儲器2400(圖24)中存儲的空閒子樹入口列表中。
已經描述了向查詢表添加路由的過程。執行類似的過程以便從查詢表刪除路由。例如，從子樹B2』2008中刪除h2 504c4需要存儲含有路由r6和h1的兩個節點描述符的新稀疏子樹描述符，在模式2的子樹入口中存儲稀疏子樹描述符，更新對應的子樹映射程序並且習慣映射程序入口504a4中存儲的子樹入口描述符304(圖4)指向新子樹入口404中存儲的更新的子樹描述符。
雖然已經參考優選實施例特別給出和描述了本發明，本領域技術人員可以理解，在不脫離本發明所附權利要求的範圍的情況下可以對本發明的形式和細節進行改變。
權利要求
1.一種提供子樹葉子的值的查詢表包括由子樹索引訪問的多個子樹入口；存儲在第一個子樹入口中的密集子樹描述符，密集子樹描述符包括密集子樹的每個葉子的值指示；和存儲在第二個子樹入口中的多個稀疏子樹描述符，每個稀疏子樹描述符包括至少一個節點描述符。
2.根據權利要求1所述的查詢表，其特徵在於節點描述符識別稀疏子樹的葉子集合的共用值。
3.根據權利要求1所述的查詢表，進一步包括根據密集子樹描述符中設置為「1」的位的數量來選擇與密集子樹的葉子對應的值的映射程序邏輯。
4.根據權利要求1所述的查詢表，其特徵在於為在子樹入口中存儲多個稀疏子樹描述符而提供的位的數量等於密集子樹描述符中的位的數量。
5.根據權利要求1所述的查詢表，其特徵在於利用行程長度編碼對節點描述符進行編碼。
6.根據權利要求5所述的查詢表，其特徵在於節點描述符中的位的數量等於子樹葉子中的位的數量加1。
7.根據權利要求6所述的查詢表，其特徵在於根據設置為「1」的第一最低有效位的位置在節點描述符中對多個子樹葉子的值進行編碼。
8.根據權利要求6所述的查詢表，其特徵在於節點描述符中的位的數量為9，並且子樹葉子中的位的數量為8。
9.根據權利要求8所述的查詢表，進一步包括可以通過子樹葉子搜索的按內容尋址存儲器；和在所選擇的稀疏子樹描述符中選擇節點描述符，將節點描述符轉換為8位編碼值並且將8位編碼值存儲在按內容尋址存儲器中的轉換邏輯。
10.根據權利要求9所述的查詢表，其特徵在於通過把在設置為「1」的第一最低有效位右邊的最低有效位設置為「任意位」並且刪除設置為「1」的第一最低有效位來轉換節點描述符。
11.一種提供子樹葉子的值的查詢表，包括由子樹索引訪問的多個子樹入口；存儲在第一個子樹入口中的密集子樹描述符，密集子樹描述符包括密集子樹的每個葉子的值指示；和在第二個子樹入口中存儲多個稀疏子樹描述符的裝置，每個稀疏子樹描述符包括至少一個節點描述符。
12.根據權利要求11所述的查詢表，其特徵在於節點描述符識別稀疏子樹葉子集合的共用值。
13.根據權利要求12所述的查詢表，進一步包括用來根據密集子樹描述符中設置位「1」的位的數量來選擇與密集子樹的葉子對應的值的裝置。
14.根據權利要求12所述的查詢表，其特徵在於為在子樹入口中存儲多個稀疏子樹描述符而提供的位的數量等於密集子樹描述符中的位的數量。
15.根據權利要求12所述的查詢表，其特徵在於利用行程長度編碼對節點描述符編碼。
16.根據權利要求15所述的查詢表，其特徵在於節點描述符中的位的數量等於子樹葉子中位的數量加1。
17.根據權利要求16所述的查詢表，其特徵在於根據設置為「1」的第一最低有效位的位置在節點描述符中對多個子樹葉子的值進行編碼。
18.根據權利要求17所述的查詢表，其特徵在於節點描述符中的位的數量為9並且子樹葉子中的位的數量為8。
19.根據權利要求87所述的查詢表，進一步包括可以通過子樹葉子搜索的按內容尋址存儲器；和用來在所選擇的稀疏子樹描述符中選擇節點描述符，將節點描述符轉換為8位編碼值並且將8位編碼值存儲在按內容尋址存儲器中的轉換裝置。
20.根據權利要求19所述的查詢表，其特徵在於通過將設置為「1」的第一最低有效位右邊的最低有效位設置為「任意位」並且刪除設置為「1」的第一最低有效位來轉換節點描述符。
21.一種為在查詢表中實現的子樹葉子提供值的方法，包括步驟由子樹索引訪問多個子樹入口；在第一個子樹入口中存儲密集子樹描述符，密集子樹描述符包括密集子樹的每個葉子的值指示；和在第二個子樹入口中存儲多個稀疏子樹描述符，每個稀疏子樹描述符包括至少一個節點描述符。
22.根據權利要求21所述的方法，其特徵在於節點描述符識別稀疏子樹葉子集合的共用值。
23.根據權利要求21所述的方法，進一步包括根據密集子樹描述符中設置為「1」的位的數量來選擇與密集子樹葉子對應的值。
24.根據權利要求21所述的方法，其特徵在於為在子樹入口中存儲多個稀疏子樹描述符而提供的位的數量等於密集子樹描述符中的位的數量。
25.根據權利要求21所述的方法，其特徵在於利用行程長度編碼對節點描述符編碼。
26.根據權利要求21所述的方法，其特徵在於節點描述符中的位的數量等於子樹葉子中的位的數量加1。
27.根據權利要求26所述的方法，其特徵在於根據設置為「1」的第一最低有效位的位置在節點描述符中對多個子樹葉子的值進行編碼。
28.根據權利要求27所述的方法，其特徵在於節點描述符中的位的數量為9並且子樹葉子中的位的數量為8。
29.根據權利要求28所述的方法，進一步包括提供可以通過子樹葉子搜索的按內容尋址存儲器；在所選擇的稀疏子樹描述符中選擇節點描述符；將節點描述符轉換為8位編碼值；和將8位編碼值存儲在按內容尋址存儲器中。
30.根據權利要求29所述的方法，其特徵在於通過將設置為「1」的第一最低有效位右邊的最低有效位設置為「任意位」並且刪除設置為「1」的第一最低有效位來轉換節點描述符。
全文摘要
一種允許在同一個存儲器中存儲稀疏子樹描述符和密集子樹的查詢表。存儲器中的子樹入口存儲密集子樹的密集子樹描述符或稀疏子樹的多個稀疏子樹描述符。通過前一個子樹中的樹葉索引子樹入口。稀疏子樹描述符存儲至少一個節點描述。節點描述符描述具有公用值稀疏子樹中的一組樹葉。利用行程長度編碼在節點描述符中對公用值編碼。
文檔編號G11C15/00GK1435032SQ00818947
公開日2003年8月6日 申請日期2000年12月8日 優先權日1999年12月10日
發明者大衛·A·布朗 申請人:睦塞德技術公司