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

　0 引言

　　隨著網絡流量的不斷增加和路由表容量的不斷增大，路由查找已經成為制約因特網的主要瓶頸。盡管采用CIDR技術能產生聚集路由，但路由器的路由表項還是很大，使得路由查找成為高速路由器的瓶頸。因此，提高路由查找速度已成為高速路由器的關鍵技術。

　　目前實現路由查表的方法主要有軟件和硬件兩類。其中基于軟件查表方法的查找次數最少為5次，這顯然已經不能滿足高速鏈路的要求；而基于Cache的查找方法，其查找依賴于流量的模式，即IP數據流具有局部性，隨著網絡數據量的增大，命中率也會降低。而基于硬件的Stanford算法則結構簡單，易于硬件實現，而且查找速度快，其最少需要訪問一次存儲器，最多需要訪問2次存儲器。但其占用存儲空間大(為33 MB)，表項更新單元數多。在最壞情況下，更新一個表項需要操作64 k個存儲單元。

　　本文采用多表結構，將查找過程分為4級。

　　因為采用串行查找實現時，查找一個IP數據包最少需要訪問一次存儲器，最多需要訪問4次。而根據四塊存儲器獨立工作的特性，采用流水線的方式進行并行化設計，則可以保證訪問一次存儲器就能完成一次數據包的查找。為了保證占用較小的空間且四個存儲塊的容量相對均衡，本文用一個動態規劃算法來求解四個目標層的值。此外，這種設計結構也支持動態更新，并且更新單元數較少。

　　1 查找算法

　　本系統的基本算法采用分段查找及前綴擴展技術來將IPv4的32位IP地址分成4段，假設i是其中一段(1≤i≤4)，length i代表第i段所對應的IP地址長度。每一段內容存儲在一塊物理地址連續的內存區域中，稱為TBLi。那么，在第一段區域TBL1中，使用前綴擴展技術，即可把所有長度小于等于length1的前綴擴展成長度為length1的前綴。圖1所示是該四級路由算法的結構框圖。

　　顯然，該結構中的第一段有2length1個表項，析出IP地址的前length1位的值為第一塊內存的偏移地址，其對應表項的數據格式如圖2所示。若前綴長度小于等于length1，則表項的第一位標識為0，其余bit位表示下一跳的轉發信息。若前綴長度大于length1，則表項的第一位標識為1，其余位填寫擴展表的索引值可以作為指向TBL2的指針。在其余的三個段中，可采用同樣的方法進行前綴擴展。

　　本算法的查找過程是在匹配一個IP地址時，從第一段開始進行分段查找，每查找一段，則解析出對應段長度的IP，并取相應內存區域的地址。例如進行第二段查找時，可將其值作為偏移量，再加上相應的基址，就可獲得該段對length1+1位開始，然后解析出length2長度的IP地址作為偏移量。之后再用TBL1表項里的索引，將其左移length2位作為基址，這樣就確定了第二塊連續存儲區域中的地址。依次類推，分段查找，直到找到下一跳地址為止。

　　本算法的插入過程與查找過程相似，先根據前綴對應的分段和索引查找到對應的子表，然后在其涉及的范圍內讀取各個表項，再根據表項的值確定是否用新的路由前綴信息覆蓋該表項。如果在此過程中，該表沒有相應的段空間，則需分配對應的存儲空間。若該段空間為空，則收回該存儲空間。

　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核心路由器環境下的查找機制。