IP報(bào)文分類算法研究

李學(xué)鋒

(襄樊學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，湖北 襄樊 441053)

IP報(bào)文分類算法研究

李學(xué)鋒

(襄樊學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，湖北 襄樊 441053)

從報(bào)文分類算法的實(shí)現(xiàn)特征出發(fā)，對(duì)當(dāng)前常用的報(bào)文分類算法進(jìn)行分類評(píng)述，分析了它們的時(shí)間、空間和更新復(fù)雜度以及各分類算法的優(yōu)勢(shì)、存在的不足和適用環(huán)境；最后，就報(bào)文分類問題的研究方向作出展望.

IP報(bào)文分類；時(shí)間復(fù)雜度；空間復(fù)雜度；更新復(fù)雜度

IP報(bào)文分類技術(shù)是交換機(jī)、路由器、防火墻等網(wǎng)絡(luò)設(shè)備必需的關(guān)鍵性基本技術(shù). IP報(bào)文分類算法的優(yōu)劣直接影響到網(wǎng)絡(luò)區(qū)分服務(wù)、基于策略的路由、虛擬專用網(wǎng)、QoS、流量計(jì)費(fèi)等網(wǎng)絡(luò)服務(wù)的性能. 隨著Internet應(yīng)用的不斷擴(kuò)展，網(wǎng)絡(luò)速率不斷提升，出現(xiàn)了許多新型的網(wǎng)絡(luò)應(yīng)用，許多新應(yīng)用對(duì)網(wǎng)絡(luò)區(qū)分服務(wù)與性能也提出更高的要求. IP報(bào)文分類技術(shù)也隨之成為網(wǎng)絡(luò)研究的一個(gè)熱點(diǎn). 經(jīng)研究，目前已經(jīng)提出了多種IP數(shù)據(jù)包快速分類算法.

1 常見報(bào)文分類算法及分析

目前常見IP報(bào)文分類算法可分成5類：基于基本樹結(jié)構(gòu)的分類算法、基于幾何算法的分類算法、啟發(fā)式分類算法、哈希分類算法、基于硬件的分類算法. 為了方便說明各算法的工作機(jī)制，構(gòu)造了一個(gè)規(guī)則表，每條規(guī)則由二個(gè)域組成，每個(gè)域的長(zhǎng)度為4位，如表1所示.

1.1 基于樹結(jié)構(gòu)的報(bào)文分類算法

基于樹結(jié)構(gòu)的報(bào)文分類算法主要有：一維樹結(jié)構(gòu)算法、分層查找樹算法[1]、集合歸并查找樹算法[2]、網(wǎng)格查找樹算法[2-4]等. 它們的主要特點(diǎn)是通過構(gòu)造一級(jí)或多級(jí)Tries樹，并用Tries樹特性進(jìn)行算法優(yōu)化.

一維樹結(jié)構(gòu)(Radix Tree)算法 它的左分支標(biāo)為‘0’，右分支標(biāo)為‘1’，結(jié)點(diǎn)表示從根到該結(jié)點(diǎn)路徑的位串.前綴為p的規(guī)則存儲(chǔ)在路徑為p的結(jié)點(diǎn)中，例如前綴為0*的規(guī)則存儲(chǔ)在根結(jié)點(diǎn)的左孩子中.

分層查找樹算法(Hierarchical Tries) 它是一維樹結(jié)構(gòu)的改進(jìn)，先對(duì)第一個(gè)域按一維樹結(jié)構(gòu)構(gòu)造一棵樹，然后對(duì)于有規(guī)則的結(jié)點(diǎn)，對(duì)于其上的規(guī)則按一維樹的方式構(gòu)造第二個(gè)域的樹. 每維分類均排列為按比特的搜索樹，并將樹相互連接，算法維數(shù)一般不超過2.

表1 二維分類規(guī)則

圖1 對(duì)應(yīng)于表1的分層查找樹

在圖1中，虛線以上是F1，虛線以下是F2. 時(shí)間復(fù)雜度為W，空間復(fù)雜度為ndW. 其優(yōu)點(diǎn)是簡(jiǎn)單、實(shí)現(xiàn)容易；缺點(diǎn)是查找、更新較慢，規(guī)則數(shù)少，有回溯查找. 例如：對(duì)包(1100，0100)而言，有二條搜索路徑，其中一條在F2域通向R5節(jié)點(diǎn)的路徑不通，因此會(huì)退回到分叉的節(jié)點(diǎn)處，然后沿另一條路徑搜索，最后找到規(guī)則R3.

