基于Hash和Radix樹的路由查找算法研究

李淵　阮軍洲

（1中國電子科技集團第五十四研究所，河北　石家莊　050081）

（2解放軍75660部隊，廣西　桂林　541002）

基于Hash和Radix樹的路由查找算法研究

李淵1阮軍洲2

（1中國電子科技集團第五十四研究所，河北石家莊050081）

（2解放軍75660部隊，廣西桂林541002）

介紹了路由查找算法的研究背景和技術指標，對比了基于Radix樹和Hash的路由查找算法，進而提出了一種基于Hash和Radix樹相結合的路由查找算法，詳細介紹了該算法的數(shù)據(jù)結構和實現(xiàn)步驟，同時給出了該算法基于FPGA的硬件實現(xiàn)模型并設計了對該模型的邏輯仿真結構，對邏輯仿真結構中的測試激勵產(chǎn)生機制作了介紹。針對邏輯仿真波形進行了分析，結果顯示該算法實現(xiàn)了8.6X106次查找/s。

Radix樹路由查找Hash表邏輯仿真

1　引言

隨著互聯(lián)網(wǎng)的迅速發(fā)展，Internet的速度不斷提高，網(wǎng)絡流量不斷增加，相應的路由表規(guī)模也不斷擴大。網(wǎng)絡容量的不斷提高要求路由器能夠每秒中內轉發(fā)盡可能多的分組，而分組轉發(fā)效率提高的重要一步就是路由查找算法的實現(xiàn)，即在路由表中查找最長前綴匹配路由。

目前，基于最長匹配原則的路由查找功能在硬件上通常采用外置TCAM或者DDR實現(xiàn)。該方法雖然滿足了路由查找對匹配命中時間及路由表項數(shù)的要求，但是也帶了功耗加大，成本增加等問題。尤其是在一些對功耗、電路板面積要求比較苛刻，甚至明確要求不能使用TCAM或DDR的場合（例如，衛(wèi)星星上交換設備），該方法顯然不能滿足要求。因此，本文提出一種基于Hash和Radix的路由查找算法，該算法適用于在FPGA片內實現(xiàn)，同時又不占用太多FPGA資源，能夠快速命中路由表項。

2　幾種路由查找算法的介紹

2.1基于Radix樹結構的查找算法

Radix樹結構是每一個分支上都帶有標號的二叉樹，其左分支對應0，右分支對應1，然后沿著與待查IP地址匹配的分支逐比特查找。進行匹配查找時，首先從根節(jié)點開始查起，每次從待查IP地址中讀取1比特，如果該比特為0則查詢當前節(jié)點的左節(jié)點；為1則查詢當前節(jié)點的右節(jié)點。按照此規(guī)則逐比特查詢，直至遇到葉子節(jié)點或者當前節(jié)點無相應子節(jié)點時結束查詢操作。對于Radix樹結構，如果待查IP地址長度為W，最壞情況下需要讀O（W）次存儲器。在基本的Radix樹結構中，即使某節(jié)點不是有效前綴，也需要分配空間來存儲子結點指針，浪費了存儲空間。因此，為了節(jié)省存儲空間，同時減少內存訪問次數(shù)，需要對Radix樹進行壓縮處理［1］。

2.2線性查找hash表算法

該算法對待查IP地址運用哈希技術和多路哈希表進行查找，從而找到最長匹配前綴。其數(shù)據(jù)結構如圖1所示。

圖1　hash表數(shù)據(jù)結構

該算法的查找過程如下：首先在數(shù)組中從后往前進行查找，即從長度最長32的元素開始，通過hash指針查找其對應的哈希表，若哈希表表項非空，則找到最長匹配前綴，查找結束；否則繼續(xù)往前查找。直至查找結束時，哈希表表項中記錄的就是能匹配上的最長前綴所對應的信息。

線性查找hash表算法采用并行查表設計，可在較短的時間內完成路由查找操作；但是對于每個前綴長度的查詢都要通過哈希函數(shù)，而性能良好的哈希函數(shù)又很難找到，同時轉發(fā)表更新時要增加一些前綴，這有可能降低哈希函數(shù)的性能，就要重新選擇哈希函數(shù)，組織哈希表，且增加了更新的難度［1］。

3　路由查找算法描述

基于Hash和Radix的路由查找算法結合了Radix樹結構的查找算法和hash表算法的優(yōu)勢，具有占用內存空間少和查表命中時間短等特點。該算法的具體查表過程如下：

①將待查目的IP地址的第一字節(jié)作為第一入口關鍵字，將待查目的IP地址的第一字節(jié)和第二字節(jié)進行組合作為第二入口關鍵字，將待查目的IP地址的第一字節(jié)、第二字節(jié)和第三字節(jié)進行組合作為第三入口關鍵字；同時送入一一對應的3個并行查找模塊；以目的IP 192.168.1.3為例，其第一入口關鍵字、第二入口關鍵字和第三入口關鍵字分別為：

②3個入口關鍵字分別通過hash函數(shù)得到其所在hash桶中的索引地址，該索引地址存儲著該入口關鍵字對應Radix樹的入口地址；其中，第一入口關鍵字的索引地址為第一入口關鍵字的本身值；第二入口關鍵字的索引地址和第三入口關鍵字的索引地址均選用CRC-10算法計算獲得，hash桶深度為8；其中，CRC-10的計算多項式為其中，為多項式因子。3個hash桶的結構如圖2所示。

圖2　Hash桶結構

③在得到3個入口關鍵字的Radix樹的入口地址后，同時進入3個Radix樹存儲空間，分別對每個Radix樹的每個節(jié)點進行訪問，每個節(jié)點由前綴比特串、8位掩碼，下一跳索引值、要比較的比特位序號、左子樹指針和右子樹指針構成；

