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

1、深度包檢測(cè)(DeepPacketInspection，DPI)是網(wǎng)絡(luò)入侵檢測(cè)與防御系統(tǒng)(NetworkIntrusionDetection/PreventionSystem，NIDPS)的核心。DPI技術(shù)實(shí)時(shí)監(jiān)測(cè)網(wǎng)絡(luò)流量，檢測(cè)數(shù)據(jù)包的頭部信息和有效載荷。由于具有豐富和靈活的表達(dá)能力，正則表達(dá)式已被廣泛應(yīng)用于DPI技術(shù)中。目前，正則表達(dá)式匹配算法主要使用確定型有限自動(dòng)機(jī)(DeterministicFiniteAutomata，DFA)表示

2、。在給定狀態(tài)和輸入字符的情況下，DFA的狀態(tài)遷移是唯一確定的。
　　基于三態(tài)內(nèi)容可尋址存儲(chǔ)器（TernaryContentAddressableMemory，TCAM）的正則表達(dá)式匹配算法提高了數(shù)據(jù)包的處理速度，成為DPI技術(shù)的一個(gè)重要研究方向。TCAM具有查找速度快、存儲(chǔ)空間小等特性，且能耗與存儲(chǔ)空間成正比。由于DFA的存儲(chǔ)空間開銷比較大，且存儲(chǔ)空間大小隨著DFA步長(zhǎng)數(shù)的增加而指數(shù)倍增，基于TCAM的DFA面臨高能耗的問題，特別

3、是多步長(zhǎng)DFA。
　　本文首先提出了基于字符索引的單步長(zhǎng)DFA算法(Character-Indexedsingle-strideDFA，CIDFA)，將單步長(zhǎng)DFA的字母表從狀態(tài)遷移表中分離，構(gòu)造字符索引，根據(jù)字符索引啟動(dòng)相應(yīng)的TCAM塊，減少查找匹配時(shí)激活的TCAM塊數(shù)，降低TCAM能耗。實(shí)驗(yàn)表明:與單步長(zhǎng)DFA相比，CIDFA在能耗上平均減少了92.7％，在存儲(chǔ)空間平均開銷上平均減少了32.0％，在吞吐量上平均提高了57.9％

4、。
　　針對(duì)多步長(zhǎng)DFA的高能耗問題，本文提出了基于并行字符索引的多步長(zhǎng)DFA算法(ParallelCharacter-Indexedmulti-strideDFA，PCIDFA)，按照多步長(zhǎng)DFA的步長(zhǎng)數(shù)構(gòu)造多個(gè)字符索引，將并行字符索引對(duì)應(yīng)的比特位圖取交集，啟動(dòng)對(duì)應(yīng)的TCAM塊，顯著降低TCAM能耗。實(shí)驗(yàn)表明:與多步長(zhǎng)DFA相比，PCIDFA在能耗上減少了三個(gè)數(shù)量級(jí)以上，在存儲(chǔ)空間開銷上平均減少了57.4％，在吞吐量上平均提高了