高性能星載IP交換機路由查找算法的研究與實現

張俊俊，陳慶華，喬廬峰，王　晶

(解放軍理工大學 通信工程學院，江蘇 南京 210000)

?

高性能星載IP交換機路由查找算法的研究與實現

張俊俊，陳慶華，喬廬峰，王晶

(解放軍理工大學 通信工程學院，江蘇 南京 210000)

摘要：由于衛星空間環境的特殊性，星載設備在設計上受到了體積、功耗、可靠性等諸多因素的限制限制，因此地面路由器中采用的路由查找算法不能簡單的搬到星上路由器中。為此，提出一種將壓縮二叉樹算法、哈希查找相結合的適合星上的IP路由查找方法。使用Xilinx xc6vlx130t FPGA實現了該查找算法，電路共占用338K字節片上存儲器資源和1 256個Slices，可以滿足三模冗余設計要求。在系統工作主頻為100 MHz、包長為64字節的情況下，查找電路的峰值查找速度能達到10.24 Gb/s,可以滿足10 Gb/s以上的系統設計需求。

關鍵詞：星載IP交換機；壓縮二叉樹；哈希查找；FPGA

0引言

隨著衛星通信技術的不斷發展，衛星通信系統的技術體制正逐漸由“彎管”轉發向星上交換過渡。當前星上交換主要采用ATM交換技術體制[1]，星載ATM交換技術可在硬件規模較小時實現較高的數據轉發能力。但隨著地面網中寬帶IP交換技術的廣泛應用，在協議體質上可以和地面網無縫鏈接的星載IP交換技術的研究成為熱點[2]。

將地面網中高性能IP交換機關鍵技術應用于衛星的最大困難是微電子器件的限制。太空中劇烈的環境溫度變化和輻射效應都會對器件的正常工作產生嚴重的影響。星載設備中大量使用的FPGA在空間環境下很容易遭受單粒子翻轉，從而發生不可預料的硬件錯誤等現象。采用三模冗余的方法可以提高電路對抗粒子效應的能力，但該方法要求一片FPGA的主要資源使用量原則上不能超過總資源量的1/3，這對IP交換機中的硬件資源提出了苛刻的要求。另外，星載IP交換機可用存儲器也受到了嚴格的限制，宇航級SRAM、SDRAM和DDR的容量和工作時鐘時鐘頻率通常遠低于普通商用級器件。

地面網中，較為主流的IP路由查找算法包括三態內容尋址存儲器(Ternary Content Addressable memory, TCAM)[4]、trie查找和哈希查找。TCAM是在CAM[5]的基礎上發展而來，與CAM相比可以支持最大長度的路由查找，它的優點是在一個時鐘周期內可以完成一次查找，但由于其成本、功耗高的缺點限制了它在星上的應用。

Trie查找又可分為二進制trie、路徑壓縮trie、多分支trie[6]和層級壓縮LC-trie[7]。路徑壓縮trie去掉了二進制trie樹中不包含轉發信息并且沒有分支的中間節點，減少了稀疏二叉樹的高度。多分支trie算法是一次檢查多個比特，與二進制trie樹相比提高了查找效率，但信息的冗余度較高，需耗費更大的存儲空間。LC-trie算法結合路徑壓縮trie和多分支trie的特點進一步優化trie樹結構，但插入和刪除操作可能導致樹的變動比較大。LC-trie算法結合路徑壓縮trie和多分支trie的特點進一步優化trie樹結構，但插入和刪除操作可能導致樹的變動比較大。

基于hash算法的路由查找[8,9]一直是查找領域研究的重點。基于哈希查找算法的機制使用hash表來存放路由信息，能實現精確匹配查找，具有查找速度快、更新簡單的優點，而且易于用硬件實現。但由于在哈希查找中會存在哈希沖突，所以構建一個好的哈希函數是保證哈希算法高效的關鍵。

因此，本文在上述研究的基礎上，針對星上IP交換的特點，提出了一種將壓縮二叉樹算法、哈希算法以及地址老化技術有效結合的路由查找算法，該算法在資源消耗較小的情況下能滿足高性能星載IP交換機的查找需求。

1IP查找電路的構成與工作機制

圖1是本文查找電路的一個結構模型， CPU上運行協議棧并產生用于硬件查找的轉發表，并通過總線把轉發表更新到trie樹節點存儲區和路由表存儲區。本設計把哈希表和直連主機表結合在一起，CPU可直接向直連主機表中添加或刪除路由表項，方便用戶對路由表進行管理。

