基于前綴擴(kuò)展的三級(jí)索引路由查找算法

唐麗梅 ，邢素霞 ，陳天華

（1.北京工商大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，北京 100048；2.北京英瑞博系統(tǒng)技術(shù)有限公司，北京 100039）

隨著網(wǎng)絡(luò)的高速發(fā)展，Internet的網(wǎng)絡(luò)傳輸量每幾個(gè)月就增加一倍，這也給高速路由的設(shè)計(jì)帶來了挑戰(zhàn)，骨干網(wǎng)路由器接口速率已經(jīng)達(dá)到Tb/s量級(jí)，IP路由查找操作已經(jīng)成為路由器轉(zhuǎn)發(fā)性能乃至Internet整體性能的主要瓶頸之一。因此提高路由查找速度的關(guān)鍵是采用快速的路由查找算法。

路由器IP路由查找面臨巨大挑戰(zhàn)，主要表現(xiàn)在：（1）實(shí)現(xiàn)最長(zhǎng)前綴匹配的路由查找算法設(shè)計(jì)困難[1]；（2）路由表龐大，查找記錄條目極多；（3）路由更新頻繁，最高每秒更新條目達(dá)幾萬條；（4）接口速率越來越高，OC-768（40 Gb/s）以太網(wǎng)及更高標(biāo)準(zhǔn)要求。實(shí)現(xiàn) 100 Gb/s接口的線速轉(zhuǎn)發(fā)，包轉(zhuǎn)發(fā)率要達(dá)到150 Mb/s，每包處理時(shí)延小于 6.72 ns。

快速的路由查找技術(shù)一直是一個(gè)熱門課題，近年來提出了不少路由查找算法，傳統(tǒng)的基于軟件的路由查找算法已經(jīng)不能滿足分組的線速轉(zhuǎn)發(fā)，目前高性能核心路由器基本上都采用基于硬件的路由查找算法。路由查表實(shí)現(xiàn)的主要功能就是最長(zhǎng)前綴匹配 （LongestPrefix Matching）?；谇熬Y值的二分搜索、頁面壓縮等基于樹的搜索存儲(chǔ)空間占用少，利用率高，但由于算法實(shí)現(xiàn)復(fù)雜，硬件實(shí)現(xiàn)上不合適。TCAM （Content Addressable Memory）[2]采用保存關(guān)鍵字掩碼的方式來保存任意長(zhǎng)度的關(guān)鍵字表項(xiàng)，并且使用并行比較，僅在一個(gè)時(shí)鐘周期內(nèi)就可以完成一次查表操作，能夠?qū)崿F(xiàn)高速查表。但是TCAM的路由表更新操作復(fù)雜、功耗大[6]、容量小且價(jià)格昂貴。這些缺點(diǎn)使研究人員考慮用基于SRAM的算法來實(shí)現(xiàn)LPM。

在基于SRAM的算法中，SRAM每比特存儲(chǔ)需要6個(gè)晶體管，功耗低，TCAM每比特的價(jià)格是SRAM的30倍?？梢?，一個(gè)好的基于SRAM的算法比TCAM更具吸引力。由于路由查表的速度和復(fù)雜性的需要，采用單一的查找算法達(dá)不到理想的速度和效率，因此應(yīng)采用多種算法的綜合以及輔助策略。

本文介紹的路由查找算法利用前綴擴(kuò)展的特性，構(gòu)造三級(jí)索引表，并利用流水線并行方式查表，最少一次訪問存儲(chǔ)器，最多3次訪問存儲(chǔ)器就能查找到包轉(zhuǎn)發(fā)信息（輸出端口、下一跳IP地址等）。由于對(duì)數(shù)據(jù)結(jié)構(gòu)作特定優(yōu)化，能支持動(dòng)態(tài)分配表項(xiàng)空間。對(duì)更新算法加入緩存的思想，大大減小了地址占用和申請(qǐng)的開銷。

1 查找算法原理

1.1 前綴擴(kuò)展特性[3]

本算法主要利用前綴擴(kuò)展的特性，采用特定的結(jié)構(gòu)來構(gòu)造索引表。前綴擴(kuò)展是將長(zhǎng)度不同的前綴集合中所有小于最長(zhǎng)前綴長(zhǎng)度的前綴統(tǒng)一擴(kuò)展為不小于最長(zhǎng)前綴長(zhǎng)度的集合。例如，有前綴集合 P={0*，10*，111*，11001*}，其中最長(zhǎng)前綴長(zhǎng)度為 5，把所有長(zhǎng)度小于 5的前綴加以擴(kuò)展，擴(kuò)展結(jié)果如表1所示。經(jīng)擴(kuò)展后，集合P形 成 一 個(gè) 新 的 集 合 P={00000*，00001*， … ，10111*，11100*，11101*，11110*，11111*}。 前綴擴(kuò)展的目的是把任意長(zhǎng)度的前綴變成固定長(zhǎng)度的前綴來簡(jiǎn)化查找操作。

