JitVector: Just-in-time code generation for network packet classification

Network packet classification plays a pivotal role in packet-switched networks; it is at the heart of many functions including firewalling, QoS routing, and OpenFlow-based switching. However, packet classification is a hard problem, as packets must be classified within a short time frame. Existing classification techniques use sophisticated data structures which are traversed by generic search algorithms - that is, the algorithm is static, while the data structure reflects the configuration of the classifier. In this paper, we propose to break up the strict separation between data structure and algorithm by specializing the algorithm´s implementation on the specific classification rules. We demonstrate the feasibility of our approach by introducing JitVector, which builds upon the well-known bit vector classification algorithm, but generates instance-specific machine code at runtime. In our evaluation, which also includes an integration into the OpenFlow Reference Switch, we show that JitVector achieves significant performance gains over an equivalent generic search scheme.