當IP報文流到達路由器，經過相應的鏈路層處理后，以串行IP包隊列的方式等待IP路由查找引擎處理。查找引擎抽取每個數據包的目的IP地址并同時對其進行hash查找和最長前綴匹配查找。一般情況下，hash查找的速度快于最長前綴匹配查找。如果目的IP地址在hash表中實現精確匹配，則返回哈希表中的路由信息并通知trie樹查找電路終止查找。如果目的IP地址在hash表中沒有實現匹配，則繼續等待trie樹的查找結果，并將其作為最終的路由查找結果，同時查找引擎把基于trie樹查找的端口號和其它路由信息更新到hash表中。這樣同一流的其他包就可以直接在hash表中快速實現精確匹配，查找到相應的轉發端口，避免對相同的目的IP地址重復進行最長前綴匹配查找，從而有效提高IP路由查找效率。

圖1IP路由查找電路結構

2星載IP查找算法的設計與優化

2.1壓縮二叉樹算法查找機制

二叉樹算法以其資源消耗小以及靈活性高的特點在路由查找方面得到了廣泛的應用，它只需根據IP地址逐個比特進行查找，直到最長前綴匹配完成。但其不足之處是，對于IPv4來說，樹的深度為32，這表示在最壞情況下存儲訪問的次數為32次。對于trie樹存儲的前綴的最大長度為W，路由表表項數為N，則二叉樹查找復雜度為O(W)，更新復雜度也是O(W)，存儲復雜度為O(NW)。

在二進制trie樹中含有許多不含轉發信息的中間節點，為減少trie樹查找存儲訪問的次數，提高trie樹的查找速度，需要對trie樹結構進行優化，去掉不含轉發信息的中間節點，這種算法稱作路徑壓縮算法。圖2(a)是前綴節點為P={P1(*),P2(1*),P3(00*),P4(101*),P5(1000*),P6(1111*)}的二進制trie樹，通過去除那些沒有包含路由前綴信息并且只有一個兒子的節點，圖2(a)變成圖2(b)。節點數據結構中增加了壓縮的位數Skip和壓縮內容兩個部分。經過路徑壓縮后，二叉樹的存儲復雜度為O(N)，只與路由表的表項數目N有關，而與前綴的長度無關。

在上世紀九十年代之前，城市地下管線管理技術正處于萌芽階段。在此段時期，由于我國國民經濟及基礎設施落后，地下管線種類少，規模小，僅為給排水、供電通訊等幾類，其管線應用水平也較低，城市地下管線信息資料僅為規劃設計數據、完工數據和開井檢查數據等，且保存方式以紙質、圖表為主，隨著保存時間的增長，不僅容易損壞、丟失，而且不便于查找、匯總分析等，造成我國城市地下管線數據信息大量丟失。當時我國的城市地下管線管理技術還處于萌芽階段，主要以傳統的管理模式為主。

圖2　路徑壓縮trie樹示例

此次二叉樹查找電路設計將路由信息分為節點存儲區和路由表兩部分，分別存儲查找使用的路由索引信息和路由轉發端口信息，如圖3所示。在圖3(c)中，節點存儲區的數據結構由左兒子、右兒子、壓縮標志位(SF)、索引以及校驗和構成。當SF=1時，表示存在比特壓縮，此時左兒子并不指向下一個節點，其高4位表示壓縮的比特位，定義最大值不超過4，這是便于FPGA查找實現考慮的；低4位表示壓縮的比特值；右兒子指向下一個節點。當SF=0時，表示不存在比特壓縮，左兒子和右兒子分別指向下一個節點。路由索引為15比特，和路由表的索引值是一一對應的關系，通過返回路由下標值，指向路由表索引，從而在路由表中找到轉發信息。

圖3　trie樹節點存儲區和路由表結構

2.2hash算法查找機制

Hash查找算法是一種高速查表算法，它通過hash函數建立起關鍵字集合到hash索引之間的一種映射，由hash索引進行表項查找。Hash函數建立的從關鍵字集合到hash索引之間的映射是一種多對一的映射，在這里32位IP地址映射為12位的哈希索引值，勢必會造成一定的hash沖突，這會嚴重影響哈希查找的性能。所以保證哈希查找算法高效最關鍵的要素就是構建一個使沖突發生概率較小的哈希函數。

文獻[10-11]分析和比較了幾種hash函數，雖然多數哈希函數如異或止折疊函數或比特抽取函數，容易用軟硬件實現，但其性能并不讓人滿意。循環冗余校驗(CRC)函數[13]具有良好的性能，使之產生沖突的概率較小，但計算復雜性較高。本文中采用的hash函數為循環冗余校驗函數。另外在設計中采用多個哈希桶，如圖4(a)所示，這樣能進一步降低哈希沖突對哈希查找性能造成的影響。

