Patent ID: 7793344

Claim:
A method for identifying redundant rules, said method comprising: receiving a sequence of rules from a network device; generating an effective rule set for one of said rules by incorporating said one rule into an upward partial packet decision diagram (PDD); determining whether or not said effective rule set is empty; in a determination that said effective rule set is empty, classifying said one rule as an upward redundant rule among said sequence of rules; determining whether or not every rule within another effective rule set of another one of said rules is consistent with a downward partial PDD; in a determination that every rule within said another effective rule set of said another one rule is consistent with said downward partial PDD, classifying said another one rule as a downward redundant rule among said sequence of rules; and in a determination that not every rule within said another effective rule set of said another one rule is consistent with said downward partial PDD, incorporating said another one rule into said downward partial PDD.