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

• US 9,275,336 B2
• Filed: 12/31/2013
• Issued: 03/01/2016
• Est. Priority Date: 12/31/2013
• Status: Expired due to Fees

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Goyal, Rajan, Bullis, Kenneth A.
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): Misir, Dave
• Application Number:
  US14/145,374
• Publication Number:
  US 20150186781A1
• Time in Patent Office: 791 Days
• Field of Search: 706/14, 706/47
• US Class Current: 1/1
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/04 Inference or reasoning models

Abstract

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.

Claims

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; and

intersecting a value bit with an unequal value bit yields the third bitmask having a null value.

2. The method of claim 1 wherein each rule includes at least one field and wherein subtracting includes subtracting, on a field-by-field basis, the skip group rule from each of the lower priority rules.

3. The method of claim 1 wherein a group of rules includes a first skip group rule and a second skip group rule;

and

wherein subtracting includes subtracting the first skip group rule from each of the lower priority rules and subtracting the second skip group rule from each of the lower priority rules having priorities lower than the second skip group rule.

4. The method of claim 1, wherein subtracting further includes, given the skip group rule including a field having a first range and each of the lower priority rules including a corresponding field having a second range, for each lower priority rule, subtracting the first range from a respective second range and including the subtracted range in a rewritten rule.

5. The method of claim 4, wherein the subtracted range includes a first sub-range and a second sub-range, the first sub-range and second sub-range being included in a first rewritten rule and a second rewritten rule.

6. The method of claim 4, wherein the first range and second range each includes one value.

7. The method of claim 1 wherein inverting the first bitmask includes for each value bit in the first bitmask, creating a mask value by:

inverting a subject value bit; and

setting remain bits to don'"'"'t-care bits; and

or'"'"'ing the mask values and yielding the inverted first bitmask value.

8. The method of claim 1 wherein the first bitmask and the second bitmask are prefixes in which don'"'"'t-care bits are the least significant bits.

9. The method of claim 1 wherein rewriting includes determining whether the skip group rule and a lower priority rule overlap;

and rewriting the lower priority rule as it is.

10. The method of claim 9 wherein, in an event, the determination is the skip group rule and lower priority rule do not overlap, writing the lower priority rule without change.

11. The method of claim 1 further comprising coalescing two or more rewritten rules into a coalesced rule.

12. A system for forcing a search processor to skip over rules within a group of rules, the system comprising:

a memory having computer executable instructions thereupon;

at least one interface for receiving 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, the set of rules including at least one skip group rule;

a compiler, comprising one or more processors, coupled to the memory and the at least one interface, the computer executable instructions when executed by the compiler cause the compiler to;

rewrite 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;

provide the rewritten rules to the search processor;

wherein the compiler rewrites the lower priority rules by 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 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, the compiler subtracts by 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 the compiler intersects the inverted first bitmask with the subject second bitmask includes, bit-by-bit, by;

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; and

intersecting a value bit with an unequal value bit yields the third bitmask having a null value.

13. A tangible non-transitory computer-readable storage medium having computer readable instructions stored therein for forcing a search processor to skip over rules within a group of rules, which when executed by 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, the set of rules including at least one skip group rule, cause the compiler to:

rewrite 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;

provide the rewritten rules to the search processor;

wherein the compiler rewrites the lower priority rules by 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 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, the compiler subtracts by 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 the compiler intersects the inverted first bitmask with the subject second bitmask includes, bit-by-bit, by;

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; and

intersecting a value bit with an unequal value bit yields the third bitmask having a null value.