基于TCAM的低能耗正則表達(dá)式匹配算法

丁麟軒，黃昆，張大方

(1. 湖南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙 410082；2. 中國科學(xué)院 計(jì)算技術(shù)研究所，北京 100190)

1 引言

近年來，隨著網(wǎng)絡(luò)應(yīng)用的日益增多，網(wǎng)絡(luò)安全面臨著越來越嚴(yán)峻的挑戰(zhàn)。網(wǎng)絡(luò)入侵檢測與防御系統(tǒng)（NIDPS, network intrusion detection/prevention system）是網(wǎng)絡(luò)安全防御的主要手段，它通過實(shí)時(shí)監(jiān)測網(wǎng)絡(luò)流量，檢查和阻止網(wǎng)絡(luò)攻擊[1]。深度分組檢測[2]（DPI, deep packet inspection）是 NIDPS、防火墻和應(yīng)用層交換機(jī)的核心部件，不僅檢查數(shù)據(jù)分組的頭部信息，而且檢查數(shù)據(jù)分組的有效載荷。由于正則表達(dá)式具有豐富和靈活的表達(dá)能力，目前主流的 NIDPS，例如 Snort[3]、Bro[4]、TippingPoint[5]、Cisco[6]廣泛采用正則表達(dá)式匹配算法進(jìn)行DPI操作。

三態(tài)內(nèi)容可尋址存儲(chǔ)器（TCAM, ternary content addressable memory）是一種快速并行查找的專門硬件。TCAM在一個(gè)時(shí)鐘周期內(nèi)并行查找所有表項(xiàng)，返回與關(guān)鍵字匹配的第一條表項(xiàng)的地址。TCAM具備三態(tài)表示特性，即TCAM表項(xiàng)可存儲(chǔ)0、1和“*”，其中“*”表示無關(guān)位，可以匹配0或1。在網(wǎng)絡(luò)處理應(yīng)用中，TCAM通常與靜態(tài)隨機(jī)存儲(chǔ)器（SRAM,static random access memory）結(jié)合在一起使用，在關(guān)鍵字查找匹配成功后，TCAM將匹配的表項(xiàng)地址發(fā)送到SRAM，輸出SRAM中保存的相應(yīng)信息。與TCAM相比，SRAM的存儲(chǔ)空間大且能耗低。

近年來，研究者提出了多種基于TCAM的正則表達(dá)式匹配算法[7～9]，實(shí)現(xiàn)線速 DPI?；?TCAM的正則表達(dá)式匹配算法采用 TCAM 表示確定型有限自動(dòng)機(jī)（DFA, deterministic finite automaton），即將狀態(tài)遷移表的每條狀態(tài)遷移邊存儲(chǔ)在一條TCAM表項(xiàng)中，每條表項(xiàng)由TCAM和SRAM兩部分組成：源狀態(tài)和輸入字符存儲(chǔ)在TCAM部分，目的狀態(tài)及其他相關(guān)信息存儲(chǔ)在與TCAM部分對應(yīng)的 SRAM部分。基于TCAM的正則表達(dá)式匹配算法的查找過程如下：首先，將當(dāng)前狀態(tài)和輸入字符組合成一個(gè)關(guān)鍵字，在TCAM中查找與該關(guān)鍵字匹配的表項(xiàng)；然后，根據(jù)匹配的表項(xiàng)地址，訪問相應(yīng)的SRAM部分，獲取遷移的目的狀態(tài)；最后，將目的狀態(tài)作為當(dāng)前狀態(tài)，讀入下一個(gè)輸入字符，重復(fù)執(zhí)行相似的TCAM查找，直至輸入字符結(jié)束。

