Multiple Decision Tree Algorithm for Packet Classification

Multiple dimension packet classification is an enabling function for many Internet applications, such as network security, network monitoring, quality of service, flow routing, etc. It is difficult to develop a packet classification algorithm that is efficient in both space and time. Based on the observation that there are only a few possible values for the protocol field in the classifier, a Multiple Decision Tree (MDT) algorithm is proposed. This algorithm is suitable for both software and hardware implementation, and is applicable for IPv6 in theory. When MDT is implemented with hardware, the multiple tree can be searched in parallel and pipeline can be used to search within a specific tree, thus the search complexity of MDT is O(1). With advantages in preprocessing time, memory consumption, and search time, MDT can be used to improve the widely used HiCuts and HyperCuts algorithms.