江國(guó)安

摘要：該文針對(duì)路由器的路由查找，簡(jiǎn)單概述了路由技術(shù)的發(fā)展，路由器的體系結(jié)構(gòu)，硬件路由表的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)等，介紹了FPGA，及基于FPGA的路由技術(shù)，研究了如何用FPGA硬件實(shí)現(xiàn)高效的路由技術(shù)。

關(guān)鍵詞：網(wǎng)絡(luò)；路由器；FPGA；硬件；路由技術(shù)

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2012)16-3806-02

核心路由器由于需要執(zhí)行復(fù)雜的IP路由查找操作,已成為制約因特網(wǎng)性能的新的瓶頸，我們需要高速有效的包調(diào)度、轉(zhuǎn)發(fā)和路由策略，此技術(shù)的研究受到業(yè)界的廣泛關(guān)注[1]。

1路由技術(shù)

英特網(wǎng)的體系結(jié)構(gòu)是分層次的，每個(gè)層次結(jié)構(gòu)上都需要對(duì)應(yīng)功能的路由器。接入網(wǎng)上的路由器主要負(fù)責(zé)的是將家庭用戶和小型企業(yè)網(wǎng)連接到ISP，它面臨的主要問(wèn)題是將使用不同的網(wǎng)絡(luò)技術(shù)的PC接入Internet，這就要求其提供高速的端口，豐富的協(xié)議支持；而企業(yè)級(jí)的路由器則是連接整個(gè)企業(yè)或校園中的所有PC,所以要求其必須易于配置，能提供高密度的端口，支持QoS等功能；骨干網(wǎng)上的路由器是不需要直連用戶端系統(tǒng)的，它們連接的是ISP和企業(yè)級(jí)網(wǎng)，需要能提供高速路由功能。所以,路由技術(shù)對(duì)于整個(gè)網(wǎng)絡(luò)是至關(guān)重要的。

1.1路由器簡(jiǎn)介

路由器的邏輯體系結(jié)構(gòu)主要由路由引擎，轉(zhuǎn)發(fā)引擎，路由表，網(wǎng)絡(luò)適配器和相關(guān)的邏輯電路等幾部分組成。轉(zhuǎn)發(fā)引擎中最關(guān)鍵的就是IP協(xié)議，控制對(duì)路由表的查找，負(fù)責(zé)把數(shù)據(jù)包從一個(gè)網(wǎng)絡(luò)適配器轉(zhuǎn)發(fā)到另一個(gè)網(wǎng)絡(luò)適配器。而路由表的查找效率是整個(gè)路由器的性能的關(guān)鍵因素，因?yàn)槊總€(gè)通過(guò)路由器的數(shù)據(jù)包都需要首先對(duì)路由表進(jìn)行查找然后決定如何進(jìn)行轉(zhuǎn)發(fā)。路由引擎不涉及通過(guò)路由器的數(shù)據(jù)通路，只負(fù)責(zé)對(duì)路由表更新，包括了高層協(xié)議，特別是路由協(xié)議，所有往往用通用的CPU代替。

1.2硬件路由表設(shè)計(jì)

路由表的實(shí)現(xiàn)方法主要有兩大類：基于軟件和基于硬件。但是基于軟件的查找次數(shù)至少為5次，這距離高速鏈路的要求已經(jīng)遠(yuǎn)遠(yuǎn)不夠了；而基于硬件的方法中則有很多結(jié)構(gòu)簡(jiǎn)單，查找速度快，其中最少的只需訪問(wèn)一次存儲(chǔ)器，最多只需要訪問(wèn)兩次存儲(chǔ)器。

通常路由器中路由表的表項(xiàng)都含有以下這些域：目的IP地址域，距離向量度量域，下一跳IP地址域，路由變化標(biāo)志域，路由計(jì)時(shí)器域。如果每一個(gè)IP地址都對(duì)應(yīng)一個(gè)表項(xiàng)，那么就會(huì)占用很大的存儲(chǔ)器空間，但是其中有很多的表項(xiàng)必定沒(méi)有被使用，所以在設(shè)計(jì)路由查找算法時(shí)就需要根據(jù)如下的原則來(lái)設(shè)計(jì)：容易在硬件上實(shí)現(xiàn)，并具有良好的性能和可擴(kuò)展性；能有效的對(duì)存儲(chǔ)器進(jìn)行利用；能提供有效的最長(zhǎng)前綴匹配，并且實(shí)時(shí)的實(shí)現(xiàn)路由表的查找；能實(shí)現(xiàn)路由表的插入和刪除并且支持廣播和組播。

2基于FPGA的路由技術(shù)

