基於前綴覆蓋級別的二分ip路由查找方法
2023-05-29 18:55:26 1
專利名稱：基於前綴覆蓋級別的二分ip路由查找方法
技術領域：
本發明涉及網際網路高速IP位址査找方法，特別是涉及一種基於前綴覆蓋 級別的二分IP路由查找方法。
背景技術：
IP路由查找是計算機網絡設備關鍵技術之一，IP路由査找需要根據到達分 組的目的IP位址，查找路由表得到該分組去往最終目的地址的下一跳信息(出 接口和下一條IP位址)。
隨著Internet的快速發展，用於主幹網絡互聯的核心路由器的接口速率已 達到2.5Gb/s~10Gb/s，這一速率要求核心路由器每秒能夠轉發幾百萬乃至上千 萬個分組，分組轉發的重要步驟就是査找路由表。因此，IP路由査找面臨巨大 挑戰①路由表越來越大，目前骨幹路由比較已經接近30萬條，並且每年增 長大約5萬條；②接口速率越來越高，10Gbps接口已經商用，40Gbps接口開 始部署；③路由更新頻繁，峰值時達到每秒數千條前綴的更新；④高功耗，網 絡設備功耗以及機房散熱設備的功耗目前已經成為網絡運營的主要成本；⑤32 比特的IPv4正在向128比特的IPv6過渡;⑥CIDR (Classless Inter-Domain Routing)的採用需要路由査找在IP路由前綴和值兩個維度進行匹配，進一步 增加了 IP路由查找的難度。以最小乙太網包長672比特來計算，為保證40Gbps 接口的線速轉發，包轉發率要達到59.5Mpps，每包處理時延小於16.8ns。
針對路由查找，業界提出了種種IP路由查找方案，按照IP路由最長前綴長度匹配的二維特性來分類的話，分類如下
① 基於前綴長度的二分搜索的內存操作次數為O (k)g2W)，其中W為IP
地址長度，對IPv4來說是32，對IPv6來說是128，基於前綴長度的二分搜索 在查找匹配時，向更長的前綴長度方向進行查找；如果不匹配，不能確定是否 該向更長或更短的方向査找，因此需要引入額外的Marker來引導二分搜索得 到正確的結果，導致增量更新複雜。
② 基於前綴長度的線性搜索一般採用Trie結構，完成1次路由查找需要進 行O (W)次內存操作，多比特Trie將內存操作次數減少到0(W/k),其中k為 每次比較的比特位數，但是需要進行前綴擴展導致增量更新複雜。
③ 基於前綴值的二分搜索完成1次路由查找需要進行O (log2N)次內存操 作，N為路由條目的隔閡素，當N為30萬時內存操作次數為18。
④ 基於前綴值的線性搜索完成1次路由查找需要進行O (N)次內存操作， 無法滿足高速IP分組轉發要求。引入TCAM三態內容尋址內存硬體，將路由 前綴按照長度進行降序排列存放，在一個TCAM時鐘周期內對所有的路由表 項進行並行查找，存在多重匹配時優先選擇低地址區的匹配前綴作為結果返 回。返回的結果是一個指向比如SRAM的地址指針，下一條信息和出接口存 放在相應的SRAM中。目前TCAM的時鐘周期可以做到5ns，可以滿足高速 接口線速轉發的要求，在高端路由設備上被大量採用。
綜上所述，方案①、②和(D等基於軟體的IP路由查找方案很難滿足目前 高速IP分組線速轉發要求，方案④基於硬體TCAM的IP路由查找速度快且性 能穩定，但是其缺點也非常明顯，主要表現在高功耗以及表項排序要求導致的 更新複雜。因此，傳統基於軟體的IP路由查找方案很難滿足目前高速IP分組線速轉發要求。
發明內容
本發明所要解決的技術問題是解決傳統基於軟體的IP路由查找方案很難 滿足目前高速IP分組線速轉發要求的問題。
為了解決上述技術問題，本發明所採用的技術方案是提供一種基於前綴覆 蓋級別的二分IP路由査找方法，首先將IP路由前綴按照前綴重疊和覆蓋關係
對該前綴進行分級；然後根據IP路由前綴的級別分別放入不同的TCAM Block 中；通過二分査找算法進行匹配査找，即先査找中間級別的TCAM Block,如 果匹配則繼續按照二分查找算法查找更高級別的TCAM Block,如果沒有匹配 則繼續按照二分査找算法査找更低級別的TCAM Block,直到査找結束。
在上述方案中，對於待添加和刪除的IP路由前綴在相應的TCAM Block 中直接進行插入和刪除，同時對於前綴覆蓋級別發生改變的前綴也要進行相應 級別的TCAM Block更新操作，實現隨機增量更新。
在將IP路由前綴按照前綴重疊和覆蓋關係進行分類的過程中，目前最大 的前綴覆蓋級別對於IPv4為7，對於IPv6為2。
本發明，根據IP路由表中前綴之間的覆蓋和重疊關係將前綴進行分級， 採用基於前綴覆蓋級別的二分路由查找，在每個級別，採用TCAM來完成路 由匹配查找，和傳統TCAM路由查找方法相比，由於同一級別的前綴不會重 疊，不存在排序要求，可以支持隨機增量更新；二分査找特性使得功耗可以降 低約50%;査找可以在卩og2(max—/ew/) + l]個TCAM時鐘周期內完成，滿足高
速分組高速轉發的要求。
圖1為本發明基於Trie結構的IP路由表前綴分級示意圖；圖2為應用本發明的路由器結構示意圖； 圖3為應用本發明的路由器原理示意圖； 圖4為本發明的工作流程圖。
具體實施例方式
本發明提供了一種基於前綴覆蓋級別的二分IP路由查找方法，根據IP路 由表中前綴之間的覆蓋和重疊關係將前綴進行分級，然後採用基於前綴覆蓋級 別的二分路由進行査找，滿足了高速IP分組高速轉發的要求。
通過對骨幹網路由表進行分析，將路由前綴按照前綴重疊和覆蓋關係對前
綴進行分級，不被任何其他前綴覆蓋的前綴稱為0級(Level 0)前綴，只被一 個前綴覆蓋的前綴稱為1級(Levdl)前綴。如圖1所示，雖然網際網路路由條 目在急劇膨脹，也存在大量前綴相互重疊和覆蓋，目前IPv4路由表最大的相 互重疊前綴個數不超過7個，而IPv6路由表最大的相互重疊前綴個數為2個。
處在相同覆蓋級別的前綴是不會相互重疊的，對於某個査找Key值，在某 個級別最多只會有一個匹配。因為如果兩個前綴重疊，則其中必有一個是另外 一個的前綴，他們應該處在不同的級別，因此在同一個Level,所有前綴都是 不重疊和覆蓋的，最多只能有一個前綴匹配待查Key值。
如果某個Key值在某個級別存在匹配，則從根到該級別的路徑上的所有前 綴都會匹配該Key值，因此，如果某Key值在某個級別存在匹配，則在更低 的級別也存在匹配；同理，如果某個Key值在某個級別不存在匹配，則在更高 的級別也不存在匹配。
基於以上分析，本發明提出一種基於路由前綴覆蓋級別的二分IP路由査 找方法，首先將路由前綴按照前綴重疊和覆蓋關係對前綴進行分級，在每個級 別，採用TCAM來完成路由匹配査找，和傳統TCAM路由查找方法相比，於同一級別的前綴不會重疊，不存在排序要求，可以支持隨機增量更新；然後， 根據二分査找算法，從中間的前綴覆蓋級別開始査找，如果匹配，則向更高覆 蓋級別方向進行査找，如果不匹配，根據上述證明肯定不存在更高級別的匹配 前綴，因此直接向更小覆蓋級別的方向進行査找，在査找失敗時不需要引入 Marke來引導二分查找，這一點和基於前綴長度的二分査找算法是完全不同的， 二分査找特性使得功耗可以降低約50%;查找可以在「k^(max一/eve/) + q個 TCAM時鐘周期內完成，其中maxjevel為最大重疊前最個數，目前對於IPv4 為7，對於IPv6為2。現在TCAM時鐘周期小於4ns，因此，對於IPv4可以 在16ns (4個TCAM時鐘周期)內完成，可以滿足40Gbps接口最小包長線速 轉發要求。如果採用流水線結構則可以在一個時鐘周期內返回IP路由査找結 果，滿足高速分組線速轉發要求，同時二分查找特性使得功耗可以降低約50%。 現有商用TCAM晶片支持TCAM Block模式，將表項內容放入同一個TCAM 晶片的不同Block,査找時只需要使能並査找特定的TCAM Block而無需驅動 整個TCAM晶片，可以達到節省TCAM功耗的目的。
本發明的主要思路，第一，對於TCAM路由轉發表項的建立來說，按照 路由前綴所處的覆蓋級別，將路由前綴放入不同的TCAM Block,或者放入不 同的TCAM晶片；第二，對於路由査找來說，採用基於覆蓋級別的二分查找 算法，先査找中間級別的TCAM Block或者TCAM晶片，如果匹配則繼續按 照二分査找算法査找更高級別的TCAM Block或者TCAM晶片，如果沒有匹 配則繼續按照二分查找算法查找更低級別的TCAM Block或者TCAM晶片， 直到二分查找結束，最後記錄的匹配結果則為最長匹配；第三，對於路由更新 來說，由於保存在同一個TCAM Block或者TCAM晶片中的前綴沒有排序要求，路由前綴的插入和刪除可以直接進行，同時對於前綴覆蓋級別發生改變的
前綴也要進行相應級別的TCAM Block或者TCAM晶片更新操作。 以下以圖1中的前綴為例具體說明如下
圖1中的19個前綴a-t分布在5個級別，分別為Level 0到Level4，其中
Level 0:3、h、i、 rru
Level 1:b、6、g、 j、 k、 0;
Level 2:c、d、f、 1、 n、 s、
Level 3:P、
Level 4:q;
假設待査的目的地址最長匹配為前綴Leve 3的p，査找過程為 第l步:査找中間的Leve12，肯定會匹配前綴s;
第2步:根據二分查找特性，將在上半區Level 3和Level 4進行査找；在 Level3進行査找，匹配前綴p;
第3步:繼續在Level4進行査找，不匹配，最後匹配的前綴p為最長匹配 結果。
如圖3所示，IP路由前綴按照前綴覆蓋級別被放置在TCAM晶片的不同 Block或者直接放置在不同的TCAM晶片中以備二分路由查找。入方向，線路 接口 (Line Interface)接收的分組(Packet)傳遞給FPGA邏輯，FPGA從分組 中提取目的地址作為査找關鍵字(Key)傳給IP路由查找部分作二分路由查找， 査找結束後對分組頭部進行修改，包括IP TTL欄位和校驗和等，修改後的分 組(ModifiedPacket)送出接口發送出去。下面結合圖2和圖4具體描述如下
101、設備啟動路由學習完成，控制CPU按照路由前綴的覆蓋級別將相應的前綴分別放入相應的TCAM Block或者TCAM Chip中；
102、 分組Packet到達線路接口 ，經過接口 Phy和Mac層到達FPGA分組
處理邏輯模塊；
103、 分組處理邏輯模塊FPGA進行分組解幀處理，提取目的IP位址作為 査找Key送路由查找邏輯進行二分査找，分組本身被緩存；
104、 開始基於前綴覆蓋級別的二分路由查找，確定二分査找的區域；
105、 判斷二分查找是否結束，也就是區域的下界是否大於上界；如果査 找結束轉110;沒有結束轉106;
106、 將査找Key值和對應的中間級別的TCAM Block或者Chip進行比較；
107、 判斷在本級別的TCAM中是否有匹配該Key值前綴存在，若不存在， 轉108，若存在轉109;
108、 將二分查找區域調整為前綴覆蓋級別的低半區；轉105;
109、 將二分查找區域調整為前綴覆蓋級別的高半區；轉105;
110、 二分査找過程結束，最後匹配的查找結果包含該分組的下一跳和出 接口信息，被送給FPGA分組處理邏輯；
111、 FPGA分組處理邏輯修改分組頭部，包括TTL、校驗和等，分組被送 網出接口排隊發送；
以上所述僅為本發明的較佳實施例，並非用於限定本發明的保護範圍。凡 在本發明的精神和原則之內，所作的任何修改、等同替換、改進等，均應包含 在本發明的保護範圍之內
權利要求
1、基於前綴覆蓋級別的二分IP路由查找方法，其特徵在於將IP路由前綴按照前綴重疊和覆蓋關係對該前綴進行分級；根據IP路由前綴的級別分別放入不同的TCAM Block中；通過二分查找算法進行匹配查找，即先查找中間級別的TCAM Block，如果匹配則繼續按照二分查找算法查找更高級別的TCAM Block，如果沒有匹配則繼續按照二分查找算法查找更低級別的TCAM Block，直到查找結束。
2、 如權利要求1所述的基於前綴覆蓋級別的二分IP路由査找方法，其特 徵在於對於待添加和刪除的IP路由前綴在相應的TCAM Block中直接進行插 入和刪除，同時對於前綴覆蓋級別發生改變的前綴也要進行相應級別的TCAM Block更新操作，實現隨機增量更新。
3、 如權利要求1或2所述的基於前綴覆蓋級別的二分IP路由查找方法， 其特徵在於在將IP路由前綴按照前綴重疊和覆蓋關係進行分類的過程中，目 前最大的前綴覆蓋級別對於IPv4為7，對於IPv6為2。
全文摘要
本發明涉及網際網路高速IP位址查找方法，是一種基於前綴覆蓋級別的二分IP路由查找方法，根據IP路由表中前綴之間的覆蓋和重疊關係將前綴進行分級，採用基於前綴覆蓋級別的二分路由查找，在每個級別，採用TCAM來完成路由匹配查找，和傳統TCAM路由查找方法相比，由於同一級別的前綴不會重疊，不存在排序要求，可以支持隨機增量更新；二分查找特性使得功耗可以降低約50％；查找可以在「log2(max_level)+1個TCAM時鐘周期內完成，其中max_level為最大重疊前綴個數，目前對於IPv4為7，對於IPv6為2，滿足高速分組轉發的要求。
文檔編號H04L12/56GK101515900SQ20091013364
公開日2009年8月26日 申請日期2009年4月13日 優先權日2009年4月13日
發明者朱國勝 申請人:武漢烽火網絡有限責任公司