Multi-field range encoding for packet classification in TCAM

Packet classification has wide applications such as unauthorized access prevention in firewalls and Quality of Service supported in Internet routers. The classifier containing pre-defined rules is processed by the router for finding the best matching rule for each incoming packet and for taking appropriate actions. Although many software-based solutions had been proposed, high search speed required for Internet backbone routers is not easy to achieve. To accelerate the packet classification, the state-of-the-art ternary content-addressable memory (TCAM) is a promising solution. In this paper, we propose an efficient multi-field range encoding scheme to solve the problem of storing ranges in TCAM and to decrease TCAM usage. Existing range encoding schemes are usually single-field schemes that perform range encoding processes in the range fields independently. Our performance experiments on real-life classifiers show that the proposed multi-field range encoding scheme uses less TCAM memory than the existing single field schemes. Compared with existing notable single-field encoding schemes, the proposed scheme uses 12% ~ 33% of TCAM memory needed in DRIPE or SRGE and 56% ~ 86% of TCAM memory needed in PPC for the classifiers of up to 10k rules.