一種路由表分布式存儲轉發架構及其查找算法

摘要：面向路由器FIS（Forwarding In Switch， FIS）處理機制，提出了一種基于路由表分布式存儲的多級流水并行查找架構，采用多個低速的具有獨立轉發和交換功能的轉發交換結點FSN（Forwarding and Switching Node）構成多級流水線，針對IPv6最長匹配前綴的查找需求，設計了一種基于前綴范圍的二分查找算法PSB-BS（Prefix Scope Based Binary Search）：將IPv6轉發表組織為分層結構，每一層對應不同長度范圍的前綴信息，采用二分查找策略對子樹層進行搜索，通過構建非對稱二分查找樹實現了轉發表在FSN結點的分布式存儲并能有效降低存儲開銷及IP查找復雜度.仿真結果表明，與目前Cisco商業路由器廣泛采用的樹位圖算法相比，PSB-BS算法顯著降低了存儲及訪存開銷.

關鍵詞：路由器；網絡路由；查找引擎

中圖分類號：TP393 文獻標識碼：A

IP Lookup Architecture and Algorithm Based on Distributed

Storage and Forwarding of Routing Table

DAI Yi，WANG Ke-fei， ZHANG He-ying， WANG Shao-gang

（College of Computer， National Univ of Defense Technology， Changsha， Hunan 410073， China）

Abstract： This paper proposed a parallel multi-level pipeline IP lookup architecture based on distributed storage of routing table that consists of multi-stage lower speed nodes called FSN performing IP-lookups and switching independently. An IPv6 binary lookup algorithm was proposed based on prefix scope called PSB-BS （prefix scope based binary search） for putting IPv6 longest prefix match in practice. The IPv6 route table was partitioned into multiple levels， each representing a specified range of prefixes. By doing binary search over these subtrie levels and especially by constructing asymmetric binary tree， our solution implemented distributed storage of forwarding table， thus reducing the storage overhead as well as the complexity of IP lookup. The experiment results demonstrate the PSB-BS algorithm reduces the storage and memory access overhead considerably， compared with the tree bitmap algorithm widely used in Cisco commercial routers.

Key words： routers； network routing； search engines

Internet網絡流量、網絡規模和上層應用的快速發展，對Internet互聯的核心設備——路由器提出了越來越高的要求.目前核心路由器FIB（Forwarding Information Base）表前綴數目已經達到45萬條，并呈現出指數級增長^[1]， 導致了DFZ（Default Free Zone）路由器FIB極限問題，下一代互聯網 IPv6協議的應用無疑對路由器轉發性能提出了更大的挑戰.為實現高速接口對報文的線速轉發，路由器采用了越來越復雜的并行處理技術.例如Cisco公司的CRS-1路由器在40 Gbps接口的SPP網絡處理器內部集成了多達188個32位的CPU[2].硬件的復雜性不但提升了成本，更抑制了性能的進一步提高.文獻[3]提出了一種新型的報文并行處理機制FIS （Forwarding in Switching），其基本思想是將報文轉發操作融入到交換網絡中分布執行，采用邊轉發邊交換的方式，實現FIB表的分布式存儲及報文轉發操作的流水執行.而現有路由器采用的是FBS （Forwarding before Switching）機制，即報文在進入交換網絡交換之前必須完成精確轉發以確定其輸出端口.在FBS處理機制中，轉發階段與交換階段在邏輯上是分離的，報文轉發操作由線卡中的網絡處理器或專用ASIC芯片集中處理，然后由多級交換網絡將報文發送到目的端口，轉發引擎芯片按照特定的FIB容量及FIB處理能力進行設計，導致路由器FIB處理極限問題.FIS處理機制將IP查找功能分解并映射到多個硬件同構的具有獨立轉發交換功能的FSN（Forwarding and Switching Node）結點分布執行，通過分解FIB表，構建FIB表到FSN結點的映射，每個FSN結點僅保存轉發控制信息一部分執行部分轉發操作，降低了IP查找復雜度；FIB信息在FSN結點的分布式存儲，解決了并行查找機制訪存瓶頸問題.FSN結點通過多級互連網絡構成FSN處理陣列，以流水的方式執行報文轉發和交換，FIS同時開發轉發和交換操作的并行度，降低對單個轉發交換部件的要求，提高路由器的整體轉發和交換能力.

