謝鯤，趙姣姣，張大方

（湖南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長(zhǎng)沙 410082）

1 引言

隨著新型網(wǎng)絡(luò)設(shè)備及新型網(wǎng)絡(luò)服務(wù)的提出和發(fā)展，傳統(tǒng)單維分組分類算法已不能滿足網(wǎng)絡(luò)應(yīng)用和服務(wù)的需求，多維分組分類算法成為分組分類技術(shù)研究的重點(diǎn)。多維分組分類算法將IP分組頭多個(gè)域的信息在相應(yīng)的規(guī)則庫(kù)中進(jìn)行多維匹配，以獲得匹配規(guī)則。網(wǎng)絡(luò)設(shè)備根據(jù)匹配規(guī)則中對(duì)應(yīng)的策略對(duì)數(shù)據(jù)分組采取相應(yīng)的措施，以完成相應(yīng)的新型服務(wù)。

維度分解是解決多維分組分類問題的基本方法。利用維度分解，多維分組分類問題首先被分解成多個(gè)簡(jiǎn)單一維匹配問題，然后通過某種數(shù)據(jù)結(jié)構(gòu)，將多個(gè)一維的匹配結(jié)果相關(guān)聯(lián)得到最終的匹配規(guī)則。現(xiàn)有的基于維度分解的多維分組分類算法主要有：ABV[1]算法，P2C[2]算法和RSFR算法[3]。

ABV算法為每一維SIP、DIP分別建立Tire樹結(jié)構(gòu)，在掛規(guī)則的Tire節(jié)點(diǎn)中存放一個(gè)Nbit的向量，以標(biāo)示規(guī)則庫(kù)中與該節(jié)點(diǎn)相匹配的所有規(guī)則（N為規(guī)則條數(shù)）。對(duì)每維處理后，取出各維匹配節(jié)點(diǎn)的Nbit向量，求交集得到最后匹配結(jié)果。ABV主要依據(jù)Nbit向量關(guān)聯(lián)出最后結(jié)果，然而每個(gè)規(guī)則節(jié)點(diǎn)均需要存儲(chǔ)Nbit向量，空間占用大，不易擴(kuò)展到大規(guī)模規(guī)則庫(kù)。P2C算法在維度分解后利用硬件TCAM（ternary content addressable memory）[4]來解決單維到多維的關(guān)聯(lián)，匹配速度快，但是需要耗費(fèi)硬件資源來支撐，并且TCAM存在高功耗、價(jià)格高、集成度低等缺點(diǎn)，只能用于小規(guī)模規(guī)則庫(kù)。RSFR算法采用元組空間 （TS, tuple space）[5]進(jìn)行算法設(shè)計(jì)，其核心是用規(guī)則重編碼對(duì) RS算法[5]進(jìn)行改進(jìn)。RSFR首先對(duì)各維進(jìn)行一維處理，而后利用RS算法查找結(jié)構(gòu)關(guān)聯(lián)出最終結(jié)果。RSFR時(shí)間性能較其他多維分解算法優(yōu)越，易于向大規(guī)模規(guī)則庫(kù)擴(kuò)展。然而RSFR算法為了減少訪問元組空間的個(gè)數(shù)，提高匹配速度，除了對(duì)規(guī)則重編碼外，還需要兩項(xiàng)復(fù)雜的預(yù)處理操作：插入偽規(guī)則和計(jì)算每條規(guī)則的BMP（最優(yōu)匹配規(guī)則）。這使得RSFR空間耗費(fèi)過大，需要存儲(chǔ)真實(shí)規(guī)則和偽規(guī)則（最壞情況需要插入40%×N條偽規(guī)則（N為規(guī)則數(shù)目）），還有每條規(guī)則的 BMP（BMP作為規(guī)則的屬性存放）。另外，規(guī)則庫(kù)更新復(fù)雜度也增加，增加刪除規(guī)則都需要處理所需的偽規(guī)則，并重新計(jì)算所有受影響的BMP。

