基于TCAM的范圍匹配方法——C-TCAM

朱國(guó)勝，余少華,2

（1. 華中科技大學(xué) 計(jì)算機(jī)學(xué)院，湖北 武漢 430074；

2. 武漢郵電科學(xué)研究院 新一代光纖通信技術(shù)和網(wǎng)絡(luò)國(guó)家重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430074）

1 引言

互聯(lián)網(wǎng)路由交換網(wǎng)絡(luò)設(shè)備需要采用分組分類技術(shù)，將到達(dá)分組的頭部信息和分類規(guī)則庫(kù)中的規(guī)則條件進(jìn)行匹配，并根據(jù)匹配結(jié)果實(shí)現(xiàn)規(guī)則動(dòng)作，包括轉(zhuǎn)發(fā)、丟棄、隊(duì)列排隊(duì)等，從而實(shí)現(xiàn)訪問(wèn)控制、安全過(guò)濾、帶寬控制等。和IP路由查找一樣，分組分類功能處在網(wǎng)絡(luò)設(shè)備的數(shù)據(jù)平面，需要進(jìn)行每分組處理，對(duì)性能要求很高。

目前，業(yè)界普遍采用三態(tài)內(nèi)容尋址存儲(chǔ)器（TCAM, ternary content-addressable memory）來(lái)實(shí)現(xiàn)高速分組分類，Cisco的Catalyst 6500高端交換機(jī)采用多片TCAM來(lái)分別實(shí)現(xiàn)3層IP路由、訪問(wèn)控制列表ACL、分組分類以及NETFLOW等功能[1]。TCAM 可配置成 36bit、72bit、144bit、288bit、576bit等寬度，用于存儲(chǔ)固定寬度的查找條件。和普通內(nèi)存通過(guò)地址尋找內(nèi)容不同，TCAM通過(guò)內(nèi)容來(lái)定位地址，它將查找關(guān)鍵字和所有TCAM表項(xiàng)進(jìn)行并行比較來(lái)定位關(guān)鍵字匹配的存儲(chǔ)地址，根據(jù)得到的地址來(lái)得到存儲(chǔ)在快速SRAM中的規(guī)則動(dòng)作。TCAM的并行特性使得分組分類查找可以在固定的時(shí)鐘周期內(nèi)完成，目前TCAM的時(shí)鐘周期可以做到2ns，可以實(shí)現(xiàn) 500MSPS的查找速率[2]，TCAM 三態(tài)特性需要采用多達(dá) 16個(gè)晶體管來(lái)實(shí)現(xiàn)一個(gè)比特的存儲(chǔ)，導(dǎo)致芯片面積較大而且價(jià)格較高，而TCAM的并行比較特性使得功耗很高，一個(gè)18Mbit的TCAM功耗高達(dá)15W[3]。因此在單板線卡設(shè)計(jì)中必須考慮TCAM 的成本、功耗和體積，并充分利用 TCAM的每個(gè)比特。

有效利用 TCAM 來(lái)完成高速分組分類的主要障礙是TCAM不適合實(shí)現(xiàn)范圍匹配，TCAM的三態(tài)特性可以很容易地實(shí)現(xiàn)規(guī)則條件中的前綴匹配和精確匹配，比如規(guī)則條件中的地址字段和協(xié)議字段匹配，而規(guī)則條件中的范圍字段比如端口范圍則無(wú)法直接實(shí)現(xiàn)，必須轉(zhuǎn)換成前綴匹配和精確匹配，一個(gè)包含范圍字段的規(guī)則需要轉(zhuǎn)換成多個(gè)規(guī)則才能存放在 TCAM 中，稱之為范圍擴(kuò)張（range expansion），范圍擴(kuò)張一方面降低了TCAM的空間使用效率，另一方面TCAM的功耗和參與比較的表項(xiàng)的數(shù)目成正比，因此范圍擴(kuò)張會(huì)導(dǎo)致TCAM功耗的增加。