在傳統(tǒng)的路由器設(shè)計(jì)中，ASIC設(shè)計(jì)占主導(dǎo)地位，但隨著硬件技術(shù)的不斷發(fā)展，新業(yè)務(wù)不斷涌現(xiàn)，為了能夠快速地響應(yīng)市場(chǎng)需求，形成自己產(chǎn)品獨(dú)特的特色和賣點(diǎn)，基于FPGA實(shí)現(xiàn)的路由器成了一種很好的選擇。

2.1 FPGA簡(jiǎn)介

現(xiàn)場(chǎng)可編程門陣列的簡(jiǎn)稱叫FPGA，是專用集成電路（ASIC）領(lǐng)域中的一種半定制電路，是在PAL、GAL、CPLD等可編程器件的基礎(chǔ)上發(fā)展得來(lái)的產(chǎn)物，解決了定制電路的不足，還克服了原有可編程器件門電路數(shù)有限的缺點(diǎn)，具有較高的靈活性，并且其設(shè)計(jì)周期短，具有成本低、風(fēng)險(xiǎn)小等優(yōu)勢(shì)。越來(lái)越多的設(shè)計(jì)都開(kāi)始從ASIC轉(zhuǎn)向FPGA，成為現(xiàn)代IC設(shè)計(jì)驗(yàn)證的主流技術(shù)。以硬件描述語(yǔ)言Verilog或VHDL設(shè)計(jì)完成的電路，都可以通過(guò)簡(jiǎn)單的綜合與布局，快速燒寫(xiě)到FPGA上進(jìn)行測(cè)試。

FPGA的主要特點(diǎn)如下：設(shè)計(jì)周期短，能夠快速成品，可以反復(fù)修正使用，風(fēng)險(xiǎn)小，更便宜的造價(jià)，開(kāi)發(fā)費(fèi)用低。FPGA采用高速CMOS工藝，功耗低，與TTL電平兼容，其內(nèi)部有豐富的觸發(fā)器和I/O引腳；所以，F(xiàn)PGA芯片是開(kāi)發(fā)路由器的最佳選擇之一。

2.2基于FPGA的路由技術(shù)

在路由器的設(shè)計(jì)過(guò)程中，選擇合適的FPGA來(lái)完成路由器中需要靈活處理的業(yè)務(wù)部分，如路由表的查找，能大大的降低開(kāi)發(fā)風(fēng)險(xiǎn)，有效地縮短開(kāi)發(fā)周期，提高性價(jià)比，增強(qiáng)特色。而IP核的使用也使得FPGA的設(shè)計(jì)可以規(guī)?；?、產(chǎn)業(yè)化[2]。隨著FPGA的發(fā)展，越來(lái)越多的廠商都開(kāi)始采用FPGA來(lái)設(shè)計(jì)實(shí)現(xiàn)路由器。利用現(xiàn)今一些成熟的IP核，如FIR濾波器、SDRAM控制器、PCI標(biāo)準(zhǔn)接口、HDLC控制器、以太網(wǎng)MAC控制器等，將不同的IP核連接起來(lái)，并有效地進(jìn)行數(shù)據(jù)控制、管理，就可以實(shí)現(xiàn)路由器功能設(shè)計(jì)。從系統(tǒng)安全的角度出發(fā)，基于FLASH的技術(shù)硬件出錯(cuò)的概率較小，具有更可靠的安全性，還可以經(jīng)過(guò)現(xiàn)場(chǎng)處理就能實(shí)現(xiàn)產(chǎn)品的升級(jí)換代，支持通過(guò)公共網(wǎng)絡(luò)實(shí)現(xiàn)遠(yuǎn)程升級(jí)等特性，這樣就減少了現(xiàn)場(chǎng)解決問(wèn)題的麻煩和代價(jià)。

FPGA的一般設(shè)計(jì)流程是由電路設(shè)計(jì)與輸入、功能仿真、綜合、再仿真、布線和上板調(diào)試等步驟組成。具體流程如圖1所示。

圖1 FPGA開(kāi)發(fā)流程圖

2.3基于硬件的路由查找實(shí)現(xiàn)

報(bào)文在經(jīng)過(guò)路由器的時(shí)候都要經(jīng)過(guò)一系列的操作后才能被轉(zhuǎn)發(fā)，如查路由表，包轉(zhuǎn)發(fā)，隊(duì)列調(diào)度等操作，這些通常是由硬件來(lái)實(shí)現(xiàn)的。要提高路由器的性能必須從優(yōu)化報(bào)文轉(zhuǎn)發(fā)路徑入手，而其中涉及的最重要的環(huán)節(jié)就是在轉(zhuǎn)發(fā)表中進(jìn)行路由查找，當(dāng)入端口接收到一個(gè)報(bào)文，它需要根據(jù)報(bào)文的目的IP地址查找出端口。轉(zhuǎn)發(fā)表中數(shù)據(jù)形式是<網(wǎng)絡(luò)地址/掩碼,端口>。假設(shè)接收到報(bào)文的目的地址是address1，理論上路由器需要對(duì)路由表中所有表項(xiàng)進(jìn)行匹配查找：將掩碼和address1進(jìn)行與運(yùn)算，若結(jié)果和網(wǎng)絡(luò)地址一致，則將此端口加入到候選端口的集合中。最終選擇的出端口是候選端口集合中掩碼最長(zhǎng)的一項(xiàng)，稱為最長(zhǎng)前綴匹配[3]。

