TCAM應(yīng)用

傳統(tǒng)的表項(xiàng)查找方法有很多，主要有：線型查找法、二叉樹查找法、哈希表查找等，這些查找方法都是基于SRAM的軟件查找方法，共同特點(diǎn)是查找速度慢。線型查找法需要遍歷表中的所有表項(xiàng)；二叉樹查找法需要遍歷樹中大多數(shù)節(jié)點(diǎn)，而且查找速度受樹的深度影響較大；哈希表查找法是軟件查找中較快的一種方法，它是根據(jù)設(shè)定的哈希函數(shù)H(key)和處理沖突方法將一組關(guān)鍵字映象到一個(gè)有限的地址區(qū)間上，并以關(guān)鍵字在地址區(qū)間中的象作為記錄在表中的存儲(chǔ)位置，這種表稱為哈希表或散列，所得存儲(chǔ)位置稱為哈希地址或散列地址。雖然哈希表查找法相對(duì)來(lái)說(shuō)比較快，但還是滿足不了高速實(shí)時(shí)通信系統(tǒng)(如40G/100G POS)的極速查找需求。 基于硬件的TCAM查找法正是在這種背景下提出的，用此方法進(jìn)行查找時(shí)，整個(gè)表項(xiàng)空間的所有數(shù)據(jù)在同一時(shí)刻被查詢，查找速度不受表項(xiàng)空間數(shù)據(jù)大小影響，每個(gè)時(shí)鐘周期完成一次查找，平均查找速度是基于SRAM算法查找的6倍，最好情況下，能達(dá)到128倍。

TCAM的硬件設(shè)計(jì)方式

TCAM器件的硬件設(shè)計(jì)方式一般有三種，如下圖1所示：

網(wǎng)絡(luò)處理器NP從報(bào)文頭中把需要查找的信息提取出來(lái)，這個(gè)待查找的信息要整理成跟TCAM所存表項(xiàng)的格式一致，稱之為KEY。KEY作為TCAM的輸入數(shù)據(jù)，經(jīng)過(guò)與表項(xiàng)對(duì)照，如果有匹配的表項(xiàng)，就把該表項(xiàng)所在的地址作為輸出，稱之為Index。然后將Index作為RAM的地址輸入，從RAM里得到所需查找的信息，稱之為Data。最后將Data返回給發(fā)起查找操作的NP，至此完成一次查找操作。

TCAM在高端路由器中的應(yīng)用及查找過(guò)程

CAM和TCAM的基本存儲(chǔ)單元

主要有：

1).ATM Switching設(shè)備中的VCI/VPI轉(zhuǎn)發(fā)和ATM-to-MPLS or ATM-to-TCP-Flow地址映射表項(xiàng)的存儲(chǔ)和查找；

2).Ethernet Switching設(shè)備中的二層MAC地址、ARP/RARP解析和三層IP路由表項(xiàng)的存儲(chǔ)和查找；

3).Emerging Protocols and functions方面的MPLS label表項(xiàng)的存儲(chǔ)和查找；

4).Packet Classification業(yè)務(wù)中的Enforce security、Enforce departmental policies和QOS檢測(cè)表項(xiàng)的存儲(chǔ)和查找；

5).安全防護(hù)設(shè)備中的FIB/LBT、MFIB及ACL表項(xiàng)存儲(chǔ)和查找。

主要有：

1.XeL(雄立科技)

2.Netlogic

這二家分別將TCAM器件稱作Intelligent Search Engine(ISE) 和Knowledge-based Processor(KBP)。

TCAMFM

（特性管理器）

在創(chuàng)建或配置訪問列表后，F(xiàn)M軟件將匹配語(yǔ)句編譯（合并）為TCAM表項(xiàng)，這樣就可以以幀轉(zhuǎn)發(fā)速度查詢TCAM

TCAMSDM

（交換數(shù)據(jù)庫(kù)管理器）

在某些Catelyst交換機(jī)中，可以將TCAM劃分為不同的功能區(qū)域，SDM軟件將配置或調(diào)整TCAM分區(qū)，Catelyst4500 和6500交換機(jī)，TCAM是固定的，不能分區(qū)。

1、從包的內(nèi)容中讀取相關(guān)字段（如，前綴、掩碼等）

2、創(chuàng)建查找關(guān)鍵字（lookup key）

3、用lookup key和TCAM中的Value段對(duì)比，如果匹配了某Value，則將該Value和對(duì)應(yīng)的Mask關(guān)聯(lián)

4、返回最長(zhǎng)匹配結(jié)果（值(Value) 掩碼(Mask))=結(jié)果）

1、TCAM 表內(nèi)所有條目都可以并行訪問，比如，如果你有100條ACL，TCAM能一次就能對(duì)比這100條ACL進(jìn)行對(duì)比操作，過(guò)去如果有100條ACL的話，需要第一條ACL對(duì)比完后再對(duì)比第二條，然后第三條，直至N條，效率很明顯沒有TCAM高。

2、TCAM的結(jié)構(gòu)已經(jīng)經(jīng)過(guò)了優(yōu)化，支持更抽象的操作，通常是基于二進(jìn)制關(guān)鍵字匹配，查詢相當(dāng)快

如FIB TCAM中每個(gè)表項(xiàng)都有對(duì)應(yīng)的下一條，而每個(gè)下一條又維護(hù)了下一條鄰居的MAC。

3、正因?yàn)橛猩线叺倪@些特性，所以無(wú)論表內(nèi)有多少條數(shù)目，性能都不會(huì)減弱。

4、TCAM 包含多組的Mask 與Value 對(duì)應(yīng)關(guān)系，對(duì)應(yīng)比例為1:8，一個(gè)Mask可對(duì)應(yīng)8個(gè)Value。最長(zhǎng)掩碼位于TCAM頂部，如255.255.255.255位于最頂部，用于最長(zhǎng)匹配，提升查找速率。

5、Mask 用于表示Value 的匹配方法，1 為必須比較并匹配，0 為不用比較。

6、TCAM的可用掩碼、值模式、LOU表項(xiàng)有限，如果訪問列表很大或需要很多第四層運(yùn)算，TCAM表和寄存器很可能溢出。

7、TCAM成本比較高，存儲(chǔ)空間的單位價(jià)格高于普通的sram，而且耗能也遠(yuǎn)遠(yuǎn)高于sram

8、由于TCAM的并行查找特性和三態(tài)，存儲(chǔ)必須以前綴形式來(lái)存儲(chǔ)，比如一個(gè)range需要拆分成幾個(gè)更小的可以表示成前綴形式的range才可以存儲(chǔ)在TCAM中

它是從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)，所以稱為“三態(tài)”，它是通過(guò)掩碼來(lái)實(shí)現(xiàn)的，正是TCAM的這個(gè)第三種狀態(tài)特征使其既能進(jìn)行精確匹配查找，又能進(jìn)行模糊匹配查找，而CAM沒有第三種狀態(tài)，所以只能進(jìn)行精確匹配查找。