④確定查找關鍵字：第一入口關鍵字對應的Radix樹中的查找關鍵字為待查目的IP地址的第二字節(jié)；第二入口關鍵字對應的Radix樹中的查找關鍵字為待查目的IP地址的第三字節(jié)；第三入口關鍵字對應的Radix樹中的查找關鍵字為待查目的IP地址的第四字節(jié)；

⑤將查找關鍵字與節(jié)點的8位掩碼進行與運算，將運算結果同前綴比特串進行比較，如二者相同則認為節(jié)點匹配，進入第⑥步；如二者不相同，則回退至前一個匹配節(jié)點，如果不存在匹配節(jié)點，則該待查目的IP沒有匹配路由項，查找模塊輸出未匹配信號，結束本次查表，進入第⑦步；

⑥當節(jié)點匹配時，如果要比較的比特位序號為零，則此節(jié)點為最終的匹配節(jié)點，查找模塊輸出下一跳索引值，結束本次查表，進入第⑦步；如果要比較的比特位序號不為零，則提取查找關鍵字中要比較的比特位序號對應的比特值，當該比特值為0時，下一節(jié)點的訪問地址為左子樹指針，當該比特值為1時，下一節(jié)點的訪問地址為右子樹指針；訪問下一節(jié)點時，返回第⑤步；

⑦當3個并行查找模塊全部完成查表，并輸出查表結果后，根據(jù)最長匹配的原則，按照第三入口關鍵字、第二入口關鍵字和第一入口關鍵字優(yōu)先級順序將最終的查表結果作為下一跳索引值，至此完成基于Hash和Radix樹的路由查找。

4　路由查找算法硬件實現(xiàn)

在對基于Hash和Radix的路由查找算法進行算法分析后，使用可綜合的Verilog HDL對該算法的硬件實現(xiàn)模型進行了RTL級的描述，其總體結構如圖3所示。

圖3　系統(tǒng)總體結構

5　仿真測試結果

為了驗證算法的功能和性能，對該模型進行功能邏輯仿真。根據(jù)所要仿真測試的功能，采用modelsim軟件搭建了仿真測試平臺，該測試平臺的總體結構如圖4所示。其仿真過程為：測試激勵產(chǎn)生器隨機產(chǎn)生路由前綴、目的IP地址以及下一跳地址；CPU配置驅動器根據(jù)測試激勵產(chǎn)生器產(chǎn)生的測試向量配置被測模塊；測試向量驅動器將測試向量輸入被測模塊；被測模塊的運行結果可以通過modelsim軟件的打印輸出窗口和波形窗口進行觀察，如圖5所示。

圖4　仿真測試平臺結構

圖5　仿真波形結果

通過功能仿真，可觀察到被測模塊的輸入輸出波形正確，被測模塊的結果輸出符合期望的路由查找結果。圖5為一次路由查找的過程：在該波形中，macth_enable=1，表示開始進行路由查找；當serach_over=1和match_ok=1時，表示一次查找完成，此時match_index輸出查找結果，即下一跳地址。

通過對仿真結果的分析和理論估計，模型的工作頻率為200 MHz，即時鐘周期為5 ns，該路由查找模塊達到的基本性能為：8.6X106次查找/s。在功能仿真中存儲1000條路由前綴需要的存儲容量少于2 Mbit。

6　結束語

與現(xiàn)有技術相比，本文提出的基于Hash和Radix樹的路由查找算法占用存儲器資源少，無需添加外設即可在FPGA片內實現(xiàn)基于最長匹配的路由查找算法；由于對目的IP地址進行了關鍵字劃分并采用了并行查找方法，縮短了路由查找時間，極大的提高了路由查表性能；該算法適合于對低功耗，低成本和穩(wěn)定性要求高的場合。

［1］CHAO J H.broadband packet switching technologies：a practical guide to atm switches and ip routers［M］.2001.

［2］李鷗，鄔江興，汪斌強，等.一種分段式高速IP路由查找方法［J］.通信學報，2001，22（5）：93-96.

［3］徐恪，徐明偉，吳建平，等.路由查找算法研究綜述［J］.軟件學報，2002，13（1）：42-50.

［4］劉亞林.動態(tài)快速路由查找算法［J］.中國工程科學，2002，4（7）：60-68.

［5］程耀林.FPGA的系統(tǒng)設計方法解析［J］.微型電腦應用，2007 （1）：48-51，68.

［6］夏宇聞.Verilog數(shù)字系統(tǒng)設計教程［M］.北京：北京航天航空出版社，2003.

Research on Router Lookup Algorithm Based on Hash and Radix Tree

LI Yuan1，RUAN Jun-zhou2
（1.The 54th Research Institute of CETC，Shijiazhuang Hebei 050081，China）
（2.Unit 75660，PLA，Guilin Guangxi 541002，China）

This paper introduces the research background and some technical parameters of the route lookup algorithm.Comparing the router lookup algorithm based on Radix tree with the router lookup algorithm based on Hash，a kind of router lookup algorithm is proposed，which combines together the router lookup algorithms based on Hash and Radix tree.The data structure and implementation steps of this algorithm are presented.The hardware implementation model based on FPGA is given and the structure of logical simulation for this model is designed.This paper introduces the test excitation generation mechanism.The analysis is performed for logical simulation waveform，and the result shows that this algorithm can realize 8.6X106 routing lookup/s.

Radix tree；router lookup；Hash table；logical simulation

TP391.4

A

1008-1739（2015）11-42-3

定稿日期：2015-05-12