引言：

隨著路由器接口速率的提高，傳統(tǒng)的軟件路由查找機(jī)制已經(jīng)不能滿足要求。目前常見的硬件解決方案是采用TCAM實現(xiàn)高速路由查找。由于路由查找具有最長前綴匹配的特點，因此采用TCAM 需要解決路由表如何存儲和管理等問題。

一、TCAM原理：

TCAM （ternary content addressable memory）是一種三態(tài)內(nèi)容尋址存儲器，主要用于快速查找ACL、路由等表項。

它是從CAM的基礎(chǔ)上發(fā)展而來的。一般的CAM存儲器中每個bit位的狀態(tài)只有兩個，“0”或“1”，而TCAM中每個bit位有三種狀態(tài)，除掉“0”和“1”外，還有一個“don’t care”狀態(tài)，所以稱為“三態(tài)”，它是通過掩碼來實現(xiàn)的，正是TCAM的這個第三種狀態(tài)特征使其既能進(jìn)行精確匹配查找，又能進(jìn)行模糊匹配查找，而CAM沒有第三種狀態(tài)，所以只能進(jìn)行精確匹配查找。

二、TCAM的應(yīng)用范圍

1、 ATM （Asynchronous Transfer Mode） 交換：

1）虛擬路徑的標(biāo)識符（VPI）、虛擬通道的標(biāo)識符（VCI）翻譯

2）ATM-to-MLPS 或者 ATM-to-TCP -Flow 映射

2、 以太網(wǎng)交換：

1）轉(zhuǎn)發(fā)2層MAC地址查找

2）地址解析協(xié)議

3、 新興協(xié)議和功能：

1）多協(xié)議標(biāo)簽交換（MPLS）標(biāo)簽搜索

4、 包分類：

1）強(qiáng)制執(zhí)行安全性

2）強(qiáng)制執(zhí)行不同的策略

3）服務(wù)質(zhì)量

三、典型應(yīng)用場景實例

準(zhǔn)備查找：

NP從報文頭提取信息，整理成與TCAM中待查表一致的數(shù)據(jù)格式，稱為Key。

查找：

將Key送入TCAM與待查表中的所有表象對照，匹配到后將對應(yīng)地址INDEX送到RAM中。

查找后處理：

最后RAM將對該報文的處理信息DATA返回NP.

3.1 典型應(yīng)用之路由查找

3.2 典型應(yīng)用之包分類

包的分類可以決定這個包是否應(yīng)該被轉(zhuǎn)發(fā)，如果要被轉(zhuǎn)發(fā)，要給予什么樣的優(yōu)先級。

四、查找方法對比：

4.1 傳統(tǒng)的查找方法

傳統(tǒng)的查找方法主要有：線型查找法、二叉樹查找法、哈希表查找等，這些查找方法都是基于SRAM的軟件查找方法，共同特點是查找速度慢。

線型查找法需要遍歷表中的所有表項；二叉樹查找法需要遍歷樹中大多數(shù)節(jié)點，而且查找速度受樹的深度影響較大；哈希表查找法是軟件查找中計較快的一種方法，它是根據(jù)設(shè)定的哈希函數(shù)H（key）和處理沖突方法將一組關(guān)鍵字映象到一個有限的地址區(qū)間上，并以關(guān)鍵字在地址區(qū)間中的象作為記錄在表中的存儲位置，這種表稱為哈希表或散列，所得存儲位置稱為哈希地址或散列地址。雖然哈希表查找法相對來說比較快，但還是滿足不了高速實時通信系統(tǒng)（如40G/100G POS）的極速查找需求。

4.2 基于CAM查找方法