表1 前綴擴(kuò)展方法

1.2 算法實(shí)現(xiàn)

三級(jí)索引[4]的具體結(jié)構(gòu)如圖1所示，其中給出如下定義：

需要擴(kuò)展的前綴為Prefix=P（如P=111000*），前綴長(zhǎng)度為Prefix length=PL，該前綴對(duì)應(yīng)的下一跳地址為next hop=NH，端口號(hào) port number=No。

根據(jù)骨干網(wǎng)路由表前綴長(zhǎng)度分布[1]，可以發(fā)現(xiàn)，前綴長(zhǎng)度幾乎分布在 8～32，而且分布極不均勻，長(zhǎng)度在 16～32的前綴約占總數(shù)的99%；前綴長(zhǎng)度為24的路由最多，約占總數(shù)的45%?？梢娐酚汕熬Y小于8和大于24的表項(xiàng)非常少，因此小于8或大于24的前綴長(zhǎng)度擴(kuò)展的前綴集合絕大多數(shù)索引集為空，造成索引表的利用率非常低，而且隨索引前綴長(zhǎng)度增加以指數(shù)衰減。根據(jù)這一特性，在本算法中做劃分前綴改進(jìn)。通過擴(kuò)展存儲(chǔ)長(zhǎng)度小于16的前綴構(gòu)造一級(jí)索引表；通過擴(kuò)展存儲(chǔ)長(zhǎng)度不大于24的前綴二級(jí)索引表；對(duì)于長(zhǎng)度大于24的前綴不進(jìn)行擴(kuò)展，由于其數(shù)量非常少，進(jìn)行前綴擴(kuò)展就顯得浪費(fèi)空間。

圖1 三級(jí)索引查表算法結(jié)構(gòu)圖

本查找算法中對(duì)第3級(jí)索引表的查找方法進(jìn)行改進(jìn)。在二級(jí)索引表項(xiàng)中設(shè)置偏移量標(biāo)志Rel。根據(jù)所有前綴中最大前綴長(zhǎng)度為L(zhǎng)m，設(shè)IP地址的前24 bit相同的所有前綴中最大前綴長(zhǎng)度為L(zhǎng)m，定義偏移量Rel為：

根據(jù)Rel的值動(dòng)態(tài)分配一個(gè)獨(dú)立的SRAM用于儲(chǔ)存三級(jí)索引表項(xiàng)，最大需要地址空間為2Rel。這樣，整個(gè)路由表的大小將被控制在一個(gè)較小的規(guī)模，而不用引入復(fù)雜的位圖壓縮[5-6]來管理儲(chǔ)存空間。

動(dòng)態(tài)分配二級(jí)表的存儲(chǔ)空間，根據(jù)一級(jí)表項(xiàng)中標(biāo)志位1分配一個(gè)連續(xù)的256個(gè)SRAM地址空間，并將首地址作為基地址存儲(chǔ)在一級(jí)表中。對(duì)三級(jí)表分配獨(dú)立的SRAM。因此分別對(duì)3個(gè)表進(jìn)行流水線查找，同時(shí)進(jìn)行查找操作，使查表速度迅速提升。

第一級(jí)索引表地址從 0～32 767，一共有 32k個(gè)（215）地址空間，每個(gè)地址空間存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)有兩種：下一跳信息或指向二級(jí)表的指針，Rel=24-Lm（前 16 bit中最大前綴長(zhǎng)度）。其表項(xiàng)結(jié)構(gòu)分別如圖2和圖3所示。

圖2 一級(jí)索引表中用于存儲(chǔ)下一跳信息的表項(xiàng)結(jié)構(gòu)

圖3 一級(jí)表中用于存儲(chǔ)二級(jí)表指針信息的表項(xiàng)結(jié)構(gòu)

