Leveraging Parallelism for Multi-dimensional Packet Classification on Software Routers

We present a software-based solution to the multi-dimensional packet classification problem which can operate at high line speeds; e.g., in excess of 10 Gbps, using high-end multicore desktop platforms available today. Our solution, called Storm, leverages a common notion that a subset of rules are likely to be popular over short durations of time. By identifying a suitable set of popular rules one can significantly speed up existing software-based classification algorithms. A key aspect of our design is in partitioning processor resources into various relevant tasks, such as continuously computing the popular rules based on a sampled subset of traffic, fast classification for traffic that matches popular rules, dealing with packets that do not match the most popular rules, and traffic sampling. Our results show that by using a single 8-core Xeon processor desktop platform, it is possible to sustain classification rates of more than 15 Gbps for representative rule sets of size in excess of 5-dimensional 9000 rules, with no packet losses. This performance is significantly superior to a 8-way implementation of a state-of-the-art packet classification software system running on the same 8-core machine. Therefore, we believe that our design of packet classification functions can be a useful classification building block for Route Bricks-style designs, where a core router might be constructed as a mesh of regular desktop machines.