基于Hash和AQT的類(lèi)決策樹(shù)包分類(lèi)算法研究

趙國(guó)鋒， 陳群麗

（重慶郵電大學(xué)，重慶 400065）

0 引言

隨著網(wǎng)絡(luò)上各種業(yè)務(wù)的快速發(fā)展，原有的路由器必須不斷提供豐富的多業(yè)務(wù)能力。近來(lái)，新型的網(wǎng)絡(luò)應(yīng)用包括區(qū)分服務(wù)(Differentiated Qualities of Service),虛擬專(zhuān)用網(wǎng)(Virtual Private Network), Qos等等。所有這些業(yè)務(wù)的實(shí)現(xiàn)都依賴(lài)于IP分類(lèi)算法，也就是說(shuō)IP分類(lèi)算法的好壞在一定程度上決定了這些業(yè)務(wù)的性能。因此研究有效的包分類(lèi)算法及其實(shí)現(xiàn)技術(shù)是目前網(wǎng)絡(luò)技術(shù)領(lǐng)域的熱門(mén)課題。

國(guó)內(nèi)外學(xué)者針對(duì)不同的應(yīng)用已提出了一些有代表性的軟件包分類(lèi)算法．一類(lèi)是基于樹(shù)型結(jié)構(gòu)的算法(Trie-based Algorithms)[1]。該類(lèi)算法構(gòu)建一個(gè)等級(jí)索引樹(shù)，用關(guān)鍵字按等級(jí)依次搜索這個(gè)索引樹(shù)。對(duì)于單個(gè)域的搜索是有效的，但這種機(jī)制的存儲(chǔ)要求會(huì)隨著搜索維數(shù)的增加而迅速增加。代表算法有Grid of-tree、AQT等。第二類(lèi)是基于哈希函數(shù)的算法[2-3]。該類(lèi)算法是根據(jù)各域前綴的長(zhǎng)度將規(guī)則聚合在一起形成元組，但哈希表的技術(shù)對(duì)于規(guī)則個(gè)數(shù)的可擴(kuò)展性較差；第三類(lèi)是并行查找算法。它將多維的匹配問(wèn)題轉(zhuǎn)換為單維的匹配，為每一維設(shè)置一個(gè)位向量來(lái)標(biāo)記與這一維相匹配的規(guī)則，各維并行執(zhí)行，最后將各維的位向量相與找到最佳匹配規(guī)則。該算法在讀取各維的位向量或聚合向量時(shí)需要較多的讀取次數(shù)，尤其是規(guī)則庫(kù)中規(guī)則的個(gè)數(shù)比較大時(shí)，所以該算法只適合硬件執(zhí)行。代表算法有Parallel Bitvectors(BV)、Aggregated Bit-vector(ABV) 等。第四類(lèi)是啟發(fā)式算法[4]。該類(lèi)型算法充分利用規(guī)則的結(jié)構(gòu)特點(diǎn)和冗余特點(diǎn),其時(shí)間復(fù)雜度一般為O(k)，空間復(fù)雜度一般為O(nk)(k為規(guī)則的維數(shù))。因此該算法只適用于單維或二維搜索的情況。對(duì)于多維的搜索，需要的存儲(chǔ)空間太大。代表算法有RFC、Hierarchical Cuttings 等。

現(xiàn)有的經(jīng)典算法都是從某一個(gè)特殊的角度提出解決方案，只能解決某一個(gè)方面的問(wèn)題，且其自身也存在一定的缺陷。本文提出了一種全新的基于Hash和AQT的類(lèi)決策樹(shù)包分類(lèi)算法，并闡述了該算法的具體實(shí)現(xiàn)過(guò)程。

1 算法設(shè)計(jì)

