一種正則表達式匹配中降低TCAM能耗的壓縮方法.pdf

1、深度包檢測是網(wǎng)絡入侵檢測及防御系統(tǒng)的核心組件之一。它通過同時檢測網(wǎng)絡數(shù)據(jù)包的包頭和有效載荷兩部分，以實時偵測惡意攻擊或識別出某些特殊的網(wǎng)絡應用等。正則表達式具有非常豐富而靈活的表達能力，因此被廣泛地應用在深度包檢測中。目前，正則表達式匹配主要采用確定性有限狀態(tài)自動機（DFA）來實現(xiàn)。在DFA中，一個源狀態(tài)接受一個輸入字符后將會跳轉(zhuǎn)到一個唯一的目的狀態(tài)。DFA具有狀態(tài)爆炸問題，即 DFA的狀態(tài)數(shù)隨著正則表達式的規(guī)模變大而指數(shù)增加。

2、　　三態(tài)內(nèi)容可尋址存儲器（TCAM）是一種非常流行的用于實現(xiàn)正則表達式匹配的硬件設備，以提高其匹配速度。隨著網(wǎng)絡應用的不斷發(fā)展，正則表達式變得越來越復雜而龐大。一個復雜而龐大的正則表達式規(guī)則集將會消耗巨大的TCAM存儲空間，而TCAM的能耗跟其空間消耗成正比，因此巨大的TCAM空間消耗反過來將會導致TCAM的高能耗問題。
　　本文提出一種TCAM能耗高效（PEDFA）的壓縮方法。PEDFA有兩種不同的表：字符索引表和遷移表。字符索

3、引表的大小與輸入字符的編碼方式相關(guān)，而遷移表的大小與正則表達式的復雜程度和規(guī)模相關(guān)。因此，遷移表被壓縮得越多，TCAM的空間消耗減少得越多，反過來能夠極大地降低TCAM的能耗。PEDFA充分地利用了TCAM的兩個特性：TCAM的‘*’通配符和第一條表項優(yōu)先匹配。PEDFA包含三個部分：預處理、可恢復性壓縮和可行性壓縮。預處理通過給 DFA狀態(tài)賦予合理的標識號，以便取得更好的可恢復性壓縮的壓縮比例。可恢復性壓縮利用TCAM的通配符將多條具