集合歸并查找樹算法(Set-Pruning tries) 它是對(duì)Hierarchical Tries的改進(jìn)，通過復(fù)制部分樹，可以不回溯搜索，此算法維數(shù)一般不超過2，規(guī)則數(shù)可以比較多. 這種方法是以增大存儲(chǔ)空間來減少查找時(shí)間. 時(shí)間復(fù)雜度為dW，空間復(fù)雜度為nd，

上面圖1經(jīng)過復(fù)制后，結(jié)果則成為圖2所示的結(jié)構(gòu). 其中R3是復(fù)制的.

圖2 對(duì)應(yīng)于表1的集合歸并查找樹

圖3 對(duì)應(yīng)于表1的網(wǎng)絡(luò)查找樹

網(wǎng)格查找樹算法(Grid-of-Tries) 如圖 3所示，該算法由華盛頓大學(xué)的 Srinivasan等提出，通過改進(jìn)Set-Pruning tries算法，刪除集合剪枝樹中復(fù)制的子樹，而保留被復(fù)制的子樹，在被刪子樹的父結(jié)點(diǎn)中增加一個(gè)標(biāo)有‘0’或‘1’的轉(zhuǎn)移指針，用于指向保留的子樹. 將復(fù)制功能通過指針實(shí)現(xiàn)，節(jié)約了空間. 具體的算法參見文獻(xiàn)[5]. 這種算法既解決了回溯查找的問題，又解決了集合歸并樹的空間增長(zhǎng)問題. 目前在VPN和多播轉(zhuǎn)發(fā)中應(yīng)用較為廣泛. 空間復(fù)雜度為Wd-1，時(shí)間復(fù)雜度為ndW. 但是規(guī)則動(dòng)態(tài)更新效率差，特別是引入轉(zhuǎn)向指針后使得快速插入和刪除過濾規(guī)則變得更加困難.

該算法雖然通過構(gòu)造多維空間的層次 tries，也可使用于多維分類，但是要犧牲時(shí)間和空間復(fù)雜度. 所以該算法常只用于二維分類.

1.2 基于幾何空間的報(bào)文分類算法

基于幾何算法的報(bào)文分類算法主要有：Cross-Producting算法[6]、AQT算法[7]、FIS算法[7]等. 它們的主要特點(diǎn)是針對(duì)規(guī)則的前綴分布，按照0l序列的排列不同，將規(guī)則分為不同的等價(jià)類.

交叉乘積算法(Cross-Producting) 它是一種適合任意維數(shù)的流分類算法，其主要思想是將d維分解成d個(gè)一維的查找，并將分解的結(jié)果通過交叉相乘的方法建立一張查找表. 從算法的空間復(fù)雜度可知，Cross-Produeting算法只適合于小規(guī)則集的場(chǎng)合. 此外，Cross-Produeting是一個(gè)靜態(tài)算法，因?yàn)槊扛乱粭l規(guī)則，其范圍集都會(huì)發(fā)生變化，從而導(dǎo)致每次更新都必須重建交叉乘積表. 該算法的時(shí)間復(fù)雜度為O(dW)，空間復(fù)雜度為O(Nd).

AQT算法 該算法由貝爾實(shí)驗(yàn)室的Buddhikot和華盛頓大學(xué)的Suri等提出，使用過濾器和數(shù)據(jù)包查找空間定位的原理，將查找空間作為整個(gè)四叉樹的根節(jié)點(diǎn).并對(duì)空間進(jìn)行遞歸劃分，得到四個(gè)方向的子空間，作為根節(jié)點(diǎn)的四個(gè)子節(jié)點(diǎn)，直到找到匹配過濾器的最小正方形(二維情況中). 在建立四叉樹的過程中引入了過濾器集、相交過濾器集的概念，并使用面積比較，這就使得算法實(shí)現(xiàn)較為復(fù)雜.后來提出利用空間定位代碼來構(gòu)造四叉樹的方法，使得實(shí)現(xiàn)與查找變得簡(jiǎn)便. 此算法具有O(N)的空間復(fù)雜度，最壞情況下有O(aW)的時(shí)間復(fù)雜度. 此算法只適用于二維情況.