1 基于前綴范圍的二分查找算法

面向FIS處理特性，本文提出一種基于前綴范圍的二分查找算法PSB-BS（Prefix Scope Based Binary Search）：將IPv6轉發表組織為分層結構，每一層僅保存含前綴信息的子樹，忽略子樹的路徑信息即孩子子樹的分布信息，有效降低了存儲開銷；采用二分查找策略對子樹層進行搜索，降低了訪存開銷.轉發表在各級FSN節點的分布式存儲，增強了路由器的FIB擴容能力；每一級FSN節點具有相同的轉發表映像，提高了系統可靠性，易于實現負載均衡，避免流量集中現象.

1.1 FIS原型系統硬件平臺結構

由于三級交換結構，例如負載均衡（load-balanced switch）交換結構[4-5]及并行報文交換結構PPS[6] （Parallel Packet Switch）等，在負載均衡、避免報文亂序、調度簡單且易于提供延遲和吞吐率保證等方面的優勢，我們采用Mesh結構的總線實現三級FSN結點間的全互連，構成3×3的交換轉發陣列.如圖1所示，FIS原型驗證系統包含9片Xilinx公司的XC4VLX25 FPGA，每片外接1片2 MB SRAM，用于保存IPv6轉發表，系統工作頻率100 M，采用外部時鐘電路進行強同步.每個FPGA芯片通過以太網接口連接外部的控制網絡（圖1中未顯示），控制平面通過以太網接口對每個FSN的SRAM芯片進行配置.

為實現對子樹層序列的二分查找，需要在高層子樹中加入指向包含更長前綴的低層子樹的標記.查找hash表時，若匹配標記，則搜索低半層子樹hash表；若匹配前綴則記錄當前LMP，將報文轉至下一級FSN節點處理；若未命中任何表項，則搜索高半層子樹hash表.對子樹層Sl，h的任何子樹T，在訪問層Sl，h的二分查找路徑上比Sl，h高的子樹層都需要加入標記，即根節點級數小于l的子樹層中都需要加入查找Sl，h中每一棵子樹的標記.實際上，盡管同一棵子樹的最大標記開銷為log2w，但標記引發的最壞情況下的回溯次數為O，因此必須消除標記造成的回溯.預計算每個標記M的最長匹配前綴，將標記LMP對應的下一跳信息保存在標記下一跳信息域中.匹配標記時，同時記錄標記LMP的下一跳信息，在低半層子樹查找失敗時，不需要再回溯到高半層子樹，標記LMP就是最終的查找結果.盡量將低層子樹放在查找路徑的前端有利于降低標記開銷，在極端情況下，按照從低層子樹到高層子樹的順序查找時，標記開銷為零，但最壞情況下的查找次數為w.理想的具有低標記開銷且存儲空間分布均衡的二分查找結構難以獲得，一方面，降低標記開銷需要將低層子樹放置在查找路徑的前端；另一方面，存儲空間的均衡分布需要在查找路徑的每一級上放置數量相同的hash表.為了構造最優二分查找樹，我們以遞歸方式劃分二分查找樹中當前節點搜索空間的高低部分，采用啟發式加權函數選擇高/低部分的子樹層，而不是簡單地選擇高半層或低半層子樹，稱之為非對稱二分法.運用兩種不同的加權函數構造非對稱二分查找樹，一種加權函數優先選擇低層子樹以降低標記開銷；另一種加權函數保證查找路徑的每一級具有相同數目的hash表；最終得到非對稱二分查找結構如圖3所示.

2 性能評測

與經典的二分查找算法相比，PSB-BS算法基于范圍的查找策略能夠有效地壓縮查找路徑、減少訪存開銷，并通過調節步長而更具靈活性和可擴展性，適用于IPv6的查找需求.

PSB-BS算法優化策略與前綴分布特性密切相關：1）為降低標記開銷，應盡量將低層子樹放置在查找路徑的前端，并采用“避重就輕”的方式消除對子樹密集層的標記開銷；2）為降低訪存開銷，應盡量將前綴覆蓋率高的層放在查找路徑的前端.

