基于多層迭代的遞歸數據流匹配改進算法

蔡艷婧 孔蘇鵬 程 實 王則林*

1(江蘇商貿職業學院電子信息學院 江蘇 南通 226001) 2(南通大學信息科學技術學院 江蘇 南通 226019)

0 引 言

包匹配算法是對通過路由器的數據包進行識別，從而可以為互聯網提供訪問控制，提高網絡服務質量以及針對不同客戶要求提供差異式服務。包匹配算法本質上是一個多維范圍匹配問題,根據預定義規則對進入網絡或主機數據包的IP頭部信息進行比較。IP頭字段信息一般包括源IP地址、目的地IP地址、源端口、目的地端口和上層協議類型。每個規則還有一個行為字段，以便對符合匹配的數據包進行相應處理。一般每條規則還有一優先級。對于傳入的數據包，如有多條規則與它匹配，數據包則匹配最高優先級的規則。包匹配的性能由內存消耗和內存訪問的次數來衡量。

目前，不同的包匹配算法在算法的空間和時間性能之間采用不同的權衡策略。基于哈希表的算法有優越的空間性能，但其時間性能卻無法得到保證[1-2]。基于決策樹的算法使用決策樹把規則庫劃分為多個線性搜索組[3-4]，此算法的速度和存儲性能會根據規則數據庫的特點有所不同。EffiCuts使用多個決策樹控制內存消耗，但也降低了算法的時間性能[5]。三元內容可尋址存儲器(TCAM)廣泛用于查找規則。然而，TCAM不能直接處理范圍類型的規則匹配，因此需要把范圍的規則轉換成前綴的規則類型，降低空間效率[6]。RFC[6]是著名的高性能算法之一，其高性能保障是有條件的，通常適用于維數低、規則庫規模不大的情形，否則會引起維度災難，產生規模爆炸問題。

本文基于RFC提出一個新的包匹配算法，將規則庫分割成幾個規則子集，每個子集的規則存儲在一個RFC數據結構中，子集的規則數量被限制在一個閾值范圍內。本文提出的改進算法可以避免產生巨大空間的外積表，因此以遞歸的方式執行RFC，確定該訪問何子集，何子集規則被匹配。另外本文還對RFC數據機構進行一些改進以提高存儲和速度性能。數值實驗表明，本文算法顯著提高了RFC用于大規模多維規則庫的可行性，同時保持了RFC算法優越的時間性能。

1 算法改進基本思想

本文改進算法的目標是提高RFC的空間效率，采用多個RFC實例。首先，本文把規則庫分為幾個子集，每個子集的規則存儲在一個獨立RFC數據結構中。每個子集由一個索引規則來進行描述，每個索引規則指向相應的RFC的數據結構。因此，如果將規則庫分為k個子集，從而k個索引規則被創建。這些索引規則被存儲在另一個RFC索引數據結構中，稱為RFC索引，以它來確認進入網絡或主機的數據包該進入哪個子集，進一步通過相應的RFC數據結構來確定具體的匹配規則。

下面舉例說明對規則庫分割的必要性。表1是由兩個頭字段組成的規則庫，在源地址(SA)領域，有五個組合:0*(R3、R6)，010*(R3、R4 R6)，1*(R2,R6)，1100(R1、R2、R6)和1110(R2、R5 R6)括號前的標識符是括號里規則的前綴匹配。在目的地址(DA)領域，有六個組合:*(R5)，110*(R5,R6)，1011(R1，R5)，0*(R4，R5)，010*(R2、R4、R5)和00*(R3，R5)。因此，兩個頭字段執行外積后有30個實體。執行外積得到的實體數量可以通過分割規則庫來減少。圖1通過幾何的方法來說明這些規則分割的思想。這些規則被分為三個子集(R1，R5，R6)、(R2，R5)和(R3，R4)。每一個子集的外積實體的數量是9、4和4，從而外積實體總數減少到17。與原來相比，分割規則庫可以有效降低外積表實體數目，從而提高存儲效率。

表1 簡單規則庫

圖1 對表1規則的幾何描述

一個有效的分割算法應該滿足以下三個要求:(1) 那些在幾何描述上彼此接近的規則應該在分類上屬于同一子集，以確保搜索過程能訪問到所有子集；(2) 每個規則應該駐留在確切某個子集里，一個不太有效的分割算法可能導致一個規則處于不同子集；(3) 規則子集的數量應該可調節以便適應不同規則庫。下面研究分析當前已有的分割規則庫算法。

