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

朱國勝，余少華,2

（1. 華中科技大學 計算機學院，湖北 武漢 430074；

2. 武漢郵電科學研究院 新一代光纖通信技術和網絡國家重點實驗室，湖北 武漢 430074）

1 引言

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

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

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

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

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

圖1 寬度為4bit的范圍擴張示例

2 相關工作

2.1 規(guī)則庫無關范圍匹配方法

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

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

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

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

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

3 C-TCAM方法

3.1 C-TCAM算法思想

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

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

3.2 問題定義和相關術語

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

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

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

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

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

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

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

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

文章的第5節(jié)的仿真實驗中將通過實驗對不同算法的規(guī)則庫擴張因子 DE和規(guī)則庫冗余因子FRE(D)進行比較。

3.3 C-TCAM體系結構

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

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

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

3.4 C-TCAM匹配算法

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

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

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

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

圖2 C-TCAM體系結構

圖3 C-TCAM-MATCH2算法

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

4 算法比較和分析

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

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

表1 不同算法的指標對比

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

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

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

二級C-TCAM方法的功耗為

或者

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

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

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

5 實驗仿真

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

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

表2 測試用規(guī)則庫規(guī)則轉換

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

圖4 不同算法的規(guī)則庫擴張因子DE對比

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

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

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

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

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

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

6 結束語

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

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

[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.