IP數(shù)據(jù)包通常包含源IP地址、目的IP地址、源端口、目的端口和協(xié)議類(lèi)型(一般稱(chēng)為5元組)，還可能包括TCP標(biāo)志位、服務(wù)類(lèi)型等，在IPv6中還會(huì)使用流標(biāo)簽。包分類(lèi)是基于這些域的多維分類(lèi)算法，不失一般性，本文討論基于5元組的包分類(lèi)算法。不同的域有不同的表示方法。IP地址一般以前綴表示，端口一般用范圍表示，而協(xié)議類(lèi)型一般是某個(gè)精確取值。通過(guò)分析大規(guī)模規(guī)則集的特征，發(fā)現(xiàn)協(xié)議類(lèi)型域只有通配符和有限幾種精確取值，據(jù)此提出一種基于Hash和AQT的類(lèi)決策樹(shù)IP數(shù)據(jù)包分類(lèi)算法。

該算法思想如下：首先根據(jù)協(xié)議類(lèi)型域的值將規(guī)則集劃分為若干個(gè)子集，這樣在每個(gè)子集里需要對(duì)4維IP數(shù)據(jù)包進(jìn)行分類(lèi)，鑒于Hash函數(shù)和AQT算法適合二維分類(lèi)的特點(diǎn)，將這兩個(gè)子集又作了細(xì)分。利用源端口和目的端口不同的取值都很有限的這一特征，構(gòu)造無(wú)沖突哈希函數(shù)。也就是把規(guī)則按照不同的源端口、目的端口劃分成不同的等價(jià)類(lèi)。然后每個(gè)等價(jià)類(lèi)指向一個(gè)兩維的AQT樹(shù)。整個(gè)規(guī)則集按照決策樹(shù)方式排列?；贖ash和AQT算法的類(lèi)決策樹(shù)IP數(shù)據(jù)包分類(lèi)算法的分類(lèi)過(guò)程（見(jiàn)圖1）如下：

① 查找數(shù)據(jù)包的時(shí)候，先要提取出協(xié)議域，根據(jù)協(xié)議類(lèi)型域的值查找到規(guī)則集中的某個(gè)子集；

② 然后根據(jù)源端口和目的端口兩個(gè)域，查找哈希表確定對(duì)應(yīng)的兩維的AQT樹(shù)；

③ 最后按照源IP、目的IP的值沿著AQT樹(shù)的分枝不斷的向底端的葉子結(jié)點(diǎn)靠近，直到葉子結(jié)點(diǎn)為空或者使LC代碼用完，最后得到的最佳規(guī)則就是要找的規(guī)則；

④ 特殊情況下，對(duì)于未知協(xié)議類(lèi)型的數(shù)據(jù)包采用線(xiàn)性查找方式進(jìn)行。

2 算法實(shí)現(xiàn)

2.1 基于協(xié)議類(lèi)型的初始決策

初始決策的構(gòu)造在根據(jù)協(xié)議類(lèi)型劃分得到的子集中進(jìn)行。因?yàn)閰⑴c初始決策構(gòu)造的規(guī)則已經(jīng)由5維降到了4維，并且規(guī)則的數(shù)量也大大減少，即使是比例最大的TCP規(guī)則也不足原有規(guī)則數(shù)量的一半，所以決策s樹(shù)的構(gòu)造過(guò)程大大加快，決策樹(shù)的高度也隨之降低。初始決策構(gòu)造完成后，就可以將IP數(shù)據(jù)流分配到各自協(xié)議的規(guī)則子集中進(jìn)行細(xì)化查找。下面是構(gòu)建基于協(xié)議類(lèi)型的初始決策樹(shù)的代碼：

2.2 基于源端口和目的端口的Hash函數(shù)尋找等價(jià)類(lèi)

（1）Hash函數(shù)的建立

將源端口和目的端口做一個(gè)交叉積，由于這兩個(gè)域不同的取值有限，所以完 全可以避免空間的爆炸問(wèn)題，比較好的解決了多維分類(lèi)Hash函數(shù)空間爆炸使空間 復(fù)雜度過(guò)大的問(wèn)題。假設(shè)源端口和目的端口的不同取值個(gè)數(shù)分別為:S_p和D _p。

（2）基于源端口和目的端口的Hash函數(shù)尋找等價(jià)類(lèi)查找過(guò)程