如圖1所示為4bit寬度的范圍字段范圍擴(kuò)張的示例，范圍[1,14]需要擴(kuò)張成6個(gè)前綴匹配或者精確匹配的條目，在 TCAM 中進(jìn)行存放并參與匹配比較，范圍[1,14]的范圍擴(kuò)張因子為6，每條攜帶范圍[1,14]的匹配規(guī)則需要擴(kuò)張成6條規(guī)則。

因此，基于TCAM的范圍匹配主要解決如下的2個(gè)問(wèn)題：①如何減少范圍擴(kuò)張，以有效利用TCAM的空間；②如何設(shè)計(jì)有效的TCAM匹配算法以降低功耗。

圖1 寬度為4bit的范圍擴(kuò)張示例

2 相關(guān)工作

2.1 規(guī)則庫(kù)無(wú)關(guān)范圍匹配方法

對(duì)每個(gè)范圍單獨(dú)進(jìn)行轉(zhuǎn)換，無(wú)需考慮規(guī)則庫(kù)里各種范圍的分布以及和其他范圍的關(guān)系。文獻(xiàn)[4]提出了一種前綴擴(kuò)展（PE, prefix expansion）方法，該方法將范圍轉(zhuǎn)換成若干個(gè)前綴，每個(gè)前綴對(duì)應(yīng)一個(gè)TCAM表項(xiàng)，在最壞情況下一個(gè)范圍需要轉(zhuǎn)換成2(W-1)個(gè)前綴，其中，W為范圍字段的長(zhǎng)度，范圍Rw=[1，2w-2]就是這種情況（前面的引言的范圍[1,14]是4bit示例）；對(duì)于長(zhǎng)度為16的源端口和目的端口來(lái)說(shuō)，最壞情況下一條規(guī)則需要轉(zhuǎn)換成(2×16-2)2=900個(gè)TCAM表項(xiàng)，對(duì)于真實(shí)分類規(guī)則庫(kù)轉(zhuǎn)換顯示平均會(huì)導(dǎo)致6倍的表項(xiàng)擴(kuò)張[5]。文獻(xiàn)[6]提出了利用 TCAM 額外比特對(duì)范圍進(jìn)行獨(dú)立編碼的DIRPE(database independent range preenconding )方法，假定TCAM的額外比特為2w，則每個(gè)范圍只需要一個(gè)TCAM表項(xiàng)就可完成轉(zhuǎn)換，由于TCAM的額外比特?cái)?shù)有限，在配置為144bit寬度時(shí)，額外比特?cái)?shù)僅為40，為減少對(duì)TCAM額外比特的需求，提出了對(duì)范圍字段進(jìn)行分段編碼以及結(jié)合規(guī)則庫(kù)相關(guān)的編碼方法，增加了每個(gè)范圍需要的TCAM表項(xiàng)數(shù)目，因此，該方法的效率和范圍字段的長(zhǎng)度和TCAM的額外比特?cái)?shù)量相關(guān)。文獻(xiàn)[7]提出了基于格雷碼（Gray code）的范圍編碼方法SRGE，該方法利用了格雷碼的相鄰編碼之間只有一個(gè)比特不同從而可以合并成一個(gè)TCAM表項(xiàng)的特點(diǎn)（將該不同比特用通配符‘*’來(lái)表示），在最壞情況下一個(gè)范圍需要轉(zhuǎn)換成 2(W-2)個(gè)前綴，該方法無(wú)需利用TCAM的額外比特，但僅對(duì)于短的范圍比較有效。

2.2 規(guī)則庫(kù)相關(guān)范圍匹配方法

