Multi-Layer Packet Classification with Graphics Processing Units

The rapid growth of server virtualization has led to widespread use of virtual switches and much interest in speeding-up the performance of these software implemented switches. Furthermore the advent of softwaredefined networking, with its strong reliance on rulebased flow classification, has led to renewed interest in fast multi-dimensional packet classification. Commercial virtual switches like Open vSwitch currently implement software-based packet classification aimed at running on general purpose CPUs. Here, the challenges are due to slow memories and limited parallelism. In this paper we explore the extent to which packet classification can be accelerated using the high parallelism and latency hiding capabilities of Graphic Processing Units (GPUs). Existing packet classification algorithms were not designed for GPUs, and thus only partially exploit a GPU's potential. for benchmarking purposes, we first propose efficient GPU implementations of algorithms curretly implemented in virtual switches - linear search and tuple search. We then design and implement Bloom search, an optimization of tuple search that achieves wire-speed processing for 10 Gbps NICs (with minimum-sized packet) for 128k rules with 512 different wildcard patterns. Finally, we integrate our implementation into Open vSwitch to support packet classification with GPU acceleration and show up to a 60-fole improvement in classification performance.