基于空間優(yōu)化的決策樹算法

摘要：通過增加一些規(guī)則來最終減少規(guī)則轉(zhuǎn)換的冗余問題，并設(shè)計一種算法實(shí)現(xiàn)這種優(yōu)化。在優(yōu)化后的規(guī)則庫、單維上用決策樹方法查找，結(jié)果以位向量的方式存放，保持了算法的高速度，同時有效地節(jié)省了空間。

關(guān)鍵詞:報文分類；范圍匹配； 規(guī)則縮減；規(guī)則膨脹

中圖分類號：TP393文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2007)11-0222-03

報文分類在當(dāng)前Internet中被廣泛地應(yīng)用于區(qū)分服務(wù)、高速路由器、網(wǎng)絡(luò)QoS、網(wǎng)絡(luò)安全等。它是當(dāng)前防火墻、入侵檢測系統(tǒng)、分組高速路由等網(wǎng)絡(luò)應(yīng)用的基石。

報文分類最簡單的形式是網(wǎng)絡(luò)路由，即只根據(jù)網(wǎng)絡(luò)包目的地址來確定下一跳地址。但在很多網(wǎng)絡(luò)應(yīng)用中，有時需要知道報文更多的信息以選擇需要的服務(wù)。一般情況是根據(jù)報文的五元組（即原地址、目的地址、傳輸層協(xié)議及端口）來確定其所屬的流及對應(yīng)的服務(wù)[1，2]。所以分類問題的實(shí)質(zhì)是路由算法問題在多維上的延伸。

1相關(guān)研究進(jìn)展

1）窮盡搜索算法

這是最簡單直觀的方法，對規(guī)則空間中的所有規(guī)則逐一搜索比較，從而找出相匹配的規(guī)則。缺點(diǎn)是速度慢，不能滿足大多數(shù)應(yīng)用的需要。

2）決策樹法[3]

這種算法的思想是將規(guī)則統(tǒng)一表示成前綴形式，需要將區(qū)間匹配轉(zhuǎn)換成多個前綴匹配來表示，然后對規(guī)則空間進(jìn)行樹型層次劃分。

3）多維分解法[4]將多維問題分解為單維解決。

一般在單維上采用成熟的樹型算法，多維上采用bv[5]或abv[6]方法進(jìn)行綜合。

4）Tuple space[7] 方法它

是一種基于空間劃分的方法。根據(jù)規(guī)則的各維長度劃分子空間；然后在子空間中用哈希方法來查找。

5）非精確算法Hash[2]算法首先在預(yù)處理階段建立一個哈希表；然后對報文頭部信息進(jìn)行哈希后作為表的入口地址來查詢對應(yīng)的規(guī)則。

2本文的改進(jìn)方法

決策樹思想是分類中一個比較成熟的方案，也可以與更多的方法配合使用。本文通過對規(guī)則空間進(jìn)行優(yōu)化處理；然后在單維上使用決策樹進(jìn)行查找，多維上用abv聚合方法進(jìn)一步處理結(jié)果。

2．1決策樹算法面臨的問題及解決方法

決策樹方法面臨的問題一般有：

a)一個前綴規(guī)則可能出現(xiàn)在多個子樹中，增大了存儲空間，可以通過把共同的前綴存放在父節(jié)點(diǎn)上以減少空間。

b)時間效率和空間效率的矛盾。樹的層數(shù)越高，所需要的存儲空間越少，但查找時間越長。可根據(jù)應(yīng)用需要合理調(diào)節(jié)。

c)區(qū)間匹配需要轉(zhuǎn)換成前綴匹配。本文提出一種算法來縮減空間，改進(jìn)效率。

2．2空間膨脹問題描述

區(qū)間匹配需要轉(zhuǎn)換成前綴匹配。若直接轉(zhuǎn)換，所耗費(fèi)的空間太大。例如區(qū)間[1，2w-2]轉(zhuǎn)換成前綴表示時為{01*，001*，…，0w-11，10*，110*，…，1w-10}，需要用2w-2條前綴匹配規(guī)則來表示一條區(qū)間匹配規(guī)則[8]；若位寬為16，則需要30條規(guī)則來表示一個范圍匹配規(guī)則；若一個規(guī)則中有兩個這樣的范圍，則最壞情況下需要302條規(guī)則來表示，空間損耗嚴(yán)重。

2．3空間優(yōu)化思想描述

對于實(shí)際規(guī)則庫的觀察，有幾種情況在轉(zhuǎn)換時極大地浪費(fèi)空間。具體情形如下：

a）規(guī)則1tcpany!20→anyany act1 

由結(jié)果看到，應(yīng)用改進(jìn)的算法大大減少了空間損耗，并且算法1與改進(jìn)的算法無沖突。若對于某些區(qū)間沒有明顯的效果時，可以用算法1來轉(zhuǎn)換。 

4結(jié)束語

將區(qū)間變?yōu)榍熬Y表示是很多網(wǎng)絡(luò)應(yīng)用要考慮的問題，如TCAM中空間壓縮、網(wǎng)絡(luò)路由對規(guī)則的優(yōu)化等。本文在不改變規(guī)則意義的基礎(chǔ)上，通過添補(bǔ)若干規(guī)則大幅提高了規(guī)則轉(zhuǎn)換的效率。關(guān)于空間壓縮算法的后續(xù)問題，即如何對改進(jìn)后的算法效果進(jìn)行理論分析、最壞情況分析等，還有待進(jìn)一步研究。

參考文獻(xiàn):

[1]GUPTA P， McKEWON N.Algorithms for packet classification[J]. IEEE Network， 2001，15（2）：24-32.

[2]TAYLOR D E. Survey taxonomy of packet classification techniques[D]. Saint Louis： Wa￣shington University， 2004.

[3]GUPTA P， McKEOWN N.Packet classification using hierarchical intelligent cuttings[C]//Proc of Hot Interconnects. 1999.

[4]TAYLOR D E， TURNER J S. Scalable packet classification using distributed crossproducting of field labels， WUCSE-2004-38[R]. Saint Louis: Department of Computer Science and Engineering，Wa￣shington University， 2004.

[5]LAKSHMAN L， STILIADIS D.High－speed policy－based packet forwarding using efficient multi－dimensional range matching[J].Comput Commun，1998，28(4):203-214.

[6]BABOESCU F， VARGHESE G.Scalable packet classification[C]//Proc of ACM SIGCOMM. San Diego:[s.n.]，2001.

[7]SRINIVASAN V，SURI S，VARGHESE G.Packet classication using tuple space search[C]//Proc of SIGCOMM. 1999.

[8]LIU Huan. Efficient mapping of range classifier into Ternary－CAM[C]//Proc of the 10th Symposium on Hign Performance Interconnects. California:[s.n.]，2002.

[9]YU Fang，KATZ R H. Efficient multi－match packet classification with TCAM[C]//Proc of Hot Interconnects. Stanford:[s.n.]， 2004.

[10]OVERMARS M H， STAPPEN A F van der.Range searching and point location among fat objects[J]. J of Algorithms， 1996，21(3):629-656.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”