文獻(xiàn)[8]提出了對(duì)每個(gè)單獨(dú)的范圍用一個(gè)額外的TCAM比特來(lái)表示的規(guī)則庫(kù)相關(guān)范圍匹配方法，只需要一個(gè) TCAM 表項(xiàng)就可以完成一個(gè)范圍規(guī)則的表示。由于目前規(guī)則庫(kù)中單獨(dú)的范圍在增加，已經(jīng)超過(guò) 300個(gè)，而且還在不斷地增加，而額外的TCAM比特?cái)?shù)量非常有限，同樣，作者也提出分段編碼方法（region-based encoding）增加TCAM表項(xiàng)從而減少對(duì)TCAM額外比特的需求。為了進(jìn)一步對(duì)范圍進(jìn)行有效地編碼并減少編碼的比特?cái)?shù)，文獻(xiàn)[9]提出層次化編碼方法，在每個(gè)層次里面，范圍都是不相交的，對(duì)每個(gè)層次里面的范圍進(jìn)行單獨(dú)編碼，假定層Li中的不相交范圍個(gè)數(shù)為Ni，則需要的比特?cái)?shù)位lb Ni，而前述方法中每個(gè)范圍需要一個(gè)TCAM比特，從而減少了每個(gè)范圍需要的比特。

另外，文獻(xiàn)[10]提出了E-TCAM方法，該方法直接修改TCAM硬件設(shè)計(jì)支持范圍匹配，可以降低90%的功耗，由于需要對(duì)TCAM硬件進(jìn)行修改，因此會(huì)增加每比特成本，存在兼容性和擴(kuò)展性問(wèn)題，短期內(nèi)無(wú)法大規(guī)模部署和實(shí)現(xiàn)。

相比而言，規(guī)則庫(kù)無(wú)關(guān)范圍匹配方法和具體規(guī)則庫(kù)無(wú)關(guān)，在規(guī)則更新方面具有優(yōu)勢(shì)。

3 C-TCAM方法

3.1 C-TCAM算法思想

我們發(fā)現(xiàn)：一條規(guī)則經(jīng)過(guò)前綴擴(kuò)展轉(zhuǎn)換或者格雷碼轉(zhuǎn)換成多條規(guī)則后，規(guī)則條件里面的非范圍字段是一樣的，僅范圍字段不一樣，可以將多條規(guī)則存放在一個(gè)TCAM表項(xiàng)中，而且，只需保存一份非范圍字段的拷貝，比如對(duì)于IPv4分組分類來(lái)說(shuō)，采用144bit TCAM位寬，非范圍字段包括源地址、目的地址、協(xié)議字段共72bit，范圍字段包括源端口、目的端口共32bit，還剩余40bit可以再保存一份源端口、目的端口字段，這樣可以將二條規(guī)則壓縮在一個(gè)TCAM表項(xiàng)里面，可以成倍地減少最壞情況下范圍擴(kuò)張，有效利用昂貴的TCAM空間。

另外，查找時(shí)，現(xiàn)有商用TCAM芯片都支持全局掩碼寄存器（GMR, global mask register）和分區(qū)掩碼寄存器（BMR, block mask register）[2],GMR寄存器可以從縱向確定 TCAM 芯片中參與比較的比特，BMR寄存器用于支持在橫向上將TCAM芯片進(jìn)行分區(qū)，支持分區(qū)禁用，本方法利用了TCAM芯片的特性，在查找時(shí)通過(guò)GMR和BMR動(dòng)態(tài)地選擇參與比較的比特和參與比較的TCAM表項(xiàng)，在減少范圍擴(kuò)張的同時(shí)減少參與比較的 TCAM 表項(xiàng)數(shù)目，從而降低功耗。

3.2 問(wèn)題定義和相關(guān)術(shù)語(yǔ)

分組分類的相關(guān)術(shù)語(yǔ)和定義沿用文獻(xiàn)[6,7]的說(shuō)法。分組的頭部由若干個(gè)字段組成，每個(gè)字段包含若干個(gè)比特。查找關(guān)鍵字 KEY是從分組頭部提取的K個(gè)字段的組合。查找關(guān)鍵字需要和存儲(chǔ)在分類規(guī)則庫(kù)中的規(guī)則條件進(jìn)行匹配。