圖4　哈希桶以及表項結構

哈希桶中每個表項的具體數據結構如圖4(b)所示。hash表主要有查找、插入和老化三種操作。

當進行查找時，IP地址通過hash函數得到一個hash值，并以hash值為地址同時對4個哈希桶中的表項進行匹配。一般情況下，hash查找可以在5個時鐘周期內返回查找結果。

Hash表的插入操作有兩種情況。一種情況是目的IP地址沒有在hash表中實現精確匹配，則查找引擎把基于ctrie查找的路由結果插入到hash表中。另一種情況是CPU可直接向hash表中插入靜態路由，并把direct host置為高電平，說明該表項只能由CPU進行管理。

Hash表的老化有兩種觸發方式。一種是正常老化，每個表項都有一個生存周期。Hash電路根據電路產生的秒脈沖自動發起老化檢查，將生存周期內沒有進行匹配過的表項清除，即把item valid置為低電平。另一種是強制更新，即ctrie更新后，需要經現有的表項清空，從而使hash表和ctrie保持同步。此時hash中的表項無論壽命如何都要進行清除，然后根據ctrie重新填入。由于強制更新會使整個hash表清空，因此進行二叉樹查找的數據包會突然增加，導致查找速度減慢。由于星上環境的特殊性，路由表不會發生太劇烈的變化，因此哈希表的表項基本保持不變。所以在此設計中我們減慢了hash表的老化速度，由此可以防止hash表更新過快，避免造成查找速度上的波動。

3仿真結果與分析

本路由查找算法實現選用的是Xilinx的xc6vlx130t FPGA，開發環境采用的是Xilinx集成開發環境ISE14.3，電路核心模塊采用Verilog HDL編程實現，并用仿真軟件Modelim SE10.0a進行測試仿真。

根據壓縮二叉樹算法，編寫測試程序，經過編譯后可以得到兩個文本文件，分別存儲在節點存儲區和IP路由表，其中節點存儲區有5 418個節點，IP路由表有1 264條表項。此章節主要測試ctrie算法與ctrie-hash算法的查找速度對比情況，如果后者的查找效率更高，則說明該算法更適合星上路由查找。

3.1ctrie算法仿真

為了對比兩種路由查找算法的性能，我們從二叉樹算法生成的路由表中選出三組IP地址43.21.12.51、25.163.209.0和10.24.0.0進行測試。對這三組IP地址連續進行兩次測試，由于這三組IP地址是進行ctrie算法查找，則每次查找所耗費的時鐘周期數是相同的。仿真波形如圖5所示，se_result_port_ctrie即是基于ctrie查找的輸出端口號，完成一次查找耗費大約35個時鐘周期。

圖5IP地址進行ctrie查找的仿真波形

3.2ctrie-hash算法仿真

對ctrie-hash算法用相同的IP地址進行測試。由于這三組IP地址是首次進行路由查找，不能在hash表中實現精確匹配，因此它們的首次查找結果是基于最長前綴匹配查找的，即完成首次查找所耗費的時鐘數與單獨進行ctrie查找所耗費的時鐘數是相同的。仿真波形如圖6所示。

圖6　IP地址進行首次ctrie-hash查找的仿真波形

IP地址首次被查找過后，hash表進行了更新，當IP地址再次進行查找時，就能在hash表中實現快速精確匹配，仿真波形如圖7 所示。Se_result_port_hash即是基于hash查找的輸出端口號，完成一次查找耗費5個時鐘周期。

圖7　IP地址第二次ctrie-hash查找的仿真波形

3.3綜合結果分析

Ctrie-hash和ctrie查找算法分別在Xilinx的xc6vlx130t FPGA進行了實現，使用Xilinx XST對其進行綜合，綜合結果如表1所示。從表1中可以看出，在路由表和哈希表深度分別為2K和 4K的情況下，基于ctrie-hash的查找電路共占用1256個Slices和77塊內部Block RAM，一些關鍵資源消耗量都大于基于ctrie的查找電路，但都低于FPGA總資源量的1/3，可以支持完全的三模冗余設計，從而滿足星載設備對可靠性的要求。

查找速度是衡量查找算法的主要依據，它決定了星上路由器的報文處理能力。時鐘頻率為100 MHz，數據包的長度為64字節時，基于ctrie查找的報文轉發速率為1.5 Gbps，而基于ctrie-hash查找的報文轉發速率能達到10.24 Gbps，可滿足吞吐率為10 Gbps以上的星載路由器需求。

表1　兩種查找算法電路綜合結果對比

4結語