一方面，維度分解可降低多維分組分類算法的難度，算法的整體性能取決于關(guān)聯(lián)數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)，因此，如何設(shè)計(jì)高效的關(guān)聯(lián)數(shù)據(jù)結(jié)構(gòu)，以聯(lián)合各維匹配結(jié)果得出最終匹配規(guī)則成為高效多維數(shù)據(jù)分組分類算法設(shè)計(jì)的關(guān)鍵。另一方面，現(xiàn)有研究表明，大規(guī)模規(guī)則庫(kù)中與前兩維匹配的子規(guī)則庫(kù)規(guī)模非常小，處理多維分組分類可以首先進(jìn)行二維分組分類[6]（二維分組分類通常根據(jù) IP分組中的源IP（SIP）、目的IP（DIP）2個(gè)域進(jìn)行規(guī)則匹配），而后在規(guī)模有限的子規(guī)則庫(kù)中對(duì)其他維進(jìn)行簡(jiǎn)單的線性匹配即可。

本文從維度分解出發(fā)，設(shè)計(jì)并實(shí)現(xiàn)了一種新的二維分組分類算法（TB, joint tuple space and bitmap）。TB將元組空間和位圖相結(jié)合作為一維匹配后的關(guān)聯(lián)結(jié)構(gòu)，并利用交叉組合思想形成需要訪問的TS路線，利用位圖過濾減少需要訪問的TS數(shù)目，可以高效快速的匹配出最終結(jié)果，并且可以克服RSFR算法的缺點(diǎn)。TB算法結(jié)構(gòu)簡(jiǎn)潔，易于實(shí)現(xiàn)，具有良好的時(shí)空性能。另外，TB預(yù)處理操作簡(jiǎn)單，規(guī)則庫(kù)更新較易且具有良好的擴(kuò)展性能。

本文的行文安排為：第2節(jié)介紹TB算法設(shè)計(jì)的基本思想，第3節(jié)對(duì)TB算法各部分進(jìn)行具體實(shí)現(xiàn)，第4節(jié)分析TB算法的性能，第5節(jié)從不同場(chǎng)景實(shí)驗(yàn)測(cè)試TB算法的性能，第6節(jié)是結(jié)束語。

2 TB設(shè)計(jì)的基本思想

TB算法結(jié)構(gòu)框架如圖 1所示。算法可分為 3部分，第1部分：分別對(duì)SIP、DIP進(jìn)行AMP匹配，并利用前綴長(zhǎng)度交叉組合成TS。第2部分：在位圖上驗(yàn)證交叉元組空間是否存在，過濾掉不存在的TS。第3部分：在通過位圖驗(yàn)證的相應(yīng)TS中進(jìn)行查找以獲得最終匹配的多維規(guī)則。

圖1 TB算法結(jié)構(gòu)

TB算法包括以下3點(diǎn)基本設(shè)計(jì)思想。

1) 維度分解設(shè)計(jì)思想。

TB算法的第一部分分別對(duì)SIP、DIP進(jìn)行所有匹配規(guī)則的查找即求AMP。不同于RSFR算法中只求最長(zhǎng)前綴匹配（LMP, longest prefix match），TB算法不僅求LMP，還要求出所有和SIP、DIP匹配的嵌套子規(guī)則（如果規(guī)則Px是規(guī)則Py前綴的子串，則稱Px為Py的一條嵌套子規(guī)則）。如圖2所示，若 SIP匹配的 LMP為規(guī)則 P4，TB算法第一步AMP(SIP)的結(jié)果為 P4、P3、P1。

圖2 規(guī)則編碼實(shí)例

2) 利用規(guī)則庫(kù)嵌套特征進(jìn)行優(yōu)化設(shè)計(jì)。

基于規(guī)則庫(kù)嵌套原理，TB算法有2處設(shè)計(jì)：第一，對(duì)于一維的AMP結(jié)果，進(jìn)行交叉組合。第二，引入規(guī)則重編碼，減少TS的個(gè)數(shù)。

在真實(shí)規(guī)則庫(kù)中，單維規(guī)則最大嵌套層次數(shù)目（稱為S）遠(yuǎn)遠(yuǎn)小于規(guī)則中不同前綴長(zhǎng)度的個(gè)數(shù)，S一般小于3，最壞情況下為5。例如規(guī)則0*和規(guī)則0100*都是規(guī)則010000*的嵌套子規(guī)則，且嵌套層次為3。換句話描述，對(duì)一個(gè)IP分組的SIP或者DIP進(jìn)行單維的AMP匹配，AMP中包含的規(guī)則數(shù)目即為S，因此可知AMP規(guī)則數(shù)目與嵌套層次相同一般小于3。這就是規(guī)則嵌套的基本特征。文獻(xiàn)[1,3,7,8]均調(diào)研得出如此結(jié)論，且此結(jié)論也用在許多經(jīng)典的算法設(shè)計(jì)中[1,6,9]，本文通過實(shí)驗(yàn)也證明了此特征。

