Method and system for skipping over group(s) of rules based on skip group rule

摘要

A method and corresponding system for providing a skip group rule feature is disclosed. When a search for a key matches a skip group rule in a group of prioritized rules, the search skips over rules having priorities lower than the skip group rule and the search continues to a next group. A convenient example of a compiler rewrites the lower priority rules by subtracting the skip group rule from them. The subtraction includes subtracting range, exact-match, mask, and prefix fields. The rewritten rules appear to a search processor as typical rules. Beneficially, the search processor requires no additional logic to process a skip group rule, skip over lower priority rules, and go on to search a next group of rules. Advantageously, this approach enables any number of skip group rules to be defined allowing for better classification of network data.

主权项

1. A method for forcing a search processor to skip over rules within a group of rules, the method comprising:
in a compiler provided with a set of rules for matching a key, the set of rules divided into groups, each group being prioritized with respect to each other and each rule within each group being prioritized with respect to each other, and the set of rules including at least one skip group rule; rewriting rules belonging to a same group as the skip group rule and having priorities lower than the skip group rule, the lower priority rules being rewritten based on the skip group rule such that in response to matching a key to the skip group rule, a search processor skips over the skip group rule and the lower priority rules; providing the rewritten rules to the search processor; wherein rewriting the lower priority rules includes subtracting the skip group rule from each of the lower priority rules, each lower priority rule being rewritten with a respective subtracted rule as one or more rewritten rules; wherein subtracting includes, given the skip group rule including a field having a first bitmask and each of the lower priority rules including a corresponding field having a second bitmask, for each second bitmask, inverting the first bitmask and intersecting the inverted first bitmask with a subject second bitmask to form an third bitmask, and including the third bitmask in a rewritten rule; wherein intersecting the inverted first bitmask with the subject second bitmask includes, bit-by-bit:
intersecting a don't-care bit of the inverted first bitmask with a don't-care bit of the subject second bitmask yields a don't-care bit in the third bitmask;intersecting a don't-care bit with a value bit yields the value bit in the third bitmask:intersecting a value bit with an equal value bit yields the value bit in the third bitmask; andintersecting a value bit with an unequal value bit yields the third bitmask having a null value.