對(duì)基于FPGA的高速路由查找算法的研究

　　2 目標(biāo)層的確定

　　在用NT(k，ω)表示前綴長(zhǎng)度為w的情況下，還需要找出k個(gè)目標(biāo)層時(shí)對(duì)應(yīng)的最小前綴擴(kuò)展數(shù)。這樣，其最優(yōu)解就是NT(k，ω)。其遞推公式如下：

　　式中，Nu(l，ω)表示將l+1層至ω-1層擴(kuò)展到ω層的前綴數(shù)目，其中若某一層不存在，則將那一層直接忽略。另外，在擴(kuò)展時(shí)還要考慮前綴捕獲問(wèn)題。Nl(ω)是ω層原有的前綴數(shù)目。

　　3 硬件結(jié)構(gòu)

　　依據(jù)該算法設(shè)計(jì)出的基于4級(jí)流水線(xiàn)的并行處理結(jié)構(gòu)如圖3所示，該結(jié)構(gòu)分為存儲(chǔ)器模塊、查找模塊和更新模塊三個(gè)部分。4個(gè)存儲(chǔ)模塊可存儲(chǔ)對(duì)應(yīng)表TBL中的數(shù)據(jù)；查找模塊可通過(guò)讀取對(duì)應(yīng)存儲(chǔ)模塊中的數(shù)據(jù)實(shí)現(xiàn)查找；更新模塊則可將要更新的路由信息添加到對(duì)應(yīng)的存儲(chǔ)塊中。

　　在FPGA設(shè)計(jì)時(shí)，每個(gè)查找模塊都是一個(gè)硬件邏輯塊，每?jī)蓚€(gè)查找模塊間都有一個(gè)寄存器用以傳輸數(shù)據(jù)，每個(gè)查找模塊都可從輸入端或寄存器中讀取信息，并解析出IP地址中的相應(yīng)位，然后計(jì)算存儲(chǔ)器的訪(fǎng)問(wèn)地址，訪(fǎng)問(wèn)存儲(chǔ)器獲取數(shù)據(jù)，并將數(shù)據(jù)寫(xiě)入寄存器或者輸出端。四個(gè)查找模塊按流水線(xiàn)的工作方式進(jìn)行處理，能夠達(dá)到訪(fǎng)問(wèn)一次存儲(chǔ)器處理一個(gè)IP數(shù)據(jù)包。

　　4 實(shí)驗(yàn)結(jié)果分析

　　通過(guò)對(duì)BGP Table中前綴的長(zhǎng)度進(jìn)行分析和統(tǒng)計(jì)，可模擬生成50,000條前綴。然后用動(dòng)態(tài)規(guī)劃求出4個(gè)目標(biāo)層(20，22，24和32)來(lái)進(jìn)行實(shí)驗(yàn)分析。實(shí)驗(yàn)可采用Stratix系列芯片，并利用Ver-ilog硬件描述語(yǔ)言和QuartusII開(kāi)發(fā)平臺(tái)進(jìn)行設(shè)計(jì)、綜合、布局布線(xiàn)，然后在靜態(tài)時(shí)序分析后進(jìn)行仿真，其時(shí)序仿真結(jié)果如圖4所示。由于查找需要一個(gè)時(shí)鐘周期，而時(shí)鐘頻率為100MHz，所以，每秒可以完成100M次查找。若IP分組為40B長(zhǎng)，則可以滿(mǎn)足20Gbps的鏈路速率。

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

　　本文給出了一種基于前綴擴(kuò)展的分段快速路由查找算法。該算法可以結(jié)合硬件實(shí)現(xiàn)的優(yōu)點(diǎn)，并運(yùn)用多級(jí)流水線(xiàn)處理方法，因而具有查找速度快、支持動(dòng)態(tài)更新和實(shí)現(xiàn)簡(jiǎn)單等優(yōu)點(diǎn)，十分適合于20 Gbps核心路由器環(huán)境下的查找機(jī)制。