規(guī)則包含規(guī)則條件和規(guī)則動(dòng)作，規(guī)則條件由相應(yīng)的K個(gè)字段組成，如果分組P的K個(gè)關(guān)鍵字字段和規(guī)則 R的 K個(gè)規(guī)則條件匹配，則認(rèn)為分組 P匹配規(guī)則R，相應(yīng)會(huì)對(duì)分組P采取規(guī)則R規(guī)定的規(guī)則動(dòng)作。每個(gè)規(guī)則字段f可以指定3種類型的匹配條件。

1) 精確匹配：關(guān)鍵字字段和規(guī)則條件字段指定的值相等。

2) 前綴匹配：規(guī)則條件字段是關(guān)鍵字字段的前綴。

3) 范圍匹配：關(guān)鍵字字段在規(guī)則條件指定的范圍里面，比如規(guī)則條件指定的范圍為[s, e]，s和 e為整數(shù)，s

分類規(guī)則庫(kù)可以存放在 TCAM 中以實(shí)現(xiàn)高速分組分類，規(guī)則在TCAM中按照優(yōu)先級(jí)從高到低排序存放，高優(yōu)先級(jí)存放在TCAM低地址區(qū)，TCAM總是返回第一個(gè)匹配的結(jié)果（低地址區(qū)）。TCAM的每個(gè)比特支持“0”、“1”和“*”3種狀態(tài)，精確匹配規(guī)則條件和前綴匹配規(guī)則條件可以直接存放，而范圍匹配則需要轉(zhuǎn)換成相應(yīng)的精確匹配和前綴匹配，因此一條規(guī)則R需要采用轉(zhuǎn)換方法E轉(zhuǎn)換成多個(gè)TCAM表項(xiàng)TCAMR[1, nR]，范圍R的擴(kuò)張因子RE=nR,假定n(D)為分類規(guī)則庫(kù)D的規(guī)則數(shù)量，nE(D)采用轉(zhuǎn)換方法 E對(duì)分類規(guī)則庫(kù)進(jìn)行轉(zhuǎn)換后所有TCAM表項(xiàng)的數(shù)目，則分類規(guī)則庫(kù)D的擴(kuò)張因子DE表示為

由于規(guī)則庫(kù)里存在不包含范圍匹配的規(guī)則，為進(jìn)一步考察范圍規(guī)則轉(zhuǎn)換的有效性，假定r(D)表示規(guī)則庫(kù)里面包含范圍的規(guī)則數(shù)，rE(D)表示對(duì)這些包含范圍的規(guī)則進(jìn)行轉(zhuǎn)換后的TCAM表項(xiàng)數(shù)，規(guī)則庫(kù)D的范圍冗余因子FRE(D)表示為

而某條規(guī)則R的范圍冗余因子FRE(R)，也就是規(guī)則R需要的額外的TCAM表項(xiàng)的個(gè)數(shù)

文章的第5節(jié)的仿真實(shí)驗(yàn)中將通過(guò)實(shí)驗(yàn)對(duì)不同算法的規(guī)則庫(kù)擴(kuò)張因子 DE和規(guī)則庫(kù)冗余因子FRE(D)進(jìn)行比較。

3.3 C-TCAM體系結(jié)構(gòu)

圖2所示為C-TCAM的體系結(jié)構(gòu)，對(duì)規(guī)則庫(kù)中包含范圍的規(guī)則進(jìn)行前綴擴(kuò)展或者格雷碼擴(kuò)展，擴(kuò)展后的規(guī)則在TCAM中進(jìn)行按照規(guī)則優(yōu)先級(jí)排序，在每行TCAM中存放二條規(guī)則，這二條規(guī)則除了源端口和目的端口不同外，其他比如源地址、目的地址、協(xié)議和規(guī)則動(dòng)作均相同，因此除了源端口和目的端口外的其他字段只需要保存一份拷貝。圖2所示假定規(guī)則庫(kù)D包含R1到R7 7條規(guī)則，并且按照優(yōu)先級(jí)進(jìn)行排序，經(jīng)過(guò)前綴擴(kuò)展編碼或者格雷碼編碼轉(zhuǎn)換后，R1需要4個(gè)TCAM表項(xiàng)（表示為R11、R12、R13、R14）、R3和R6需要一個(gè)TCAM表項(xiàng)，其他規(guī)則需要2個(gè)TCAM表項(xiàng)，轉(zhuǎn)換后的規(guī)則存儲(chǔ)如圖 2所示，R1的 4個(gè) TCAM 表項(xiàng)占據(jù) 2行TCAM，其他規(guī)則均占據(jù)一行TCAM，需要注意的是，雖然R3和R6只需要一個(gè)TCAM表項(xiàng)，但依然在GMR3對(duì)應(yīng)的比特存放了R3和R6對(duì)應(yīng)的源端口和目的端口，而且和 GMR1對(duì)應(yīng)的源端口和目的端口相同，這主要是為了保證匹配算法返回的結(jié)果正確，具體原因在3.4節(jié)的C-TCAM查找部分進(jìn)行說(shuō)明。