CAM 能夠在一個硬件時鐘周期內(nèi)完成關(guān)鍵字的精確匹配查找。我們常用的隨機(jī)存儲器通過輸入地址來返回該地址處所對應(yīng)的數(shù)據(jù)信息，但是CAM 的訪問方式不同，它只需要輸入關(guān)鍵字的內(nèi)容，CAM 就會將此關(guān)鍵字與CAM 中所有的表項同時進(jìn)行匹配比較，最后返回匹配表項在CAM 中所對應(yīng)的地址。它是一種精確匹配，不使用掩碼。

傳統(tǒng)CAM只能執(zhí)行精確匹配，一般不適用于IP路由表。如果要使用CAM來進(jìn)行最長前綴匹配路由查找，可以讓每一類可能的地址前綴長度使用一個CAM，每個CAM保存對應(yīng)長度的所有前綴的集合。對于IPv4來說（IP地址位寬為32bit，IPv6地址位寬為128bit），則一共需要使用32個CAM。這種方法有一個明顯缺點，即在對地址前綴長度具體分布沒有準(zhǔn)確了解之前，為了保證能夠存W個前綴的表項，每個CAM都需要有W個表項的空間，因此，CAM存儲空間的利用率較低。

4.3 基于TCAM查找方法

為了能夠克服CAM的缺點，又提出了一種CAM 實現(xiàn)機(jī)制TCAM （ternary CAM） ，TCAM 的優(yōu)點是它所保存的表項在長度要求上非常靈活，可以在同一個TCAM 芯片中保存任意長度的關(guān)鍵字表項。

TCAM 中每一個表項都是以《數(shù)據(jù)、掩碼》序偶的形式保存，假設(shè)地址關(guān)鍵字的長度范圍從1 到W，那么數(shù)據(jù)和掩碼分別占用W 比特。與傳統(tǒng)CAM的區(qū)別是，后者表項的各個比特位只能是0或1，而前者的則有三個狀態(tài)：0，1或X。X是一種無關(guān)態(tài)，可以是“0”或“1”，它由局部掩碼來實現(xiàn)，而且可以表示可變長前綴?？梢岳么诵再|(zhì)對路由表進(jìn)行壓縮，減少對TCAM的占用。

最高優(yōu)先級匹配：我們就需要保證在TCAM 的低地址存儲前綴較長的關(guān)鍵字表項，而在地址高的區(qū)域存儲前綴較短的關(guān)鍵字表項。由于有”don’t care” 即有三態(tài)的存在，所以key值可能有多個匹配，當(dāng)一個key存在多個匹配的時候，匹配經(jīng)過邏輯單元比較返回匹配程度最高的表項（在ipv4經(jīng)常遇到）

五、結(jié)論

基于硬件的TCAM查找法，整個表項空間的所有數(shù)據(jù)在同一時刻被查詢，查找速度不受表項空間數(shù)據(jù)大小影響，每個時鐘周期完成一次查找，平均查找速度是基于SRAM算法查找的6倍，最壞情況下，能達(dá)到128倍。

TCAM 具有速度快、實現(xiàn)簡單的優(yōu)點，但是它也具有三個不足之處：

第一、與一般的隨機(jī)存儲器RAM 相比， 單位比特的TCAM 更為昂貴，而且存儲芯片的容量相對要小一些；

第二、由于TCAM 使用的是 并行匹配比較方式，所以TCAM 芯片的 功耗較大。 查找過程所有關(guān)鍵字表項都進(jìn)行了比較，但是實際能夠匹配上的關(guān)鍵字只是幾項，因此 大部分的比較操作都被浪費了；

第三、 TCAM 需要保證前綴較長的關(guān)鍵字保存在前綴較短的關(guān)鍵字之前，這種關(guān)鍵字之間的順序關(guān)系使得TCAM的關(guān)鍵字更新工作變得相對復(fù)雜了。例如，當(dāng)加入一條新的表項時，為了能夠仍然保持關(guān)鍵字間的順序關(guān)系，就需要移動一些前綴長度比新表項要長的一些表項，因此TCAM 的更新操作較為復(fù)雜（具體地址管理方法此處不詳細(xì)說明）。

編輯：jq