TCAM 在高速路由查找中的應(yīng)用及其FPGA實(shí)現(xiàn)-基礎(chǔ)電子

精品文檔-下載后可編輯TCAM在高速路由查找中的應(yīng)用及其FPGA實(shí)現(xiàn)-基礎(chǔ)電子摘要：當(dāng)前隨著網(wǎng)絡(luò)帶寬的不斷增加，對(duì)路由器轉(zhuǎn)發(fā)速度的要求也越來(lái)越高。如何進(jìn)行路由的快速查找目前成為限制報(bào)文快速轉(zhuǎn)發(fā)的瓶頸，為了解決這一問(wèn)題比較流行的方式是采用TCAM器件進(jìn)行路由的快速查找。本文詳細(xì)介紹了TCAM器件在高速路由查找中的應(yīng)用及其管理算法，同時(shí)重點(diǎn)給出了TCAM器件的FPGA實(shí)現(xiàn)。

1引言

路由器轉(zhuǎn)發(fā)IP分組時(shí)，轉(zhuǎn)發(fā)引擎需要在路由表中查找該IP報(bào)文中目的地址所對(duì)應(yīng)的路由信息，從而決定IP報(bào)文的轉(zhuǎn)發(fā)方式。目前設(shè)計(jì)快速的路由查找方法已經(jīng)成為提高路由器整體性能的關(guān)鍵之一[1]。隨著網(wǎng)絡(luò)速率的提高，傳統(tǒng)的基于軟件的路由查找機(jī)制已經(jīng)不能滿足要求，目前工業(yè)界中使用多的硬件路由查找方法是使用內(nèi)容尋址存儲(chǔ)器（CAM）。但由于路由查找具有長(zhǎng)前綴匹配的特點(diǎn)[2]，人們又提出了另一種CAM實(shí)現(xiàn)機(jī)制—ternaryCAM（TCAM），TCAM器件相對(duì)于CAM的優(yōu)點(diǎn)是它所保存的表項(xiàng)在長(zhǎng)度要求上非常靈活，可以在同一個(gè)TCAM芯片中保存任意長(zhǎng)度的關(guān)鍵字表項(xiàng)。但是它也有不足之處：、TCAM更為昂貴，而且容量相對(duì)較??；第二、TCAM使用并行匹配比較方式，功耗較大。第三、TCAM需要保證前綴較長(zhǎng)的關(guān)鍵字保存在前綴較短的關(guān)鍵字之前，這種順序關(guān)系使得TCAM關(guān)鍵字更新更為復(fù)雜。本文介紹了TCAM在路由快速查找中的應(yīng)用及其管理算法，同時(shí)利用FPGA設(shè)計(jì)實(shí)現(xiàn)了TCAM,使得路由查找更為靈活，系統(tǒng)設(shè)計(jì)更加簡(jiǎn)單。

2利用TCAM進(jìn)行路由查找

圖1是使用TCAM進(jìn)行路由查找的示意圖。表項(xiàng)長(zhǎng)度是按路由前綴的長(zhǎng)度降序排列。假設(shè)為目的地址101.11.3.10的ip報(bào)文查找轉(zhuǎn)發(fā)路徑。TCAM同時(shí)將它保存的所有表項(xiàng)與關(guān)鍵字101.11.3.10進(jìn)行匹配查找，表項(xiàng)A1，A2都與關(guān)鍵字匹配，但是TCAM返回地址的表項(xiàng)，即A1。

路由表是動(dòng)態(tài)的，也就是說(shuō)路由表項(xiàng)會(huì)隨著網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的不斷變化而相應(yīng)的增加或者刪除。一般來(lái)說(shuō)，在路由更新的同時(shí)，路由查找是不能夠進(jìn)行的，在這段時(shí)間內(nèi)報(bào)文需要緩存在報(bào)文緩沖區(qū)內(nèi)等待路由更新的完成，因此慢的路由更新對(duì)系統(tǒng)報(bào)文緩沖區(qū)的容量有很大的要求，同時(shí)也會(huì)延長(zhǎng)報(bào)文轉(zhuǎn)發(fā)的時(shí)間。所以要盡可能的減小路由更新的時(shí)間。