已有基于 TCAM 的正則表達(dá)式匹配算法主要關(guān)注減少TCAM存儲(chǔ)開銷，很少關(guān)注減少TCAM能耗。TCAM雖然匹配查找速率快，但是存在能耗高等缺點(diǎn)。在正則表達(dá)式匹配中，導(dǎo)致TCAM高能耗的原因是：給定一個(gè)查找的關(guān)鍵字（即當(dāng)前狀態(tài)和輸入字符），TCAM將該關(guān)鍵字與TCAM中存儲(chǔ)的所有遷移邊表項(xiàng)進(jìn)行并行比較。例如，存儲(chǔ)空間大小為18 MB的TCAM一次查找操作所需能耗高達(dá)15 W[10]，這將導(dǎo)致嵌入TCAM芯片的路由器、交換機(jī)或者其他硬件設(shè)備能耗過載。同時(shí)，隨著網(wǎng)絡(luò)應(yīng)用的發(fā)展，網(wǎng)絡(luò)攻擊和應(yīng)用日益復(fù)雜化，特征規(guī)則集條數(shù)不斷增多且描述越來越復(fù)雜，存儲(chǔ)DFA所需的 TCAM 存儲(chǔ)空間也越來越大，從而導(dǎo)致TCAM能耗開銷進(jìn)一步提高。

本文提出一種基于字符索引的正則表達(dá)式匹配算法，減少TCAM的能耗。該算法的核心思想是：將TCAM分為索引塊和存儲(chǔ)塊；DFA的字母表存儲(chǔ)在TCAM索引塊中，每個(gè)字符的索引范圍存儲(chǔ)在對應(yīng)的 SRAM 中；狀態(tài)遷移邊的源狀態(tài)存儲(chǔ)在TCAM 存儲(chǔ)塊中，目的狀態(tài)存儲(chǔ)在對應(yīng)的 SRAM中。該算法的匹配查找過程如下：首先，在TCAM索引塊中查找當(dāng)前的輸入字符，在對應(yīng)的SRAM中獲取相應(yīng)的索引范圍；然后，根據(jù)索引范圍啟動(dòng)對應(yīng)的TCAM存儲(chǔ)塊，匹配當(dāng)前狀態(tài)，在SRAM中獲取遷移的目的狀態(tài)。

本文的主要貢獻(xiàn)是：1）提出了基于字符索引的DFA（CIDFA, character-indexed DFA），減少匹配時(shí)激活的TCAM塊數(shù)，降低TCAM能耗；2）針對Snort和 Bro特征規(guī)則集開展實(shí)驗(yàn)，結(jié)果表明，與DFA相比，CIDFA在 TCAM 能耗上平均減少了92.7%，在 TCAM 存儲(chǔ)空間開銷上平均減少了32.0%，在吞吐量上平均提高了57.9%。

2 相關(guān)工作

DPI技術(shù)的核心是正則表達(dá)式匹配算法，基于硬件的正則表達(dá)式匹配算法主要從壓縮存儲(chǔ)空間等方面開展研究?；贔PGA的算法[11～14]實(shí)現(xiàn)了非確定性有限自動(dòng)機(jī)（NFA, nondeterministic finite automata），基于ASIC的算法[15～18]則實(shí)現(xiàn)了DFA。Kumar等人[15,16]提出了基于D2FA的正則表達(dá)式匹配算法，壓縮了 DFA的遷移邊，Smith等人[19,20]提出了基于 XFA的正則表達(dá)式匹配算法，壓縮了DFA的狀態(tài)。在基于TCAM的算法方面，Meiners等人[8]提出了共享遷移邊、融合狀態(tài)遷移表等優(yōu)化算法壓縮了DFA的存儲(chǔ)空間，將DFA實(shí)現(xiàn)在較小的TCAM片上，Peng等人[9]利用NFA和DFA結(jié)構(gòu)上的關(guān)聯(lián)，提出了鏈?zhǔn)紻FA壓縮算法，保證匹配速度的同時(shí)，壓縮了DFA的狀態(tài)空間。在數(shù)據(jù)分組分類領(lǐng)域，Meiners等人[21～23]提出了多種TCAM表項(xiàng)壓縮算法，降低TCAM的存儲(chǔ)空間開銷。

