Fast TCAM-Based Multi-Match Packet Classification Using Discriminators

Ternary content addressable memory (TCAM) is a widely used technology for network devices to perform packet classification. TCAM compares a search key with all ternary entries in parallel to yield the first matching entry. To generate all matching entries, either storage or speed penalty is inevitable. Because of the inherit disadvantages of TCAM, including power hungry and limited capacity, the feasibility of TCAM-based multi-match packet classification (TMPC) is thus debatable. Discriminators appended to each TCAM entry have been used to avoid storage penalty for TMPC. We are motivated to minimize speed penalty for TMPC with discriminators. In this paper, a novel scheme, which utilizes unused TCAM entries to accelerate the search performance, is presented. It selectively generates TCAM entries to merge overlapping match conditions so that the number of accessed TCAM entries can be significantly reduced. By limiting the number of generated TCAM entries, the storage penalty is minimized since our scheme does not need extra TCAM chips. We further present several refinements to the search procedure. The experimental results show that our scheme can drastically improve the search performance with extra 10-20 percent TCAM entries. As a result, the power consumption, which correlates to the number of accessed TCAM entries per classification, can be reduced.