引言：

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

一、TCAM原理：

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

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

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

1、 ATM （Asynchronous Transfer Mode） 交換：

1）虛擬路徑的標(biāo)識(shí)符（VPI）、虛擬通道的標(biāo)識(shí)符（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、 包分類(lèi)：

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

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

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

三、典型應(yīng)用場(chǎng)景實(shí)例

準(zhǔn)備查找：

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

查找：

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

查找后處理：

最后RAM將對(duì)該報(bào)文的處理信息DATA返回NP.

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

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

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

四、查找方法對(duì)比：

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

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

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

4.2 基于CAM查找方法

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

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

4.3 基于TCAM查找方法

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

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

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

五、結(jié)論

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

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

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

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

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

編輯：jq