TCAM具有查找速度快、存儲(chǔ)空間小等特性，且能耗與存儲(chǔ)空間成正比，在部署大規(guī)模設(shè)備的網(wǎng)絡(luò)環(huán)境中，如何降低TCAM能耗成為研究熱點(diǎn)。在IP查找和數(shù)據(jù)分組分類領(lǐng)域，研究者提出了多種低能耗的TCAM方案，Zane等人[24]提出了適用于IP查找的 CoolCAM，將路由表拆分成多個(gè)子表，通過將IP地址映射到路由表的一個(gè)子表，縮小查找范圍。Spitznagel等人[25]改進(jìn)了CoolCAM的結(jié)構(gòu)，提出了適用于數(shù)據(jù)分組分類的Extended TCAM，將一個(gè)索引過濾器與多個(gè) TCAM 存儲(chǔ)塊相連，限制TCAM查找過程中激活的TCAM塊數(shù)。Ma等人[10]提出了SmartPC，將源IP地址和目的IP地址組成的地址對作為預(yù)分類器，數(shù)據(jù)分類器中的規(guī)則按照地址對的范圍，啟發(fā)式地存儲(chǔ)在不同的 TCAM 塊中，且每條規(guī)則僅存儲(chǔ)在一個(gè)TCAM塊中。SmartPC僅需激活預(yù)分類器和部分TCAM塊，即可完成規(guī)則匹配。SmartPC在能耗上平均減少了88%，索引開銷小于TCAM存儲(chǔ)空間的4%，是目前所知最優(yōu)的低能耗分組分類算法。

與上述低能耗TCAM方案不同，本文第一次提出基于TCAM的低能耗正則表達(dá)式匹配算法。本文的方法將TCAM分為索引塊和存儲(chǔ)塊，DFA的字母表存儲(chǔ)在TCAM索引塊中，源狀態(tài)存儲(chǔ)在TCAM存儲(chǔ)塊中。匹配查找過程時(shí)，首先在TCAM索引塊中查找當(dāng)前讀入的字符，根據(jù)SRAM中返回的索引范圍，啟動(dòng)對應(yīng)的TCAM存儲(chǔ)塊，完成查找。本文的方法不僅降低TCAM能耗，而且減少DFA所需的存儲(chǔ)空間，同時(shí)提高匹配吞吐量。

3 基于字符索引的正則表達(dá)式匹配算法

3.1 基于TCAM的正則表達(dá)式匹配

對于給定的特征規(guī)則集，在TCAM上實(shí)現(xiàn)正則表達(dá)式匹配的步驟如下：首先，構(gòu)造特征規(guī)則集的DFA；然后，構(gòu)建DFA的TCAM表，即將DFA的每條狀態(tài)遷移邊存儲(chǔ)在一條TCAM表項(xiàng)中。每條表項(xiàng)由TCAM和SRAM兩部分組成：源狀態(tài)和輸入字符存儲(chǔ)在TCAM部分，目的狀態(tài)存儲(chǔ)在與TCAM部分對應(yīng)的SRAM部分。該算法的匹配查找過程如下：首先，將當(dāng)前狀態(tài)和輸入字符組合成一個(gè)關(guān)鍵字，啟動(dòng)TCAM的全部表項(xiàng)查找該關(guān)鍵字，返回與該關(guān)鍵字匹配的第一條表項(xiàng)的地址；然后，根據(jù)匹配表項(xiàng)的地址，獲取SRAM中存儲(chǔ)的目的狀態(tài)；最后，將目的狀態(tài)作為當(dāng)前狀態(tài)，讀入下一個(gè)輸入字符，重復(fù)執(zhí)行相似的 TCAM 查找，直至輸入字符結(jié)束。

圖 1給出了特征規(guī)則集{.*ab.*c}的 DFA和TCAM表，圖1(a)中，初始狀態(tài)為0，匹配狀態(tài)為3，“[^]”表示非字符子集，[^ab]表示除了a和b以外的其他輸入字符。圖1(b)中，TCAM表的表項(xiàng)總數(shù)與DFA的遷移邊條數(shù)相同，源狀態(tài)和目的狀態(tài)對應(yīng)狀態(tài)遷移表中狀態(tài)的二進(jìn)制編碼，輸入字符為三態(tài)編碼，特征規(guī)則集中出現(xiàn)的輸入字符為該字符的二進(jìn)制 ASCII碼，其他字符用“********”表示，“********”可匹配除特征規(guī)則集中字符之外的任意輸入字符。

