A TCAM-based Two-dimensional Prefix Packet Classification Algorithm

摘要

Packet classification (PC) has become the main method to support the quality of service and security of network application. And two-dimensional prefix packet classification (PPC) is the popular one. This paper analyzes the problem of ruler conflict, and then presents a TCAMbased two-dimensional PPC algorithm. This algorithm makes use of the parallelism of TCAM to lookup the longest prefix in one instruction cycle. Then it uses a memory image and associated data structures to eliminate the conflicts between rulers, and performs a fast two-dimensional PPC.Compared with other algorithms, this algorithm has the least time complexity and less space complexity.