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