引言：

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

一、TCAM原理：

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

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

二、TCAM的應用范圍

1、 ATM （Asynchronous Transfer Mode） 交換：

1）虛擬路徑的標識符（VPI）、虛擬通道的標識符（VCI）翻譯

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

2、 以太網交換：

1）轉發2層MAC地址查找

2）地址解析協議

3、 新興協議和功能：

1）多協議標簽交換（MPLS）標簽搜索

4、 包分類：

1）強制執行安全性

2）強制執行不同的策略

3）服務質量

三、典型應用場景實例

準備查找：

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

查找：

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

查找后處理：

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

3.1 典型應用之路由查找

3.2 典型應用之包分類

包的分類可以決定這個包是否應該被轉發，如果要被轉發，要給予什么樣的優先級。

四、查找方法對比：

4.1 傳統的查找方法

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

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

4.2 基于CAM查找方法

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

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

4.3 基于TCAM查找方法

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

TCAM 中每一個表項都是以《數據、掩碼》序偶的形式保存，假設地址關鍵字的長度范圍從1 到W，那么數據和掩碼分別占用W 比特。與傳統CAM的區別是，后者表項的各個比特位只能是0或1，而前者的則有三個狀態：0，1或X。X是一種無關態，可以是“0”或“1”，它由局部掩碼來實現，而且可以表示可變長前綴。可以利用此性質對路由表進行壓縮，減少對TCAM的占用。

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

五、結論

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

TCAM 具有速度快、實現簡單的優點，但是它也具有三個不足之處：

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

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

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

編輯：jq