圖中的GMR用于從縱向上選擇和查找關(guān)鍵字進(jìn)行匹配的比特，當(dāng)選擇 GMR=GMR0+ GMR1+GMR2，GMR3和GMR4對(duì)應(yīng)的比特不參與匹配比較；當(dāng)選擇 GMR=GMR0+GMR2+GMR3，GMR1和GMR4對(duì)應(yīng)的比特不參與匹配比較，可以看出，GMR4對(duì)應(yīng)的比特為空閑比特，在2種情況下都不參與比較，對(duì)于IPv4分組分類，TCAM配置為144bit寬度，GMR4的寬度為 8bit，某些規(guī)則條件還包括TCP標(biāo)志字段，這時(shí)這些空閑比特可以進(jìn)一步被利用。

圖中的BMR用于從橫向上選擇參與匹配比較的TCAM表項(xiàng)，由于規(guī)則存在重疊關(guān)系，C-TCAM方案需要經(jīng)過(guò)二輪匹配才能確定匹配的規(guī)則，比如R7的規(guī)則條件包含R14，但是R7定義的動(dòng)作和R1不同，為保證結(jié)果正確（選擇優(yōu)先級(jí)高的 R14），C-TCAM需要查找匹配需要進(jìn)行二輪匹配，判決邏輯用于對(duì)二次匹配的結(jié)果進(jìn)行比較，并選擇低地址區(qū)的匹配結(jié)果作為最終分組分類結(jié)果，對(duì)分組執(zhí)行規(guī)則條件對(duì)應(yīng)的動(dòng)作。

3.4 C-TCAM匹配算法

經(jīng)過(guò)上述的擴(kuò)展和壓縮存儲(chǔ)后，減少了范圍擴(kuò)張數(shù)目，有效利用TCAM的空間，較好地解決了基于TCAM的范圍匹配的第一個(gè)問(wèn)題；對(duì)于第二個(gè)問(wèn)題，需要設(shè)計(jì)有效的TCAM匹配算法減少參與比較的表項(xiàng)數(shù)目以降低功耗。

可以看出，表項(xiàng)通過(guò)壓縮存儲(chǔ)后，為了返回正確的結(jié)果，需要進(jìn)行兩輪查找，并選擇兩輪查找的索引小者作為查找結(jié)果用于定位規(guī)則動(dòng)作。

在上節(jié)曾提到，雖然 R3和 R6只需要一個(gè)TCAM 表項(xiàng)，但依然在 GMR3對(duì)應(yīng)的比特存放了R3和R6對(duì)應(yīng)的源端口和目的端口，而且和GMR1對(duì)應(yīng)的源端口和目的端口相同，主要是因?yàn)槿绻鸕3和R6的GMR3對(duì)應(yīng)的比特放置通配，則在第二輪查找時(shí)R3和R6總是會(huì)返回匹配，會(huì)導(dǎo)致結(jié)果的不正確。例如，假定某關(guān)鍵字KEY應(yīng)該匹配R72，在第二輪匹配時(shí)，R3、R6和R72都返回匹配，R3優(yōu)先級(jí)最高，判決邏輯會(huì)選擇 R3作為匹配結(jié)果，從而導(dǎo)致結(jié)果錯(cuò)誤，如果在GMR3的對(duì)應(yīng)比特放置一份和GMR1相同的源端口和目的端口，則可避免該問(wèn)題的出現(xiàn)。