元組空間的思想是基于每個字段中前綴的位數把規則庫分為元組。每個元組對應于一個前綴，檢查所有字段的組合,以及由此產生的元組稱為元組空間[6]。以一個三維元組(5，6，7)為例,屬于這個三維元組的規則第一個字段是5位的前綴，第二個字段是6位前綴以及第三個字段為7位的前綴。因為每個規則只有一個前綴組合,元組空間不會違背分割的第二個要求。但這并不意味著任意前綴組合存在幾何關聯,所以元組空間分割的思想不能滿足分割的第一個要求。由于高成本的前綴擴張也很難調整元組的數量。采用一個類似元組的思想提出了空間利用嵌套層元組,每個字段的長度定義為嵌套的數量水平相應的前綴。盡管這個算法的元組數量顯著低于元組空間元組的數量,但第一個分割的要求仍不滿足。貪婪算法運用外積法減少使用嵌套級別的元組數目,但是不符合分割的第二個要求，嵌套元組也不支持更新，因為插入一個規則時，新的前綴可能改變所有規則的嵌套層數。

決策樹算法使用規則的字段屬性將規則庫分成一個個子集，當用于分割規則庫的屬性是字段值時,決策樹提供的相同子集的規則在幾何描述上相互接近，從而決策樹在執行數據包匹配時只有一個子集被訪問到。通過調整在一個葉節點上的規則數來控制子集的數量。然而,規則決策樹算法也不符合分割的第二個要求。因通配符規范在規則庫的規則描述中很常見,從而對規則庫分割的幾何方法只能減少規則的重復,而不能避免規則重復。一些方法被提出以減少重復規則[8]，一些算法使用多個決策樹來提高規則庫的分割效率[9]，另一些分割算法利用不同的屬性劃分規則集。上述方法在合理的消耗下沒有一個能完全避免規則的重復問題。

與基于元組分割算法相比,使用決策樹對規則庫規則分割的算法只有一個規則重復問題需要克服。本文提出使用一個隨需應變的方法來避免規則的重復問題，步驟如下：

(1) 生成一棵平衡二叉樹，每個內部節點的關聯規則被分為兩個子集。在構造決策樹的過程,刪除任何重復規則，所有從第一個決策樹刪除的規則都被存儲在第二個決策樹。

(2) 基于第一步過程構造第二個決策樹，在第二個決策樹構造過程中的任何重復規則被搬到第三個決策樹，如此迭代。

(3) 生成所有決策樹。決策樹的任一葉節點的規則被插入一個RFC的數據結構，因此，RFC數據結構的數量等于所有決策樹的葉節點總數。

規則劃分的詳細步驟描述如下:

(1) 定義一個閾值去限制存儲在一個RFC數據結構中的規則的數量，所有規則都與第一個決策樹的根節點相關聯。如果規則的數量大于閾值,那么把規則分為兩個子集。為了對規則庫進行分割，選擇一個有效區分這些規則的字段。

(2) 計算規則庫每個字段不同的前綴的數量，選擇前綴數目最多的字段來分割。

(3) 對選定的字段,進一步確定可以將規則平衡劃分成兩個部分的一個點。

(4) 針對選擇的字段，統計小于或等于選擇點的端點規則數量，對每個端點分別統計大于選擇點的起始點的規則數量。和選擇點相比，數字最接近被選中。

(5) 根據選擇的點，可以將規則集劃分為三個子集:規則的范圍低于所選點、規則的范圍高于所選點和范圍在選定的點的未分類的規則。

重復上述步驟，對前兩個規則集做進一步劃分，直到每個子集生成的規則數量小于閾值。將決策樹中所有未分類的規則插入到下一個決策樹的根節點進行進一步的劃分。

用一個例子說明上述過程，表2所示為五個字段的17條規則組成的規則庫。設置閾值為4。在分割的第一次迭代過程中,源地址字段前綴的不同數目最大，因此選擇它把規則分庫分成三個子集,每個子集對應于樹的一個節點。如圖2所示,根節點的左子節點存儲規則的源地址字段低于所選點,根節點的右子結點存儲較大的規則源地址字段，中間的根節點存儲未分類的規則。因為左、右子節點的規則數超過4位,應該進一步分割以便生成更小的子集。決策樹中所有未分類的規則(包括R15、R16、R12和R13)形成第二個決策樹的根節點。由于子集的大小對應于根節點不超過閾值,第二個決策樹只有一個節點。

表2 五個字段的規則庫