每個(gè)一級(jí)表表項(xiàng)共有32 bit，第0 bit是指示標(biāo)記（tag），用于指示該表項(xiàng)存儲(chǔ)的是路由信息還是指針信息，即當(dāng)tag=0時(shí)表示該表項(xiàng)存儲(chǔ)的是下一跳路由信息（簡(jiǎn)稱路由表項(xiàng)），包括路由前綴長(zhǎng)度（PL）、下一跳 IP地址（NH）、端口號(hào)（No）以及偏移量信息，如圖 2所示；tag=1時(shí)表示該表項(xiàng)存儲(chǔ)的是指向二級(jí)索引表的地址索引信息，如圖 3所示。當(dāng) tag=0時(shí)，第 1～4 bit表示路由前綴長(zhǎng)度，5～20 bit用于標(biāo)記下一跳 IP地址，21～28表示輸出索引信息，29～32表示輸出端口號(hào)?？紤]到長(zhǎng)度在16～24 bit之間的前綴占99.93%，設(shè)置第二級(jí)索引表，擴(kuò)展目的IP的第3字節(jié)，每個(gè)二級(jí)表從0到255，一共有256個(gè)地址空間。每個(gè)地址空間存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)也有兩種（和一級(jí)表類似）：下一跳信息或指向二級(jí)表的指針，其表項(xiàng)結(jié)構(gòu)與一級(jí)索引結(jié)構(gòu)類似。

對(duì)于長(zhǎng)度小于16的路由前綴，根據(jù)一級(jí)索引表中的下一跳IP地址即可完成查找。對(duì)于長(zhǎng)度大于16小于或等于24的路由前綴，需要同時(shí)對(duì)一級(jí)表和二級(jí)表進(jìn)行存儲(chǔ)，首先在其前16 bit對(duì)應(yīng)的一級(jí)表地址空間中存儲(chǔ)二級(jí)表的指針信息，而剩下的比特位則同樣通過前綴擴(kuò)展的方法擴(kuò)展到8 bit，然后再存儲(chǔ)到二級(jí)表中即可，擴(kuò)展后在相應(yīng)的表項(xiàng)中存儲(chǔ)的都是下一跳路由信息。二級(jí)表的表項(xiàng)結(jié)構(gòu)如圖4所示。

圖4 二級(jí)表中用于存儲(chǔ)三級(jí)表指針信息的表項(xiàng)結(jié)構(gòu)

對(duì)于長(zhǎng)度大于24的路由前綴，需要同時(shí)對(duì)一級(jí)表、二級(jí)表和三級(jí)表進(jìn)行存儲(chǔ)，首先在其前16 bit對(duì)應(yīng)的一級(jí)表地址空間中存儲(chǔ)二級(jí)表的指針信息，而中間8 bit對(duì)應(yīng)的二級(jí)表地址空間中存儲(chǔ)的是三級(jí)表的指針信息，對(duì)于剩下的比特位，根據(jù)其長(zhǎng)度，根據(jù)二級(jí)索引表指針可在三級(jí)表的動(dòng)態(tài)存儲(chǔ)空間中快速找到第三級(jí)地址，然后將路由信息存入其中，三級(jí)表中表項(xiàng)信息獲取完成后，查表過程結(jié)束。

2 路由表的更新

本算法的更新過程與查找過程都是先根據(jù)前綴對(duì)應(yīng)的分段和索引查找到對(duì)應(yīng)的子表，然后在其涉及的范圍內(nèi)讀取各個(gè)表項(xiàng)，再根據(jù)表項(xiàng)的值確定是否用新的路由前綴信息覆蓋該表項(xiàng)。如果在查找該段前綴時(shí)，該表沒有相應(yīng)的段空間，則需在儲(chǔ)存模塊中分配相應(yīng)的存儲(chǔ)單元，當(dāng)某段地址空間為空時(shí)，收回該儲(chǔ)存空間。路由表需要更新的時(shí)候，首先CPU根據(jù)前綴的長(zhǎng)度進(jìn)行擴(kuò)展，送入FPGA進(jìn)行判斷，根據(jù)路由表項(xiàng)信息完成插入和刪除操作。

2.1 一級(jí)索引表更新

對(duì)于長(zhǎng)度不大于16的前綴Li，首先進(jìn)行前綴擴(kuò)展，得到 m個(gè)擴(kuò)展前綴，在一級(jí)表中讀出以 Li（i=1，2，…，m）為地址的內(nèi)容，若該內(nèi)容是路由信息或是空白信息，則不作處理，將新的路由信息寫入一級(jí)表中的地址中即可；若該內(nèi)容為二級(jí)表的指針信息，那么將該指針信息作為二、三路由表對(duì)應(yīng)的SSRAM[7]中要釋放的地址塊號(hào)送到一級(jí)索引的SSRAM存儲(chǔ)空間管理模塊中。插入過程如圖5所示。

圖5 一級(jí)索引表更新

2.2 二、三級(jí)索引表更新

