Packet classification is concerned with categorizing packets into traffic aggregates according to some configurable set of rules and apply some collective action to the aggregates’ packets. It is a fundamental ingredient in essentially any network functionality today, from the elementary, like Internet packet forwarding, to the complex, like firewalls, OpenFlow switches, or load-balancers. Packet classification must be done for all packets received by a device, preferably at line rate, and, what is more, over possibly hundreds of thousands of rules. This makes efficient hardware and software implementations extremely difficult, or may in fact inhibit any sorts of fast implementation whatsoever.
In the first two quarters of the SW-TCAM project, we have studied the question of how to boost software-based packet classification performance by exploiting data level parallelism built into every modern CPU. We have proposed a new classifier decomposition scheme, whereas a huge and complex classifier is disassembled into a set of smaller and simpler classifier modules, substantially curtailing the complexity of rule matching by reducing the lookup semantics at each module to quasi-exact matching and permitting to do lookups across multiple modules simultaneously.
In this report, we give a mathematical analysis on the decomposability of packet classifiers. We show that the problem is NP-complete even in a minimalistic setting using the notion of Rule Dependence Graphs. Then we show a method to estimate the expected number of parallel modules in a decomposition over a random classifier model and we show empirically that the estimate gives robust results in a variety of settings.
Rétvári Gábor, tudományos főmunkatárs, BME Távközlési és Médiainformatikai Tanszék, retvari@tmit.bme.hu
Gulyás András, egyetemi adjunktus, BME Távközlési és Médiainformatikai Tanszék, gulyas@tmit.bme.hu
Kőrösi Attila, tanszéki mérnök, BME Távközlési és Médiainformatikai Tanszék, korosi@tmit.bme.hu
A kutatási beszámoló letölthető innen (PDF)
2017. január 18.