3.2 TCAM分塊存儲(chǔ)和字符索引

TCAM是分塊存儲(chǔ)的，每個(gè)TCAM塊中包含了固定數(shù)目的TCAM表項(xiàng)。TCAM提供部分激活的機(jī)制，即查找過程中可以僅啟動(dòng)TCAM中的部分TCAM 塊，而不必啟動(dòng)整個(gè) TCAM。利用 TCAM部分激活機(jī)制的前提是：必須保證在激活的少數(shù)TCAM塊中進(jìn)行準(zhǔn)確無誤的查找。本文通過字符索引達(dá)到這一目的。

圖1 特征規(guī)則集{.*ab.*c}的DFA和TCAM表

算法1給出了TCAM分塊存儲(chǔ)和構(gòu)建字符索引的偽代碼。其中，TransitionTable表示特征規(guī)則集的狀態(tài)遷移表，TCAMTable表示特征規(guī)則集對應(yīng)的TCAM表，StorBlock表示存儲(chǔ)塊，IndexBlock表示索引塊，blockSize表示每個(gè) TCAM 塊的大小。第1)～3)行代碼是由狀態(tài)遷移表構(gòu)建TCAM表的步驟，即將狀態(tài)遷移表的每條狀態(tài)遷移邊保存在 TCAM表中，每條遷移邊由三元組成：源狀態(tài)srcID、輸入字符input和目的狀態(tài)destID。第4)～10)行代碼為構(gòu)建存儲(chǔ)塊的步驟，首先，將TCAM表中的表項(xiàng)按照輸入字符升序排列，計(jì)算輸入字符相同的TCAM表項(xiàng)數(shù)，賦值給變量minStorEntryNum，根據(jù)TCAM塊的大小，計(jì)算每個(gè)輸入字符所需的存儲(chǔ)塊數(shù)，賦值給變量storBlockNum；然后，將srcID和destID組合為存儲(chǔ)塊表項(xiàng)，按照TCAM塊的大小構(gòu)建存儲(chǔ)塊。由于storBlockNum存儲(chǔ)塊中包含的表項(xiàng)總數(shù)大于或等于minStorEntryNum，故在最后一個(gè)存儲(chǔ)塊中可能存在未使用的TCAM表項(xiàng)，本文采用無關(guān)位（“*”）填滿這些表項(xiàng)，保證TCAM中沒有空白的表項(xiàng)。第11)～15)行代碼表示構(gòu)建索引塊的步驟，首先，將storBlockNum個(gè)存儲(chǔ)塊的編號(hào)storBlockID存儲(chǔ)在每個(gè)輸入字符input的索引范圍indexRange中；然后，按照TCAM塊的大小構(gòu)建索引塊。

算法1 BlockOrganized(TransitionTable)

1) for eachtransitioninTransitionTabledo

2)TCAMTablePushBack (srcID,input,destID);

3) end for

4) for eachentryinTCAMTabledo

5) Sort(entryinascending order ofinput);

6)minStorEntryNum= Count(entrywith sameinput);

7)storBlockNum=Ceil(minStorEntryNum/block-Size);

8)StorEntryPushBack(srcID,destID);

9) end for

10)StorBlock= Partition(StorEntrysrcID,block-Size);

11) for eachinputinalphabetTabledo

12)indexRangeInsert(storBlockIDaccording tostorBlockNum);

13)IndexEntryPushBack(input,indexRange);

14) end for

15)IndexBlock= Partition (IndexEntryinput,blockSize)

