基于Hash和AQT的類決策樹包分類算法研究

趙國鋒， 陳群麗

（重慶郵電大學，重慶 400065）

0 引言

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

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

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

1 算法設計

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

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

① 查找數據包的時候，先要提取出協議域，根據協議類型域的值查找到規則集中的某個子集；

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

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

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

2 算法實現

2.1 基于協議類型的初始決策

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

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

（1）Hash函數的建立

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

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

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

2.3 基于源IP、目的IP的AQT樹搜索規則

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

AQT算法是將二維數據解釋為平面空間的矩陣，使用四叉樹作為其實現的基本數據結構，用遞歸空間分解技術將分類規則存儲于四叉樹的結點中。四樹中的結點最多可以有四個孩子，四個指針分別標示為00,01, 10, 11。

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

3.1 實驗條件及結果

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

表1 規則集實例

3.2 算法性能分析

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

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

圖2 搜索時間測試

圖3 空間性能測試

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

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

表2中N,K為總的規則數和查找內存次數；W為總長度；而N1,N2,W1,K1都是各部分的規則數、長度和次數；其中N＞N1，N＞N2，W＞W1和W＞W2。

4 結語

本文算法是在協議類型域有限的基礎上實現初始分類決策，不僅繼承了Hash算法優秀時間性能、AQT算法優秀的空間性能和更新性能，而且克服了原有的Hash算法和AQT算法不易應用于多維分類等不足，將Hash函數、AQT算法與決策樹有機結合起來[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數據包分類算法的研究[D]. 重慶:重慶郵電大學, 2006.

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

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

[7] 周曉飛,楊靜宇 姜文瀚.核最近鄰凸包分類算法[J].中國圖象圖形學報,2007,12(07):1209-1222.

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

[9] 關愛芳.網絡處理器中包分類引擎設計[D].西安:西北工業大學,2007.

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