A middle ground between CAMs and DAGs for high-speed packet classification

Packet classification is a computationally intensive task that routers need to perform at high speed to implement features such as QoS, access control, and VPNs. A classification rule-set consists of a prioritized set of rules, where each rule is a condition-action pair. Current approaches to classification can be categorized as belonging in one of two extreme categories: (1) an incoming packet is fed to custom hardware which concurrently checks all rules for applicability and returns the action of the highest priority applicable rule; (2) a graph-like data-structure is stored in memory and traversed based on the bits in the incoming packet´s header. Both these approaches suffer from severe limitations: the former uses a large amount of hardware; the latter requires huge amounts of memory to achieve high performance. Our thesis is that the right approach to packet classification lies in the middle. Specifically, we describe an architecture with a small number of hardware-based rule evaluation units operating in parallel. We show that dividing the rule-set across these units so as to make them fit in the hardware available is NP-hard; our primary contribution is a heuristic for doing this division.