圖2給出了圖1應(yīng)用本文算法后的結(jié)構(gòu)示意，其中， TCAM塊的大小為4，TCAM索引塊保存TCAM 存儲(chǔ)塊編號(hào)的二進(jìn)制編碼，用于指示每個(gè)字符對應(yīng)的存儲(chǔ)塊范圍；TCAM 存儲(chǔ)塊保存源狀態(tài)的二進(jìn)制編碼，對應(yīng)的SRAM部分保存目的狀態(tài)的二進(jìn)制編碼。

圖2 特征規(guī)則集{.*ab.*c}的分塊存儲(chǔ)和字符索引

基于字符索引的正則表達(dá)式匹配算法的查找過程如下：首先，在TCAM索引塊中查找當(dāng)前的輸入字符，返回SRAM中的存儲(chǔ)塊編號(hào)；然后，根據(jù)存儲(chǔ)塊編號(hào)啟動(dòng)對應(yīng)的TCAM存儲(chǔ)塊，匹配當(dāng)前狀態(tài)，在SRAM中獲取遷移的目的狀態(tài)；最后，將目的狀態(tài)作為當(dāng)前狀態(tài)，讀入下一個(gè)輸入字符，重復(fù)執(zhí)行相似的TCAM查找，直至輸入字符結(jié)束。

比較圖 2和圖 1可知，本文的算法將基于TCAM的正則表達(dá)式匹配分為2個(gè)階段：第1個(gè)階段查找TCAM索引塊，第2個(gè)階段查找TCAM存儲(chǔ)塊。本文的算法在能耗、存儲(chǔ)空間、吞吐量等重要指標(biāo)上的變化將在下一節(jié)匯總詳細(xì)討論。

4 實(shí)驗(yàn)評估

在正則表達(dá)式處理軟件[26]的基礎(chǔ)上，本文采用C/C++設(shè)計(jì)實(shí)現(xiàn)了DFA和CIDFA，并運(yùn)行在CPU為Intel Xeon X5506、內(nèi)存為16 GB的計(jì)算機(jī)上。在軟件模擬實(shí)驗(yàn)中，本文采用 TCAM 仿真工具[27]模擬DFA和CIDFA的TCAM能耗、存儲(chǔ)空間開銷和吞吐量等性能指標(biāo)。

4.1 實(shí)驗(yàn)方法

本文處理的特征規(guī)則集來自于Snort和Bro特征庫，其中，R1～R9取自Snort特征庫， R10取自Bro特征庫。特征規(guī)則集的參數(shù)如表1所示，其中，通配符表達(dá)式的主要形式為{.*{子表達(dá)式}.*{子表達(dá)式}}，“.*”表示匹配任意數(shù)目的輸入字符。計(jì)數(shù)器表達(dá)式的主要形式為{[c1…cn]{n}}，“[c1…cn]”表示匹配輸入字符為“c1”至“cn”中的任意一個(gè)，“{n}”表示重復(fù)出現(xiàn)n次。由特征規(guī)則集生成DFA時(shí)，通配符表達(dá)式容易引起DFA狀態(tài)空間急劇增大[20]，導(dǎo)致存儲(chǔ)自動(dòng)機(jī)所需的TCAM空間開銷增加，能耗也隨之增大。

表1 特征規(guī)則集的參數(shù)統(tǒng)計(jì)

本文采用的特征規(guī)則集中，通配符表達(dá)式條數(shù)占規(guī)則總數(shù)的1.3%～42.3%，DFA狀態(tài)的規(guī)模為5 000～100 000個(gè)，存儲(chǔ)狀態(tài)遷移表的TCAM包含400 000～8 000 000條表項(xiàng)，能夠模擬不同規(guī)模的DFA在本文算法下性能的改變。

