Research On Algorithms For Fast Packet Classification

Packet classification is a key technology of next generation routers and firewalls. It is one of the hottest topics, and research on the problem is significant.Several representative classification algorithms are introduced in this paper, with discussing which applications they are suitable for. Researches on classification are done on two major threads, algorithmic and architectural. Firstly, a new structure of content-addressable memory is presented, which supports multi-dimension range match and is named multi-dimension range CAM with MDR-CAM for sort, and its partition of dimensions is flexible. The results of theoretic analysis show that the algorithms can be directly implemented on MDR-CAMs, with the time complexity 0(1) and space complexity O(n).Then, a dynamic multi-dimensional hardware algorithm for a network application on routers with several advancements is proposed. The algorithm takes decision tree with each leaf storing a small group of rules as data structure for fast lookup, bounds the worst-case classification time by calculating the maximum number of rules in one small group by the depth of the leaf and the maximum available classification time, supports quick update and reduces the use of temp memory by employing a double link whose length is restricted to renew the decision tree, and can be implemented on FPGA with the optimization of decision tree and a simple memory management strategy. The results of simulation show that the algorithm can classify about 2.5 mega packet headers per second on 50MHz search clock with the worst-case classification time C_sum=34 clock and the space complexity 0(n).