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

0 引言
隨著網(wǎng)絡(luò)流量的不斷增加和路由表容量的不斷增大，路由查找已經(jīng)成為制約因特網(wǎng)的主要瓶頸。盡管采用CIDR技術(shù)能產(chǎn)生聚集路由，但路由器的路由表項(xiàng)還是很大，使得路由查找成為高，速路由器的瓶頸。因此，提高路由查找速度已成為高速路由器的關(guān)鍵技術(shù)。
目前實(shí)現(xiàn)路由查表的方法主要有軟件和硬件兩類。其中基于軟件查表方法的查找次數(shù)最少為5次，這顯然已經(jīng)不能滿足高速鏈路的要求；而基于Cache的查找方法，其查找依賴于流量的模式，即IP數(shù)據(jù)流具有局部性，隨著網(wǎng)絡(luò)數(shù)據(jù)量的增大，命中率也會(huì)降低。而基于硬件的Stanford算法則結(jié)構(gòu)簡(jiǎn)單，易于硬件實(shí)現(xiàn)，而且查找速度快，其最少需要訪問一次存儲(chǔ)器，最多需要訪問2次存儲(chǔ)器。但其占用存儲(chǔ)空間大(為33 MB)，表項(xiàng)更新單元數(shù)多。在最壞情況下，更新一個(gè)表項(xiàng)需要操作64 k個(gè)存儲(chǔ)單元。
本文采用多表結(jié)構(gòu)，將查找過程分為4級(jí)。
因?yàn)椴捎么胁檎覍?shí)現(xiàn)時(shí)，查找一個(gè)IP數(shù)據(jù)包最少需要訪問一次存儲(chǔ)器，最多需要訪問4次。而根據(jù)四塊存儲(chǔ)器獨(dú)立工作的特性，采用流水線的方式進(jìn)行并行化設(shè)計(jì)，則可以保證訪問一次存儲(chǔ)器就能完成一次數(shù)據(jù)包的查找。為了保證占用較小的空間且四個(gè)存儲(chǔ)塊的容量相對(duì)均衡，本文用一個(gè)動(dòng)態(tài)規(guī)劃算法來求解四個(gè)目標(biāo)層的值。此外，這種設(shè)計(jì)結(jié)構(gòu)也支持動(dòng)態(tài)更新，并且更新單元數(shù)較少。

1 查找算法
本系統(tǒng)的基本算法采用分段查找及前綴擴(kuò)展技術(shù)來將IPv4的32位IP地址分成4段，假設(shè)i是其中一段(1≤i≤4)，length i代表第i段所對(duì)應(yīng)的IP地址長(zhǎng)度。每一段內(nèi)容存儲(chǔ)在一塊物理地址連續(xù)的內(nèi)存區(qū)域中，稱為TBLi。那么，在第一段區(qū)域TBL1中，使用前綴擴(kuò)展技術(shù)，即可把所有長(zhǎng)度小于等于length1的前綴擴(kuò)展成長(zhǎng)度為length1的前綴。圖1所示是該四級(jí)路由算法的結(jié)構(gòu)框圖。

顯然，該結(jié)構(gòu)中的第一段有2length1個(gè)表項(xiàng)，析出IP地址的前l(fā)ength1位的值為第一塊內(nèi)存的偏移地址，其對(duì)應(yīng)表項(xiàng)的數(shù)據(jù)格式如圖2所示。若前綴長(zhǎng)度小于等于length1，則表項(xiàng)的第一位標(biāo)識(shí)為0，其余bit位表示下一跳的轉(zhuǎn)發(fā)信息。若前綴長(zhǎng)度大于length1，則表項(xiàng)的第一位標(biāo)識(shí)為1，其余位填寫擴(kuò)展表的索引值可以作為指向TBL2的指針。在其余的三個(gè)段中，可采用同樣的方法進(jìn)行前綴擴(kuò)展。
本算法的查找過程是在匹配一個(gè)IP地址時(shí)，從第一段開始進(jìn)行分段查找，每查找一段，則解析出對(duì)應(yīng)段長(zhǎng)度的IP，并取相應(yīng)內(nèi)存區(qū)域的地址。例如進(jìn)行第二段查找時(shí)，可將其值作為偏移量，再加上相應(yīng)的基址，就可獲得該段對(duì)length1+1位開始，然后解析出length2長(zhǎng)度的IP地址作為偏移量。之后再用TBL1表項(xiàng)里的索引，將其左移length2位作為基址，這樣就確定了第二塊連續(xù)存儲(chǔ)區(qū)域中的地址。依次類推，分段查找，直到找到下一跳地址為止。
本算法的插入過程與查找過程相似，先根據(jù)前綴對(duì)應(yīng)的分段和索引查找到對(duì)應(yīng)的子表，然后在其涉及的范圍內(nèi)讀取各個(gè)表項(xiàng)，再根據(jù)表項(xiàng)的值確定是否用新的路由前綴信息覆蓋該表項(xiàng)。如果在此過程中，該表沒有相應(yīng)的段空間，則需分配對(duì)應(yīng)的存儲(chǔ)空間。若該段空間為空，則收回該存儲(chǔ)空間。

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í)還要考慮前綴捕獲問題。Nl(ω)是ω層原有的前綴數(shù)目。