TCAM存儲(chǔ)空間的大小為TCAM寬度與表項(xiàng)數(shù)的乘積，其中，表項(xiàng)數(shù)由 TCAM 塊的大小與TCAM塊數(shù)的乘積決定。DFA占用的TCAM寬度為源狀態(tài)和輸入字符占用的比特?cái)?shù)之和。本文采用的特征規(guī)則集的字母表為ASCII碼，輸入字符占用的比特?cái)?shù)為8 bit，對于狀態(tài)數(shù)為S的DFA，源狀態(tài)占用的比特?cái)?shù)為，故 DFA占用的 TCAM 寬度為(W+8)bit，其 TCAM 存儲(chǔ)空間開銷為W=[lbS]。對于CIDFA，索引塊的TCAM寬度為輸入字符的比特?cái)?shù)，即8 bit，存儲(chǔ)塊的TCAM寬度為源狀態(tài)占用的比特?cái)?shù)，即Wbit，CIDFA的TCAM存儲(chǔ)空間開銷S2=8RY1+WRY2。

本文以吞吐量衡量算法的匹配速率。吞吐量為每次讀入字符的比特?cái)?shù)與TCAM查找時(shí)延之商，對于單步長正則表達(dá)式匹配算法，每次讀入一個(gè)ASCII字符，為 8 bit。假定上述X、Y1和Y2個(gè) TCAM塊的查找時(shí)延分別為Dx、Dy1和Dy2，DFA的吞吐量為8/Dx，CIDFA的吞吐量為8/(Dy1+Dy2)。

4.2 能耗

圖3給出了10個(gè)特征規(guī)則集在TCAM能耗上減少的比例。不同 TCAM 塊大小下，CIDFA在TCAM能耗上減少的比例為78.8%～98.5%，平均減少比例為92.7%。當(dāng)TCAM塊大小為32時(shí)，CIDFA在TCAM能耗上減少的比例最小，為8.8%～84.8%，平均減少比例為80.3%。隨著TCAM塊大小的增加，CIDFA在TCAM能耗上減少的比例不斷提高，當(dāng)TCAM塊大小為1 024時(shí)，CIDFA在TCAM能耗上減少的比例達(dá)到最大，為98.0%～98.5%，平均減少比例為98.2%。

圖3 能耗減少比例

圖4給出了當(dāng)TCAM塊大小為64、256和1 024時(shí)，DFA與 CIDFA的 TCAM能耗比較。不同TCAM 塊大小下，同一特征規(guī)則集對應(yīng)的 DFA的TCAM能耗基本一致；隨著TCAM塊大小的增加，同一特征規(guī)則集對應(yīng)的CIDFA的TCAM能耗不斷減少。

4.3 存儲(chǔ)空間開銷和吞吐量

本文采用 4.1節(jié)中介紹的方法計(jì)算 DFA和CIDFA的TCAM存儲(chǔ)空間開銷和吞吐量。

在存儲(chǔ)空間方面，DFA的TCAM片上保存狀態(tài)遷移邊的源狀態(tài)和輸入字符。CIDFA額外開銷了一部分TCAM空間作為索引塊，但是，TCAM片上僅保存狀態(tài)遷移邊的源狀態(tài)。

表2給出了DFA和CIDFA的TCAM存儲(chǔ)空間開銷比較。與DFA相比，CIDFA在TCAM存儲(chǔ)空間開銷上平均減少了 32.0%。對于不同大小的TCAM塊，同一特征規(guī)則集對應(yīng)的DFA和CIDFA的TCAM存儲(chǔ)空間開銷分別相同。

圖4 不同TCAM塊大小下，DFA與CIDFA的TCAM能耗比較

吞吐量決定了算法的匹配速率，由于 DFA和CIDFA每次匹配操作處理的比特?cái)?shù)相同，故算法的吞吐量由匹配時(shí)的查找時(shí)延決定。DFA的查找時(shí)延為啟動(dòng)全部TCAM塊完成查找操作的時(shí)間，CIDFA的查找時(shí)延為啟動(dòng)TCAM索引塊和TCAM存儲(chǔ)塊完成查找的時(shí)間之和。

表2 DFA和CIDFA的TCAM存儲(chǔ)空間開銷比較

