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 this 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.
The report contains the results of the first evaluation of the proposed scheme and an initial comparison to the Intel DPDK built-in librte_acl classifier library. Our initial results are promising: we provide empirical evidence that even very large classifiers can effectively be decomposed into only a couple of dozen modules (which, again, can be searched in parallel) and we present preliminary runtime performance analysis to show that this may yield improved classification performance when implemented in a real classifier.
Zubor Márton, tanársegéd, BME Matematika Intézet, zuborm@math.bme.hu
A kutatási beszámoló letölthető innen (PDF)
2017. január 18.