由于TCAM需要維持所有的路由表項(xiàng)按照前綴長(zhǎng)度有序，所以對(duì)于路由的動(dòng)態(tài)更新來(lái)說(shuō)，效率就會(huì)比較低。以圖1為例，假設(shè)現(xiàn)在需要在轉(zhuǎn)發(fā)表中增加新的表項(xiàng)101.11.128/18，按照表項(xiàng)組織的方式，新的表項(xiàng)應(yīng)該保存在表項(xiàng)101.11.3/24（A1）和表項(xiàng)101.11/16（A2）之間，但是目前在這兩個(gè)表項(xiàng)之間沒(méi)有空閑的表項(xiàng)空間，所以需要通過(guò)移動(dòng)其它表項(xiàng)為新表項(xiàng)騰出空間。下一小節(jié)我們給出一種較好的表項(xiàng)管理算法，可以有效降低表項(xiàng)更新的開銷。

3Prefix-lengthorderingconstraintalgorithm（PLO_OPT）表項(xiàng)管理算法

TCAM要求所有的路由按照前綴長(zhǎng)度降序排列，令Pj代表的是前綴長(zhǎng)度為j的所有路由集合，如果jk，那么所有Pj中的路由表項(xiàng)都應(yīng)該保存在Pk中的路由表項(xiàng)之前。TCAM只要求前綴長(zhǎng)度集合塊之間的順序關(guān)系，對(duì)于每個(gè)前綴長(zhǎng)度集合塊內(nèi)部各個(gè)路由前綴之間的順序關(guān)系沒(méi)有嚴(yán)格規(guī)定。利用這一思想，文獻(xiàn)[3]提出了PLO_OPT算法，算法實(shí)現(xiàn)如圖2所示。當(dāng)需要在TCAM中加入長(zhǎng)度為k（20≤k≤32）的路由前綴時(shí)，首先從長(zhǎng)度21的前綴塊開始，將前綴塊的項(xiàng)移動(dòng)到一項(xiàng)（即TCAM的空閑表項(xiàng)區(qū)域），這樣在長(zhǎng)度為22的前綴塊處就有了一個(gè)空閑表項(xiàng)；然后將長(zhǎng)度為22前綴塊中的項(xiàng)移動(dòng)到這一個(gè)空閑表項(xiàng)處，使得長(zhǎng)度為23前綴塊中出現(xiàn)了空閑表項(xiàng)；以此類推，直到新加入表項(xiàng)所在的前綴塊為止，那時(shí)就只需要將該新表項(xiàng)加入到分配處的空閑表項(xiàng)處就可以了（8≤k≤20時(shí)情況類似）。顯然，這種算法的復(fù)雜度為W/2（其中W是路由前綴的長(zhǎng)度）。

在圖2的例子中，只需要移動(dòng)A5、A4、A2三個(gè)表項(xiàng)就可以在P1與P2之間騰出空間并且仍然保持TCAM前綴長(zhǎng)度有序。為了進(jìn)一步提高性能，可以為每一個(gè)前綴長(zhǎng)度集合塊預(yù)留一部分空間，當(dāng)然空間的分配要根據(jù)路由前綴的分布進(jìn)行，因?yàn)橐话闱闆r下前綴長(zhǎng)度大于24的情況非常少[4]，所以比較簡(jiǎn)單通用的方法是假定前綴服從正態(tài)分布。

4TCAM功能介紹及其FPGA實(shí)現(xiàn)

TCAM基本框圖如圖3所示。與RAM相似，TCAM是將表項(xiàng)存儲(chǔ)在一個(gè)陣列中。每個(gè)表項(xiàng)的寬度稱為字寬，TCAM中表項(xiàng)的個(gè)數(shù)稱為TCAM的深度。字寬和深度可以表征TCAM的容量。TCAM的優(yōu)點(diǎn)是它所保存的表項(xiàng)在長(zhǎng)度上要求非常靈活，可以保存任意長(zhǎng)度的表項(xiàng)。其中每個(gè)表項(xiàng)都是以地址，掩碼〉序偶的形式保存。在寫TCAM模式時(shí)，Wren信號(hào)有效，此時(shí)通過(guò)地址線Address和數(shù)據(jù)線Data配合掩碼信號(hào)線Wrx，掩碼信號(hào)能使Wrx_used將表項(xiàng)寫入目的地址。假設(shè)關(guān)鍵字長(zhǎng)度范圍是0-6，那么長(zhǎng)度為3的關(guān)鍵字110*就可以以110000,000111序偶的形式表示。在查找TCAM模時(shí),Find_start信號(hào)表征新的查找開始，直接通過(guò)Data送入要查找的關(guān)鍵字,TCAM判斷關(guān)鍵字是否與表項(xiàng)相等，如果相等表示關(guān)鍵字與該表項(xiàng)匹配，信號(hào)Mfound為高，Maddress輸出表項(xiàng)地址。否則不匹配。同時(shí)表項(xiàng)可以由Wrdelete信號(hào)配合Wren和所要?jiǎng)h除的表項(xiàng)地址進(jìn)行更新。