目前IPv6轉發表實驗數據較少，不足以評估查找算法的性能，僅具備參考價值，另一方面學術界對IPv6前綴分布特性尚未達成一致.我們采用隨機生成的IPv6轉發表評估了PSB-BS算法應用于FIS處理機制時，每一級FSN節點的存儲開銷、平均訪存開銷，并獨立評估了PSB-BS算法和樹位圖算法的存儲開銷.PSB-BS查找算法采用CAM節點[7]的存儲方式來保存子樹的前綴信息：每個前綴表項包含匹配位（match bits）、匹配長度（match length）、下一跳（next hop）3個信息域.子樹最大高度h=5，那么每個前綴項包含h bits的匹配位，「log2（h+1）=3 bits的匹配長度和10 bits的下一跳信息（支持1 024個端口），每個子樹塊存儲2個前綴，溢出前綴指針為8 bits，因此每個子樹條目長度為48 bits.溢出前綴塊和子樹塊具有相同尺寸，每個溢出前綴塊至多保存2個前綴，每個FSN節點可支持29個溢出前綴.參與比較的樹位圖算法[8]，步長為4；采用位向量分離、CAM存儲和路徑壓縮3種存儲優化方法；節點長度為38 bits；只有CAM節點保存了前綴的下一跳信息，其他前綴的下一跳信息保存在結果節點（result node，一個結果節點可保存3個前綴的下一跳信息）.

圖4統計了FIS中采用非對稱二分查找結構的PSB-BS算法隨著前綴數量的增加，每一級FSN節點及溢出前綴的存儲開銷.第一級FSN節點存儲開銷明顯大于二、三級FSN節點，這是因為映射到第一級FSN節點的S47，5需要為低層子樹S53，5及第二級的S59，5加入查找標記，S35，5則需要為第二級的S41，5加入查找標記.有時甚至需要為這些標記生成新的子樹，這將耗費大量存儲開銷.第二級和第三級FSN節點存儲開銷相當，溢出前綴所耗費的存儲開銷很小，僅占總存儲開銷的0.02%（4 k）～0.9%（100 k）.

3 結 論

本文基于FIS報文處理特性，針對IPv6更長位寬的轉發需求，提出了基于前綴范圍的二分查找算法PSB-BS（Prefix Scope Based Binary Search）：基于前綴范圍的子樹表示法消除了對路徑信息的保存，降低了存儲開銷，實驗結果表明，該策略可將存儲開銷降低為樹位圖算法的50%；二分查找策略能夠有效壓縮查找路徑，減少訪存開銷，適用于IPv6更長位寬的查找并有利于轉發表在FSN結點的均衡分布.通過構造PSB-BS算法非對稱二分查找樹，實現了IPv6轉發表到FSN結點的分布式存儲與轉發.仿真結果表明，隨著前綴數目的增加，每一級FSN結點的平均查找次數幾乎沒有變化，反映了PSB-BS算法良好的可擴展性.

參考文獻

[1] BGP routing table analysis report [EB/OL]. http：//bgp.potaroo.net.

[2] Cisco Corporation. Next generation networks and the Cisco carrier routing system： white paper of Cisco Systems[R/OL]. San Jose， CA， USA： Cisco Corporation， 2007. http：//www.Cisco.com/warp/public/cc/pd/rt/ 12000/clc/prodlit/reqng_wp.pdf.

[3] DAI Yi， SUN Zhi-gang， SU Jin-shu. Analysis of an evolvable architecture of internet routers [C]//Proceedings of IEEE Workshop on High Performance Switching Routing （HPSR）. New York： IEEE， 2007： 1-5.

[4] KESLASSY I. The load-balanced router [D]. Stanford， CA： Stanford University， 2004.

[5] LIN B， KESLASSY I. The concurrent matching switch architecture [J]. IEEE/ACM Transactions on Networking， 2010，18（4）： 1330-1343.

[6] IYER S， MCKEOWN N. Analysis of the parallel packet switch architecture [J]. IEEE/ACM Transactions on Networking， 2003， 11（2）： 314–324.

[7] EATHERTON W N. Hardware-based internet protocol prefix lookups [D]. Washington， DC： Electrical Engineering Department， Washington University， 1999.

[8] BABOESCU F， RAJGOPAL S， HUANG L B， et al. Hardware implementation of a tree based IP lookup algorithm for OC-768 and beyond [C]//Proceedings of Design Con’05. 2005： 1680-1687.