圖4 對(duì)應(yīng)于表1的AQT算法的查找樹

FIS算法 貝爾實(shí)驗(yàn)室的Feldman和Muthukrishman提出該算法，通過改進(jìn)SegmentTree(利用規(guī)則之間的覆蓋關(guān)系構(gòu)造Fat Incest Segment tree)，允許通過調(diào)整樹的層數(shù) L，犧牲空間來換取較快的匹配速度. 其時(shí)間復(fù)雜度為O((L+1)W)，空間復(fù)雜度為O(L*NL+1/L). 該算法一般用于二維分類，其時(shí)間復(fù)雜度和空間復(fù)雜度與樹的層數(shù)相關(guān)，并隨規(guī)則數(shù)目的增加而增長(zhǎng).

1.3 啟發(fā)式報(bào)文分類算法

基于啟發(fā)的IP數(shù)據(jù)包分類算法有RFC算法[8]、HiCuts算法[9]等. 它們的主要特點(diǎn)是利用規(guī)則的某些特性來構(gòu)造查找數(shù)據(jù)結(jié)構(gòu)，從而形成查找入口，加快查找速度.

RFC(Recursive Flow Classification，遞歸流分類)算法 其主要思想是把報(bào)文分類問題視作報(bào)文頭的S位到T位的classID之間的一個(gè)映射，T=logN 且T<

RFC算法是一種速度較快的常用分類算法 它對(duì)一個(gè)報(bào)文的分類分為多個(gè)階段實(shí)現(xiàn)，充分利用硬件流水線技術(shù)，具有很高的吞吐量；主要缺點(diǎn)是存儲(chǔ)需求大，不能用于大型數(shù)據(jù)庫，不支持過濾規(guī)則的快速動(dòng)態(tài)更新，預(yù)處理時(shí)間較長(zhǎng).

智能層次切分算法(Hierarchical Intelligent Cuttings) HiCuts是1999年由斯坦福大學(xué)的Pankaj Gupta博士和Nick McKeown教授提出的一種靈活的報(bào)文分類算法，基本思想是以每個(gè)報(bào)頭域?yàn)橐粋€(gè)層次，將報(bào)文空間逐層等距分組，生成報(bào)文分類決策樹. 當(dāng)報(bào)文到達(dá)時(shí)，遍歷決策樹找到一個(gè)與之匹配的存儲(chǔ)少量規(guī)則的葉結(jié)點(diǎn)，再使用線性查找算法，找到最佳匹配.

圖5 對(duì)應(yīng)于表1的空間切分

圖6 對(duì)應(yīng)于表1的Hicuts樹

HiCuts算法在規(guī)則表達(dá)能力、分類速度和空間占用上與其它算法相比具有明顯的優(yōu)勢(shì)，但是在某些情況下會(huì)出現(xiàn)空間膨脹與樹的平衡問題. 文獻(xiàn)[10]針對(duì)上面的問題提出了改進(jìn)的方法.

1.4 哈希報(bào)文分類算法

針對(duì)報(bào)文分類的哈希分類算法(Hash算法)可以分為沖突哈希報(bào)文分類算法和無沖突哈希報(bào)文分類算法二類. 常用的有沖突的Hash算法用于多維IP包分類，由于規(guī)則的比特?cái)?shù)很長(zhǎng)，所以要將大量規(guī)則映射到一個(gè)較小的空間，沖突率非常高，從而導(dǎo)致查找和更新時(shí)間不確定，影響了算法的性能. 無沖突哈希查找算法的基本思想是將多維分類算法轉(zhuǎn)化為二維分類算法，基于源/目的端口和協(xié)議三域交叉組合情況較少，利用這三個(gè)域構(gòu)造無沖突函數(shù)，而對(duì)于IP地址部分仍采用其他分類方法. 因此，無沖突Hash算法一般作為多維IP包分類算法中的一部分，不是完整意義上的Hash算法，無法完全具備Hash算法的優(yōu)點(diǎn)，算法預(yù)處理過程復(fù)雜、對(duì)內(nèi)存需求較大、支持的匹配規(guī)則集有限.