在硬件設(shè)計(jì)實(shí)現(xiàn)路由卡時(shí)，主要需要設(shè)計(jì)實(shí)現(xiàn)狀態(tài)機(jī)，存儲(chǔ)器，譯碼器，掩碼器，比較器，地址寄存器等部分。根據(jù)所需查找的目的IP地址，狀態(tài)機(jī)用來(lái)控制路由表的查找，路由表中存儲(chǔ)的是所要查找的路由信息。主要的工作原理如下：當(dāng)路由器從某一個(gè)網(wǎng)絡(luò)適配器接收到一個(gè)需要轉(zhuǎn)發(fā)的數(shù)據(jù)包后，會(huì)對(duì)IP路由表進(jìn)行查找，這個(gè)過(guò)程也就是把IP數(shù)據(jù)包的目的IP地址送到IP地址寄存器中，同時(shí)對(duì)狀態(tài)機(jī)發(fā)一個(gè)指令，狀態(tài)機(jī)收到后，會(huì)從存儲(chǔ)器中讀出路由表中對(duì)應(yīng)的表項(xiàng)，然后和IP地址寄存器中的相應(yīng)幾位經(jīng)譯碼器，掩碼器后進(jìn)行比較，反饋比較后結(jié)果給狀態(tài)機(jī)，狀態(tài)機(jī)接著控制下一輪的比較，當(dāng)所有的比較結(jié)束后，轉(zhuǎn)發(fā)引擎在路由信息寄存器中讀取最終的結(jié)果，并且狀態(tài)機(jī)在某一特定的端口設(shè)置標(biāo)志，來(lái)告訴CPU查找的狀態(tài)是否已經(jīng)結(jié)束。

通常路由查找算法的速度依賴于這個(gè)算法為了找到路由表項(xiàng)需要訪問(wèn)內(nèi)存的次數(shù)。假設(shè)一個(gè)路由算法需要訪問(wèn)5次內(nèi)存，訪問(wèn)內(nèi)存的速度是70ns，那么總共的查找時(shí)間就是350ns，也就是說(shuō)在1秒鐘大約能完成300000次路由查找。優(yōu)化路由查找性能的方法主要有三類：基于硬件的方法，表緊縮技術(shù)和哈西表技術(shù)。文獻(xiàn)[4][5]中提出了提高更新的速度的解決方案。

3小結(jié)

針對(duì)網(wǎng)絡(luò)流量的增加，及對(duì)路由器性能要求的提高，該文簡(jiǎn)單介紹了路由器和硬件路由表的設(shè)計(jì)，并結(jié)合FPGA技術(shù)，介紹了基于FPGA的路由技術(shù)，從硬件的角度對(duì)IP路由查找的硬件實(shí)現(xiàn)做了簡(jiǎn)單的介紹和分析，同時(shí)可以得出結(jié)論，為了使路由表的查找速率更快，基于ISA總線的實(shí)現(xiàn)已經(jīng)遠(yuǎn)遠(yuǎn)不夠了，由于VHDL語(yǔ)言固有的靈活性和可編程性，可以實(shí)現(xiàn)更為靈活和高效的路由查找，因此使用FPGA芯片來(lái)實(shí)現(xiàn)路由查找技術(shù)，是未來(lái)不可避免的趨勢(shì)。

參考文獻(xiàn)：

[1] RuizSanchez M A,Biersack E W,Dabbous W.Survey and taxonomy of IP address lookup algorit hms[J].IEEE Network,2001,15(2):8-23.

[2]汪超.以太網(wǎng)交換架構(gòu)路由器中基于FPGA的E1接口設(shè)計(jì)[D].上海:上海交通大學(xué),2009.

[3]譚明鋒，龔正虎.基于AsIc實(shí)現(xiàn)的高速可擴(kuò)展并行IP路由查找算法[J].電子學(xué)報(bào)，2005，33(2)：209-213.

[4] Gupta P,Lin S, McKeown N.Routing Lookups in Hardware at Memory Access Speeds[C]//Guerin R. Proceedings of IEEE INFOCOM98, San Francisco, CA:IEEE Computer Society Press,1998:1240-1247.

[5] Brodnik A.Small Forwarding Tables for Fast Route Lookups[J].ACM Computer Communication Review,1997,27(4):3-14.