基于規(guī)則的嵌套特征，TB算法運(yùn)用交叉組合思想進(jìn)行算法設(shè)計(jì)。第一部分對(duì)SIP、DIP求得AMP后，分別取 SIP、DIP各個(gè)匹配規(guī)則的前綴長(zhǎng)度，將其交叉組合成元組空間，由于S數(shù)目很小，因此交叉組合形成的TS個(gè)數(shù)也很小，一般小于9最壞情況下為25，下一步只需要在這些數(shù)目規(guī)模有限的TS中進(jìn)行訪問，時(shí)間性能得到第一步保證。因?yàn)楹投S均匹配的規(guī)則必在這些交叉元組空間中，這是TB算法關(guān)聯(lián)各維結(jié)果后形成的TS訪問路線。例如SIP的AMP長(zhǎng)度為2、3，DIP的AMP長(zhǎng)度為1、4，那么交叉組合形成的TS分別為TS（2，1）、TS（2，4）、TS（3，1）、TS（3，4），在這些 TS 中訪問一定可以找到與二維均匹配的最優(yōu)規(guī)則。

為減少所需形成TS的數(shù)目，TB算法還引入規(guī)則重編碼設(shè)計(jì)。規(guī)則重編碼思想廣泛應(yīng)用于分組分類算法設(shè)計(jì)中，因?yàn)橹鼐幋a可以大大降低形成的元組空間個(gè)數(shù)，減少交叉元組空間在位圖上的命中率，提高匹配速度。在TB中，根據(jù)規(guī)則P所有嵌套子規(guī)則的前綴長(zhǎng)度，將規(guī)則P分成多個(gè)子串，并歸入不同的層次。為了理解編碼過程，圖2是取自文獻(xiàn)[3]的編碼實(shí)例，規(guī)則P4（010000）有2個(gè)嵌套子規(guī)則分別為P1（0）、P3（0100），因此，將P4 分為3 個(gè)位串＜0＞＜100＞＜00＞，將這3個(gè)位串分別歸入第一層，第二層和第三層。對(duì)所有規(guī)則如此處理后，為每一層的位串賦予新的 ID如圖2所示，規(guī)則新的編碼為連接該規(guī)則在各層相關(guān)位串的新ID。例如規(guī)則P4編碼后為（0000100）?？梢姡幋a后規(guī)則不同長(zhǎng)度的數(shù)目將大大減少，即從W（W為IP地址的長(zhǎng)度）降低為規(guī)則庫(kù)的最大嵌套層次數(shù)S。RSFR算法正是基于此將RS的時(shí)間性能從O(2W?1)提升為O(2S?1)。圖2中，實(shí)例規(guī)則庫(kù)的嵌套層次為3，編碼后規(guī)則不同長(zhǎng)度個(gè)數(shù)由7降至3，長(zhǎng)度分別為2、5、7。

3) 元組空間和位圖相結(jié)合的關(guān)聯(lián)結(jié)構(gòu)。

在進(jìn)行多維關(guān)聯(lián)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)時(shí)，交叉組合形成的TS并不一定真正存在，為了進(jìn)一步減少訪問TS的個(gè)數(shù)，利用位圖技術(shù)來對(duì)所需訪問的TS進(jìn)行空間的過濾。若沒有通過位圖，則不需要訪問對(duì)應(yīng)TS；若通過位圖，則在相應(yīng)的TS中查找所匹配的規(guī)則。位圖技術(shù)是TB算法時(shí)間性能的第二步保證，結(jié)合規(guī)則庫(kù)嵌套原理使得TB算法在平均時(shí)間性能上仍優(yōu)于RSFR算法。

3 TB算法具體實(shí)現(xiàn)

圖1給出了TB算法的匹配數(shù)據(jù)結(jié)構(gòu)框架，本節(jié)具體說明算法3個(gè)部分的實(shí)現(xiàn)。

