A packet classification approach for ternary content-addressable memory using domain transformation

A novel algorithm using domain transformation, called DTRM, is proposed to solve the range expansion problem of ternary content-addressable memory (TCAM), in which the rules containing range fields have to be represented by multiple TCAM entries. Firstly, the number of encoding bits of 2k-1 needed in the database independent range pre-encoding algorithm is replaced by any value so that the extra bits in TCAM entries can be fully used to encode and to construct a new range domain; Secondly, the relationships among rules are used to design a domain transformation function, and the original domain of each field is transformed to a new domain so that the classifier can be expressed by a small number of TCAM entries. When a packet arrives, the packet header is transformed to the new domain with the corresponding approach, and the transformed result is then compared with all the TCAM entries to get match rules. Simulation results and comparisons with the parallel packet classification algorithm show that the proposed algorithm not only reduces range expansion from 1.6 to 1.21 and increases the storage efficiency from 63% to 82%, but also gains better update performance.