李學(xué)鋒

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

IP報文分類算法研究

李學(xué)鋒

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

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

IP報文分類；時間復(fù)雜度；空間復(fù)雜度；更新復(fù)雜度

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

1 常見報文分類算法及分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 基于幾何空間的報文分類算法

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

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

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

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

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

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

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

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

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

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

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

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

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

1.4 哈希報文分類算法

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

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

1.5 基于硬件的報文分類算法

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

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

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

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

3 總結(jié)與展望

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

[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] 張 李, 涂曉東, 何 誠. 流分類技術(shù)研究[J]. 電子科技大學(xué)學(xué)報, 2004, 33 (6): 678-681.

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

[5] 孫 毅, 劉 彤, 蔡一兵, 等. 報文分類算法研究[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報文分類的P-HiCuts算法[J]. 哈爾濱工業(yè)大學(xué)學(xué)報, 2008, 40(3): 448-452.

[11] 殷 科, 鄧亞平, 唐 紅. 基于Hash_tree的多維IP包分類算法[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é)與計算機科學(xué)學(xué)院講師.

陳 丹)