算法第1部分，分別求出與IP分組的SIP、DIP匹配的所有規(guī)則，此部分需要一個(gè)查找AMP的一維包匹配算法。TB算法與RSFR算法一樣均采用文獻(xiàn)[10]提出的BSH（binary search on hash table）算法實(shí)現(xiàn)。BSH算法是一維分組分類算法，根據(jù)IP分組的SIP或者DIP在散列表上進(jìn)行折半查找，最終查找出與一維地址匹配的最長(zhǎng)匹配規(guī)則即LMP。文獻(xiàn)[10]指出 BSH算法一次查找最多需要lbW次散列訪問，W為IP地址的位寬。因此對(duì)于IPv4最多需要lb 32，即 5次散列訪問，對(duì)于 IPv6需要lb128即7次。本文采用BSH一是便于與RSFR比較，因?yàn)?個(gè)算法該部分均可根據(jù)需要換取效率更高的一維匹配算法，二是BSH算法查找性能較好，訪問內(nèi)存次數(shù)只與IP地址位寬有關(guān)，與規(guī)則庫(kù)大小無關(guān)，因此易于向大規(guī)模規(guī)則庫(kù)和IPv6擴(kuò)展。

然而BSH是針對(duì)LMP的一維算法，TB需要的一維匹配算法需要匹配出AMP。因此，在TB算法設(shè)計(jì)中，將規(guī)則重編碼思想和 BSH相結(jié)合，以得到AMP結(jié)果。算法在規(guī)則重編碼階段已經(jīng)記錄了編碼后所有規(guī)則的長(zhǎng)度，如圖2實(shí)例中，編碼后不同規(guī)則長(zhǎng)度數(shù)目為 3，分別為 2、5、7，因此當(dāng)求得SIP、DIP的LMP后，可根據(jù)此LMP的前綴長(zhǎng)度以及編碼后所有規(guī)則的長(zhǎng)度，直接求得AMP，例如在圖2中若某SIP的LMP規(guī)則為P4，其長(zhǎng)度為7，則與此SIP匹配的所有AMP的長(zhǎng)度一定分別為2、5、7，具體值即為取P4的前2、5位組成的規(guī)則，即 P1、P3。然而在 TB算法中只需要記錄AMP規(guī)則的長(zhǎng)度即可。因此采用BSH算法實(shí)現(xiàn)TB算法第1部分，則TB算法和RSFR算法此部分內(nèi)存訪問次數(shù)相同。

算法第2部分，采用位圖標(biāo)識(shí)各個(gè)TS的存在狀態(tài)，對(duì)于IPv4，所有可能的規(guī)則前綴長(zhǎng)度為從0到32，因此所有可能形成的TS個(gè)數(shù)為33×33。因此位圖的大小設(shè)為 33×33bit，稱之為bitMap[33][33]。位圖初值為0，標(biāo)識(shí)各TS不存在，即沒有規(guī)則屬于此TS。當(dāng)將編碼后形成的規(guī)則放入對(duì)應(yīng)的TS時(shí)初始化位圖相應(yīng)位置的值為1，標(biāo)識(shí)此TS存在。例如二維規(guī)則（0000100*，01011*）屬于TS（7,5），設(shè)位圖bitMap[7][5]值為true即為1。將第一部分形成的交叉元組在位圖上進(jìn)行過濾查找時(shí)，相應(yīng)位置為0則過濾掉，不必進(jìn)行算法第3部分查找。位圖結(jié)構(gòu)簡(jiǎn)單，可以用軟件或者硬件實(shí)現(xiàn)，若用片上硬件實(shí)現(xiàn)，則可加快驗(yàn)證速度。

算法第3部分，需要在通過位圖的相應(yīng)TS中進(jìn)行查找，在具體一個(gè)TS中用散列進(jìn)行匹配，算法時(shí)間性能取決于訪問TS的個(gè)數(shù)，因此本文記錄算法訪問TS的個(gè)數(shù)。

