一種改進的多維高速報文分類算法

摘 要：RFC算法是目前具有代表性的一種報文分類算法，具有匹配速度快、占用內存少、支持范圍匹配等優點，但是它不能處理變長字符串域。結合多模式匹配算法的思想，對RFC算法進行了有益擴充，使新算法能夠根據變長字符串域進行分類。實驗結果表明，改進的算法在有效擴展KFC算法的適用范圍的基礎上，仍具有良好的性能。

關鍵詞：報文分類； RFC算法； AC自動機； 模式匹配

中圖法分類號：TP301.6文獻標識碼：A

文章編號：1001—3695(2007)02—0027—03

1 引言

報文分類通常是指根據數據報文頭的若干字段，將數據流劃分為不同的類別，以便對每一類數據流作不同的處理。報文分類在許多領域都有重要應用，如消息處理、內容過濾、支持QoS的路由器、防火墻、入侵檢測和Web信息檢索等。

在某些應用中，僅需要根據報文中指定的頭域字段（如源IP地址和目的IP地址）對數據流分類，解決這類問題的一些算法參見文獻[1—5]。隨著網絡應用的豐富，需要根據更多的頭域字段對數據流進行分類。一般情況下，根據包頭的K個（K＞2）字段對數據流分類很困難。研究表明，解決K域包分類問題的算法，在空間復雜度為O(N)的情況下，需要的時間復雜度是O(log K-1N)，或在時間復雜度為O(log N)的情況下，空間復雜度是O(NK)，這里N是分類規則的數目[8]。已經有一些解決K域報文分類問題的算法[5—8]，P.Gupta和N.McKeown提出的RFC(Recursive Flow Classification，遞歸流分類)算法[6]就是其中之一，它可以在O(1)時間復雜度內運行，并且空間需求對一般應用而言均可接受。E.W.Spitznagel改進了RFC算法[8]，進一步降低了它的空間開銷。

但在某些應用領域中，需要根據應用協議的一些字段對數據報文分類，這些字段往往是字符串類型，并且長度變化范圍較大。一個典型的應用是郵件過濾系統，它可以根據IP地址、端口號、郵件的發件人和/或收件人地址等條件對郵件進行分類處理。RFC算法無法適用于分類規則中含有變長字符串的情況。本文結合多模式匹配的思想，對RFC算法進行擴充，使新算法能夠對含有變長字符串域的報文進行分類。

2 報文分類問題

實現報文分類的實體稱為分類器，其核心是一張分類規則表。規則表由一系列規則R構成，每條規則包含分類條件和類標志（簡稱ClassID）兩部分，如圖1所示。

報文分類問題關注的是分類條件，以及如何根據分類條件快速地確定與數據流對應的ClassID。分類條件包含K個域，分別對應數據流的不同部分，如網絡層的源IP地址和目的IP地址、傳輸層的源端口和目的端口，以及應用層協議的某些字段等。

ClassID的含義視具體應用環境而定，通常它與一種或多種處理方式相關聯，如路由選擇、按優先級轉發或流量計費等，本文不詳細討論。

報文分類的典型應用包括訪問控制、垃圾郵件過濾、Web信息檢索等。表1給出了訪問控制列表的一個示例。

實現報文分類的一個簡單方法是蠻力搜索，即對逐條規則進行檢查，直到發現匹配的規則或已經檢查完所有的規則為止。這種方法簡單，而且空間需求小，但是當規則數量較多時，時間性能很差。人們已經提出了多個更好的分類算法，RFC算法就是其中之一，它具有非常快的匹配速度，空間需求也相對合理。

3 RFC算法

RFC算法利用實際應用中規則的結構特性和冗余度，將整個頭域分為若干個段，通過計算分段中等價類和遞歸操作，實現空間的分步壓縮映射。其基本思想是將報文分類看成從包頭的S bit到T bit（T=log N，且T<

實現Sbit到Tbit的映射，一個理想的方法是在內存中建立一個索引數組，分類條件由Sbit構成，共有2^S種不同的組合，預先計算出每種組合的ClassID，放在索引數組的對應單元中。這樣對每一個數據包P，一次內存訪問就可以找到相應的ClassID。該方法簡單、快速，但是需要相當大的存儲器空間，因此不現實。

RFC算法將映射由一步化作多步，每步進行類似的操作，完成一次空間壓縮，將一個較大的等價類集合（CES）映射成較小的等價類集合（CES），如圖2所示。這種方法雖然要幾步才能得到最終結果，但所需內存大大降低，使Sbit信息到Tbit類標志的映射實際可行。RFC算法由建立(預處理)和搜索兩個過程組成，在建立過程中，RFC算法分三個階段完成2^S域到2^T域的映射，并生成中間索引表，用于搜索規則。建立過程還生成預處理向量表，預處理向量表用以計算生成中間索引表，因此是計算過程中的臨時數據。在搜索過程中，分類器提取數據包中的頭域信息，根據中間索引表，分四步搜索到相應的規則，完成數據包的分類和處理規則的查找。

RFC算法的查找過程是把包頭的相應字段劃分為同樣的塊，每一塊作為并行查找的索引，后續各階段查找的索引值由前幾個階段的查找結果合并而成，最后一個階段的查找結果就是與輸入對應的ClassID。

