Fast Packet Classification with a Varying Rule Set

Multi-dimensional packet classification is increasingly important for applications ranging from fire-walls to traffic accounting. Fast link speeds, the desire to classify with fine granularity, and the need for agility in a dynamic environment all pose significant challenges for packet classification. We propose an approach that is capable of handling a changing set of classification rules that span multiple fields. Our approach is based on extracting a relatively small set of bits that uniquely identify the packets satisfying each rule. Changes to the rule set are handled in-line via a fast update mode that adds to the rule table, while a background process performs reoptimization of the full rule table less frequently. The classification process can be efficiently implemented using pipelined hardware and supports high packet arrival rate