[發明專利]一種路由查找方法和裝置

有效

• 申請號: 200910129472.6
• 申請日: 2009-03-20
• 公開（公告）號: CN101505279A
• 公開（公告）日: 2009-08-12
• 發明（設計）人: 卜佑軍;黃慧群;王濱;劉勤讓;申涓;張風雨;王超
• 申請（專利權）人: 中國人民解放軍信息工程大學
• 主分類號: H04L12/56
• 分類號: H04L12/56
• 代理公司: 北京集佳知識產權代理有限公司
• 代理人: 逯長明;王寶筠

技術領域

本發明涉及計算機網絡及通信領域，具體地說，涉及路由查找方法及 裝置。

背景技術

互連網協議路由轉發表線速查找技術是核心骨干路由器關鍵技術之 一。路由查找是指對每個到達的IP報文根據其目的IP地址確定其應轉發 的輸出端口號和下一跳地址。為提高IPv4地址空間的利用率，減緩路由 表中表項的增長速度，提出的無類域間路由(Classless?Inter-domain? Routing，CIDR)技術，地址前綴長度可為不超過IPv4地址寬度的任意長 度。CIDR技術的應用要求在進行地址查找時選擇地址前綴長度最大的表 項作為最終的查找結果，即進行最長前綴匹配(Longest?Prefix?Match， LPM)。傳統的基于單一下一跳的高速查找方案大都是基于硬件三重內容 可編址存儲器(Ternary?Content?Addressable?Memory，TCAM)來實現的， 在基于TCAM的實現方案中引入流水線技術可以滿足核心路由器查找速 率和更新速率的要求。

傳統的路由機制中，網絡的中間節點到目的節點除按路由協議得到的 最優路徑外，還存在多條次優路徑，但目前只選擇最短路徑來轉發數據報 文，網絡資源沒能得到充分利用。

隨著因特網的快速發展，由于安全、費用和帶寬等因素，路由器需要 為某些數據流做負載平衡和策略路由，在路由表中為一些目的網絡保存多 個下一跳信息，因此路由器的路由表中存在著相當數量的多下一跳路由， 目前很多擁塞避免機制就是利用次優路徑承擔網絡中間節點的負載。多下 一跳路由的存在是路由表的重要特征之一，它增加了路由查找方案設計的 復雜度，而且支持多下一跳路由查找的方法很有限。

現有技術中提供的一種支持多下一跳路由的高速路由查找方案，通過 建立兩級索引表的方式組成高速查找結構，適宜于流水線查找。但只是從 多下一跳地址中利用一定的策略選擇一個下一跳，不適合路由器根據查找 結果做負載平衡。

現有技術中提供的另一個基于TCAM的多下一跳路由并行查找的方法， 將多下一跳的路由查找分為兩個階段：第一個階段是進行路由前綴匹配， 第二個階段是進行匹配前綴的多下一跳路由查找。具體地，通過對路由表 項增加長度標識，使前綴長度體現在表項中，實現了TCAM中表項免排序 技術；使用前綴擴展，將前綴長度種類減少到只有四種(16、20、24、32)， 采用4個TCAM并行查找，在查找周期內即可得到匹配表項；又通過對表 項增加了多下一跳表示，第二階段的多下一跳路由查找仍然通過TCAM來 進行，提高了TCAM資源的利用率，降低了系統的復雜性。但該方法由于 采用了前綴擴展技術以及在表項中增加前綴長度標識和下一跳序號標識， 使得路由表項迅猛膨脹，致使TCAM芯片的成本和功耗加大，且由于IPv6 的前綴長度種類比IPv4豐富，使前綴擴展變得復雜，因此該方法不適合 擴展到IPv6的多下一跳路由信息擴展。同時，由于第一階段和第二階段 均需對相同的4片TCAM進行操作，每次操作的周期數隨多下一跳數目的 不同而不同，無法引入流水線技術來提高查找速度。這些不足均限制了此 并行查找方法的使用。

發明內容

本發明解決的技術問題是提供一種可支持多下一跳路由信息的路由 查找方法及裝置，可以一次查出多條下一跳路由信息，同時提供每條路由 信息的流量分配比例，從而可以在數據平面上完成負載均衡的轉發。

本發明實施例提供的一種路由查找方法，包括：

將待查找地址與預定的最長前綴進行匹配；

得到所述最長前綴對應的多下一跳路由的數目及偏移地址；

獲取所述多下一跳路由對應的基址，根據所述基址確定多個下一跳路 由轉發的索引地址并保存，具體包括：按照下一跳路由的數目確定相應的 存儲區域，根據多下一跳路由信息的數目，連續訪問相應存儲區，讀出多 個索引地址，將下一跳路由的數目對應的索引地址及相應流量分配比例保 存到所述相應的存儲區域；

根據所述索引地址得到對應的多下一跳路由轉發信息；

其中，路由器根據所述路由轉發信息和所述流量分配比例，完成負 載均衡轉發或策略路由。

本發明實施例提供的一種路由查找裝置，包括：

匹配單元，用于將待查找地址與預定的最長前綴進行匹配，得到所述 最長前綴對應的多下一跳路由的數目及偏移地址；