圖3是TB算法具體匹配過程的實(shí)例，算法匹配過程非常簡(jiǎn)潔：對(duì)于某IP分組，若匹配出SIP的AMP分別為規(guī)則P4、P3、P1，由圖2可知這些規(guī)則編碼后對(duì)應(yīng)的長(zhǎng)度分別為7、5、2，同樣對(duì)于DIP，P14、P12對(duì)應(yīng)的長(zhǎng)度為 5、2，利用這些規(guī)則長(zhǎng)度交叉組合成 6個(gè) TS 分別為 TS（7，5）、TS（7，2）、TS（5，5）、TS（5，2）、TS（2，5）、TS（2，2）。而后，將上述6個(gè)TS在位圖上過濾，位圖相應(yīng)位置為1表明此TS存在，則在該TS中匹配，若匹配到即將此規(guī)則作為當(dāng)前IP分組匹配的最優(yōu)規(guī)則，若后續(xù)在其他TS中匹配到優(yōu)先級(jí)更高的規(guī)則，則替換，最終找到最優(yōu)的匹配規(guī)則。

圖3 TB算法分組匹配實(shí)例

4 TB算法性能分析

本節(jié)分析TB算法和RSFR算法時(shí)空需求并比較各方面的性能。TB算法空間需求為：BSH算法空間+位圖+TS中規(guī)則，RSFR空間為：BSH算法空間+RS算法空間（包括偽規(guī)則和規(guī)則）；TB算法內(nèi)存訪問次數(shù)為：AMP（SIP）.access + AMP（DIP）.access+交叉組合形成的元組空間中通過位圖即存在的元組空間個(gè)數(shù)，其中access表示相應(yīng)算法的訪問內(nèi)存次數(shù)。RSFR算法內(nèi)存訪問次數(shù)為：LMP（SIP）.access+LMP（DIP）.acces+RS.access。2 種算法在一維處理上均采用BSH算法，雖然TB求解一維的AMP，RSFR求解一維的LMP，但由上節(jié)算法具體實(shí)現(xiàn)可知，這部分的內(nèi)存訪問次數(shù)和空間需求與RSFR算法相同，因此時(shí)空性能主要取決于第2部分。下面可以暫不考慮一維的開銷，對(duì)2種算法性能進(jìn)行比較分析。

1) 預(yù)處理復(fù)雜度：TB和RSFR均需要對(duì)規(guī)則進(jìn)行重編碼，此外，TB預(yù)處理中只需要將每條規(guī)則存放入相應(yīng)的元組空間，并根據(jù)形成的元組空間初始化位圖。而RSFR除了存放規(guī)則外，還需要插入需要的偽規(guī)則，并計(jì)算各條規(guī)則的 BMP規(guī)則。顯然TB預(yù)處理操作簡(jiǎn)單，所需時(shí)間少。

2) 更新復(fù)雜度：TB算法不需要RSFR中2項(xiàng)復(fù)雜的預(yù)處理，因此規(guī)則庫(kù)更新較易，因?yàn)椴恍枰獮樵黾觿h除規(guī)則處理偽規(guī)則，并重新計(jì)算所有受到影響的BMP。

3) 空間占用：TB算法只需要在TS中存儲(chǔ)規(guī)則，不需插入任何偽規(guī)則，也不需要在預(yù)處理中為規(guī)則存放 BMP，大大降低了空間耗費(fèi)。TB算法中增加的位圖空間相比RSFR中插入的很多偽規(guī)則，空間占用非常小，TB空間性能大大優(yōu)于RSFR。

4) 時(shí)間性能分析：2種算法均不考慮2個(gè)一維匹配過程，對(duì)于RSFR算法最多訪問元組空間個(gè)數(shù)為O(2S?1)（S為規(guī)則庫(kù)嵌套的最大層次），TB算法第一部分求出AMP的個(gè)數(shù)分別為S，交叉組合形成的元組空間個(gè)數(shù)為S×S，算法需要訪問的元組空間個(gè)數(shù)最多為O(S×S)。但是由規(guī)則嵌套特征可知S數(shù)目很小，因此O(S×S)不會(huì)非常大于O(2S?1)。雖然從分析看TB時(shí)間性能不如RSFR，但是TB算法通過兩點(diǎn)降低了訪問元組空間的個(gè)數(shù)，第一，算法采用位圖過濾，S×S個(gè)TS中只有標(biāo)示存在才需要訪問，大大降低了訪問TS的個(gè)數(shù)。第二，TB算法形成的TS個(gè)數(shù)少于RSFR算法，因?yàn)殡m然兩算法均通過規(guī)則重編碼使得元組空間個(gè)數(shù)很少，但是在RSFR算法中仍有一些TS是純粹的偽規(guī)則組成，這些TS在TB算法中不存在。分析可知，TB算法的時(shí)間性能主要取決于規(guī)則庫(kù)嵌套層次和位圖的過濾效果，嵌套層次決定了交叉形成的TS個(gè)數(shù)，位圖過濾決定了真正需要訪問的TS個(gè)數(shù)。然而實(shí)際中，每個(gè)數(shù)據(jù)分組交叉形成的TS中有大部分并不真正存在，可以通過位圖過濾掉。本文實(shí)驗(yàn)仿真的數(shù)據(jù)是通過多個(gè)大規(guī)模流量文件測(cè)試并取得其平均值，可見TB算法除了空間性能優(yōu)越外，時(shí)間性能通過位圖過濾仍然優(yōu)于RSFR。