對(duì)于大于16的前綴長(zhǎng)度的二、三級(jí)表更新算法，首先擴(kuò)展到24 bit前綴。更新方式與一級(jí)索引表更新類似。此外，本算法引入Freeunit[2]來優(yōu)化空間管理，改進(jìn)更新操作。每種長(zhǎng)度的地址前綴塊分配一個(gè)Freeunit，其容量根據(jù)前綴長(zhǎng)度而定。較長(zhǎng)的前綴塊對(duì)應(yīng)的分配容量較大，反之，容量較小。Freeunit的實(shí)現(xiàn)可以采用堆?；蜿?duì)列等數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)。二、三級(jí)索引表更新前綴項(xiàng)進(jìn)出緩存池過程如圖6所示。

圖6 前綴項(xiàng)進(jìn)出緩存池過程

把Freeunit作為一個(gè)緩沖池BP，當(dāng)刪除一個(gè)表項(xiàng)時(shí)，只是單獨(dú)的將表項(xiàng)內(nèi)容刪除，而不改變前綴塊和整個(gè)三級(jí)索引表項(xiàng)結(jié)構(gòu)，同時(shí)將刪除的表項(xiàng)放入到Freeunit中；當(dāng)添加新的表項(xiàng)時(shí)，從對(duì)應(yīng)的 Freeunit中取出當(dāng)前的空閑表項(xiàng)，直接添加，由此可以大大減少因?yàn)楸眄?xiàng)的添加和刪除而釋放地址空間所需時(shí)間，申請(qǐng)新的地址空間造成的時(shí)間開銷。

圖7 三級(jí)流水線并行處理算法硬件結(jié)構(gòu)

硬件結(jié)構(gòu)設(shè)計(jì)如圖7所示，三級(jí)索引結(jié)構(gòu)包括3個(gè)流水線并行查找模塊和3個(gè)更新單元。每個(gè)表都需要一個(gè)單獨(dú)的SSRAM進(jìn)行存儲(chǔ)，這樣，一共就使用6塊SSRAM。對(duì)于一級(jí)索引，有30 720個(gè)表項(xiàng)，每個(gè)表項(xiàng)有64 bit（8 B）存儲(chǔ)空間，則一個(gè)一級(jí)表就需要 237.5 KB大小的SSRAM，所以每個(gè)一級(jí)表選用了一個(gè)500 KB容量的SSRAM。第二級(jí)索引表和第三索引表的大小不能精確確定，選用了一個(gè)4 MB容量的SSRAM和2 MB容量的SSRAM。而對(duì)于第三級(jí)表，由于其容量很小，因此將三級(jí)表和二級(jí)表放在同一塊SSRAM里。每個(gè)查找模塊都可從輸入端或寄存器中讀取表項(xiàng)信息，解析IP地址位[8]，訪問存儲(chǔ)器獲取數(shù)據(jù)，最后將數(shù)據(jù)寫入寄存器或者送到輸出端進(jìn)行輸出轉(zhuǎn)發(fā)操作。

表2 算法查找速度比較表

3 實(shí)驗(yàn)結(jié)果及算法比較

實(shí) 驗(yàn) 環(huán) 境 為 ：Celeron，500 MHz Windows XP，256 MB RAM。索引算法用FPGA實(shí)現(xiàn)，采用Xilinx公司的spartan-6系列芯片。它們可以提供豐富的片內(nèi)SRAM資源，均以SRAM為儲(chǔ)存介質(zhì)。為了測(cè)量性能，通過隨機(jī)數(shù)的方法產(chǎn)生隨機(jī)IP地址、掩碼和端口索引號(hào)，用數(shù)組記錄這些信息，在添加路由表前記錄系統(tǒng)時(shí)鐘，添加完成后又記錄一次系統(tǒng)時(shí)鐘，進(jìn)行大量的插入操作后計(jì)算完成一次操作所用的時(shí)間。查找與刪除操作也采用同樣的方法來測(cè)量。通過對(duì)比可知，三級(jí)前綴劃分并改進(jìn)第3級(jí)索引可有效提高地址空間利用率，減少空索引集數(shù)量，加入緩存的更新算法有效減少了更新開銷時(shí)間，從而提升查找速度。由于查找需要一個(gè)時(shí)鐘周期，而時(shí)鐘頻率為100 MHz，因此每秒可以完成100 M次查找，假設(shè)報(bào)文長(zhǎng)度均為40 B，可以滿足20 Gb/s的鏈路速率。

