TCAM 在高速路由查找中的應用及其FPGA實現(xiàn)-基礎電子

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

1引言

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

2利用TCAM進行路由查找

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

路由表是動態(tài)的，也就是說路由表項會隨著網(wǎng)絡拓撲結構的不斷變化而相應的增加或者刪除。一般來說，在路由更新的同時，路由查找是不能夠進行的，在這段時間內(nèi)報文需要緩存在報文緩沖區(qū)內(nèi)等待路由更新的完成，因此慢的路由更新對系統(tǒng)報文緩沖區(qū)的容量有很大的要求，同時也會延長報文轉(zhuǎn)發(fā)的時間。所以要盡可能的減小路由更新的時間。

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

3Prefix-lengthorderingconstraintalgorithm（PLO_OPT）表項管理算法

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

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

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

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

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

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

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

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

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

5總