表3給出了DFA和CIDFA的吞吐量比較。與DFA相比，CIDFA在吞吐量上平均提高了57.9%。對于不同大小的TCAM塊，同一特征規(guī)則集對應(yīng)的DFA吞吐量相同；隨著 TCAM 塊大小的增加，同一特征規(guī)則集對應(yīng)的CIDFA吞吐量不斷下降。當(dāng)TCAM塊大小為32，CIDFA的吞吐量達(dá)到最大，比DFA提高50.3%～99.5%；當(dāng)TCAM塊大小為1 024時(shí)，CIDFA的吞吐量最低，比DFA提高36.6%～ 70.9%。

表3 DFA和CIDFA的吞吐量比較

5 結(jié)束語

本文提出了一種基于字符索引的正則表達(dá)式匹配算法，該算法將TCAM分為索引塊和存儲(chǔ)塊，其中，索引塊中保存DFA的字母表，存儲(chǔ)塊中保存DFA的源狀態(tài)。匹配時(shí)，首先在索引塊中查找當(dāng)前讀入的字符，然后，僅啟動(dòng)與讀入字符對應(yīng)的部分存儲(chǔ)塊，即可完成查找操作。該算法能夠避免啟動(dòng)全部的存儲(chǔ)塊，從而達(dá)到降低能耗的目的。

針對實(shí)際特征規(guī)則集的實(shí)驗(yàn)表明：與 DFA相比，CIDFA在能耗上平均減少了92.7%，在存儲(chǔ)空間平均開銷上平均減少了32.0%，在吞吐量上平均提高了57.9%。因此，CIDFA是一種低能耗的高效TCAM 方案，不僅確保查找速率，而且顯著降低TCAM能耗和存儲(chǔ)空間。

本文的算法可應(yīng)用于數(shù)據(jù)中心網(wǎng)絡(luò)中大規(guī)模流量識(shí)別技術(shù)，有助于減少數(shù)據(jù)中心網(wǎng)絡(luò)中成千上萬臺(tái)交換機(jī)的能耗，下一步的研究方向是實(shí)現(xiàn)基于TCAM的多步長正則表達(dá)式匹配算法。

[1] PAXSON V, ASANOVIC K, DHARMAPURIKAR S,et al.Rethinking hardware support for network analysis and intrusion prevention[A].Proceeding of USENIX Workshop on Hot Topics in Security[C]. Vancouver, Canada, 2006.

[2] SOMMER R, PAXSON V. Enhancing byteleve network intrusion detection signatures with context[A]. Proceeding of ACM Conference on Computer and Communications security[C]. Washington, DC, USA,2003, 262- 271.

[3] Snort::rules[EB/OL]. http://www.snort.org/start/rules, 2013-12-01.

[4] The bro network security monitor[EB/OL]. http:// bro-ids.org, 2013.

[5] HP TippingPoint S1200N IPS A7500 module[EB/OL]. http://h17007.www1.hp.com/us/en/products/network-security/HP_TippingPoint_S1200N_IPS_A7500_Module/index.aspx?jumpid=reg_r1002_usen,2013-12-01.

[6] Intrusion prevention system(IPS)-Cisco systems[EB/OL]. http://www.cisco.com/en/US/products/ps5729/Products_Sub_Category_Home.html,2013-12-05.

[7] YU F, KATZ R, LAKSHMAN T V. Gigabit rate packet patternmatching using TCAM[A]. Proceeding of IEEE International Conference on Network Protocols[C]. Berlin, Germany, 2004.

[8] MEINERS C R, PATEL J, NORIGE E,et al. Fast regular expression matching using small TCAMs for network intrusion detection and prevention systems[A]. Proceeding of the 19th USENIX Security Symposium[C]. Washington, DC, USA, 2010, 8.

[9] PENG K, TANG S, CHEN M,et al. Chain-based DFA deflation for fast and scalable regular expression matching using TCAM[A]. Proceeding of ACM/IEEE Symposium on Architectures for Networking and Communications Systems[C]. Brooklyn, NY, USA, 2011.

[10] MA Y, BANERJEE S. A smart pre-classifier to reduce power consumption of TCAMS for multi-dimensional packet classification[A].Proceeding of ACM Conference of the Special Interest Group on Data Communication[C]. Helsinki, Finland, 2012.

