江國安

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

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

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

1.1路由器簡介

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

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

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

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

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

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

2.1 FPGA簡介

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

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

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

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

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

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

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

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

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

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

3小結(jié)

針對網(wǎng)絡(luò)流量的增加，及對路由器性能要求的提高，該文簡單介紹了路由器和硬件路由表的設(shè)計，并結(jié)合FPGA技術(shù)，介紹了基于FPGA的路由技術(shù)，從硬件的角度對IP路由查找的硬件實現(xiàn)做了簡單的介紹和分析，同時可以得出結(jié)論，為了使路由表的查找速率更快，基于ISA總線的實現(xiàn)已經(jīng)遠(yuǎn)遠(yuǎn)不夠了，由于VHDL語言固有的靈活性和可編程性，可以實現(xiàn)更為靈活和高效的路由查找，因此使用FPGA芯片來實現(xiàn)路由查找技術(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è)計[D].上海:上海交通大學(xué),2009.

[3]譚明鋒，龔正虎.基于AsIc實現(xiàn)的高速可擴(kuò)展并行IP路由查找算法[J].電子學(xué)報，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.