System and method for reducing flow rules in forwarding tables

Abstract

An initial rule set in a table, such as a packet forwarding table, including a plurality of rules each having a key, an action, and a priority, may be reduced to a reduced rule set. Such reduction may include identifying relationships among the plurality of rules in the initial rule set, reassigning priority to each rule in the initial rule set based on its action and the identified relationships, duplicating all rules from each priority into each lower priority to produce an expanded rule set, and for each priority, replacing one or more of the rules with fewer inclusive rules, thereby producing a reduced rule set. Reduction may further include determining whether to perform additional rule processing on the reduced rule set, removing any redundant rules from the reduced rule set, converting any of the rules meeting a predetermined condition into don't care rules, and for each priority, replacing one or more of the rules in the reduced rule set with fewer inclusive rules.