由上一個(gè)階段已經(jīng)將5維IP數(shù)據(jù)包降為4維數(shù)據(jù)，并且將數(shù)據(jù)包轉(zhuǎn)移到各個(gè)協(xié)議的子判決層上。進(jìn)入子判決層后，利用在源端口、目的端口各種不同的取值都很有限的基礎(chǔ)上。構(gòu)造無(wú)沖突的哈希函數(shù)。也就是把規(guī)則按照不同的源端口、目的端口劃分成不同的等價(jià)類(lèi)。然后每個(gè)等價(jià)類(lèi)指向一個(gè)兩維的AQT樹(shù)。

2.3 基于源IP、目的IP的AQT樹(shù)搜索規(guī)則

由上一步中，已經(jīng)利用源端口、目的端口兩個(gè)域輸入已經(jīng)構(gòu)建好的無(wú)沖突 Hash函數(shù)，然后查找哈希表確定對(duì)應(yīng)的兩維的AQT樹(shù)。再按照源IP、目的IP的值沿著AQT樹(shù)的分枝不斷的向底端的葉子結(jié)點(diǎn)靠近，直到葉子結(jié)點(diǎn)為空或者使LC代碼用完，最后得到的最佳規(guī)則就是要找的規(guī)則。

AQT算法是將二維數(shù)據(jù)解釋為平面空間的矩陣，使用四叉樹(shù)作為其實(shí)現(xiàn)的基本數(shù)據(jù)結(jié)構(gòu)，用遞歸空間分解技術(shù)將分類(lèi)規(guī)則存儲(chǔ)于四叉樹(shù)的結(jié)點(diǎn)中。四樹(shù)中的結(jié)點(diǎn)最多可以有四個(gè)孩子，四個(gè)指針?lè)謩e標(biāo)示為00,01, 10, 11。

3 仿真實(shí)驗(yàn)與算法性能分析

3.1 實(shí)驗(yàn)條件及結(jié)果

為檢測(cè)本文算法性能，本文在普通 PC上進(jìn)行了性能測(cè)試，測(cè)試環(huán)境為P4 1.7 內(nèi)存384 MB。測(cè)試了由ClassBench產(chǎn)生的5維共1000個(gè)規(guī)則集。AQT中的可調(diào)因子α取2。表1為實(shí)驗(yàn)中所選取的1000個(gè)規(guī)則集中的部分實(shí)例。

表1 規(guī)則集實(shí)例

3.2 算法性能分析

本文所提出的基于Hash和AQT的類(lèi)決策樹(shù)IP數(shù)據(jù)包分類(lèi)算法首先要經(jīng)過(guò)1次查表處理基于協(xié)議類(lèi)型的初始決策，而后經(jīng)過(guò)K次訪問(wèn)內(nèi)存進(jìn)行查找無(wú)沖突的Hash函數(shù)，最后沿AQT的分枝不斷下降到達(dá)葉子結(jié)點(diǎn)，最后找到相應(yīng)的規(guī)則。由此可見(jiàn)，AQT決策樹(shù)的樹(shù)深是一個(gè)是個(gè)決定因素，其查找性能主要由決策樹(shù)的樹(shù)深決定，平均性能由決策樹(shù)的平均樹(shù)深決定，最差性能由決策樹(shù)的最大樹(shù)深決定。時(shí)間性能上來(lái)看， Hash函數(shù)時(shí)間性能為O(K)，AQT時(shí)間性能為O(N2)。因此本文算法的復(fù)雜度為O(1 +K1+N2)。其中K為訪問(wèn)Hash函數(shù)訪問(wèn)內(nèi)存數(shù)，N2為規(guī)則數(shù)，搜索時(shí)間測(cè)試見(jiàn)圖2。

從空間性能測(cè)試(見(jiàn)圖3)來(lái)看，1位的協(xié)議類(lèi)型所占空間基本可以忽略不計(jì)，而2維的目的端口和源端口是利用Hash函數(shù)來(lái)查找的，因此這部分空間O(N1)相對(duì)來(lái)說(shuō)也較小，其中N1是規(guī)則數(shù)。剩下的2維源IP和目的IP是由AQT算法來(lái)實(shí)現(xiàn)的，這部分的空間性能為O(αW1)，W1為IP地址的長(zhǎng)度，α為可調(diào)因子。因此本文算法的總空間性能就是O(N1+αW1)。

