基于FPGA的高速路由查找算法
加入技術(shù)交流群
3 硬件結(jié)構(gòu)
依據(jù)該算法設(shè)計(jì)出的基于4級流水線的并行處理結(jié)構(gòu)如圖3所示，該結(jié)構(gòu)分為存儲器模塊、查找模塊和更新模塊三個部分。4個存儲模塊可存儲對應(yīng)表TBL中的數(shù)據(jù)；查找模塊可通過讀取對應(yīng)存儲模塊中的數(shù)據(jù)實(shí)現(xiàn)查找；更新模塊則可將要更新的路由信息添加到對應(yīng)的存儲塊中。本文引用地址：http://www.ex-cimer.com/article/191858.htm
在FPGA設(shè)計(jì)時，每個查找模塊都是一個硬件邏輯塊，每兩個查找模塊間都有一個寄存器用以傳輸數(shù)據(jù)，每個查找模塊都可從輸入端或寄存器中讀取信息，并解析出IP地址中的相應(yīng)位，然后計(jì)算存儲器的訪問地址，訪問存儲器獲取數(shù)據(jù)，并將數(shù)據(jù)寫入寄存器或者輸出端。四個查找模塊按流水線的工作方式進(jìn)行處理，能夠達(dá)到訪問一次存儲器處理一個IP數(shù)據(jù)包。
4 實(shí)驗(yàn)結(jié)果分析
通過對BGP Table中前綴的長度進(jìn)行分析和統(tǒng)計(jì)，可模擬生成50,000條前綴。然后用動態(tài)規(guī)劃求出4個目標(biāo)層(20，22，24和32)來進(jìn)行實(shí)驗(yàn)分析。實(shí)驗(yàn)可采用Stratix系列芯片，并利用Ver-ilog硬件描述語言和QuartusII開發(fā)平臺進(jìn)行設(shè)計(jì)、綜合、布局布線，然后在靜態(tài)時序分析后進(jìn)行仿真，其時序仿真結(jié)果如圖4所示。由于查找需要一個時鐘周期，而時鐘頻率為100MHz，所以，每秒可以完成100M次查找。若IP分組為40B長，則可以滿足20Gbps的鏈路速率。
5 結(jié)束語
本文給出了一種基于前綴擴(kuò)展的分段快速路由查找算法。該算法可以結(jié)合硬件實(shí)現(xiàn)的優(yōu)點(diǎn)，并運(yùn)用多級流水線處理方法，因而具有查找速度快、支持動態(tài)更新和實(shí)現(xiàn)簡單等優(yōu)點(diǎn)，十分適合于20 Gbps核心路由器環(huán)境下的查找機(jī)制。
評論