兩階段式快速封包分類演算法

Fast Packet Classification with a Two-Stage Architecture

謝長志(Chang-Chih Hsieh)

指導教授 ： 王勝德

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2007年)

https://doi.org/10.6342/NTU.2007.01468

摘要

封包分類為路由器、防火牆等網路安全設備核心工作之一，其作用在於使用封包標頭部（packet header) 中傳輸層（Transport Layer) 與網路層（Network Layer) 這兩層的欄位，來決定封包是否符合規則資料庫（rule database) 中的某條規則。而隨著網路軟、硬體設備的普及與進步，傳統適用於小維度、且僅能處理少量封包的分類法則已經漸漸無法負荷，諸如虛擬私人網路(Virtual Private Network)、服務品質保證(Quality of Service) 。如何提供一個有效率且具備實用價值的方法，是一項極為重要的議題。

我們提出一個多維度封包分類的架構，主要分為兩個階段：第一個階段為利用決策樹(Decision Tree)進行初步的搜尋分類，我們將規則資料庫依據規則編號分群，決策樹的葉節點儲存著以位元向量(Bit Vector)表示的群編號，由根節點搜尋至葉節點可以知道封包可能符合哪幾群。第二階段則針對各群中的特定位元組建立位元向量表，透過決策樹葉節點所提供的資訊，我們讀取特定群數中的位元向量表來進行更細部的分類。透過此架構，我們期望能夠在合理的記憶體空間內，有極佳的搜尋效率，由實驗結果得知，我們在記憶體用量以及存取次數上的表現均優於以往傳統的封包分類演算法。

關鍵字

封包分類 ； 位元向量 ； 決策樹 ； 遞迴式智能型切割

並列摘要

Packet classification is one of the most critical functions for network security devices such as routers and firewalls. A packet classifier uses the packet header information to decide if a packet matches a rule in the rule database. As the network wired speed increases, a fast packet classification architecture is required to process the incoming packets.

In this paper, we propose a two-stage packet classification approach. The first stage uses the decision tree to conduct an initial coarse search, which partitions the rule database into groups according to their rule numbers; the leaf of the decision tree stores the group number that is expressed with bit vectors. By searching from root to leaf, we classify the incoming packets into groups. The second stage focuses on building bit vector tables for the specific groups for performing a fine search, which conducts detailed classifications to find out the exact matched rule. Through this structure, we can produce an excellent search engine within reasonable memory storage requirements. From the experiment results, we show that the performance of our method is better than existing packet classification algorithms in the average case.

並列關鍵字

Packet Classification ； Bit Vector ； Decision Tree ； HiCut

參考文獻

[1] J J. V. Lunteren and A. P. J. Engberse, “Multi-field Packet Classification Using Ternary CAM,” In IEEE Electronics Letters, vol. 38, no. 1, pp. 21-23, January 2002.

[2] F. Baboescu and G. Varghese, “Packet Classification for Core Routers: Is there an alternative to CAMs?”, Proceedings of 22nd IEEE Infocom, vol. 1, pp. 53-63, Mar-Apr 2003.

[3] M. H. Overmars and A. F. van der Stappen, “Range Searching and Point Location Among Fat Objects”, Journal of Algorithms, vol. 21 no. 3, pp. 629-656, 1996.

[4] P. Gupta and N. McKeown, “Packet classification using hierarchical. Intelligent cuttings,” IEEE Micro, vol.20, no.1, pp.34–41, Feb. 2000.

[5] SS. Singh, F. Baboescu, G. Varghese and J. Wang, "Packet classification Using Multidimensional Cutting," Proc. ACM SIGCOMM, pp. 213-224, August 2003.