網絡處理器中路由轉發資料庫的優化的製作方法
2023-11-04 15:32:12 2
專利名稱：網絡處理器中路由轉發資料庫的優化的製作方法
技術領域：
本發明一般地涉及數據通信網絡路由裝置中優化的路由查找表。特別地，本發明涉及一種用於在具有不同存取速度的多個存儲器裝置之間分配網絡路由信息、由此減少網絡處理器中路由確定時間的系統及方法。
背景技術：
數據通信網絡中的多層網絡交換機和路由器有時候利用專業化的專用集成電路(ASIC)，這些集成電路被設計為對分組數據執行大量交換和路由操作。這些ASIC包括網絡處理器(NP)，其適於執行開放系統互聯(OSI)數據鏈路層(第2層)切換操作和網絡層(第3層)路由操作中的許多操作。具有路由性能的NP一般編譯和維護路由表，這些路由表被用來為數千路由取回下一跳地址。諸如路由轉發資料庫(RFD)的路由表被保持於既快速又可編程的片上寄存器中。
儘管NP的寄存器可存儲數千網絡路由，但是這對於容納路由器在工作過程中獲悉的所有網絡地址來說仍然不足。當路由數量超過NP的最大容量時，寫入額外路由的意圖可能在插入時失敗或者造成不可預計的路由行為。這樣，現有路由器會試圖通過限制保存到NP的路由數量和刪除超過其最大存儲容量的那些路由來避免這樣的問題。然而，這種做法並不是解決方案，因為它會造成即使當有效路由比寄存器已經保持的路由使用得更為頻繁時，仍然刪除這些有效路由。
因此需要一種增大NP存儲容量的系統和方法，其方式為在優先考慮那些使用最為頻繁的路由的同時，向NP提供對所有已知路由的存取。
發明內容
本發明在優選實施例中的特徵在於一種路由裝置，其包括適於接收協議數據單元(PDU)的埠；路由表，用於在具有多個路由trie節點的多路路由trie中存儲多個路由，該路由表包括第一存儲器，用於高速緩存多個路由trie節點的第一組；以及第二存儲器，用於高速緩存多個路由trie節點的第二組；尋路引擎，適於搜索路由表用於尋找與接收的PDU相關聯的多個路由之一；以及路由管理器，適於將第二組的一個或多個節點從第二存儲器重定位至第一存儲器，其中第一存儲器的每個節點的利用總數高於第二存儲器的每個節點的利用總數。在優選實施例中，路由管理器還適於將第一組的一個或多個節點從第一存儲器重定位至第二存儲器。
在優選實施例中，第一存儲器比第二存儲器具有更快的存取速度。第二存儲器例如可以是隨機存取存儲器，第一存儲器可以是專用集成電路(ASIC)的寄存器存儲器比如網絡處理器。利用本發明，路由裝置可根據需要將多路路由trie中被最為頻繁地搜索的節點分配和重分配至最快的存儲器，由此減少搜索路由表所需的時間。
例如，當路由表的搜索利用PDU的網際網路協議(IP)地址來識別匹配時，路由裝置取迴轉發信息，其包含PDU所傳輸到的下一跳地址。路由trie的節點被搜索得越頻繁，則其關聯的利用總數越高。在優選實施例中，網絡處理器中這些節點的利用總數一般是閒置時間，其是由出於路由搜索的目的而最後存取該節點時起已逝去的閒置數字微處理器時鐘周期的數量來代表的。例如，第二存儲器中節點的利用總數優選為在由網絡管理員給定的時間段中搜索該節點的頻率。
本發明在一些實施例中是一種在包括第一存儲器和第二存儲器的路由裝置的轉發路由資料庫中高速緩存多個路由的方法，多個路由的每一個與以多路路由trie的形式組織的多個節點相關聯。該方法包括步驟如果存儲器空間可用，則將與多個路由的一個或多個相關聯的節點分配給第一存儲器；如果第一存儲器中的存儲器空間不可用，則將與多個路由的一個或多個相關聯的節點分配給第二存儲器；為分配給第一存儲器的一個或多個節點和為分配給第二存儲器的一個或多個節點生成利用總數；將分配給第一存儲器的一個或多個節點的利用總數與分配給第二存儲器的一個或多個節點的利用總數做比較；以及如果第二存儲器中一個或多個節點的至少一個節點的利用總數超過第一存儲器中一個或多個節點的至少一個節點的利用總數，則將第二存儲器中的該至少一個節點重分配給第一存儲器。在優選實施例中，該方法還包括步驟如果第二存儲器中至少一個節點的利用總數超過第一存儲器中至少一個節點的利用總數，則將第一存儲器中的至少一個節點重分配至第二存儲器。
如果第一存儲器是相對快的存儲器、第二存儲器是相對慢的存儲器，則本發明將重分配多路路由trie的節點，從而路由trie中搜索最為頻繁的節點被分配給第一存儲器。在該處理中，本發明優選實施例的方法適於將第二存儲器中存取頻繁的節點重定位至第一存儲器，以最小化用以執行路由trie的搜索和取回與入站PDU相關聯的轉發信息所需要的平均時間。
通過在附圖的各個圖中的示例非限制地圖示了本發明，在附圖中圖1是按照本發明優選實施例的多層路由裝置的功能方框圖；圖2是按照本發明優選實施例的交換模塊的功能方框圖；圖3是按照本發明優選實施例的交換模塊的功能方框圖，其示出包括NP內部和外部存儲器的路由查找表；圖4是按照本發明優選實施例的路由查找表，其包括多路數據結構和轉發表；圖5是按照本發明優選實施例以列表形式示出的代表性分級數組；圖6是按照本發明優選實施例在模塊中利用的轉發表；圖7是按照本發明優選實施例的多路trie結構，其示意性地示出完全在NP寄存器之內實現的路由查找表；圖8是按照本發明優選實施例的多路trie結構，其示意性地示出在內部寄存器和外部RAM上分布的路由查找表；圖9是按照本發明優選實施例的多路trie結構，其示意性地示出其中RAM包括一個或多個次trie以增大寄存器的路由查找表；圖10是按照本發明優選實施例在圖9的trie已被刪除而利用轉發信息中的冗餘之後的trie結構；圖11是按照本發明優選實施例的處理流程圖，通過該處理，路由裝置監視和更新路由查找表；以及圖12是按照本發明優選實施例的處理流程圖，通過該處理，交換模塊基於節點的活動性，選擇性地將路由查找表中的節點重定位至寄存器存儲器或RAM。
具體實施例方式
圖1中圖示了用於經過通信網絡多路傳送數據分組的多層路由裝置的功能方框圖。例如，路由裝置100是多個節點和其他可尋址實體中的一個，其可操作地耦接至通信網絡，比如區域網(LAN)、廣域網(WAN)、城域網(MAN)、網際網路協議(IP)網、網際網路或其組合。路由裝置100優選地包括多個交換模塊11O，它們藉助於用於在交換模塊之間傳輸協議數據單元(PDU)的交換結構150來可操作地相互耦接。交換模塊110可採用交換處理器、交換單元或交換刀片(switch blade)的形式，其適於可拆卸地接合該底板152中的槽或總線系統(未示出)，該槽或總線系統可操作地將每個交換模塊110相互耦接。
多個交換模塊11O的每一個包括至少一個網絡接口模塊(NIM)102，其包括一個或多個可操作地耦接至網絡通信鏈路的外部埠103。優選實施例中多個交換模塊110的每一個還包括一個或多個網絡處理器(NP)106，其一般能夠但不限於進行如開放系統互聯(OSI)參考模型中限定的至少第2層交換和第3層路由操作。由此，每個模塊11O適於經由NIM102傳輸協議數據單元(PDU)到網絡和從網絡接收PDU，以及藉助交換結構150相互傳輸PDU和接收PDU。
出於本申請的目的，從通信鏈路向交換結構150流入交換模塊11O的PDU在此被稱為輸入PDU，輸入PDU進入路由裝置100時經過的交換模塊110一般被稱為輸入交換模塊。從交換結構150流至通信鏈路的PDU在此被稱為輸出PDU，發送這些PDU的交換模塊被稱為輸出交換模塊。本實施例的多個交換模塊110中的每一個可根據信號流及其方向用作輸入交換模塊和輸出交換模塊。
圖2中圖示了交換模塊的功能方框圖，其用於執行優化的多存儲器路由分配。交換模塊110優選地包括至少一個NIM102、至少一個NP106、微處理器262和結構接口模塊208。每個NIM102可操作地耦接至用於接收和發送數據業務量的一個或多個外部埠。在優選實施例中，路由裝置100是IEEE802.3啟動的交換機，NIM102適於執行物理層和數據鏈路層控制，其可操作地將路由裝置100耦接至一個或多個通信介質，包括有線、無線和光通信鏈路。優選實施例中的NP106是千兆比特乙太網交換機，型號是BCM5695，由加州Irvine的DCOM生產。
NIM102接收的輸入PDU經由內部數據總線206傳輸到NP106，在該處NP尋路引擎230基於與輸入PDU相關聯的屬性來進行交換和路由決策，這些屬性例如包括目標和源地址、協議類型、優先級信息和包括802.1Q標籤的虛擬區域網(VLAN)信息。路由決策是從路由查找表250中保持的大量路由之中確定的。優選實施例的交換模塊110適於利用兩個或多個存儲器來保持所有已知路由的完整記錄，這些存儲器包括(1)NP106內部的第一存儲器；以及(2)NP106外部的第二存儲器，該第二存儲器本身就能增大NP固有的受限存儲器容量。路由、代價以及輸入PDU所要轉發的關聯下一跳地址是經配置管理器264由網絡管理員手工配置的，和/或由利用動態路由協議比如開放最短路徑優先(OPSF)的微處理器262與地址解析協議(ARP)相結合來編譯的。
在輸入PDU的下一跳目標地址被確定之後，尋路引擎230執行用以從路由裝置100傳輸PDU所必需的基本上所有分組的處理。這些分組處理操作例如可包括但不限於報頭轉換，用於重新封裝數據；置入VLAN標籤，用於將一個或多個VLAN標籤附加至PDU；提取VLAN標籤，用於從PDU去除一個或多個VLAN標籤；服務質量(QoS)，用於保留網絡資源；記帳和計費，用於監視客戶業務量；多協議標記交換(MPLS)管理、認證，用於有選擇性地過濾PDU；存取控制；高層學習，包括地址解析協議(ARP)控制；埠監視，用於再現和重定向PDU便於業務量分析；資源學習；服務級別(CoS)，用於確定向PDU分配交換機資源時的相對優先級；以及染色標記，用於監管和業務量整形。
在尋路引擎230的分組處理之後，PDU由隊列管理器240暫時緩衝於輸入隊列存儲器242中，直至帶寬可用以經過交換結構150傳輸PDU。然後PDU經由結構接口模塊208傳輸到恰當的輸出交換模塊，用於向PDU的目標節點方向傳輸。
在優選實施例中，結構接口模塊208適於將輸入PDU傳輸到交換結構150以及從其他的一個或多個交換模塊的每一個接收輸出PDU。在優選實施例中，從結構接口模塊208接收的輸出數據被緩衝於輸出隊列存儲器248中，其例如經過尋路引擎230用於統計處理，以及經由NIM102之一從恰當的輸出埠發送。
圖3中圖示了交換模塊的功能方框圖，其適於通過在多個存儲裝置之間分配路由存儲來形成優化的多存儲器路由查找表。特別地，交換模塊11O在路由查找表中保持路由，該查找表跨越第一存儲器(即NP106內部的主路由存儲器)和第二存儲器(即輔路由存儲器)。輔路由存儲器一般比主路由存儲器慢，可位於NP106內部或外部。路由在主路由存儲器和輔路由存儲器之間的優化分配是由微處理器262基於NP106以及微處理器262所編譯的路由使用統計來確定的。
如圖3中更具體地所示，優選實施例的NP尋路引擎230包括解析引擎332、分類器333、轉發處理器336和輸出處理器338。解析引擎332檢查從NIM102接收的輸入幀，提取與輸入PDU的識別、轉發和尋路相關的一個或多個域。如果目標介質存取控制(MAC)地址是已知的，則PDU被不經更改地交換到恰當的輸出埠。如果是未知的，則源MAC通過源學習335被添加到輸入埠上的第2層地址表334，該PDU被傳輸到所有關聯的輸出埠。
如果幀例如包括交換模塊11O的目標MAC地址和另一節點的目標IP位址，則分類器333試圖識別目標節點、對應路由、以及通向目標節點的路徑上的下一跳地址。在這樣操作時，分類器333優選地從輸入PDU的一個或多個域中產生索引，它利用該索引來搜索路由查找表250。如果檢測到匹配，則路由查找表250取回一指針，其指向NP轉發表354中的轉發信息，轉發處理器336使用該轉發信息以包括下一跳地址的新物理層報頭來封裝該分組，該PDU被傳輸到隊列管理器240。隊列管理器240以所需服務級別(CoS)/服務質量(QoS)要求在輸入存儲器242中緩衝這些PDU，隨後按照帶寬分配方案——比如嚴格的優先級或加權的公平隊列——將這些PDU釋放至交換結構150。
在優選實施例中，路由查找表250包括(a)NP106中相對快的主路由存儲器，用於保持使用最為頻繁的路由；以及(b)NP106外部的輔路由存儲器，用以補充主路由存儲器。在優選實施例中，所用NP是Broadcom5695網絡處理器。NP106內部的較快主路由存儲器是寄存器存儲器352，其適於近似地高速緩存3800個IPv4路由。NP外部是附加的輔路由存儲器，包括隨機存取存儲器(RAM)360，用於存儲用以擴展交換模塊110容量所需的附加路徑。
如下文更具體討論的，這些路由是以可查找的路由樹或來自單詞「reTRIEval」的「tries」來邏輯地組織的，所述trie包括與關聯路由的一個或多個位相對應的路由trie節點。在優選實施例中，目標地址的位可分配給寄存器352和RAM360中存儲的多個路由trie節點。在優選實施例中，節點在寄存器352和RAM360之間的分布是動態地限定的並且會周期性地再限定，以便在寄存器中安置使用最為頻繁的節點。以此方式，寄存器352和RAM360能夠在最小化平均路由確定時間的同時保持所有感興趣的路由。
存取寄存器352中保持的查詢trie的節點的頻率由NP106監視並記錄於寄存器活動性表358中。在Broadcom5695NP情況下，該頻率也被稱為利用總數—是以在給定的時間段上獲得的命中率的形式來度量的，對節點的每次查找都會產生命中。
對RAM360中保持的路由trie節點的存取頻率(即利用總數)由微處理器262編譯，並且以保持於數據存儲266中的一個或多個RAM活動性表364的形式來記錄。相同的度量都可用來確定節點在RAM360和寄存器352中的活動性，而優選實施例中的交換模塊110是根據給定時間段上出於路由查找的目的存取節點的次數，來度量這些節點在RAM360中的活動性。
RAM活動性表364包括RAM trie中每個次trie根節點及其利用總數的列表。次trie根是路由trie部分的根節點，該路由trie僅保持在輔路由存儲器360中而不是主路由存儲器中。次trie可以是深入的一個或多個節點，並且由次trie根來牽頭，該次trie根在路由trie中的父節點被保持於主路由存儲器352中。為了一致，次trie根的利用總數等於其所有子節點的最大利用總數。在優選實施例中，如果必要，次trie根的列表則根據利用率從最多利用率排序至最少利用率，以便於識別最活躍的節點並將其重定位至主路由存儲器352。
在一些實施例中，微處理器262還維護數據存儲266中保持的寄存器葉列表366。寄存器葉列表366優選為由微處理器262使用的數據結構，其用以在本地跟蹤由寄存器活動性表358提供的利用總數。寄存器葉列表366中保持的利用總數由NP106編譯，隨後由微處理器262使用，以便於識別主路由存儲器352中最不活躍的節點並將其重定位至輔路由存儲器360。
圖4中示出了路由查找表，其包括多存儲器、多叉數據結構和轉發表。也被稱為取回樹或「trie」結構的多叉數據結構由交換模塊110用來查找具有一個或多個分組屬性的路由數據並將關聯指針取回到轉發表354中。該trie結構包括分布於寄存器存儲器352和RAM360中的多個分級數組，每個數組對應於路由查找結構中的一個或多個節點。主路由存儲器——即寄存器存儲器352——一般是在製造NP106之時固定的具有硬體受限的容量的高速存儲器。輔路由存儲器——即RAM360——通常在NP106外部，比片上寄存器存儲器352的成本效益更高。RAM360一般比寄存器存儲器352具有更大的存儲容量，能夠容易地存儲即使在大型網絡中為所有已知路由提供可查找的存取所需的所有分級數組。
在一些實施例中，輔路由存儲器適於存儲完整的路由trie，其包括那些也保持於主路由存儲器中的節點。然而為了說明簡化，圖4和圖7-10中所示的輔路由存儲器僅包括那些例如由於其相對低的利用總數而從主路由存儲器排除掉的節點。
這些數組在RAM360中的數量和大小可由微處理器262限定並可動態地重限定，以向尋路引擎230提供完整的網絡拓撲圖。然而由於存取速度更快，學習到的路由在空間可用時首先被記錄至寄存器存儲器352，如果並且當寄存器存儲器達到容量時，則在RAM360中由微處理器262建立新節點。RAM360中建立的新節點是指從寄存器存儲器352中排除掉的節點。本領域技術人員將理解在RAM360中記錄所有新路由節點的好處在於，如果寄存器存儲器352中的查找無法產生匹配，則提供全面和可查找的路由trie。
如圖4所示，寄存器352包括第一分級數組A401、第二分級數組B402、第三分級數組C403和第四分級數組D404，它們示意性地代表用以查找四個字節的IPv4地址的路由trie結構的排列。每個數組401-404優選地在NP的寄存器存儲器352中維護以便於進行存取。
第一分級數組，即數組A401，對應於trie結構的根節點，包括多個元素，其例如包含元素A1-A2...A100。每個元素A1-A2...A100對應於字符串，該字符串包含所接收的PDU的IPv4目標地址的一個或多個最高有效位。第四分級數組，即數組D404，代表寄存器352中路由trie結構的葉節點，包括多個元素，其例如包含元素D1-D2。每個元素D1-D2對應於字符串，該字符串包含所接收的PDU的IPv4目標地址的一個或多個最低有效位。當PDU的目標IP位址的所有位與數組D404的多個條目的一個相匹配時，從葉節點取回指向表354的指針450。第二分級數組即數組B402和第三分級數組即數組C403對應於路由trie結構的中間節點，其是在穿越根節點和葉節點之間時查找的。
第五分級數組即數組B*405、第六分級數組即數組C*406和第七分級數組即數組D*407代表僅保持於RAM360中的路由trie結構的節點。分級數組405-407由微處理器262交換模塊軟體管理。如果在到達路由trie的葉之前，寄存器352中的查找被NP106終止，則一般查找RAM360中的這些節點。
圖5中示出了以列表形式描繪的代表性分級數組。在優選實施例中，分級數組的每個條目，即表500中的每行，包括Valid_bit指示符501、stop_bit指示符502以及指向子數組的索引503。儘管分級數組500一般具有相同格式，而與它是記錄於寄存器存儲器352還是RAM360中無關，但是NP106中所用分級數組的索引503也可包括預設值，其用來迫使交換模塊11O終止NP106中的查找和在微處理器262中恢復利用RAM360中的路由數據的查找。
當查找的分級數組在該數組中由查找的一個或多個位的值給定的位置處包含有效條目時，則在IP位址的一個或多個位之間檢測到匹配。例如具有值「n」的IP位址的一連串一個或多個位是對應於分級數組500中的「第n」元素。然後通過利用指針而索引到存儲器中，可取回與該一個或多個位的值相關聯的條目，該指針由數組基值與查找的位值之和來給定。
當測試的地址位與分級數組500中的條目相匹配時，路由查找表250檢查valid_bit指示符501，以初步確定該條目是否包含指向後續表的有效索引。例如值1表示第三列503中的索引-1指向子數組或轉發表354中的另一節點，而例如值O或未定義的值則表示缺乏匹配的路由規則。在缺乏匹配時，路由查找表可將預設路由規則或者與檢測到的最長前綴匹配相關聯的路由規則應用於查找中的該點。
如果valid_bit指示符501等於1，則路由查找表還檢測stop_bit指示符502，以確定是否繼續查找路由trie結構。等於0的stop_bit指示符表示，第三列503中的索引是指向待查找的寄存器352中下一路由trie節點的指針。具有值1的stop_bit指示符表示該特定節點是葉節點。該葉節點可以是針對整個路由trie的葉或者針對寄存器存儲器352中保持的次trie的葉。
如果葉節點是針對整個路由trie的葉，則路由查找表250通過利用來自列503的指針而從轉發表354取回關聯的轉發信息來完成查找。如果葉節點是針對主路由存儲器352中保持的路由trie部分的葉而不是針對整個路由trie的葉，則NP106的查找被終止，而由微處理器262利用輔路由存儲器360來恢復。在寄存器352中比預期時間早結束並且在RAM360中完成的查找將被發送到「軟體」。由微處理器262執行的查找可被僅指向RAM360中的路由次trie或者重新橫貫整個路由trie。在優選實施例中，NP106通過將索引值設為等於預設索引值，強行令該查找由軟體和輔路由存儲器360執行。
圖6中示出了葉節點，其提供指向優選實施例中所用的轉發表。轉發表354的每行代表轉發表條目，其由路由trie結構中葉節點650的索引503來指向。按照本發明的優選實施例，多個葉節點650被分布於寄存器352和RAM360之間，以向NP106提供對使用最為頻繁的路由trie節點的存取，由此減少查找時間。
轉發表354中的每個條目包括轉發信息，其包含下一跳地址601，即匹配PDU將被轉發到的MAC目標地址。在一些實施例中，MAC源地址602和虛擬區域網(VLAN)標識符603也被取回並在PDU被傳輸到下一跳時包含在PDU的數據鏈路層報頭中。本領域技術人員將理解，轉發表600可適於包括附加信息，其例如包含輸出埠103的編號。
圖7中示出了多路路由trie結構，其示意性地示出完全在主路由存儲器即寄存器存儲器352中實現的路由查找。路由trie結構700對應於這樣的情形，其中寄存器存儲器352能夠本地高速緩存和解析交換模塊110所知的每個路由。因此在此例中，路由trie700的每個節點在NP的寄存器存儲器352中被高速緩存，而無需NP106求助於輔路由存儲器比如RAM360。
多路路由trie結構700包括多個節點，其邏輯關係由連接這些節點的支路來表明。多個節點包括根節點A1和中間節點B1-B2、C1-C4和葉節點D1-D8。一般而言，是從根節點A1到與輸入PDU的IP目標地址相匹配的多個葉節點D1-D8之一中連續查找節點。如上所討論，匹配的葉節點包括指向轉發表354中一條目的索引，從該條目可取回適用的轉發信息。
圖8中示出了多路路由trie結構，其示意性地示出主路由存儲器352和輔路由存儲器360上分布的路由查找表。路由trie結構800對應於這樣的情形，其中寄存器352的容量對於本地高速緩存交換模塊110所知的所有路由是不足的。在此情況下，路由trie800的一個或多個節點被保持於NP的寄存器存儲器352外部的RAM360中。
與上面關於圖7討論的多路路由trie700相似，trie結構800包括源自與待查找的標準相關聯的節點的多個支路。多個節點包括根節點A1和中間節點B1-B2、C1-C5，其中的每一個被本地高速緩存於NP的寄存器存儲器352中。葉節點在這裡包括本地高速緩存於NP的寄存器存儲器352中的第一組節點D2-D3、D10-12、D5-D7。該路由trie還包括RAM360中保持的第二組節點D1*、D8*、D9*。寄存器352和RAM360中保持的這些節點之間的邏輯邊界是由劃分線802圖示的。
為了使路由查找表250在寄存器352和RAM360之間動態地查找，與RAM360中的子節點D1*、D8*、D9*相關聯的每個父節點包括預設索引值，其造成NP106中的路由查找終止並且回復至微處理器262，其利用輔路由存儲器中保持的路由信息。如果輔路由存儲器360的查找在葉節點D1*、D8*、D9*之間產生了匹配，則指向轉發表354的指針被識別，適用的轉發信息被取回。
在優選實施例中，如果主路由存儲器352容量已滿，則新學習的路由被交付給輔路由存儲器360。也就是，與新學習的路由相對應的節點被併入RAM360內的路由trie結構中，然後監視其利用總數。如果並且當路由管理器356確定了RAM360中的節點比寄存器中的節點使用得相對更為頻繁，則該節點可被自動地重定位至寄存器存儲器352。
圖9中示出了多路路由trie結構，其示意性地示出以下路由查找表，該路由查找表包含輔助存儲器360中的一個或多個次trie用以增大寄存器存儲器352。如上所述，RAM360可用來存儲多路路由trie結構的一個或多個葉以及一個或多個次trie。例如從根節點A1直接分路的整個次trie可被交付給RAM360或者從寄存器352移至RAM360，以釋放寄存器352中的空間用於使用更為頻繁的路由，從而利用寄存器352所給予的相對更快的存取速度。
RAM360中保持的次trie可包括任意數量的節點，並且可作為與根節點和葉節點之間的許多中間節點併入。例如，RAM360中保持的次trie包括中間節點C5*910和子葉節點D10*911、D11*912以及D4*913。RAM360中的次trie結構還可通過從節點A100分支到分級數組B*中的子節點的次trie，來從根節點A1或其他中間節點直接進行分支，如圖4所示。
圖10中示出了在trie已被刪除以利用該轉發信息中的冗餘之後的圖9的多路路由trie結構。特別地，優選實施例的交換模塊110適於識別次trie，其具有多個葉節點以及與相同的轉發信息相關聯的中間節點。如果該轉發信息對於具有公共父節點的每個子節點是相同的，則優選實施例中的交換模塊110引入轉發表354中的新條目，該條目使父節點直接地指向轉發表354，由此解析該轉發信息，而無需橫貫路由trie結構直至真正的葉。
如果圖9中的葉節點D10*911和D11*912例如關聯於相同的轉發信息，則通過將節點C5*強行直接指向轉發表354來將其從中間節點轉換成準葉節點。也就是，如果MAC目標地址(DA-10等於DA-11)、MAC源地址(SA-10等於SA-11)和VLAN(VLAN-10等於VLAN-11)對於D10*911和D11*912是相同的，則改變節點C5*910來及早地終止查找並直接地指向1010轉發表354。特別地，與葉節點C5*910相關聯的stop_bit指示符502的值從0變為1，索引至適用的轉發信息的新指針被插入分級數組中相應條目的第三列503中。具有新指針的條目由葉節點650的列表中的準葉節點C5*910代表，並且指向轉發表中用於D10*911或D11*912的預先存在的條目。
在優選實施例中，通過周期性地監視寄存器葉列表366和RAM活動性表364，來對刪除模塊359進行控制，以識別冗餘和使次trie變小，來增加存儲器和/或減少查找時間。該刪除可應用於寄存器352中、RAM360中或寄存器352和RAM360之間的次trie。
本領域技術人員將發現，使節點C5*910成為準葉節點的操作會使節點D10*911和D11*912在路由查找處理中被繞過。結果，節點D10*911和D11*912將變為不活躍的，其利用總數降至0。如果節點D10*和D11*在節點C5*910變成準葉之前被記錄於寄存器存儲器352中，則當活動性級別降至輔助存儲器360中最為活躍的級別以下時，路由查找表250將節點D10*911和D11*912自動重定位至RAM360。在一些實施例中，冗餘節點，包括D10*911和D11*912，可通過標準的路由老化機制而從多路路由trie中被相繼地去除。
圖11中示出了處理流程圖，交換模塊通過該處理監視並更新路由查找。交換模塊110像其他路由器一樣，通過各種路由交換協議——例如包括OSPF——從其他路由器動態地學習(步驟1102)新路由，或者由網絡管理員以靜態路由來手工地配置。路由管理器356立即確定(步驟1104)在何處將該新路由的一個或多個節點插入多路路由trie結構中，該結構代表路由裝置100的網絡拓撲。在插入一個或多個節點的處理中，路由管理器356將任何新節點邏輯地連結到共享公共IP位址前綴的父節點。
路由管理器356確定(步驟1106)NP的寄存器存儲器352中對於新路由的空間可用性。如果存儲器可用，則寄存器存儲器確定步驟(測試步驟1108)的回答是肯定的，利用插入(步驟1110)父節點來負責新分支的新索引503將新路由的一個或多個節點引入寄存器352中。如果新節點構成寄存器352中的新葉節點，則新的葉確定步驟(測試步驟1112)的回答是肯定的，該路由被添加(步驟1114)到寄存器葉列表366，其用以跟蹤寄存器352中記錄的節點的活動性，以及將其活動性與RAM360中的節點相比較。寄存器葉列表366中的利用總數統計優選為由網絡處理器106編譯和在寄存器活動性表358中編譯的統計子集。寄存器葉列表366中的節點可從最活躍到最不活躍進行歸類和排列，以便於識別和便於從寄存器存儲器352到RAM存儲器360轉移節點。
如果寄存器352中沒有可用的存儲器，則寄存器存儲器確定步驟(測試步驟1108)的回答是否定的，新節點被記錄(步驟1115)於RAM360中。記錄至RAM360的新路由還可被監視以確定其利用總數是否以及何時高得足以保證重定位至寄存器存儲器352。如果新節點也是新的「次trie根節點」，則新的根確定(測試步驟1116)的回答是肯定的，該節點被添加(步驟1118)到RAM活動性表364中。術語「次trie根節點」是指RAM360中的路由trie節點，其父節點駐留於寄存器存儲器352中。RAM360中的次trie根位於主路由存儲器和輔路由存儲器之間的邏輯邊界處，並且是根據相對於寄存器352中的節點頻率而查找這些節點時的頻率來重定位至寄存器存儲器352中的候選。
圖12中示出了處理1200的流程圖，交換模塊通過該處理來監視路由活動並將路由查找表中的節點有選擇性地重定位至主路由存儲器352或輔路由存儲器360。在優選實施例中，查找活動性，即利用總數統計，是確定節點是保持於NP106的相對快的寄存器存儲器352中還是保持於相對慢的外部RAM362中的主要因素。按照優選實施例，與相對不活躍的路由直接有關的節點被分配至相對較慢的RAM360，而與相對活躍的節點有關的節點被分配至相對快的寄存器存儲器352。
在優選實施例中，路由查找表250確定(步驟1202)寄存器葉列表366中列舉的葉節點的利用總數以及RAM活動性表364中次trie根節點的利用總數。在優選實施例的NP106中，寄存器存儲器352中路由trie節點的利用總數是由NP106利用預配置的算法來自動跟蹤的。在優選實施例中，NP106被配置為每當出於路由查找目的而存取節點時增加與該節點相關聯的「命中位」，即一位計數器。NP106或微處理器262周期性地檢查寄存器352中各節點的命中位，以確定設置哪些命中位。如果設置了命中位，則該命中位被初始化為零。如果未設置命中位，則增加一計數器，其跟蹤該節點的閒置周期數。因此每單位時間的閒置周期數是活動性的度量。不活躍的路由經確定的一段時間不被使用時可被刪除或「老化」。在路由被刪除之前維護該路由所需要的命中數優選為由網絡管理員確定的可編程位閾值。
路由管理器356確定RAM362中專有地保持的路由trie節點、特別是活動性表364中次trie根的活動性。對於這些節點，該利用總數是由給定時間段內查找這些節點的次數所給定的頻率度量。在優選實施例中，由微處理器262執行的機器可讀指令使路由管理器356在出於路由查找的目的而使用節點時使RAM活動性表364中的使用計數器增加。對這些使用統計進行累計的時間段優選為由網絡管理員提供的可編程時間段。在優選實施例中，RAM360中次trie根的利用總數等於其最為活躍的子節點的利用總數。
如果RAM360中有比寄存器352中使用更為頻繁的一個或多個路由，則相對活動性確定測試(測試步驟1204)的回答是肯定的，至少一個相對不活躍的節點從寄存器352重定位(步驟1206)至RAM360。隨著寄存器352中的存儲器現在可用了，至少一個相對活躍的路由從RAM360同時重定位至寄存器352(步驟1208)。優選地，交換模塊110在十分之一秒至一秒級別的更新間隔中根據需要周期性地重複重定位節點的處理1200。
在寄存器352或RAM360之間重定位節點的處理1200中，交換模塊110在路由查找表250中保留trie結構的整體拓撲組織。一般而言，節點的重定位需要(a)在寄存器352或RAM360中的分級數組中產生該節點將被移動到此的條目；(b)在新條目中產生一將它連結至恰當的轉發信息的指針；以及(c)刪除從中移除該節點的存儲器中該數組內現有的條目。
除寄存器352中有可用的存儲器之外，在節點可被重定位至寄存器352之前，一些實施例中的節點必須具有超過閒置周期閾值的活動性級別。為了具有路由重定位資格而必需的周期數優選為由網絡管理員確定的可編程閒置周期閾值。
儘管上面的描述包含了許多說明，但是這些不應當理解為限制本發明的範圍，而是僅僅提供此發明的一些當前優選實施例的說明。
因此，本發明已經通過實例非限制性進行了公開，應當參照所附權利要求來確定本發明的範圍。
權利要求
1.一種路由裝置，包括適於接收協議數據單元(PDU)的埠；路由表，用於在具有多個節點的多路trie中存儲多個路由，該路由表包括第一路由存儲器，用於高速緩存所述多個節點的第一組；以及第二路由存儲器，用於高速緩存所述多個節點的第二組；尋路引擎，適於搜索所述路由表用於尋找與所述PDU相關聯的所述多個路由之一；以及路由管理器，適於將所述第二組的一個或多個節點從所述第二路由存儲器重定位至所述第一路由存儲器，其中所述第一路由存儲器的每個所述節點的利用總數高於所述第二路由存儲器的每個所述節點的利用總數。
2.權利要求1的路由裝置，其中所述路由管理器還適於將所述第一組的一個或多個節點從所述第一路由存儲器重定位至所述第二路由存儲器。
3.權利要求1的路由裝置，其中所述第一路由存儲器比所述第二路由存儲器具有更快的存取速度。
4.權利要求3的路由裝置，其中所述第二路由存儲器是隨機存取存儲器。
5.權利要求3的路由裝置，其中所述第一路由存儲器是寄存器存儲器。
6.權利要求5的路由裝置，其中所述尋路引擎和寄存器存儲器被具體實施於專用集成電路(ASIC)中。
7.權利要求6的路由裝置，其中所述ASIC是網絡處理器。
8.權利要求1的路由裝置，其中所述路由表的所述搜索包括所述PDU的網際網路協議(IP)地址的搜索。
9.權利要求1的路由裝置，其中所述多個節點的每一個的利用總數是每個節點搜索活動性的度量。
10.權利要求1的路由裝置，其中所述路由裝置還包括轉發表，當所述尋路引擎識別出關聯於所述PDU的所述多個路由之一時，轉發信息從該轉發表中被取回。
全文摘要
公開了一種路由裝置及相關的方法，用於在兩個或更多存儲器裝置之間分配轉發路由表的多路trie的節點。在優選實施例中，該路由裝置包括路由表，用於在多路trie中存儲多個路由，該多路trie在用於高速緩存多個trie節點的第一組的第一存儲器中和在用於高速緩存多個trie節點的第二組的第二存儲器中；以及路由管理器，適於將第二組的一個或多個節點從第二存儲器重定位至第一存儲器，從而第一存儲器的每個節點的利用總數高於第二存儲器的每個節點的利用總數。
文檔編號G06F12/02GK1761238SQ200510102920
公開日2006年4月19日 申請日期2005年9月14日 優先權日2004年9月14日
發明者格雷戈裡·佩奇 申請人:阿爾卡特公司