C-TCAM匹配算法如圖3所示，該算法輸入為查找關(guān)鍵字KEY，輸出為匹配的規(guī)則在TCAM中的地址對(duì)應(yīng)的索引，用于定位規(guī)則動(dòng)作。在獲取Index1之后，計(jì)算Index1所在的Block，BMR被賦值給Index1所在Block及其以上的Block，匹配得到Index2，將Index1和Index2中的較小者返回。原因是在第一輪匹配時(shí)，對(duì)于存放位置大于Index1的表項(xiàng)的比較是沒(méi)有意義的，而且會(huì)增加功耗，通過(guò)對(duì)大于Index1的Block進(jìn)行禁用，在第二輪只允許 Index1所在的 Block及其以上的Block參與比較，從而降低功耗，也不會(huì)影響結(jié)果的正確性。

圖2 C-TCAM體系結(jié)構(gòu)

圖3 C-TCAM-MATCH2算法

上述C-TCAM方法將2個(gè)表項(xiàng)進(jìn)行壓縮存儲(chǔ)，稱之為二級(jí)C-TCAM。由于TCAM的位寬是可配的，如果經(jīng)過(guò)二級(jí)C-TCAM壓縮存儲(chǔ)后還有空閑比特可用，可以進(jìn)行多級(jí)壓縮存儲(chǔ)進(jìn)一步提供空間利用率，查找算法經(jīng)簡(jiǎn)單修改后依然適用。必須注意，多級(jí)擴(kuò)展會(huì)導(dǎo)致查找性能的下降，因此，必須綜合考慮空間、功耗和性能等因素。

4 算法比較和分析

表1所示為不同算法的關(guān)鍵指標(biāo)對(duì)比，包括最壞情況下的范圍轉(zhuǎn)換擴(kuò)張因子、對(duì)TCAM額外比特的占用需求、規(guī)則更新的代價(jià)、功耗以及匹配性能等。表中F為包含范圍匹配的字段的個(gè)數(shù)（對(duì)于IP分組分類來(lái)說(shuō)為2：源端口字段和目的端口字段），W為包含范圍匹配的字段的長(zhǎng)度，N為規(guī)則庫(kù)規(guī)則條目總數(shù)。

最壞情況下擴(kuò)張因子方面，二級(jí)C-TCAM方法比前綴擴(kuò)展方法和格雷碼方法降低一倍，優(yōu)勢(shì)比較明顯。

表1 不同算法的指標(biāo)對(duì)比

TCAM額外比特方面，前綴擴(kuò)展和格雷碼無(wú)需額外比特，二級(jí)C-TCAM方法需要2Wbit，在IP分組分類下為2×16=32bit，C-TCAM方法的額外比特是利用空閑的TCAM bit，不但不會(huì)新增另外的TCAM空間，而且對(duì)空閑空間進(jìn)行了充分的利用。

規(guī)則更新方面，C-TCAM方法與前綴擴(kuò)展和格雷碼方法相同，一條規(guī)則的添加、刪除和規(guī)則庫(kù)里其他規(guī)則無(wú)關(guān)，支持規(guī)則的增量更新。

功耗方面：最壞情況下的功耗Pmax是硬件設(shè)計(jì)的功耗預(yù)算計(jì)算和電源設(shè)計(jì)時(shí)必須考慮的內(nèi)容。TCAM功耗和參與比較的 TCAM 條目總數(shù)相關(guān)，前綴擴(kuò)展方法和格雷碼方法的最壞情況下功耗分別為

二級(jí)C-TCAM方法的功耗為

或者

參數(shù) ρ的取值和第一輪匹配時(shí) Index1所在的Block號(hào)相關(guān)，假定Index1所在Block號(hào)為B1，所用到的TCAM的所有Block數(shù)量為B，則

