Leveraging Parallelism for Multi-Dimensional Packet Classification on Software Routers

Date Added: Jun 2010
Format: PDF

The authors 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 multi-core desktop platforms available today. The 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 the 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.