5) 重編碼的依賴程度：重編碼降低了TS的個(gè)數(shù)，有利于提高匹配速度，然而對(duì)算法的更新帶來了困難。RSFR算法的性能完全依賴于重編碼，否則退化為RS算法。而TB算法中就算不引入重編碼，訪問的TS個(gè)數(shù)由規(guī)則庫(kù)嵌套原理可知，也是極其有限的，時(shí)間性能上不會(huì)有很大波動(dòng)。因此TB算法在設(shè)計(jì)的選擇上有更大的自由空間。

5 仿真實(shí)驗(yàn)

仿真平臺(tái)由C++語言編寫完成，運(yùn)行環(huán)境為：Pentium 4 3.00GHz CPU，512MB內(nèi)存，Windows XP操作系統(tǒng)。仿真實(shí)驗(yàn)采用PALAC（packet lookup and classification simulator）平臺(tái)[11]的流量生成器生成網(wǎng)絡(luò)流量。為了有效驗(yàn)證算法性能，本文采用華盛頓大學(xué)開發(fā)的ClassBench平臺(tái)[8]生成仿真所用的規(guī)則庫(kù)。ClassBench是一組工具，它將真實(shí)的規(guī)則庫(kù)作為種子，通過高層參數(shù)的調(diào)控生成符合真實(shí)規(guī)則庫(kù)特征的規(guī)則庫(kù)，與其他研究中運(yùn)用路由表生成規(guī)則庫(kù)相比，能更準(zhǔn)確真實(shí)的模擬了分組分類算法的運(yùn)行環(huán)境。本文運(yùn)用ClassBench生成大小不同且類型不同的規(guī)則庫(kù)，規(guī)則庫(kù)3種類型分別是 Access Control List（ACL）、Firewall（FW）、IP Chain（IPC）。

實(shí)驗(yàn)中，將論文所提出的TB算法與RSFR算法進(jìn)行性能比較。5.1節(jié)中為了驗(yàn)證算法在小規(guī)模規(guī)則庫(kù)中運(yùn)行的性能，規(guī)則庫(kù)大小為300～6 000條不等。為了驗(yàn)證算法的擴(kuò)展性能，在5.2節(jié)規(guī)則庫(kù)大小為5 000～100 000條不等。對(duì)這些規(guī)則庫(kù)進(jìn)行實(shí)驗(yàn)分析可知它們均符合規(guī)則庫(kù)的嵌套特征。分組分類算法主要性能衡量指標(biāo)為時(shí)間性能即數(shù)據(jù)分組匹配速度及算法存儲(chǔ)空間占用2個(gè)方面。時(shí)間性能方面通過統(tǒng)計(jì)各算法的平均內(nèi)存訪問次數(shù)來衡量?？臻g占用方面，統(tǒng)計(jì)各算法需要存儲(chǔ)的規(guī)則和偽規(guī)則，規(guī)則的每一維度占用40bit（32bit存儲(chǔ)IP地址，8bit用來表示前綴長(zhǎng)度）。需要注意的是，2個(gè)算法均統(tǒng)計(jì)兩個(gè)一維算法 BSH占用的空間，并且對(duì)于 TB算法需要統(tǒng)計(jì)位圖的空間，RSFR算法需要統(tǒng)計(jì)其偽規(guī)則所需空間。