在把規則庫分成幾個子集后，子集的規則被存儲在RFC的數據結構中，運用一個索引規則去描述子集空間。每個索引規則的范圍從子集的所有規則的相應字段的最小開始點到最大端點。因此，假如把一個規則庫分成k個子集，也就創建了k個索引規則。表3列出了表2的索引規則和它們相應的在每個字段上的范圍。在為所有的子集創建了索引規則后，運用一個RFC數據結構(索引RFC)去存儲這些索引規則。

表3 關于表2的索引規則

對于每個RFC數據結構，在第一階段，五個過濾字段被分成七塊,包括六個16位數據塊和一個8位的塊。對于每個塊,相應于包頭字段的值，為訪問對應的等價類ID(eqID)構造2w實體的索引數組，其中w表示塊大小。每個eqID與類位圖相關聯去指示和塊等效集相匹配的規則。每個eqID的類位圖是不同的，下一階段中，通過外積eqID使兩到三塊組合成一新塊，新塊的類位圖等于所有合并eqIDs的類位圖的交積。在新的階段中，每一個不同的類位圖表示一組等價的集，然后給每一個等價集分配一個eqID。新eqIDs存儲在一個索引數組中，這個索引數組的大小等于合并eqIDs的乘積。這個過程繼續到所有的塊都被合并。對傳入的數據包,搜索過程在一個RFC數據結構中首先把數據包報頭分成七塊。每個塊的值用來訪問索引數組的eqID。如果有任何后續階段,搜索過程使用eqID組合去生成下一階段的索引。隨著搜索過程遍歷到最后階段，最終誕生一個eqID,和這個新誕生的eqID對應的類位圖被用來訪問最終匹配的規則。

對于一個進入的數據包，這個完整的搜索過程首先遍歷索引RFC數據結構找到匹配的索引規則，然后通過訪問相應的RFC的數據結構繼續搜索匹配索引規則的子集。本文算法框架由六個RFC的數據結構組成,其中，五個關于結果子集，一個關于索引規則。表4展示了原始RFC的外積表實體和本文算法的外積表實體。在這個例子中,本文算法減少了63%原始RFC的外積實體。

表4 原始RFC和本文算法在每個階段的外積表實體

2 算法的進一步改進

本文提出三種技術來進一步改善本文所提算法的時間和內存消耗性能。

1) 合并小的子集。在對規則庫進行分割時，可能會產生小的子集，這些小的子集將導致無效的RFC數據結構，最終造成額外對這些數據結構的內存訪問。為了避免這種情況，本文設計了一個閾值，當某個子集的規則數小于這個閾值時，就將其與別的子集合并。這些合并的子集存儲在一個共同的RFC數據結構中。

2) 合并第一個階段中不同的RFC數據結構。規則庫分割成K個組需要設計K+1個RFC數據結構。每個RFC數據結構都需要單獨遍歷，從而在第一個階段中的索引數組中為了檢索到相應的eqID就需要7×(K+1)內存訪問。可以把不同RFC數據結構但相同塊的索引數組進行合并，達到減少內存訪問的次數。這樣一次內存訪問就可以獲得不同RFC數據結構相同塊的eqIDs。第一階段的RFC數據結構檢索的內存訪問的次數就從7×(K+1)降到7。

3) 減少內存消耗。第一階段每個RFC數據結構存儲eqIDs需要6個16 bit的塊和1個8 bit的塊，每個16 bit的塊的搜索表是216個實體的索引數組，每個8 bit的塊的搜索表是28個實體的索引數組。假如把規則庫分割成K個子集，在第一階段就需要6×216×(K+1)+28×(K+1)實體。為了減少內存消耗，可以在第一階段中設計用二進制搜索數組替換索引數組，對于每個索引數組，存儲在相鄰實體中的eqIDs可以是相同的。將它們合并為一個區間，從第一個實體到最后一個實體的eqID相同。通過這種方式，可以將索引數組2w實體轉換成一個n-間隔數組，它可以采用二進制搜索。該方法可以減少在第一階段的內存消耗。

3 實 驗

本文運用真實的和合成的規則庫去評價本文算法的性能，在實驗中運用三種類型的規則集：訪問空列表(ACL)、防火墻(FW)和IP鏈(IPC)。這些數據集可以從文獻[7]獲取。實驗目的是為了比較本文算法和其他幾種算法的性能。

實驗結果由三部分組成:第一部分描述不同規模的子集在時間和內存消耗之間的平衡；第二部分展示了基于不同子集合并閾值的性能改進；第三部分是一項性能研究，比較本文所提算法與已存算法的性能。

