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

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

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

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

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