李淵　阮軍洲

（1中國(guó)電子科技集團(tuán)第五十四研究所，河北　石家莊　050081）

（2解放軍75660部隊(duì)，廣西　桂林　541002）

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

李淵1阮軍洲2

（1中國(guó)電子科技集團(tuán)第五十四研究所，河北石家莊050081）

（2解放軍75660部隊(duì)，廣西桂林541002）

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

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

1　引言

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

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

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

2.1基于Radix樹結(jié)構(gòu)的查找算法

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

2.2線性查找hash表算法

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

圖1　hash表數(shù)據(jù)結(jié)構(gòu)

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

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

3　路由查找算法描述

基于Hash和Radix的路由查找算法結(jié)合了Radix樹結(jié)構(gòu)的查找算法和hash表算法的優(yōu)勢(shì)，具有占用內(nèi)存空間少和查表命中時(shí)間短等特點(diǎn)。該算法的具體查表過(guò)程如下：

①將待查目的IP地址的第一字節(jié)作為第一入口關(guān)鍵字，將待查目的IP地址的第一字節(jié)和第二字節(jié)進(jìn)行組合作為第二入口關(guān)鍵字，將待查目的IP地址的第一字節(jié)、第二字節(jié)和第三字節(jié)進(jìn)行組合作為第三入口關(guān)鍵字；同時(shí)送入一一對(duì)應(yīng)的3個(gè)并行查找模塊；以目的IP 192.168.1.3為例，其第一入口關(guān)鍵字、第二入口關(guān)鍵字和第三入口關(guān)鍵字分別為：

②3個(gè)入口關(guān)鍵字分別通過(guò)hash函數(shù)得到其所在hash桶中的索引地址，該索引地址存儲(chǔ)著該入口關(guān)鍵字對(duì)應(yīng)Radix樹的入口地址；其中，第一入口關(guān)鍵字的索引地址為第一入口關(guān)鍵字的本身值；第二入口關(guān)鍵字的索引地址和第三入口關(guān)鍵字的索引地址均選用CRC-10算法計(jì)算獲得，hash桶深度為8；其中，CRC-10的計(jì)算多項(xiàng)式為其中，為多項(xiàng)式因子。3個(gè)hash桶的結(jié)構(gòu)如圖2所示。

圖2　Hash桶結(jié)構(gòu)

③在得到3個(gè)入口關(guān)鍵字的Radix樹的入口地址后，同時(shí)進(jìn)入3個(gè)Radix樹存儲(chǔ)空間，分別對(duì)每個(gè)Radix樹的每個(gè)節(jié)點(diǎn)進(jìn)行訪問(wèn)，每個(gè)節(jié)點(diǎn)由前綴比特串、8位掩碼，下一跳索引值、要比較的比特位序號(hào)、左子樹指針和右子樹指針構(gòu)成；

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

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

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

⑦當(dāng)3個(gè)并行查找模塊全部完成查表，并輸出查表結(jié)果后，根據(jù)最長(zhǎng)匹配的原則，按照第三入口關(guān)鍵字、第二入口關(guān)鍵字和第一入口關(guān)鍵字優(yōu)先級(jí)順序?qū)⒆罱K的查表結(jié)果作為下一跳索引值，至此完成基于Hash和Radix樹的路由查找。

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

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

圖3　系統(tǒng)總體結(jié)構(gòu)

5　仿真測(cè)試結(jié)果

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

圖4　仿真測(cè)試平臺(tái)結(jié)構(gòu)

圖5　仿真波形結(jié)果

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

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

6　結(jié)束語(yǔ)

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

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

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

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

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

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

［6］夏宇聞.Verilog數(shù)字系統(tǒng)設(shè)計(jì)教程［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