Source: https://patents.google.com/patent/US9275336B2/en
Timestamp: 2018-10-22 10:56:19
Document Index: 406918377

Matched Legal Cases: ['Application No. 13', 'Application No. 13', 'Application No. 13', 'Application No. 13', 'Application No. 13', 'Application No. 13', 'Application No. 13', 'Application No. 14']

US9275336B2 - Method and system for skipping over group(s) of rules based on skip group rule - Google Patents
Method and system for skipping over group(s) of rules based on skip group rule Download PDF
US9275336B2
US9275336B2 US14145374 US201314145374A US9275336B2 US 9275336 B2 US9275336 B2 US 9275336B2 US 14145374 US14145374 US 14145374 US 201314145374 A US201314145374 A US 201314145374A US 9275336 B2 US9275336 B2 US 9275336B2
US14145374
US20150186781A1 (en )
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.
In accordance with an example, a method for forcing a search processor to skip over rules within a group of rules is provided. Given 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 method includes, in a compiler, 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. The method further includes providing the rewritten rules to the search processor.
In accordance with another example, a system for forcing a search processor to skip over rules within a group of rules is provided. The system includes memory having computer executable instructions thereupon and at least one interface 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. The system further includes a compiler coupled to the memory and 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. The compiler further caused to provide the rewritten rules to the search processor.
In accordance with yet another example, a tangible computer-readable storage medium having computer readable instructions stored therein for forcing a search processor to skip over rules within a group of rules is provided. The computer readable instructions 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. The compiler further caused to provide the rewritten rules to the search processor.
In other examples of the method, 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.
In some examples of the method, each rule includes at least one field. In these examples, subtracting includes subtracting, on a field-by-field basis, the skip group rule from each of the lower priority rules.
In other examples of the method, a group of rules includes a first skip group rule and a second skip group rule. In these examples, 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.
In some examples of the method, subtracting 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 second range in a rewritten rule.
In other examples of the method, the subtracted second 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.
In some examples of the method, the first range and second range each includes one value.
In other examples of the method, 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.
In some examples of the method, 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. The method further includes or'ing the mask values to yield the inverted first bitmask value.
In other examples of the method, intersecting the inverted first bitmask with the subject second bitmask includes, bit-by-bit, intersecting a don't-care bit with another don't-care bit 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.
In some examples of the method, the first bitmask and the second bitmask are prefixes in which don't-care bits are the least significant bits.
In other examples of the method, writing includes determining whether the skip group rule and a lower priority rule overlap. The method further includes rewriting the lower priority rule overlap based on the determination.
In some examples of the method, in an event, the determination is the skip group rule and lower priority rule do not overlap, the method includes writing the lower priority rule without change.
Other examples of the method further include coalescing two or more rewritten rules into a coalesced rule.
FIG. 4 is a block diagram of example rule with fields.
FIG. 6 is a block diagram of a set of rules for matching a key divided into groups of prioritized rules including skip group rules.
FIG. 7 is a functional diagram of an example of a compiler rewriting lower priority rules based on a skip group rule.
FIGS. 8A and 8B are a series of diagrams showing an example of subtracting a skip group rule from lower priority rules in two-dimension search space.
FIG. 9A is a diagram of an example of subtracting a skip group rule from a lower priority rule, each rule having one range field.
FIG. 9B is a diagram of an example of subtracting a skip group rule from a lower priority rule, each rule having two range fields.
FIG. 9C is a diagram of an example of subtracting a skip group rule from a lower priority rule, each rule having three range fields.
FIG. 10 is a diagram of an example of subtracting a skip group rule from a lower priority rule, each rule having a prefix field.
FIGS. 11A-11D are a series of diagrams showing an example of coalescing two or more rewritten rules together.
FIG. 12 is a diagram of an example of non-overlapping rules.
FIGS. 13A-13D are diagrams of a range field for a range match, exact-match field for an exact match, prefix field for a prefix match, and mask field for a mask match, respectively.
FIG. 14 is a diagram showing an example of rule with six dimensions.
FIG. 2C is a block diagram 240 illustrating an example embodiment of an access router 108 employing the search processor 202. The access router 108 receives an input packet 250 at an ingress packet processor 242. The ingress packet processor 242 then forwards a lookup request with a packet header of the input packet 250 to the search processor 202. The search processor 202 determines, based on packet header of the lookup request, a forwarding path for the input packet 250 and responds to the lookup requests over the Interlaken interface 252 to the egress packet processor 244. The egress packet processor 244 then outputs the forwarded packet 248 to the network.
As an example, a packet is received by the line car 306 a at the MAC layer 326 a. The MAC layer 326 a sends the packet to the forwarding table 324 a. Then, the packet and appropriate forwarding table information is stored in the local buffer memory 322 a. Based on the determination, the router selects an appropriate line card 306 b, stores the packet and forwarding information in the local buffer memory 322 b of the appropriate line card, and forwards the packet out to the network.
FIG. 4 shows a classifier table 400 including rules for classifying a packet or “key.” As shown, the classifier table 400 contains seven rules R1-R7 each containing two fields, Field-1 110, and Field-2 115. Although the table 400 shows rules being 2-tuple (e.g., containing only two fields), it should be noted that rules may contain n number of fields and be n-tuple. Each rule specifies one or more values (e.g., Internet Protocol (IP) addresses or Layer 4 ports or protocols) in each field, also called a “dimension,” to be matched against a key.
With reference to FIGS. 13A-13D, each dimension of a rule is associated with one of the following types of match: range match, exact-match, prefix match, and mask match. FIG. 13A shows an example of a range field 1300 for a range match. The range field 1300 has a maximum value 1305 and minimum value 1310. The range match determines whether a given key is within the maximum value 1305 and minimum value 1310 as set in the range field 1300. FIG. 13B shows an example of an exact match field 1315 for an exact match. The exact match field 1315 has a value 1320. The exact match determines whether a given key exactly matches the value 1320 as set in the exact match field 1315.
FIG. 13C shows an example of a prefix field 1325 for a prefix match. The prefix field 1325 includes a length 1330 and value 1335. The prefix match determines whether a number of bits, as set by the length 1330, of the value 1335 matches a first set of bits in a given key. For example, given the length 1330 of eight bits, the prefix match matches a first eight bits of a key to the first eight bits of the value 1335. FIG. 13D shows an example of a mask field 1340 for a mask match. The mask field 1340 includes a value 1345 and mask 1350. The mask match determines whether a given set of bits in a key, as indicated by the mask 1350, matches the value 1345. Collectively, the content representing these values, are referred to as “dimension data” of a rule.
FIG. 14 shows an example rule 1400, also known as a “key matching rule,” used to match a key 1405. In this example, the key 1405 is an IPv4 header with the fields as shown. The rule 1400 is a six-tuple rule with six dimensions (dim_0, dim_1, dim_2, dim_3, dim_4, and dim_5). Each of the dimensions contains information used to match one of the fields in the key 1405. For example, the first dimension, dim_0, specifies a prefix match using the first five bits of a 32-bit value given in the dimension. For this prefix match, a search processor (e.g., the search processor 202 of FIG. 2A) compares the first five bits of the IP address in the source IP field with the first five bits of the value in dim_0 (as described above with reference to FIG. 13C) and the search processor responds with a match or no-match response.
Classes specified by the rules may overlap. For instance, one packet may match several rules. In this case, when several rules overlap, an order in which the rules appear in the classifier may determine the relative priority of the rule. In other words, a packet that matched multiple rules belongs to the class identified by the identifier (class ID) of the rule among them that appears first in the classifier. Alternatively, a unique priority associated with a rule may determine its priority, for example, the rule with the highest priority.
FIG. 5 is a block diagram 500 illustrating an example embodiment of a compiler loading rules into a memory structure. A software compiler 504 receives a rule set 502. The software compiler 504 generates a binary format of compiled rules 510. The binary format of compiled rules 510 includes a tree 512, buckets 514 and rules 516. The tree 512 includes nodes 511 a-d, leaf nodes 513 a-b, and a root node 532. Each leaf node 513 a-b of the tree 512 points to one of a set of buckets 514. Within each bucket are bucket entries which contain rule or chunk pointers 518. The rules 516 include chunks of rules 520. A chunk 520 (of rules) can be a sequential group of rules, or a group of rules scattered throughout the memory, either organized by a plurality of pointers or by recollecting the scattered chunk 520 (e.g., using a hash function).
FIG. 6 shows an example set of rules 600 configured using a rule groups feature in which rules are separated into a large number of groups of rules, each containing a small number of rules. The groups are prioritized with group 1 (605 a) having a higher priority than group 2 (605 b) and group 3 (605 c), and group 2 (605 b) having a higher priority than group 3 (605 c). The rules are prioritized within each group, for example, rule R1 has a higher priority than rules R2 and R3, and R2 has a higher priority than rule R3, etc. A key is compared against all the rules in a first group. If the key does not match any rule in the first group, then the key is compared against the rules in a second group and on down the list of groups.
One or more rules in a group are skip group rules (e.g., rules having a skip group flag set). If the key matches a skip group rule, the search within that group stops and moves onto the next group. In the example shown in FIG. 6, rules R2 and R5 are skip group rules. Assume a key matches rules R2, R3, R5, R6, and R7 because the rules overlap. Without a skip group rule feature, rule R2 is matched because the rule has a priority higher than the priorities of rules R3, R5, R6, and R7. With a skip group rule feature, however, matching skip group rule R2 forces the search to skip over the lower priority rules of the group 1 (605 a), viz., rule R3 and the search tries matching rules in the next group, group 2 (605 b). In group 2 (605 b), the key matches rules R5 and R6. But because rule R5 is a skip group rule, the skip group feature forces the search to skip over the other matching lower priority rule of group 2 (605 b) viz. rule R6. The search tries matching rules in the next group, group 3 (605 c). In group 3 (605 c), the key matches rule R7. Because rule R7 is the next highest priority rule to match and is not influenced by any other higher priority skip group rule belonging to group 3 (605 c), rule R7 is the matched rule for this particular key. It may be convenient to call skip group rules as “negative” in that they affect lower priority rules but are never matched themselves.
FIG. 7 shows an example of a compiler 700 for carrying out an approach of providing the skip group rule functionality described above. The compiler includes a rewriting module 705 and interface 710 communicatively coupled to each other as shown. A set of rules for matching a key is provided to the compiler 700, for example the example set of rules 600 of FIG. 6. Again, the set of rules 600 is divided into groups of rules according to the rule group feature described above. The set of rules 600 includes skip group rules R2 and R5.
The rewriting module 705 rewrites rules belonging to a same group as the skip group rule and having priorities lower than the skip group rule. These lower priority rules are rewritten based on the skip group rule such that when a search processor matches a key to the skip group rule, the search processor skips over the lower priority rules and searches a next group of rules. The rewriting module 705 outputs a set of rewritten rules 715 as shown. The interface 710 provides the set of rewritten rules 715 to the search processor to match against a key.
One advantage of the foregoing approach (and its examples described herein) is that the search processor requires no additional logic to process a skip group rule to provide the skip group rule functionality. To the search processor, the rules affected by the skip group rule are typical rules. Advantageously, the approach adds the capability to force the search processor to skip over rules within a group of rules without adding complexity to the search processor. In turn, this keeps the power and size requirements of the search processor unchanged.
Another advantage of the foregoing approach (and its examples described herein) is that a user can define any number of skip group rules as well as any number of groups. This is beneficial because, for example, a service provider can devise a comprehensive access control list (ACL) that is well tailored to the needs of end users. Such capacity and flexibility make this approach more capable than other approaches to providing skip group rule functionality.
For example, a conventional hardware-based approach uses a ternary content-addressable memory or “TCAM.” A TCAM is a hardware device that functions as a fully associative memory. A TCAM cell stores three values: 0, 1, or ‘X,’ which represents a don't-care bit and operates as a per-cell mask enabling the TCAM to match rules containing wildcards, such as a kleene star ‘*.’ In operation, a whole packet header is presented to a TCAM to determine which entry (rule) it matches. However, the complexity of the TCAM hardware has allowed only a limited and inflexible number of skip group rules as well as limited number of groups. Typically, a user can only define one skip group rule.
A convenient example of the compiler 700 rewrites rules with priority lower than a skip group rule by subtracting the skip group rule from each of the lower priority rules. This process is repeated for each group containing a skip group rule, independently. In given group, a skip group rule is subtracted from lower priority rules belonging to that group. The group may contain many rules and, as mentioned above, the skip group rule approach does not put any restriction on a number of rules in a group as well as total number of separate groups in the rules set. Each lower priority rule is rewritten as one or more rewritten rules. For rules having more than one field, the compiler 700 subtracts the skip group rule from each of the lower priority rules on a field-by-field basis. In some examples of the compiler 700 the order in which the compiler 700 processes multiple fields may be selected or processed as they are received. In any case, the order in which the compiler 700 processes multiple fields does not matter.
In the case of a range field, each rule is represented by a minimum value and maximum value. The compiler 700 is provided with a skip group rule including a range field of a first range and lower priority rules each including a corresponding range field of a second range. For each lower priority rule, the compiler 700 subtracts the first range from a respective second range and includes the subtracted second range in a rewritten rule.
FIGS. 8A and 8B show the result of subtracting a skip group rule from lower priority rules in a two-dimensional search space. As shown, group 1 (805) includes rules R1, R2, and R3; and group 2 (810) includes rule R4. Each of the rules is a two-tuple rule having a first range field and a second range field. As shown, the rules are represented, graphically, as two-dimensional boxes. Each of the boxes has an edge representing the first range field and another edge representing the second range field. A black dot 815 represents a key that is matched against the rules.
In this example, rule R2 is a skip group rule for group 1 (805). According to the definition of the skip group rule, a lookup for the key 815 matches rule R2 and then skips the lower priority rules of the group 1 (805), viz., rule R3. The lookup then proceeds to the group 2 (810) and matches rule R4.
FIG. 8B shows the rewritten rules after the subtraction. As shown, rule R2 no longer exists and R3 is trimmed forming rewritten rule R3′. As a result, the lookup for the key 815 matches rule R4.
Examples of rules with range, prefix, and exact-match field types can be represented by an n-dimensional box with a minimum value and maximum value for each field (for an exact-match field, the minimum and maximum values are the same). FIGS. 9A-C show examples of subtracting a skip group rule R2 from a lower priority rule R1, in which each rule has one, two, and three fields, respectively. The results of the subtraction as rewritten rule R1′. (Examples of rules with four or more dimensions are left as an exercise for the reader.)
In some cases, subtracting one box (e.g., the skip group rule R2) from another (e.g., lower priority rule R1) does not necessarily result in a box (e.g., rewritten rule R1′). That is, it may not be possible to represent a subtracted multi-dimensional region as single rule. The result of the subtraction, however, is a shape that can be decomposed into boxes, in which each box can be represented by a single rule. In one case, each subtraction results in twice as many boxes as there are dimensions. FIGS. 9A-C show the rewritten rule R1′ decomposed into two, four, and six rules, respectively. The minimum number of boxes resulting from a subtraction is zero, which happens if the subtracted rule encompasses the other rule. If there is no intersection between a skip group rule and a lower priority rule, the lower priority rule is written as it is without any change.
Conceptually, one can think of the process of decomposing the boxes (i.e., rules) as happening one dimension at a time. In the two-dimensional example above, the compiler 700 (FIG. 7) may process the horizontal dimension (field) first, peeling off the two large side boxes, and then the remaining upper and lower boxes. The compiler 700 (FIG. 7) may just as well process the vertical dimension first. The order in which the compiler processes the dimensions does not matter. Different orders of decomposition generate different sets of boxes that are equivalent. And, thus resulting in a subtracted rule being represented by more than one rule.
There may be more than one skip group rule in a group. Consider an example group of prioritized rules R1, R2, R3, R4, R5, and R6 in which R2 and R4 are skip group rules. The compiler 700 (FIG. 7) subtracts skip group rule R2 from the lower priority rules R3, R4, R5, and R6, and subtracts skip group rule R4 from R5 and R6. The result of the subtraction are rewritten rules R3-R2, R5-R2-R4, and R6-R2-R4, which may be also written as R3-R2, R5-R2, R5-R4, R6-R2, and R6-R4.
For mask fields, each rule is represented as a value/mask pair. In one example of the approach, the subtraction of a mask field of a skip group rule (B) from a mask field of a lower priority rule (A) i.e., A-B, is equivalent to the mask field of the lower priority rule (A) intersected with the inverse of the mask field of the skip group rule (B). The approach is described below with reference to the following example:
mask field of lower priority rule (A)=xxx0 (equivalent to a list of decimal values {0, 2, 4, 6, 8, 10, 12, 14})
mask field of skip group rule (B)=1x0x (equivalent to a list of decimal values {8, 9, 12, 13})
in which, 0 or 1 is a value bit, and x represents a ‘don't-care’ bit.
An inverse of a mask field of a skip group rule cannot always be represented as a single masked value. In that case, the inverse of the mask field of a skip group rule is several masked values or'ed together. To calculate the inverse of the mask field of a skip group rule, for each bit in the value that is a 0 or 1 (not don't-care bit x) create a masked value with that bit inverted and set all other bits to don't-care bit (x). The inverse of the mask field of a skip group rule (B) is an or'ed list of the mask values created thus created (B′).
In the example, from the masked value 1x0x, create masked values 0xxx and xx1x. The inverse of 1x0x is (0xxx or xx1x).
The result of the subtraction, which is the mask field of a lower priority rule (A) intersected with the or'ed list of the mask values created (B′), is calculated by intersecting the mask field of the lower priority rule (A) with each of the mask values from the list (B′) and then or'ing the results. Again, this may be represented as more than a single masked value.
Intersecting the mask field of the lower priority rule (A) with each of the mask values from the list (B′) is done bit-by-bit according to the following:
A don't-care bit intersected with another don't-care bit yields a don't-care bit.
A don't-care bit intersected with a value yields the value.
A value intersected with an equal value yields that value.
A value intersected with an unequal value means the entire intersection is empty.
In the example, intersecting the mask field of the lower priority rule of xxx0 (A) with each of the mask values from the list of 0xxx and xx1x (B′) and then or'ing the results producing a masked field of a rewritten rule (C) is a follows:
C=xxx0 and (0xxx or xx1x)
C=(xxx0 and 0xxx) or (xxx0 and xx1x)
C=0xx0 or xx10
in which the operation “and” represents computing an intersection, as per the above explanation.
The resulting masked field of the rewritten rule (C), 0xx0 or xx10, is equivalent to lists of values {0, 2, 4, 6} or {2, 6, 10, 14}, which is equivalent to a list of values {0, 2, 4, 6, 10, 14}.
For prefix fields, each field is represented as a value/length pair. A convenient example of the compiler processes a prefix field as a special case of a mask field in which the ‘don't-care’ bits are the least significant bits (LSB's). FIG. 10 shows an example of subtracting a prefix field of a skip group rule 100X (decimal equivalent 8 and 9) from a prefix field of the lower priority rule 10XX (decimal equivalent 8, 9, 10, and 11). The don't care bits are the least significant bits in the prefixes. As shown, the result of the subtraction is a prefix field of 101X (decimal equivalent 10 and 11) for the rewritten rule.
FIG. 11A shows an example set of two-tuple rules R1, R2, and R3 each with range fields X and Y. Rule R1 has a higher priority than rules R2 and R3, and rule R2 has a higher priority than rule R3. Rules R1 and R2 are skip group rules.
FIGS. 11B and 11C show an example of the compiler subtracting rule R1 from rule R3 and subtracting rule R2 from rule R3. The results of the subtraction are rewritten rules, including rules R3-A, R3-B, R3-C, R3-D, R3-E, and R3-F.
FIG. 11D shows the compiler coalescing rewritten rules R3-B and R3-E into a coalesced rule R3-G and coalescing rewritten rules R3-D with R3-F into another coalesced rule R3-H. In the example, range field X of the rewritten rule R3-B and the corresponding range field X of the rewritten rule R3-E are combined into one range field X of the coalesced rule R3-G. For example, given a first range field of 1-10 and second range field of 11-20, the compiler combines them into a continuous range field of 1-20. (A similar combination of range fields occurs for the coalesced rule R3-H.) Coalescing rewritten rules is advantageous because it reduces the number of rules stored in memory and, thus, decreases time to lookup rules to match a key.
FIG. 12 shows an example group of rules include rules R1, R2, and R3. Rule R3 has a higher priority than rules R1 and R2, and rule R1 has a higher priority than rule R2. Subtracting rule R1 from rule R2 does not affect rule R2 because rules R1 and R2 do not overlap. A convenient example of the compiler, determines whether a skip group rule and a lower priority rule overlap. The compiler rewrites the lower priority rule based on the determination. When the compiler determines there is no overlap between the skip group rule and lower priority rule, the compiler, in one example, rewrites the lower priority rule as it is. In another example, the compiler leaves the non-lapping lower priority rule unchanged.
In one example, a computer program can be written in any form of programming language, including compiled and/or interpreted languages, and the computer program can be deployed in any form, including as a stand-alone program or as a subroutine, element, and/or other unit in image processor 100 suitable for use in a computing environment to carry out the features and functions of various examples discussed herein. A computer program can be deployed to be executed on one computer or on multiple computers at one site.
Compiler 700 (FIG. 7) may comprise one or more processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and any one or more processors of any kind of digital computer. Generally, a processor receives instructions and data from a read-only memory or a random access memory or both. The elements of a computer may comprise a processor for executing instructions and one or more memory devices for storing instructions and data. Generally, a computer can include, can be operatively coupled to receive data from and/or transfer data to one or more mass storage devices (e.g., a memory module) for storing data (e.g., magnetic, magneto-optical disks, or optical disks). The memory may be a tangible non-transitory computer-readable storage medium having computer-readable instructions stored therein for processing images, which when executed by one or more processors (e.g., compiler 700 of FIG. 7) cause the one or more processors to carry out or implement the features and functionalities of various examples discussed herein.
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:
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 with a value bit yields the value bit in the third bitmask;
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:
US14145374 2013-12-31 2013-12-31 Method and system for skipping over group(s) of rules based on skip group rule Active 2034-07-18 US9275336B2 (en)
US14145374 US9275336B2 (en) 2013-12-31 2013-12-31 Method and system for skipping over group(s) of rules based on skip group rule
US20150186781A1 true US20150186781A1 (en) 2015-07-02
US9275336B2 true US9275336B2 (en) 2016-03-01
ID=53482181
US14145374 Active 2034-07-18 US9275336B2 (en) 2013-12-31 2013-12-31 Method and system for skipping over group(s) of rules based on skip group rule
US (1) US9275336B2 (en)
US20130034100A1 (en) * 2011-08-02 2013-02-07 Cavium, Inc. Lookup front end packet input processor
Moon D. et al., "Bridging the Software/Hardware Forwarding Divide", Technical Report, University of California at Berkeley, 2010. *
Office Action corresponding to United States Patent Application No. 13/565,775, mailed Aug. 26, 2014.
Office Action corresponding to United States Patent Application No. 13/565,775, mailed Feb. 9, 2015.
Office Action corresponding to United States Patent Application No. 13/831,191, mailed Dec. 12, 2014.
Office Action corresponding to United States Patent Application No. 13/831,191, mailed May 21, 2015.
Office Action corresponding to United States Patent Application No. 13/831,232, mailed Nov. 21, 2014.
Office Action corresponding to United States Patent Application No. 13/831,415, mailed Dec. 18, 2014.
Office Action corresponding to United States Patent Application No. 13/831,415, mailed Jun. 4, 2015.
Office Action corresponding to United States Patent Application No. 14/145,918, mailed Aug. 19, 2015.
Yu, F., "High Speed Deep Packet Inspection with Hardware Support", Dissertation-University of California, Berkeley, Fall 2006. *
US20150186781A1 (en) 2015-07-02 application
US20080165783A1 (en) 2008-07-10 Access list key compression
Suri et al. 2003 Compressing two-dimensional routing tables
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:GOYAL, RAJAN;BULLIS, KENNETH A.;REEL/FRAME:032877/0344