基于多層迭代的遞歸數(shù)據(jù)流匹配改進(jìn)算法

蔡艷婧 孔蘇鵬 程 實(shí) 王則林*

1(江蘇商貿(mào)職業(yè)學(xué)院電子信息學(xué)院 江蘇 南通 226001) 2(南通大學(xué)信息科學(xué)技術(shù)學(xué)院 江蘇 南通 226019)

0 引 言

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

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

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

1 算法改進(jìn)基本思想

本文改進(jìn)算法的目標(biāo)是提高RFC的空間效率，采用多個(gè)RFC實(shí)例。首先，本文把規(guī)則庫(kù)分為幾個(gè)子集，每個(gè)子集的規(guī)則存儲(chǔ)在一個(gè)獨(dú)立RFC數(shù)據(jù)結(jié)構(gòu)中。每個(gè)子集由一個(gè)索引規(guī)則來(lái)進(jìn)行描述，每個(gè)索引規(guī)則指向相應(yīng)的RFC的數(shù)據(jù)結(jié)構(gòu)。因此，如果將規(guī)則庫(kù)分為k個(gè)子集，從而k個(gè)索引規(guī)則被創(chuàng)建。這些索引規(guī)則被存儲(chǔ)在另一個(gè)RFC索引數(shù)據(jù)結(jié)構(gòu)中，稱(chēng)為RFC索引，以它來(lái)確認(rèn)進(jìn)入網(wǎng)絡(luò)或主機(jī)的數(shù)據(jù)包該進(jìn)入哪個(gè)子集，進(jìn)一步通過(guò)相應(yīng)的RFC數(shù)據(jù)結(jié)構(gòu)來(lái)確定具體的匹配規(guī)則。

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

表1 簡(jiǎn)單規(guī)則庫(kù)

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

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

元組空間的思想是基于每個(gè)字段中前綴的位數(shù)把規(guī)則庫(kù)分為元組。每個(gè)元組對(duì)應(yīng)于一個(gè)前綴，檢查所有字段的組合,以及由此產(chǎn)生的元組稱(chēng)為元組空間[6]。以一個(gè)三維元組(5，6，7)為例,屬于這個(gè)三維元組的規(guī)則第一個(gè)字段是5位的前綴，第二個(gè)字段是6位前綴以及第三個(gè)字段為7位的前綴。因?yàn)槊總€(gè)規(guī)則只有一個(gè)前綴組合,元組空間不會(huì)違背分割的第二個(gè)要求。但這并不意味著任意前綴組合存在幾何關(guān)聯(lián),所以元組空間分割的思想不能滿(mǎn)足分割的第一個(gè)要求。由于高成本的前綴擴(kuò)張也很難調(diào)整元組的數(shù)量。采用一個(gè)類(lèi)似元組的思想提出了空間利用嵌套層元組,每個(gè)字段的長(zhǎng)度定義為嵌套的數(shù)量水平相應(yīng)的前綴。盡管這個(gè)算法的元組數(shù)量顯著低于元組空間元組的數(shù)量,但第一個(gè)分割的要求仍不滿(mǎn)足。貪婪算法運(yùn)用外積法減少使用嵌套級(jí)別的元組數(shù)目,但是不符合分割的第二個(gè)要求，嵌套元組也不支持更新，因?yàn)椴迦胍粋€(gè)規(guī)則時(shí)，新的前綴可能改變所有規(guī)則的嵌套層數(shù)。

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

與基于元組分割算法相比,使用決策樹(shù)對(duì)規(guī)則庫(kù)規(guī)則分割的算法只有一個(gè)規(guī)則重復(fù)問(wèn)題需要克服。本文提出使用一個(gè)隨需應(yīng)變的方法來(lái)避免規(guī)則的重復(fù)問(wèn)題，步驟如下：

(1) 生成一棵平衡二叉樹(shù)，每個(gè)內(nèi)部節(jié)點(diǎn)的關(guān)聯(lián)規(guī)則被分為兩個(gè)子集。在構(gòu)造決策樹(shù)的過(guò)程,刪除任何重復(fù)規(guī)則，所有從第一個(gè)決策樹(shù)刪除的規(guī)則都被存儲(chǔ)在第二個(gè)決策樹(shù)。

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

(3) 生成所有決策樹(shù)。決策樹(shù)的任一葉節(jié)點(diǎn)的規(guī)則被插入一個(gè)RFC的數(shù)據(jù)結(jié)構(gòu)，因此，RFC數(shù)據(jù)結(jié)構(gòu)的數(shù)量等于所有決策樹(shù)的葉節(jié)點(diǎn)總數(shù)。

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

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

(2) 計(jì)算規(guī)則庫(kù)每個(gè)字段不同的前綴的數(shù)量，選擇前綴數(shù)目最多的字段來(lái)分割。

(3) 對(duì)選定的字段,進(jìn)一步確定可以將規(guī)則平衡劃分成兩個(gè)部分的一個(gè)點(diǎn)。

(4) 針對(duì)選擇的字段，統(tǒng)計(jì)小于或等于選擇點(diǎn)的端點(diǎn)規(guī)則數(shù)量，對(duì)每個(gè)端點(diǎn)分別統(tǒng)計(jì)大于選擇點(diǎn)的起始點(diǎn)的規(guī)則數(shù)量。和選擇點(diǎn)相比，數(shù)字最接近被選中。

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

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

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

表2 五個(gè)字段的規(guī)則庫(kù)

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

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

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

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

表4 原始RFC和本文算法在每個(gè)階段的外積表實(shí)體

2 算法的進(jìn)一步改進(jìn)

