趙國鋒， 陳群麗

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

0 引言

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

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

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

1 算法設(shè)計

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

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

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

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

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

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

2 算法實現(xiàn)

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

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

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

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

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

（2）基于源端口和目的端口的Hash函數(shù)尋找等價類查找過程

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

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

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

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

3 仿真實驗與算法性能分析

3.1 實驗條件及結(jié)果

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

表1 規(guī)則集實例

3.2 算法性能分析

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

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

圖2 搜索時間測試

圖3 空間性能測試

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

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

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

4 結(jié)語

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

[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ù)包分類算法的研究[D]. 重慶:重慶郵電大學(xué), 2006.

[3] 錢萌,董小明.基于統(tǒng)計決策樹的包分類算法[J].華東理工大學(xué)學(xué)報:自然科學(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包分類算法研究[D].重慶:重慶郵電大學(xué), 2007.

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

[7] 周曉飛,楊靜宇 姜文瀚.核最近鄰?fù)拱诸愃惴╗J].中國圖象圖形學(xué)報,2007,12(07):1209-1222.

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

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

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