Scalable Many-Field Packet Classification for Traffic Steering in SDN Switches

Packet classification is a key function for software-defined networking switches. For example, OpenFlow Switch examines up to 15 required fields, against thousands of rules. With the proliferation of new header fields in a ruleset, it becomes a great challenge to design a high performance packet classification solution. In this paper, we present a scalable many-field packet classification algorithm and its prototype implementation on a graphics processing unit (GPU). By exploiting the sparsity of ruleset, our algorithm uses a few effective bits (EB) to divide a large ruleset into multiple subsets with low rule replication for economic memory usage at the offline stage. These EB are chosen based on our selection metrics: wildcard ratio, independence index, and diversity index. Using these EB, our algorithm can quickly filter out the majority rules which do not need to be full-matched to improve the online system performance. Moreover, the choice of EB is adjustable to meet the implementation requirements of varying environments for good performance scalability. Our prototype on a single NVIDIA K20C GPU achieves more than 160 MPPS throughput for 100K 15-field synthetic ruleset.