B1總是小于等于B，因此ρ總是小于等于1，C-TCAM方法功耗最低。

查找性能方面，其他方法需要一個(gè)時(shí)鐘周期，二級(jí)C-TCAM需要2個(gè)時(shí)鐘周期，但是可以看到，現(xiàn)有商用TCAM時(shí)鐘周期可以做到2ns，以最小以太網(wǎng)分組長(zhǎng) 672bit(包括前導(dǎo)碼、幀間隔)來(lái)計(jì)算，為保證 100Gbit/s接口的線速轉(zhuǎn)發(fā)，分組轉(zhuǎn)發(fā)率要達(dá)到148.8Mpacket/s，每分組處理時(shí)延小于6.72ns，二級(jí)C-TCAM依然可以滿足要求。

5 實(shí)驗(yàn)仿真

由于真實(shí)的分類規(guī)則包含隱私信息無(wú)法公開(kāi)獲取，采用Classbench[11]工具來(lái)生成分類規(guī)則庫(kù)和測(cè)試用Trace文件。Classbench是華盛頓大學(xué)圣路易斯分校Taylor等開(kāi)發(fā)的開(kāi)放源代碼分組分類規(guī)則和測(cè)試用Trace文件生成工具，Classbench通過(guò)分析真實(shí)的訪問(wèn)控制列表、防火墻和 Linux的IPChains，得到種子文件，這些種子文件包含用于生成分類規(guī)則庫(kù)的相關(guān)參數(shù)，比如地址字段長(zhǎng)度分布、協(xié)議字段分布、端口字段通配分布、端口范圍和精確匹配分布等。Classbench生成的Trace文件包含隨機(jī)的頭部信息，用于分類匹配算法的測(cè)試。

利用Classbench，生成了6個(gè)規(guī)則庫(kù)D1到D6，規(guī)則庫(kù)的規(guī)則條目以及經(jīng)過(guò)前綴擴(kuò)展轉(zhuǎn)換、格雷碼轉(zhuǎn)換、C-TCAM轉(zhuǎn)換后的規(guī)則條目如表2所示。

表2 測(cè)試用規(guī)則庫(kù)規(guī)則轉(zhuǎn)換

從表2可以看出，經(jīng)過(guò)C-TCAM轉(zhuǎn)換后，TCAM規(guī)則條目大大減少。為便于比較，圖4和圖5給出了基于表2的不同算法的規(guī)則庫(kù)擴(kuò)張因子DE對(duì)比和規(guī)則庫(kù)冗余因子FRE(D)對(duì)比，從圖中可以看出，C-TCAM 方法的擴(kuò)張因子和冗余因子比前綴擴(kuò)展方法和格雷碼方法的要低。因此在TCAM空間方面具有優(yōu)勢(shì)。

圖4 不同算法的規(guī)則庫(kù)擴(kuò)張因子DE對(duì)比

圖5 不同算法的規(guī)則庫(kù)冗余因子FRE(D)對(duì)比

功耗方面，TCAM的功耗和參與比較的TCAM的條目數(shù)相關(guān)?；谝?guī)則庫(kù)D3的1 024條規(guī)則，選擇 TCAM Block大小為 128bit，TCAM 寬度為144bit，利用 Classbench生成測(cè)試用 Trace文件，Trace文件包含2 000個(gè)分組頭信息。將2 000個(gè)分組輸入不同的分類匹配方案進(jìn)行仿真測(cè)試，記錄每個(gè)分組頭需要比較的TCAM條目的數(shù)，如圖6所示。

圖6(a)為前綴擴(kuò)展方法和C-TCAM的匹配條目對(duì)比，圖6(b)為格雷碼方法和C-TCAM的匹配條目對(duì)比。圖中，橫軸表示2 000次實(shí)驗(yàn)，縱軸表示每次實(shí)驗(yàn)需要比較的TCAM條目數(shù)。