圖2 搜索時(shí)間測(cè)試

圖3 空間性能測(cè)試

更新時(shí)間性能來(lái)看，初始的協(xié)議類(lèi)型的初始決策容易，更形主要是在后續(xù)的2維Hash函數(shù)更新和2維AQT決策樹(shù)更新上面。2維Hash函數(shù)更新性能為O(1)，2維AQT決策樹(shù)更新性能為其中N2為規(guī)則數(shù)，α為可調(diào)因子。因此，算法的更新性能為其中N2為AQT算法的IP規(guī)則數(shù)，α為可調(diào)因子。各部分算法比較見(jiàn)表2所示。

表2 Hash、AQT和本文算法性能比較

表2中N,K為總的規(guī)則數(shù)和查找內(nèi)存次數(shù)；W為總長(zhǎng)度；而N1,N2,W1,K1都是各部分的規(guī)則數(shù)、長(zhǎng)度和次數(shù)；其中N＞N1，N＞N2，W＞W(wǎng)1和W＞W(wǎng)2。

4 結(jié)語(yǔ)

本文算法是在協(xié)議類(lèi)型域有限的基礎(chǔ)上實(shí)現(xiàn)初始分類(lèi)決策，不僅繼承了Hash算法優(yōu)秀時(shí)間性能、AQT算法優(yōu)秀的空間性能和更新性能，而且克服了原有的Hash算法和AQT算法不易應(yīng)用于多維分類(lèi)等不足，將Hash函數(shù)、AQT算法與決策樹(shù)有機(jī)結(jié)合起來(lái)[5-10]。通過(guò)實(shí)驗(yàn)和性能分析得出，本文算法最大化的提高了時(shí)間性能、空間性能。

[1] Simone M,Giancarlo C,Riccardo B,et al. A Low-complexity Packet Classification Algorithm for Multiple Description Video Streaming over IEEE802.11E Networks Image Processing[C]//ICIP 15th IEEE International Conference. USA:ICIP, 2008:3072-3075.

[2] 江朝勇.IP數(shù)據(jù)包分類(lèi)算法的研究[D]. 重慶:重慶郵電大學(xué), 2006.

[3] 錢(qián)萌,董小明.基于統(tǒng)計(jì)決策樹(shù)的包分類(lèi)算法[J].華東理工大學(xué)學(xué)報(bào):自然科學(xué)版,2008,34(03):432-435.

[4] Phang S Y, Lee H J, Lim H. Design and Implementation of V6GEN and V6PCF: A Compact IPv6 Packet Generator and a New Packet Classification Framework for IPv6[C]//Convergence and Hybrid Information Technology, 2008. ICCIT'08. Third International Conference on 2008.Busan:Pongseo Univ.,2008:38-43.

[5] 余磊. IP包分類(lèi)算法研究[D].重慶:重慶郵電大學(xué), 2007.

[6] 戴雪龍，王永綱，張萬(wàn)生.并行層壓縮樹(shù)包分類(lèi)算法[J].中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào),2006,36(03):297-300.

[7] 周曉飛,楊靜宇 姜文瀚.核最近鄰?fù)拱诸?lèi)算法[J].中國(guó)圖象圖形學(xué)報(bào),2007,12(07):1209-1222.

[8] 甘利杰.路由器中的包分類(lèi)算法研究[J].計(jì)算機(jī)科學(xué),2006, 33(11):54-57.

[9] 關(guān)愛(ài)芳.網(wǎng)絡(luò)處理器中包分類(lèi)引擎設(shè)計(jì)[D].西安:西北工業(yè)大學(xué),2007.

[10] 劉鐸.快速包分類(lèi)算法的研究[D].合肥:中國(guó)科學(xué)技術(shù)大學(xué).2006.