| Author | Kogan, Kirill; Nikolenko, Sergey I.; Rottenstreich, Ori; Culhane, William; Eugster, Patrick |
|---|
| Date | 2014 |
|---|
| Type | Conference Proceedings |
|---|
| Abstract | Efficient packet classification is a core concern for network services. Traditional multi-field classification approaches, in both
software and ternary content-addressable memory (TCAMs), entail tradeoffs between (memory) space and (lookup) time. TCAMs
cannot efficiently represent range rules, a common class of classification rules confining values of packet fields to given ranges. The
exponential space growth of TCAM entries relative to the number
of fields is exacerbated when multiple fields contain ranges. In
this work, we present a novel approach which identifies properties
of many classifiers which can be implemented in linear space and
with worst-case guaranteed logarithmic time and allows the addition of more fields including range constraints without impacting
space and time complexities. On real-life classifiers from Cisco
Systems and additional classifiers from ClassBench [7] (with real
parameters), 90-95% of rules are thus handled, and the other 5-
10% of rules can be stored in TCAM to be processed in parallel. |
|---|
| Isbn | 978-1-4503-2836-4 |
|---|
| Serie | SIGCOMM '14 |
|---|
| In | Proceedings of the 2014 ACM conference on SIGCOMM, p.15-26 |
|---|
| Publisher | ACM |
|---|
| Partn | TUD-CS-2014-1097 |
|---|
| Url | https://tubiblio.ulb.tu-darmstadt.de/id/eprint/98211 |
|---|