1) 不同規模子集下的性能平衡。第一部分的一個子集的規則數是通過一個因子決定的。定義因子d1，子集的規則大小等于規則總數除以d1。規則集被分割，直到在每個子集的規則數小于閾值。本實驗使用三個因數:4、8、16，在接下來的評價中選擇最佳性能的因子。

圖3顯示了在三種不同類型的規則庫、三個不同大小的子集下，最壞情況下的內存需求和內存訪問的次數。如圖3(a)所示，隨著子集中規則數減少，即子集個數增多，內存需求逐漸劣化。然而,圖3(b)也顯示，隨著子集中規則數增加，子集個數減少，內存訪問增加。這是因為傳入數據包可能匹權衡利弊后，設置因子d1為8，因為此值可以更好地權衡存儲和速度性能。因此子集的大小等于規則的數量除以8。

(a) 內存需求

(b) 訪問次數圖3 三種類型的規則庫在三個因子下內存需求和訪問次數

2) 子集合并的不同閾值。第二部分實驗，設置一個閾值來合并小的子集從而達到提高算法性能。合并閾值也決定使用因子d2,合并閾值等于子集的大小除以d2。子集合并如果它們的規則數小于合并閾值。初始設置三個因子：2、3、4。在接下來的評價中選擇的最佳性能的因子。

圖4給出了在三種不同類型的規則庫、三個子集合并的不同閾值下，在最壞情況下的內存需求和內存訪問的次數。圖4(a)表明在RFC算法中，一個大的合并閾值可能招致更多的內存需求，因為越來越多的子集合并導致更大的外積表。圖4(b)顯示一個小合并閾值可能招致更多的內存訪問，因為RFC的數據結構的數量不能有效減少。因此,傳入數據包在搜索過程中匹配更多的子集可能導致更多的內存訪問。

(a) 內存需求

(b) 訪問次數圖4 三個合并閾值下內存需求和訪問次數

進一步比較本文算法在允許子集合并(設置因子d2為3)和沒有子集合并兩種情況下的性能，如圖5所示。圖5(a)顯示，隨著子集的合并，內存需求略有增加，RFC數據結構存儲更多的規則通常會導致更多的外積實體。圖5(b)表明，子集合并可以減少內存訪問。要在存儲和速度性能之間權衡，本文傾向于速度，因為本文算法相比于RFC算法顯著降低了內存需求。

(a) 內存需求

(b) 訪問次數圖5 三種類型的規則庫，兩種合并閾值下的內存 和速度性能比較

3) 算法性能比較分析。比較本文算法與RFC[6]、HSM[8]、Hypercuts[4]、ISET[9]的性能，結果如圖6-圖8所示。一些結果不能顯示是因為用于構建數據結構程序內存消耗太大，導致無法運行。

(a) 內存需求

(b) 訪問次數圖6 ACL1規則庫中的五種算法的速度性能比較

(a) 內存需求

(b) 訪問次數圖7 FW1規則庫中的五種算法的速度性能比較

(a) 內存需求

(b) 訪問次數圖8 IPC1規則庫中的五種算法的速度性能比較

圖6(a)、圖7(a)和圖8(a)顯示五種算法的內存性能比較。本文算法改善了RFC和HSM存儲性能，因其都使用類似的數據結構。本文算法內存需求比ISET大，然而ISET的速度性能也明顯遜色于本文算法。針對不同規則庫Hypercuts的結果有所不同。雖然在ACL類型中Hypercuts表現良好,但運用于FW和IPC時其性能卻嚴重惡化，而本文算法在這兩種類型的規則庫速度和存儲性能都優于Hypercuts。總之,本文算法是最好的可行性方案。雖然從單一性能角度可能不是最好的方案,但它總是提供一致的吞吐量且避免最壞情況。

4 結 語

RFC是一個性能很好的包匹配算法，但是在生成外積表時要消耗大量內存，因此不適用于大規模的規則庫。為了改善內存性能，本文基于RFC提出一個改進算法把規則庫分割成幾個子集。在同一子集中的規則被存儲在同一RFC數據結構中，每個子集用一個索引規則來進行描述。所有的索引規則被存儲在一個RFC索引中，這些RFC索引指向相應的RFC數據結構。并進一步提出三種技術去改進內存和速度性能。運用三種規則庫去評價該算法的性能，實驗表明，本文提出的算法綜合性能最優。