算法的查找速度與階段數P有關，P值越大，查找速度越慢。但是查找速度與規則條數N無關，時間復雜度是O(1)。因此，即便用軟件實現，該算法的分類速度也可達到每秒百萬包次。算法的空間需求與階段數P和縮減樹的結構都有關系。一般而言，P值越小，空間開銷越大。P值一定的情況下，縮減樹結構不同，算法的空間需求也可能有較大差異。參考文獻[6]給出了優化縮減樹結構的一些啟發式原則，還針對分類規則數量特別巨大的情況，提出了采用合并鄰接組(Adjacency Groups)的方法來進一步降低空間開銷。

4 改進的算法

表1所示的分類規則表，源IP、目的IP、源端口和目的端口域可以按照RFC算法處理，為它們分別建立索引子表。但是，對于兩個字符串類型的域（發件人和收件人），由于它們的長度變化范圍較大，試圖為它們建立索引子表，將郵箱賬號映射為eqID是不現實的。因此，這種情況下不能直接使用RFC算法。

考慮變長字符串域中所有可能出現的字符串，仍然可以將它們分為多個互不相交的子集，每一個子集對應一個eqID值。在RFC算法中，使用CBM數組來記錄每一個eqID被哪些分類規則所包含，為后續階段的多字段合并服務。本文也采用CBM數組。以郵件報文中的發件人這個域為例，可以劃分為四個子集{不包含在其他子集中的所有字符串}，{abcd}，{aef，xyzk}，{aefgh}，用兩個比特對它們進行編碼，從00b—11b，相應的CBM數組如圖3所示。

字符串“aefgh”構成的子集，eqID為11b，對應的CBM值是10100，表示第三條和第五條分類規則的字符串域l包含“aefgh”。

剩下的問題是，對輸入的任意字符串，如何快速地找到它對應的eqID。

受Aho-Corasick多關鍵字匹配算法[9]思想的啟發，在預處理階段，分別為每一個變長字符串類型的域構造一個匹配自動機DFA M，查找時，借助DFA M將輸入的字符串映射成對應的eqID值。下面給出匹配自動機DFA M的形式定義。

至此，可以為任意的字符串域構造匹配自動機DFA M和CBM數組，所需要的輸入數據是該域中所有字符串及其所在規則對應的ClassID。算法如下：

對其他類型的域以及字符串域的后續各階段的預處理，與RFC算法相同。算法在實現查找操作時，對于字符串域的第一階段，輸入的是任意字符串，輸出的是該字符串對應的eqID值。這個過程需要借助上面構造的匹配自動機DAF M，算法如下：

需要說明的是，這里的查找與Aho-Corasick多關鍵字匹配算法的查找不同：在多關鍵字匹配算法中，只要輸入串String的任意一個子串與關鍵字集合的任意一個關鍵字相同，則匹配成功；而這里的查找算法輸入串String必須與該域中的某個字符串完全相同，方為匹配成功。以圖4的自動機DFA M1為例，當輸入“aef”串時，算法2的輸出為2；當輸入“aefg”串時，盡管它包含“aef”串，但是算法2的輸出不為2，而是0，因為“aefg”串使DFA M1最終停留在狀態8，它不是接收狀態， f(8)=0。

除字符串域的第一階段查找采用算法2實現以外，改進算法的查找過程與RFC算法相同，不再詳述。

5 改進算法的性能

5.1 時間復雜度分析

算法1只在預處理階段被每一個字符串域執行一次。其中，第一個for循環內的語句體共循環m次（m是該域中字符串的總個數）；第二個for循環內的語句體被當前字符串中的每一個字符執行一次，因此循環的次數是當前字符串含有的字符個數。綜上所述，該算法的時間復雜度是O(M)，這里M是該字符串域包含的字符的總個數。

算法2要在運行時被頻繁調用，每執行一次分類操作，調用一次或多次（如果有多個字符串域）。其中，for循環內的語句體最多執行L次(L是輸入串String包含的字符個數)。實際應用中，L值一般不超過某個較小的常數，該算法的時間復雜度是O(1)。查找過程的其他步驟與RFC算法相同，因此，改進后的算法，總的查詢時間復雜度仍然是O(1)。

5.2 空間復雜度分析

算法的空間需求，除了為字符串集合構造匹配自動機以外，與RFC算法相同。因此這里只討論匹配自動機的空間需求。匹配自動機的空間開銷與其狀態節點數成正比，而狀態節點數與該域中的字符總個數M成正比，因此匹配自動機的空間復雜度是O(M)。

從圖4可知，字符總數M一定時，如果字符串的前綴重復越多，匹配自動機的狀態節點數就越少。因此可以根據這一特點，降低空間需求。例如垃圾郵件過濾系統中，由于許多郵件地址具有相同的后綴（如.com，.net）構造匹配自動機時，從右向左讀入郵件地址中的字符，有利于減少空間開銷。

5.3 算法的實驗

對表1所示的分類規則，在Linux下用標準C編程，實現了改進的算法。在Dell PowerEdge 2600 Intel Xeon服務器（2.4GHz雙CPU，1GB內存）上，使用隨機生成的數據（其中域中字符串長度為15—35）。測試結果如圖5所示。

在測試所用的硬件平臺上，改進后的算法每秒能夠完成約200萬次查找。這對于面向應用協議的報文分類（非包分類）而言，應該是足夠快的。

6 結束語

本文結合Aho-Corasick多關鍵字匹配算法的基本思想，擴充了RFC算法，使新算法能夠對含有變長字符串域的報文進行分類。實驗結果表明，新算法具有很快的匹配速度，而且易于實現，是一種值得應用的報文分類算法。

當然，新算法仍有局限性，特別是當字符串中包含的字符數較大時，構造匹配自動機需要較大的存儲空間。如何進一步降低空間開銷，將是下一步研究工作的重點。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。