Fast Packet Classification with a Two-Stage Architecture
Date Issued
2007
Date
2007
Author(s)
Hsieh, Chang-Chih
DOI
zh-TW
Abstract
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.
Subjects
封包分類
位元向量
決策樹
遞迴式智能型切割
Packet Classification
Bit Vector
Decision Tree
HiCut
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-96-R94921102-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):9fd1c68c6cf639fa8cf9e9ed8ab554e1