SAX-PAC (Scalable And eXpressive PAcket Classification).

Abstract

Efficient packet classification is a core concern for network services. Traditional multi-field classification approaches, in both \nsoftware and ternary content-addressable memory (TCAMs), entail tradeoffs between (memory) space and (lookup) time. TCAMs \ncannot efficiently represent range rules, a common class of classification rules confining values of packet fields to given ranges. The \nexponential space growth of TCAM entries relative to the number \nof fields is exacerbated when multiple fields contain ranges. In \nthis work, we present a novel approach which identifies properties \nof many classifiers which can be implemented in linear space and \nwith worst-case guaranteed logarithmic time and allows the addition of more fields including range constraints without impacting \nspace and time complexities. On real-life classifiers from Cisco \nSystems and additional classifiers from ClassBench [7] (with real \nparameters), 90-95% of rules are thus handled, and the other 5- \n10% of rules can be stored in TCAM to be processed in parallel.