Fang Yu and Randy H. Katz

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-04-1316
March 2004

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/CSD-04-1316.pdf

Today's packet classification systems are designed to provide the highest priority matching result, e.g., the longest prefix match, even if a packet matches multiple classification rules. However, new network applications, such as intrusion detection systems, require information about all matching results. We call this the multi-match classification problem. In several complex network applications, multi-match classification is usually the first step followed by other processing that is dependent on the classification results. Therefore, classification should be even faster than line rate. Pure software solutions cannot support such applications due to their slow speeds.

In this paper, we present a solution with Ternary Content Addressable Memory (TCAM), which produces multi-match classification results with only one TCAM lookup and one SRAM lookup per packet -- about ten times fewer memory lookups than pure software solutions. In addition, we present a scheme to remove the negation format in rule sets, which can save up to 95% of TCAM space than the straight-forward solution. We show that using the pre-processing scheme presented in the paper, header processing for SNORT rule set can be done with one TCAM and one SRAM lookup using a 135KB TCAM.

BibTeX citation:

@techreport{Yu:CSD-04-1316,
    Author = {Yu, Fang and Katz, Randy H.},
    Title = {Efficient Multi-Match Packet Classification with TCAM},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2004},
    Month = {Mar},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/5589.html},
    Number = {UCB/CSD-04-1316},
    Abstract = {Today's packet classification systems are designed to provide the highest priority matching result, e.g., the longest prefix match, even if a packet matches multiple classification rules. However, new network applications, such as intrusion detection systems, require information about all matching results. We call this the multi-match classification problem. In several complex network applications, multi-match classification is usually the first step followed by other processing that is dependent on the classification results. Therefore, classification should be even faster than line rate. Pure software solutions cannot support such applications due to their slow speeds. <p>In this paper, we present a solution with Ternary Content Addressable Memory (TCAM), which produces multi-match classification results with only one TCAM lookup and one SRAM lookup per packet -- about ten times fewer memory lookups than pure software solutions. In addition, we present a scheme to remove the negation format in rule sets, which can save up to 95% of TCAM space than the straight-forward solution. We show that using the pre-processing scheme presented in the paper, header processing for SNORT rule set can be done with one TCAM and one SRAM lookup using a 135KB TCAM.}
}

EndNote citation:

%0 Report
%A Yu, Fang
%A Katz, Randy H.
%T Efficient Multi-Match Packet Classification with TCAM
%I EECS Department, University of California, Berkeley
%D 2004
%@ UCB/CSD-04-1316
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/5589.html
%F Yu:CSD-04-1316