[11] SIDHU R, PRASANNA V K. Fast regular expression matching using FPGA[A]. Proceeding of IEEE International Symposium on Field-Programmable Custom Computing Machines[C]. Rohnert Park,CA, USA, 2001.

[12] CLARK C R, SCHIMMEL D E. Scalable pattern matching on high-speed networks[A]. Proceeding of IEEE International Symposium on Field-Programmable Custom Computing Machines[C]. Napa Valley, CA, USA, 2004.

[13] SOURDIS I, PNEVMATIKATOS D. Pre-decoded CAMs for efficient and high-speed NIDS pattern matching[A]. Proceeding of IEEE International Symposium on Field-Programmable Custom Computing Machines[C]. Napa Valley, CA, USA, 2004.

[14] MOSCOLA J, LOCKWOOD J, LOUI R P,et al. Implementation of a content-scanning module for an internet firewall[A]. Proceeding of IEEE International Symposium on Field-Programmable Custom Computing Machines[C]. Napa Valley, CA, USA, 2003.

[15] KUMAR S, DHARMAPURIKAR S, YU F,et al. Algorithms to accelerate multiple regular expressions matching for deep packet inspection[A]. Proceeding of ACM Conference of the Special Interest Group on Data Communication[C]. Pisa, Italy, 2006.

[16] KUMAR S, TURNER J, WILLIAMS J. Advanced algorithms for fast and scalable deep packet inspection[A]. Proceeding of ACM/IEEE Symposium on Architectures for Networking and Communications Systems[C]. San Jose, CA, USA, 2006.

[17] BECCHI M, CADAMI S. Memory-efficient regular expression search using stae merging[A]. Proceeding of IEEE International Conference on Computer Communications[C]. Anchorage, Alaska, USA, 2007.

[18] BECCHI M, CROWLEY P. An improved algorithm to accelerate regular expression evaluation[A]. Proceeding of ACM/IEEE Symposium on Architectures for Networking and Communications Systems[C]. San Jose, CA, USA, 2008.

[19] SMITH R, ESTAN C, JHA S. XFA: faster signature matching with extended automata[A]. Proceeding of IEEE Symposium on Security and Privacy[C]. Oakland, CA, USA, 2008.

[20] SMITH R, ESTAN C, JHA S,et al. Deflating the big bang: fast and scalable deep packet inspection with extended finite automata[A].Proceeding of ACM Conference of the Special Interest Group on Data Communication[C]. Seattle, WA, USA, 2008.

[21] MEINERS C R, LIU A X, TORNG E. TCAM Razor: a systematic approach towards minimizing packet classifiers in TCAMs[A]. Proceeding of IEEE International Conference on Network Protocols[C].Beijing, China, 2007.

[22] LIU A X, MEINERS C R, ZHOU Y. All-match based complete redundancy removal for packet classifiers in TCAMs[A]. Proceeding of IEEE International Conference on Computer Communications[C].Phoenix, AZ, USA, 2008.

[23] MEINERS C R, LIU A X, TORNG E. Bit weaving: a non-prefix approach to compressing packet classifiers in TCAMs[A]. Proceeding of IEEE International Conference on Network Protocols[C]. Princeton,NJ, USA, 2009.

[24] ZANE F, NARLIKAR G, BASU A. CoolCAMs: power-efficient TCAMs for forwarding engines[A]. Proceeding of IEEE International Conference on Computer Communications[C]. San Francisco,USA, 2003.

[25] SPITZNAGEL E, TAYLOR D, TURNER J. Packet classification using extended TCAMs[A]. Proceeding of IEEE International Conference on Network Protocols[C]. Atlanta, Georgia, USA, 2003.

[26] Regular expression processor[EB/OL].http://regex.wustl.edu/index.php/Main_Page, 2013-12-01.

[27] AGRAWAL B, SHERWOOD T. Modeling TCAM power for next generation network devices[A]. Proceeding of IEEE International Symposium on Performance Analysis of Systems and Software[C].Austin, TX, USA, 2006.