5.1 小規(guī)模規(guī)則庫(kù)性能分析

已有研究表明，真實(shí)規(guī)則庫(kù)的大小一般為5 000條左右。首先測(cè)試算法在小規(guī)模規(guī)則庫(kù)（300～6 000條）上運(yùn)行的性能。圖4(a)為TB算法和RSFR算法的平均訪問內(nèi)存次數(shù)，圖4(b)是2種算法空間大小需求。表1統(tǒng)計(jì)了2種算法數(shù)據(jù)結(jié)構(gòu)形成的TS的個(gè)數(shù)以及最壞的內(nèi)存訪問次數(shù)。

需要指出的是，雖然兩算法第1部分的單維匹配算法可通過并行提高速度，但測(cè)試中仍按照串行進(jìn)行測(cè)試，即按照第4節(jié)分析的性能公式計(jì)算。由圖 4(a)可知，算法 TB平均內(nèi)存訪問次數(shù)優(yōu)于RSFR算法，平均低于RSFR算法26.6%。注意此平均訪問次數(shù)中均包含2個(gè)一維算法BSH的訪問次數(shù)，而由具體實(shí)現(xiàn)可知2種算法一維匹配算法性能相同，因此實(shí)驗(yàn)結(jié)果表明若不計(jì)算一維算法，TB算法的平均內(nèi)存訪問次數(shù)仍優(yōu)于RSFR算法。這證明了在第 4節(jié)分析的結(jié)果，雖然不考慮一維，RSFR算法的訪問次數(shù)為O(2S?1)，TB算法訪問次數(shù)為O(S×S)，但是TB算法通過位圖過濾和減少 TS個(gè)數(shù)保證了算法平均訪問次數(shù)仍然優(yōu)于RSFR算法。因?yàn)橛梢痪S匹配結(jié)果交叉形成的S×S個(gè) TS中大部分并不存在，可通過位圖排除，且由表 1統(tǒng)計(jì)的 TS個(gè)數(shù)可知，TB算法不需要插入偽規(guī)則，所以不存在由純粹偽規(guī)則組成的TS，形成的TS個(gè)數(shù)少于RSFR算法，有利于降低位圖命中率，提高速度。然而TB算法在最壞內(nèi)存訪問次數(shù)性能方面不如RSFR算法穩(wěn)定，如表1所示，雖然2種算法最壞訪問次數(shù)彼此相差不大，但是RSFR算法較為穩(wěn)定。這是由于 TB算法最壞內(nèi)存訪問次數(shù)取決于交叉形成的S×S個(gè)TS在位圖中的命中率。

圖4 小規(guī)模規(guī)則庫(kù)（300～6 000條）性能測(cè)試

表1 TS個(gè)數(shù)及最壞內(nèi)存訪問次數(shù)

圖4(b)為2個(gè)算法空間需求性能比較，由圖可見雖然兩算法都隨規(guī)則庫(kù)規(guī)模增大而線性增長(zhǎng)，但是TB算法較RSFR算法節(jié)省大量空間，平均降低35.1%的空間需求。因?yàn)門B算法不需要插入任何偽規(guī)則，且隨著規(guī)則庫(kù)規(guī)模增大空間優(yōu)勢(shì)越明顯。

綜上分析，TB算法在空間和時(shí)間性能上均優(yōu)于RSFR，實(shí)驗(yàn)證明了TS和位圖相結(jié)合的優(yōu)勢(shì)。

5.2 大規(guī)模規(guī)則庫(kù)性能分析

圖5 大規(guī)模規(guī)則庫(kù)（5 000～100 000條）性能測(cè)試

