對基于FPGA的高速路由查找算法的研究

　　2 目標層的確定

　　在用NT(k，ω)表示前綴長度為w的情況下，還需要找出k個目標層時對應的最小前綴擴展數。這樣，其最優解就是NT(k，ω)。其遞推公式如下：

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

　　3 硬件結構

　　依據該算法設計出的基于4級流水線的并行處理結構如圖3所示，該結構分為存儲器模塊、查找模塊和更新模塊三個部分。4個存儲模塊可存儲對應表TBL中的數據；查找模塊可通過讀取對應存儲模塊中的數據實現查找；更新模塊則可將要更新的路由信息添加到對應的存儲塊中。

　　在FPGA設計時，每個查找模塊都是一個硬件邏輯塊，每兩個查找模塊間都有一個寄存器用以傳輸數據，每個查找模塊都可從輸入端或寄存器中讀取信息，并解析出IP地址中的相應位，然后計算存儲器的訪問地址，訪問存儲器獲取數據，并將數據寫入寄存器或者輸出端。四個查找模塊按流水線的工作方式進行處理，能夠達到訪問一次存儲器處理一個IP數據包。

　　4 實驗結果分析

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

　　5 結束語

　　本文給出了一種基于前綴擴展的分段快速路由查找算法。該算法可以結合硬件實現的優點，并運用多級流水線處理方法，因而具有查找速度快、支持動態更新和實現簡單等優點，十分適合于20 Gbps核心路由器環境下的查找機制。