A Sub-Tuple-Partition-Based Fast Two-Dimensional Packet Classification Algorithm

Packet classification is important for network applications such as firewalls, intrusion detection, and differentiated services. There are a lot of research papers about the packet classification. The algorithms based on tuple space firstly presented by Srinivasan have a common problem: the matched rules can not be located in which tuples they are by preprocessing. So it makes their average lookup performance unstable. For two-dimensional packet classification, a new regulation to partition the tuple into some sub-tuples and a new algorithm for two-dimensional packet classification are presented. The sub-tuple based algorithm has an advantage of locating the matched rule's tuple through the result of three independent one-dimensional lookups. So the sub-tuple-based algorithm can increase lookup speed and get stable lookup performance.