算法查找速度比較表如表2所示，算法存儲(chǔ)容量比較表如表3所示。從實(shí)驗(yàn)結(jié)果來看，當(dāng)表項(xiàng)數(shù)目較小時(shí)，二進(jìn)制trie樹查找[9]過程表項(xiàng)次數(shù)較多，相應(yīng)的查找速度也較慢。隨著表項(xiàng)數(shù)目的增加，查找速度變化非常緩慢，已經(jīng)不能適用于快速的路由查找。對(duì)于動(dòng)態(tài)前綴樹查找方法，查找中表項(xiàng)比較的次數(shù)隨表項(xiàng)數(shù)目變化的速度比較緩慢，相應(yīng)的查找性能變化比較平緩，基本維持在同一個(gè)數(shù)量級(jí)上，平均查找速度低。二級(jí)索引頁面壓縮算法查找速度隨查找表項(xiàng)的數(shù)目變化的速度較緩慢，相應(yīng)的查找性能較好，由于壓縮處理，表項(xiàng)占用空間很小。缺點(diǎn)是壓縮算法[10]用硬件實(shí)現(xiàn)不合適。四級(jí)流水線查找速度快，訪存次數(shù)少，此算法使用的存儲(chǔ)容量比較大，特別是在表項(xiàng)數(shù)目較多的情況下。與三級(jí)索引SRAM快速查找RAM的查找算法相比，三級(jí)索引算法具有很快的查找速度，甚至當(dāng)表項(xiàng)數(shù)目達(dá)到100 000時(shí)，仍然可以達(dá)到50 Mp/s多的查找速度。從存儲(chǔ)容量上來看，較四級(jí)流水線RAM查找存儲(chǔ)容量更小。由比較可知，三級(jí)索引SRAM快速查找在查找速度、儲(chǔ)存空間、更新速度方面都具有優(yōu)勢(shì)。該算法非常適于需要高速報(bào)文轉(zhuǎn)發(fā)的網(wǎng)絡(luò)環(huán)境。

表3 算法存儲(chǔ)容量比較表

本文提出基于三級(jí)索引來實(shí)現(xiàn)路由查表算法，并利用前綴擴(kuò)展和引入更新緩存的技術(shù)來實(shí)現(xiàn)優(yōu)化。最快的查找只要一次訪問存儲(chǔ)器就可以找到端口索引，獲得下一跳信息需要2次訪問存儲(chǔ)器。最多3次訪問存儲(chǔ)器就可以獲得端口索引。在實(shí)現(xiàn)高速查找的同時(shí)，兼顧到存儲(chǔ)空間利用率和實(shí)現(xiàn)復(fù)雜度等多種因素，比單純使用四級(jí)流水線查找速度提高了15%；對(duì)第3級(jí)索引表采用動(dòng)態(tài)管理，節(jié)省了30%儲(chǔ)存空間。

[1]王波.基于FPGA的快速路由查找算法研究及實(shí)現(xiàn)[D].西安：西安電子科技大學(xué)，2009.

[2]苗建松，丁煒.改進(jìn)的TCAM路由更新方法與實(shí)現(xiàn)[J].微電子學(xué)與計(jì)算機(jī)，2006，23（10）：144-149.

[3]劉亞林，劉東.基于前綴擴(kuò)展的快速路由查找算法[J].計(jì)算機(jī)學(xué)報(bào)，2001，24（12）：1272-1278.

[4]張毅，郭玲麗.基于 FPGA的高速路由查找算法[J].電子元器件應(yīng)用，2009，11（9）：22-27.

[5]彭元喜，唐玉華，龔正虎.基于壓縮 NH表的高速 IP路由查找算法的研究[J].電子學(xué)報(bào)，2002，（2）：32-36.

[6]王利媛，馬躍，徐塞虹.對(duì)路由表結(jié)構(gòu)和查找算法的研究[J].計(jì)算機(jī)應(yīng)用，2004（11）：10-12.

[7]MCEWAN A A，SAUL J.A high speed reconfigurable firewall based on parameterizable FPGA-based content addressable memories[J].The Journal of Supercomputing，2001，19（1）：93-103.

[8]IOANNIDIS I， GRAMA A， ATALLAH M J.A-daptive data structures forIP lookups[J]. AlM Journalof Experimental Algorithmics， 2005（10）：75-84.

[9]譚興曄，張勇，雷振明.基于快速搜索樹的路由查表算法[J].計(jì)算機(jī)應(yīng)用研究，2005（7）：231-235.

[10]徐恪，吳建平，吳劍.路由查找算法評(píng)價(jià)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].小型微型計(jì)算機(jī)系統(tǒng)，2003，24（2）：274-276.