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

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

0 引 言

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

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

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

1 算法改進基本思想

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

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

表1 簡單規(guī)則庫

圖1 對表1規(guī)則的幾何描述

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

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

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

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

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

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

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

規(guī)則劃分的詳細步驟描述如下:

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

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

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

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

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

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

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

表2 五個字段的規(guī)則庫

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

表3 關于表2的索引規(guī)則

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

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

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

2 算法的進一步改進

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

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

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

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

3 實 驗

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

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

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

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

(a) 內存需求

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

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

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

(a) 內存需求

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

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

(a) 內存需求

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

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

(a) 內存需求

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

(a) 內存需求

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

(a) 內存需求

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

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

4 結 語

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