Research On TCAM Based Packed Classification

In the past, packet classification performance of security device is the bottleneck of network, which is realized by software. Nowadays, TCAM based high speed packet classification attract a lot of attention, however, the synthesization of communication devices and security devices brings new challenge.Combined with the research and development of Integrated Security Gateway (ISG) in the project "Research and Industrialization of IPv4/IPv6 Unite Network Chip" supported by Mayor Dedicated Research Project of Science and Technology Fruit Translation of Jiangsu Province, this dissertation analyses the current TCAM based high speed packet classification algorithms, then proposes a TCAM based packet classification algorithm for range and a multi match supporting TCAM based packet classification algorithm, at last, designs and implements a packet classification solution for ISG with negation match, range match and multi match. Its main work and contributions are outlined as follows:■Introduces the current packet classification algorithms, and compares them based on time and space complexity and difficulty of engineering implementation, then evaluates the excellence and efficiency of them.■A Hybrid range encoding scheme (HYBRID-RES) is proposed, which encodes range rules by either GRAY based range encoding (GBRE) algorithm or bit vector mapping range encoding (BVMRE) based on the rule's expansion ratio and frequency. The performance analysis and experiment demonstrate that Hybrid-RES can significantly improve TCAM utilization updating complexity.■Develops a multi match algorithm-MWSS (Multi-match With Set Splitting) based on geometric intersection. MWSS fulfill multi match by rule rebuilding and pretty TCAM entry management, and splits rules into multiple groups and performs separate TCAM lookups into these groups, where wire-speed processing is guaranteed. The performance analysis and experiment demonstrate that MWSS can significantly improve TCAM utilization and obtain favorable expansibility, although needs several TCAM lookups.■From the development requirements of ISG and oriented toward ISG features, designs and implements a packet classification solution combining HYBRID-RES and MWSS, which negation match, range match and multi match is completed. Its engineering implementation scheme has been successfully applied to the actual development of ISG.