A TCAM-based Two-dimensional Prefix Packet Classification Algorithm

作     者：王志恒 刘刚 白英彩 

作者机构：Department of Computer Science & Engineering Shanghai Jiaotong University Shanghai 200030 Department of Computer Science & Engineering Donghua University Shanghai 200051 Department of Computer Science & Engineering Shanghai Jiaotong University Shanghai 200030acket classification (PC) has become the main method to support the quality of service and security of network application. And two-dimeusioual prefix packet classification (PPC) is the popular one. This paper analyzes the problem of ruler conflict and then presents a TCAM-based 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-dimeusional PPC. Compared with other algorithms this algorithm has the least time complexity and less space complexity. 

出 版 物：《Journal of Donghua University(English Edition)》 (东华大学学报（英文版）)

年 卷 期：2004年第21卷第1期

页      面：39-45页

学科分类：11[军事学] 0810[工学-信息与通信工程] 1105[军事学-军队指挥学] 08[工学] 081002[工学-信号与信息处理] 110503[军事学-军事通信学] 

基　　金：Foundation item: supported by Intel Corporation (No. 9078) 

主　　题：Ternary Content Addressable Memory (TCAM ) packet classification algorithm twodimensional prefix packet classification 

摘      要：Packet classification (PC) has become the main method to support the quality of service and security of network application. And two-dimeusioual prefix packet classification (PPC) is the popular one. This paper analyzes the problem of ruler conflict, and then presents a TCAM-based 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-dimeusional PPC. Compared with other algorithms, this algorithm has the least time complexity and less space complexity.