本文設計實現了可適用于星載IP交換機的路由查找算法，該算法結合了壓縮二叉樹和哈希查找算法，使其能支持最長前綴匹配和精確匹配查找，有效的提高了路由查找效率。整個查找電路在Xilinx的xc6vlx130t FPGA上實現，占用的資源較小，可支持完全的三模冗余設計，能滿足星載路由器的設計需求。時鐘頻率的提高和使用片外存儲，能進一步提高其查找性能，這也是下一步要做的工作。

參考文獻：

[1]Tonguz O K, Sunil Maloo. Internet Access via LEO Satellite Networks: TCP/IP or ATM? [C]. Global Telecommunications Conference. Piscataway:IEEE,1999:301-305.

[2]Buster D. Towards IP for Space-based Communications Systems: a CISCO Systems Assessment of a Single Board Router [C]. Military Communication Conference. Piscataway: IEEE, 2005: 1-7.

[3]ZHENG K, HU C. A TCAM-based Distributed Parallel IP Lookup Scheme and Performance Analysis [J]. IEEE/ACM Trans, 2006, 14(4): 863-875.

[4]Akhbarizadeh M J, Nourani M. A TCAM-based Parallel Architecture for High Speed Packet Forwarding [J]. IEEE Trans, 2007, 56(1): 58-72.

[5]吳彤, 楊嗣超, 諸鴻文. 路由表快速查找算法 [J]. 通信技術, 2000, 4(111): 52-55.

WU Tong, YANG Si-chao, ZHU Hong-wen. Routing Table for Fast Lookup Algorithm [J]. Communications Technology, 2000, 111(4): 52-55.

[6]Srinivasan V, Varghese G. Faster IP Lookups using Controlled Prefix Expansion [C]. Proc. Acm Sigmatics. Madison: IEEE, 1998: 1-10.

[7]Nilsson S, Karlsson G. IPAddress Lookup using LC-Trie [J]. IEEE Journal on Selected Areas in Communications, 1999; 17(6):1083-1092.

[8]XI T, YAN Q. Guided Multiple Hashing: Achieving Near Perfect Balance for Fast Routing Lookup [C]. ICNP, 21th International Conference. Goettingen: IEEE, 2013: 1-10.

[9]Demetriades S, Hanna S C M, Melhem R. An Efficient Hardware-based Multi-Hash Scheme for High Speed IP Lookup [C]. Proc. HOTI. Stanford: IEEE, 2008.

[10]Martinez C, LIN W M. Advanced Hash Algorithms with Keys Bits Duplication for IP Address Lookup [C]. Networking and Servics Conference. Valencia: IEEE, 2009: 137-142.

[11]Yamaguchi F, Nishi H. Hardware-based Hash Functions for Network Applications [C]. Networks, 19thIEEE Internet Conference. Singapore:IEEE,2013:1-6.

張俊俊(1991—)，男，碩士，主要研究方向為高性能路由查找算法；

陳慶華(1976—)，男，講師，主要研究方向為交換技術和計算機網絡；

喬廬峰(1971—)，男，教授、碩士生導師，主要研究方向為通信和計算機網絡中關鍵芯片和電路技術；

王晶(1989—)，男，碩士，主要研究方向為高性能路由調度算法。

Reasearch and Implementation of Routing Lookup Algorithm

for High-Performance Satellite-Borne IP Switch

ZHANG Jun-jun, CHEN Qing-hua, QIAO Lu-feng, WANG Jing

(Institute of Communication Engineering, PLA University Science and Technology, Nanjing Jiangsu 210000, China)

Abstract：Due to the particular environment of the space, there exist many restrictions on satellite-borne equipment such as size, power consumption and reliability, the routing lookup algorithm adopted by ground router might not be completely suitable for space router. For this reason, a novel IP router lookup algorithm in combination of compressed binary tree algorithm with Hash lookup algorithm is proposed. The whole design is implemented in Xilinx xc6vlx130t FPGA, with the circuits occupying 338K bytes on-chip memory resource and 1256 Slices, and thus could meet the requirements of the triple modular redundancy. This algorithm,with a peak lookup speed of 10.24 Gb/s,could satisfy the system design requirement of above 10 Gps in working frequency of 100 MHz and in packet length of 64 bytes.

Key words：satellite-borne IP switch; compressed binary tree; Hash locating; FPGA

作者簡介：

中圖分類號：TN918

文獻標志碼：A

文章編號：1002-0802(2015)12-1395-05

收稿日期：2015-07-16；修回日期：2015-10-20Received date:2015-07-16；Revised date：2015-10-20

doi:10.3969/j.issn.1002-0802.2015.12.015