CGFE: Efficient Range Encoding for TCAMs

High-performance packet classification is essential for a wide range of fundamental network functions, including access control, firewalls, and advanced programmable network applications. Ternary content addressable memory (TCAM) is heavily used for packet classification due to its impressive performance but it is size-limited, expensive, and power-intensive. Since TCAM requires special encoding for ranges in packet classifiers, minimizing the encoding size is essential. Classical methods such as DIRPE and SRGE work well for different types of ranges and have different limitations. We present the chunked Gray fence encoding (CGFE), a novel encoding that combines the advantages of DIRPE's fence encoding and Gray code reflectivity in SRGE, achieving the best of both worlds. CGFE reduces the number of TCAM entries needed for range-based packet classifiers, improving TCAM efficiency and lowering energy consumption. We prove that CGFE uses the same or smaller number of TCAM entries than both DIRPE and SRGE for every possible range, reducing the number of ternary strings up to 2× in theory and, as we show in a comprehensive practical evaluation, by 40.8% and 9.3% on average, respectively, for rules with two 16-bit range fields.