A Memory-efficient Multi-dimensional Hardware-specific Algorithm for Packet Classification

作者：Huo Hongwei^*; Ye Mangu; Gao Dongpei

来源：Chinese Journal of Electronics, 2010, 19(4): 634-636.

• Packet classification
• Field-programmable gate array (FPGA)
• Decision tree
• Linear space complexity

The paper presents a memory-efficient multi-dimensional hardware-specific algorithm for fast packet classification The algorithm builds a decision tree in which each leaf node stores a relatively small number of rules The maximum number of rules is determined by the level of a node in the tree and the maximum available searching time so that the worst-case classification time can be bounded The algorithm allows quick updates and has relatively small storage requirements It can be tailored for a Field-programmable gate array (FPGA) implementation using an optimization for the tree and a simple memory management strategy The results show that the algorithm can classify about 2 5M packet headers per second on 50MHz search clock with the worst-case classification time C-sum = 34 clock cycle and the space complexity O(n)

• 出版日期2010-10
• 单位西安电子科技大学