文獻(xiàn)[11]中提出的一種哈希樹的分類算法，時(shí)間復(fù)雜度為O(n+1)，空間復(fù)雜度為O(n*N+2N).

1.5 基于硬件的報(bào)文分類算法

基于硬件的算法，具有最快的分類時(shí)間，但需要增加一個(gè)容量為dNW(w為每一維的長(zhǎng)度)的TCAM存儲(chǔ)器，由于這種存儲(chǔ)器價(jià)格高，耗電量大，不能直接支持范圍匹配，因而對(duì)規(guī)則數(shù)量、規(guī)則維數(shù)和每維寬度的可擴(kuò)展性均較差，只能用于較小的數(shù)據(jù)包分類問題.

2 各類IP分類算法性能綜合比較

上述各IP綜合算法的綜合比較如表2所示.

表2 各類IP算法性能綜合比較

3 總結(jié)與展望

IP報(bào)文分類算法的性能主要受處理速度、存儲(chǔ)空間、規(guī)則維數(shù)(d)、長(zhǎng)度(W)、更新難度、可擴(kuò)展性和移植性等因素影響，每一種算法往往只能在某一方面具有優(yōu)勢(shì). 隨著網(wǎng)絡(luò)帶寬的增加和用戶對(duì)網(wǎng)絡(luò)服務(wù)多樣性需求的增長(zhǎng)，對(duì) IP報(bào)文分類算法也必將提出新的要求：IP報(bào)文分類算法能提供更高的分類速率；IP報(bào)文分類算法盡量不受或少受規(guī)則個(gè)數(shù)N、維數(shù)d和匹配長(zhǎng)度W等參數(shù)影響；更好的可擴(kuò)展性和移植性.

[1] GUPTA P, MCKEOWN N. Algorithms for packet classification[J]. IEEE Network Special Issue, 2001, 15(2): 24-32.

[2] SRINIVASAN V, VARGHESE G, SURI S, et al. Fast and scalable: ayer four switching[C]//Proc. of ACM SIGCOMM. Vancouver:[s.n.],1998.

[3] 張 李, 涂曉東, 何 誠(chéng). 流分類技術(shù)研究[J]. 電子科技大學(xué)學(xué)報(bào), 2004, 33 (6): 678-681.

[4] 單 征, 趙榮彩, 張 錚. 報(bào)文分類算法研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2005(7): 149-152.

[5] 孫 毅, 劉 彤, 蔡一兵, 等. 報(bào)文分類算法研究[J]. 計(jì)算機(jī)應(yīng)用研究, 2007, 24 (4): 5-11.

[6] 葉滿谷. 基于FPGA的高速流分類算法研究[D]. 西安: 西安電子科技大學(xué)碩士論文, 2008.

[7] 張慶宏. 高性能包分類算法研究[D]. 西安: 西安電子科技大學(xué)碩士論文, 2008.

[8] GUPTA P, MCKEOWN N. Packet classification on multiple fields[C]//proc. of ACM SIGCOMM. Cambridge:[s.n.],1999.

[9] GUPTA P, MCKEOWN N. Packet classification using hierarchical Intelligent cuttings[J]. IEEE Micro, 2000, 20(1): 34-41.

[10] 龔 儉, 魏 薇, 周 鵬. 適用于GIDS報(bào)文分類的P-HiCuts算法[J]. 哈爾濱工業(yè)大學(xué)學(xué)報(bào), 2008, 40(3): 448-452.

[11] 殷 科, 鄧亞平, 唐 紅. 基于Hash_tree的多維IP包分類算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2005(32): 123-125.

Research on IP Packet Classification Algorithm

LI Xue-feng
(School of Mathematical and Computer Sciences, Xinagfan University, Xinagfan 441053, China)

According to their implementation features, this paper divided IP packet classification algorithms usually used into different types and described them one by one in detail. It also gives the time complexity, space complexity, update complexity of the algorithms. It summarized the advantages, disadvantages as well as suitable application environments of different kinds of packet classification algorithms and prospected the future research issues on packet classification problem.

IP packet classification; Time complexity; Space complexity; Update complexity

TP393

A

1009-2854(2010)08-0038-04

2010-07-02

李學(xué)鋒(1968— )，男，湖北隨州人，襄樊學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院講師.

陳 丹)