為了證明算法的擴(kuò)展性能，測(cè)試算法在大規(guī)模規(guī)則庫(kù)下的性能，規(guī)則數(shù)目分別為5 000～100 000條不等。實(shí)驗(yàn)結(jié)果如圖5所示，從圖5(a)可知，TB算法平均內(nèi)存訪問次數(shù)優(yōu)于RSFR算法，且平均訪問次數(shù)隨規(guī)則庫(kù)規(guī)模的增大波動(dòng)很小，相差不大，最大和最小訪問次數(shù)相差為 2，具有良好的擴(kuò)展性，比RSFR算法擴(kuò)展性能穩(wěn)定。仔細(xì)分析可知，對(duì)于RSFR算法開始的規(guī)則5 000～30 000條的訪問次數(shù)較高，是因?yàn)檫@些規(guī)則庫(kù)類型為 Firewall（FW），F(xiàn)W類型的規(guī)則庫(kù)嵌套層次S比較大，而這對(duì)于TB算法影響不大，因?yàn)?TB算法中運(yùn)用位圖結(jié)構(gòu)進(jìn)行過濾，只有真正存在的 TS才進(jìn)一步訪問。圖5(b)表明，對(duì)于大規(guī)模規(guī)則庫(kù)，空間上TB算法仍低于RSFR算法，且增長(zhǎng)速度低于RSFR算法，因?yàn)镽SFR算法隨著規(guī)則庫(kù)規(guī)模擴(kuò)大，插入的偽規(guī)則條數(shù)亦增大。

6 結(jié)束語

本文從維度分解設(shè)計(jì)思想出發(fā)，將元組空間和位圖結(jié)構(gòu)相結(jié)合作為一維處理后的關(guān)聯(lián)結(jié)構(gòu)，設(shè)計(jì)并實(shí)現(xiàn)了一種新的高性能二維分組分類算法。TB算法首先進(jìn)行維度分解，查找各維的AMP，然后運(yùn)用交叉組合形成元組空間并在位圖上進(jìn)行過濾，在各元組空間中查找后返回優(yōu)先級(jí)最高的匹配規(guī)則。相比于傳統(tǒng)的元組空間算法，TB算法不需要插入任何偽規(guī)則，大大降低了算法空間需求，并通過采用位圖過濾技術(shù)以及減少元組空間個(gè)數(shù)，提高了算法的時(shí)間性能。論文最后通過在規(guī)模不同的規(guī)則庫(kù)上進(jìn)行實(shí)驗(yàn)測(cè)試，證明了算法TB在空間和時(shí)間性能上均優(yōu)于 RSFR算法，且具有良好的擴(kuò)展性能。

[1]BABOESCU F, VARGHESE G.Scalable packet classification[J].IEEE /ACM Transactions on Networking, 2005, 13(1):2 - 14.

[2]LUNTEREN J V, ENGBERSEN T.Fast and scalable packet classification[J].IEEE Journal of Selected Areas in Communications, 2003,21(4): 560-571.

[3]PI-CHUNG W, CHUN-LIANG L, CHIA-TAI C,et al.Performance improvement of two-dimensional packet classif i cation by filter rephrasing[J].IEEE /ACM Transactions on Networking, 2007, 15(4):906-917.

[4]ZANE F, NARLIKAR G, BASU A.Coolcams: power-efficient TCAMs for forwarding engines[A].Proc of Twenty-Second Annual Joint Conference of the IEEE Computer and Communications[C].San Francisco, 2003, 42-52.

[5]SRINIVASAN V, SURI S, VARGHESE G.Packet classification using tuple space search[A].Proc of ACMSIGCOMM 1999[C].Cambridge,Massachusetts, United States, 1999.135-146.

[6]BABOESCU F, SUMEET S, GEORGE V.Packet classification for core routers: is there an alternative to CAMs?[A]Proc of IEEE INFOCOM 2003[C].Toronho, Ontarion, Canada, 2003, 53-63.

[7]FELDMAN A, MUTHUKRISHNAN S.Tradeoffs for packet classification[J].IEEE INFOCOM, 2000.1193-1202.

[8]DAVID E T, JONATHAN S T.ClassBench: a packet classification benchmarks[A].Proceedings of IEEE/ACM Trans on Networking[C].San Francisco, CA, USA, 2007,499-511.

[9]LAKSHMAN T V, STIDIALIS D.High speed policy-based packet forwarding using efficient multi-dimensional range matching[A].Proc of.ACM SIGCOMM 1998[C].Vancouver, British Columbia, Canada,1998, 203-214.

[10]MALDVOGEL M, VARGHESE G, TURNER J,et al.Scalable high speed IP routing lookups[A].Proc of ACM SIGCOMM, Cannes,France, 1997.25-36.

[11]PANKAJ G, BALKMAN J.PALAC: Packet Lookup and Classification Simulator[Z].User's Manual, ver.4, Rev.2000.