TCAM通過(guò)保存關(guān)鍵字掩碼的方式使得它可以保存任意長(zhǎng)度的關(guān)鍵字表項(xiàng)，因此使用TCAM非常適合進(jìn)行長(zhǎng)前綴路由的查找，目前不少工業(yè)界的廠商都在進(jìn)行對(duì)TCAM的設(shè)計(jì)研究。由于可能存在多個(gè)表項(xiàng)匹配的情況，因此TCAM需要在這些匹配的表項(xiàng)中選取一個(gè)表項(xiàng)作為的查找結(jié)果，TCAM規(guī)定在所有匹配的表項(xiàng)中選取地址的表項(xiàng)作為的結(jié)果。為了能夠進(jìn)行長(zhǎng)前綴路由的查找，我們就需要保證在TCAM的低地址存儲(chǔ)前綴較長(zhǎng)的關(guān)鍵字表項(xiàng)，而在地址高的區(qū)域存儲(chǔ)前綴較短的關(guān)鍵字表項(xiàng)。

在利用FPGA設(shè)計(jì)TCAM時(shí)，我們采用ALTERA公司的APEX20K1000E系列芯片。利用VHDL硬件描述語(yǔ)言借助QUARTUS2開發(fā)平臺(tái)進(jìn)行設(shè)計(jì)。TCAM的實(shí)現(xiàn)可以利用QUARTUS2中提供的altcam宏模塊。該模塊對(duì)CAM的設(shè)計(jì)包括三個(gè)模式：single-matchmode，multiple-matchmode,fastmultiple-matchmode。由于TCAM器件允許相同的表項(xiàng)存在，所以選用multiple-matchmode和fastmultiple-matchmode可以實(shí)現(xiàn)TCAM的功能，其中這兩種模式的區(qū)別在于查找的速度和所用資源不同。以容量為32x32的TCAM為例，采用multiple-matchmode設(shè)計(jì)需要1個(gè)ESB（embeddedsystemblock嵌入式系統(tǒng)塊）和98個(gè)LE（logicelement邏輯單元）；而采用fastmultiple-matchmode設(shè)計(jì)則需要2個(gè)ESB和79個(gè)LE。但是查找的速度上后者近似兩倍于前者。

圖4是采用multiple-matchmode設(shè)計(jì)TCAM的仿真圖。其中寫入表項(xiàng)要兩到三個(gè)時(shí)鐘周期（要求掩碼要三個(gè)時(shí)鐘周期），查找需要兩個(gè)時(shí)鐘周期。該種模式下由于存在多個(gè)匹配的情況，所以start信號(hào)后面的是個(gè)匹配的表項(xiàng)（地址），mnext后面的是接下來(lái)的一個(gè)表項(xiàng)，此時(shí)mnext持續(xù)有效時(shí)間不能超過(guò)兩個(gè)時(shí)鐘周期。圖中1被寫入兩個(gè)地址1，8；在start后輸出的是低的地址1，mnext后輸出的是接下來(lái)的地址8。

圖5是采用fastmultiple-matchmode設(shè)計(jì)TCAM的仿真圖，其中查找只需要一個(gè)時(shí)鐘周期。圖中當(dāng)查找數(shù)據(jù)000110時(shí)，由于存在地址為1，3的兩個(gè)表項(xiàng)與之匹配，所以送出地址低的一個(gè)表項(xiàng)。

從圖5中可以看出，當(dāng)采用fastmultiple-matchmode時(shí)，時(shí)鐘頻率為50MHZ，所以每秒鐘可以完成50M次查找，完全滿足端口速率為10G的oc-192路由接入，適應(yīng)骨干路由器的高速查找要求。目前雖然FPGA資源有限，路由器大容量路由表不能完全存儲(chǔ)在一片F(xiàn)PGA中，但可以將FPGA內(nèi)部實(shí)現(xiàn)的TCAM作為cache來(lái)加速路由查找。隨著技術(shù)的進(jìn)步，F(xiàn)PGA的容量將不斷加大，到那時(shí)在一片F(xiàn)PGA上應(yīng)該可以存儲(chǔ)大量的路由表項(xiàng)。

5總