本文提出三種技術(shù)來(lái)進(jìn)一步改善本文所提算法的時(shí)間和內(nèi)存消耗性能。

1) 合并小的子集。在對(duì)規(guī)則庫(kù)進(jìn)行分割時(shí)，可能會(huì)產(chǎn)生小的子集，這些小的子集將導(dǎo)致無(wú)效的RFC數(shù)據(jù)結(jié)構(gòu)，最終造成額外對(duì)這些數(shù)據(jù)結(jié)構(gòu)的內(nèi)存訪(fǎng)問(wèn)。為了避免這種情況，本文設(shè)計(jì)了一個(gè)閾值，當(dāng)某個(gè)子集的規(guī)則數(shù)小于這個(gè)閾值時(shí)，就將其與別的子集合并。這些合并的子集存儲(chǔ)在一個(gè)共同的RFC數(shù)據(jù)結(jié)構(gòu)中。

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

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

3 實(shí) 驗(yàn)

本文運(yùn)用真實(shí)的和合成的規(guī)則庫(kù)去評(píng)價(jià)本文算法的性能，在實(shí)驗(yàn)中運(yùn)用三種類(lèi)型的規(guī)則集：訪(fǎng)問(wèn)空列表(ACL)、防火墻(FW)和IP鏈(IPC)。這些數(shù)據(jù)集可以從文獻(xiàn)[7]獲取。實(shí)驗(yàn)?zāi)康氖菫榱吮容^本文算法和其他幾種算法的性能。

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

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

圖3顯示了在三種不同類(lèi)型的規(guī)則庫(kù)、三個(gè)不同大小的子集下，最壞情況下的內(nèi)存需求和內(nèi)存訪(fǎng)問(wèn)的次數(shù)。如圖3(a)所示，隨著子集中規(guī)則數(shù)減少，即子集個(gè)數(shù)增多，內(nèi)存需求逐漸劣化。然而,圖3(b)也顯示，隨著子集中規(guī)則數(shù)增加，子集個(gè)數(shù)減少，內(nèi)存訪(fǎng)問(wèn)增加。這是因?yàn)閭魅霐?shù)據(jù)包可能匹權(quán)衡利弊后，設(shè)置因子d1為8，因?yàn)榇酥悼梢愿玫貦?quán)衡存儲(chǔ)和速度性能。因此子集的大小等于規(guī)則的數(shù)量除以8。

(a) 內(nèi)存需求

(b) 訪(fǎng)問(wèn)次數(shù)圖3 三種類(lèi)型的規(guī)則庫(kù)在三個(gè)因子下內(nèi)存需求和訪(fǎng)問(wèn)次數(shù)

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

圖4給出了在三種不同類(lèi)型的規(guī)則庫(kù)、三個(gè)子集合并的不同閾值下，在最壞情況下的內(nèi)存需求和內(nèi)存訪(fǎng)問(wèn)的次數(shù)。圖4(a)表明在RFC算法中，一個(gè)大的合并閾值可能招致更多的內(nèi)存需求，因?yàn)樵絹?lái)越多的子集合并導(dǎo)致更大的外積表。圖4(b)顯示一個(gè)小合并閾值可能招致更多的內(nèi)存訪(fǎng)問(wèn)，因?yàn)镽FC的數(shù)據(jù)結(jié)構(gòu)的數(shù)量不能有效減少。因此,傳入數(shù)據(jù)包在搜索過(guò)程中匹配更多的子集可能導(dǎo)致更多的內(nèi)存訪(fǎng)問(wèn)。

(a) 內(nèi)存需求

(b) 訪(fǎng)問(wèn)次數(shù)圖4 三個(gè)合并閾值下內(nèi)存需求和訪(fǎng)問(wèn)次數(shù)

進(jìn)一步比較本文算法在允許子集合并(設(shè)置因子d2為3)和沒(méi)有子集合并兩種情況下的性能，如圖5所示。圖5(a)顯示，隨著子集的合并，內(nèi)存需求略有增加，RFC數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)更多的規(guī)則通常會(huì)導(dǎo)致更多的外積實(shí)體。圖5(b)表明，子集合并可以減少內(nèi)存訪(fǎng)問(wèn)。要在存儲(chǔ)和速度性能之間權(quán)衡，本文傾向于速度，因?yàn)楸疚乃惴ㄏ啾扔赗FC算法顯著降低了內(nèi)存需求。

(a) 內(nèi)存需求

(b) 訪(fǎng)問(wèn)次數(shù)圖5 三種類(lèi)型的規(guī)則庫(kù)，兩種合并閾值下的內(nèi)存 和速度性能比較

3) 算法性能比較分析。比較本文算法與RFC[6]、HSM[8]、Hypercuts[4]、ISET[9]的性能，結(jié)果如圖6-圖8所示。一些結(jié)果不能顯示是因?yàn)橛糜跇?gòu)建數(shù)據(jù)結(jié)構(gòu)程序內(nèi)存消耗太大，導(dǎo)致無(wú)法運(yùn)行。

(a) 內(nèi)存需求

(b) 訪(fǎng)問(wèn)次數(shù)圖6 ACL1規(guī)則庫(kù)中的五種算法的速度性能比較

(a) 內(nèi)存需求

(b) 訪(fǎng)問(wèn)次數(shù)圖7 FW1規(guī)則庫(kù)中的五種算法的速度性能比較

(a) 內(nèi)存需求

(b) 訪(fǎng)問(wèn)次數(shù)圖8 IPC1規(guī)則庫(kù)中的五種算法的速度性能比較

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

4 結(jié) 語(yǔ)

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