從圖6(a)可以看出，前綴擴(kuò)展方法每次需要比較的TCAM條目數(shù)固定為3 062，表現(xiàn)為直線，C-TCAM(PE)方法需要比較的TCAM條目數(shù)在1 577和3 154之間波動(dòng)，其均值為2 457，小于前綴擴(kuò)展方法的3 062。

同樣，從圖6(b)可以看出，格雷碼方法每次需要比較的TCAM條目數(shù)固定為2 765，表現(xiàn)為直線，C-TCAM (SRGE)方法需要比較的TCAM條目數(shù)在1 423和2 826之間波動(dòng)，其均值為2 258，小于格雷碼方法的2 765。

圖6 不同匹配算法需要比較的TCAM條目數(shù)（規(guī)則庫(kù)D3）

6 結(jié)束語(yǔ)

針對(duì)基于 TCAM 分組分類在實(shí)現(xiàn)范圍匹配時(shí)存在的TCAM空間利用率低和功耗高的問(wèn)題，本文提出了一種新的基于 TCAM 的范圍匹配方法C-TCAM：空間方面，通過(guò)二級(jí)壓縮存儲(chǔ)，C-TCAM可以將2個(gè)擴(kuò)展后的TCAM表項(xiàng)壓縮成一個(gè)，最壞情況下表項(xiàng)擴(kuò)張因子為W-1或者W-2，提高了空間利用率；功耗方面，通過(guò)查找算法來(lái)避免無(wú)效表項(xiàng)參與比較從而降低了功耗；分析和仿真顯示C-TCAM 方法在實(shí)現(xiàn)高速分組分類的同時(shí)在空間利用率、功耗等方面具有優(yōu)勢(shì)。

必須看到，雖然基于現(xiàn)有商用TCAM，C-TCAM可以支持 100Gbit/s的線速分組分類，但是該方法需要經(jīng)過(guò)多個(gè) TCAM 時(shí)鐘周期才能完成一次分組分類，因此，它是一種在性能、空間和功耗上做出選擇的方案。

[1] Suran de Silva. Cisco 6500 FIB forwarding capacities[EB/OL].http://www.nanog.org/mtg-0702/presentations/fib-desilva.pdf,2007.

[2] Netlogic microsystems[EB/OL]. http://www.netlogicmicro.com/,2010.

[3] ZANE F, NARLIKAR G, BASU A. CoolCAMs: power-efficient TCAMs for forwarding engines[A]. Proceedings of the 22nd IEEE INFOCOM[C]. San Francisco, USA, 2003. 42-52.

[4] TAYLOR D, SPITZNAGEL E, TURNER J. Packet classification using extended tcams[A]. ICNP '03 Proceedings of the 11th IEEE International Conference on Network Protocols[C]. 2003.120-131.

[5] SRINIVASAN V, VARGHESE G, SURI S, et al. Fast and scalable layer four switching[A]. ACM SIGCOMM 98[C]. 1998.191-202.

[6] TAYLOR D E. Survey and taxonomy of packet classification techniques[J]. ACM Computer Surverys, 2005,37(3): 238-275.

[7] VENKATACHARY S, LAKSHMINARAYANAN K, RANGARAJAN A. Algorithms for advanced packet classification with ternary cams[J].ACM SIGCOMM Computer Communication Review, 2005 35(4):193-204.

[8] BREMLER-BARR A, HENDLER D. Space-efficient TCAM-based classification using gray coding[A]. INFOCOM 2007, The 26th IEEE International Conference on Computer Communications[C]. 2007.1388-1396.

[9] LIU H. Efficient mapping of range classifier into ternary-cam[A].High Performance Interconnects[C]. 2002.95-100.

[10] BREMLER-BARR A, HAY D, HENDLER D, et al. Layered interval codes for tcam-based classification[A]. INFOCOM 2009, the 28th IEEE International Conference on Computer Communications[C].2009.1305-1313.

[11] TAYLOR D E, TURNER J S. ClassBench: a packet classification benchmark[J]. IEEE/ACM Transactions on Networking, 2007, 15(3):499-511.