基于空間優化的決策樹算法

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

關鍵詞:報文分類；范圍匹配； 規則縮減；規則膨脹

中圖分類號：TP393文獻標志碼：A

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

報文分類在當前Internet中被廣泛地應用于區分服務、高速路由器、網絡QoS、網絡安全等。它是當前防火墻、入侵檢測系統、分組高速路由等網絡應用的基石。

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

1相關研究進展

1）窮盡搜索算法

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

2）決策樹法[3]

這種算法的思想是將規則統一表示成前綴形式，需要將區間匹配轉換成多個前綴匹配來表示，然后對規則空間進行樹型層次劃分。

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

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

4）Tuple space[7] 方法它

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

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

2本文的改進方法

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

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

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

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

b)時間效率和空間效率的矛盾。樹的層數越高，所需要的存儲空間越少，但查找時間越長?？筛鶕眯枰侠碚{節。

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

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

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

2．3空間優化思想描述

對于實際規則庫的觀察，有幾種情況在轉換時極大地浪費空間。具體情形如下：

a）規則1tcpany!20→anyany act1 

由結果看到，應用改進的算法大大減少了空間損耗，并且算法1與改進的算法無沖突。若對于某些區間沒有明顯的效果時，可以用算法1來轉換。 

4結束語

將區間變為前綴表示是很多網絡應用要考慮的問題，如TCAM中空間壓縮、網絡路由對規則的優化等。本文在不改變規則意義的基礎上，通過添補若干規則大幅提高了規則轉換的效率。關于空間壓縮算法的后續問題，即如何對改進后的算法效果進行理論分析、最壞情況分析等，還有待進一步研究。

參考文獻:

[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.

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