Multi-rule approach to encoding a group of rules

• US 9,544,402 B2
• Filed: 12/31/2013
• Issued: 01/10/2017
• Est. Priority Date: 12/31/2013
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Worrell, Frank, Goyal, Rajan, Billa, Satyanarayana Lakshmipathi
• Primary Examiner(s): Homayounmehr, Farid
• Assistant Examiner(s): LWIN, MAUNG T
• Application Number:
  US14/145,918
• Publication Number:
  US 20150189046A1
• Time in Patent Office: 1,106 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

A multi-rule approach for encoding rules grouped in a rule chunk is provided. The approach includes a multi-rule with a multi-rule header representing headers of the rules and, in some cases, dimensional data representing dimensional data of the rules. The approach further includes disabling dimension matching of always matching dimensions, responding to an always match rule with a match response without matching, interleaving minimum/maximum values in a range field, interleaving value/mask values in a mask field, and for a given rule of rule chunk, encoding a priority field at the end of dimension data stored for the rule in the multi-rule. Advantageously, this approach provides efficient storage of rules and enables the efficient comparison of rules to keys.

Claims

1. A method for encoding a plurality of key matching rules grouped in a chunk, each of the key matching rules beginning with a header and having at least one dimension, the method comprising:

in a rule encoding engine, communicatively coupled to memory and provided with a chunk of key matching rules, building a multi-rule corresponding to the chunk comprising;

storing in the memory a multi-rule header of the multi-rule, the multi-rule header representing, collectively, a plurality of headers stored one after the other, the multi-rule header being decoded by a rule matching engine in a single decode operation to extract the plurality of headers of the key matching rules, wherein the plurality of headers include values which control the rule matching engine processing of the key matching rules, including dimensions, the rule matching engine formats the key matching rules based on a key and matches the key matching rules against the key to find a match based on the values stored in the plurality of headers.

2. The method of claim 1 wherein storing the multi-rule header of the multi-rule further includes storing, consecutively, a rule validity value for each of the key matching rules of the chunk in which storing a first value for the rule validity value corresponding to a subject key matching rule enables matching of the subject key matching rule, while storing a second value instead of the first value disables matching of the subject key matching rule.

3. The method of claim 2 wherein storing the rule validity values includes, given a key matching rule that always matches, storing a rule validity value having a third value;

and given another key matching rule that never matches, storing a rule validity value having a fourth value instead of the third value.

4. The method of claim 1 wherein storing the multi-rule header of the multi-rule further includes, given key matching rules each having at least one dimension, storing, consecutively, an enable value for each dimension in which storing a first value for the enable value corresponding to a subject dimension enables matching of the subject dimension, while storing a second value instead of the first value disables matching of the subject dimension.

5. The method of claim 4 wherein disabling matching of the subject dimension further includes instructing a decoder to provide an always match dimension result.

6. The method of claim 4 wherein disabling matching of the subject dimension further includes instructing a decoder not to assign a dimension match engine to the subject dimension.

7. The method of claim 4 wherein disabling matching of the subject dimension further includes masking the subject dimension for a decoder.

8. The method of claim 1 wherein storing the multi-rule header of the multi-rule further includes storing, consecutively, a priority value for each of the key matching rules of the chunk in which storing a priority value for subject key matching rule indicates a priority of the subject key matching rule relative to the key matching rules of the chunk.

9. The method of claim 1 wherein the chunk includes two key matching rule.

10. The method of claim 1 further comprising, given a key matching rule having at least one dimension, storing in the memory a value associated with the at least one dimension, the value being stored as dimension data of the multi-rule.

11. The method of claim 10 wherein storing the dimension data of the multi-rule further includes for a given key matching rule of the chunk, storing a priority value at the end of the dimension data stored for the rule in the multi-rule.

12. The method of claim 10 wherein storing the dimension data of the multi-rule includes, given a dimension of the subject key matching rule is a range field with a minimum value and a maximum value, interleaving the minimum value with the maximum value to form an interleaved value;

and

storing in the memory the interleaved value of the range field associated with the subject key matching rule.

13. The method of claim 10 wherein storing the dimension data of the multi-rule includes, given a dimension of the subject key matching rule is a mask field with a value and a mask, interleaving the value with the mask to form an interleaved value;

and

storing in the memory the interleaved value of the mask field associated with the subject key matching rule.

14. A system for encoding one or more a plurality of key matching rules grouped in a chunk, each of the key matching rules including beginning with a header and having at least one dimension, the system comprising:

a memory;

at least one interface for receiving a chunk of key matching rules;

a rule encoding engine communicatively coupled to the memory and the at least one interface, the rule encoding engine configured to build a multi-rule corresponding to the chunk by;

storing in the memory a multi-rule header of the multi-rule, the multi-rule header representing, collectively, a plurality of headers stored one after the other, the multi-rule header being decoded by a rule matching engine in a single decode operation to extract the plurality of headers of the key matching rules, wherein the plurality of headers include values which control the rule matching engine processing of the key matching rules, including dimensions, the rule matching engine formats the key matching rules based on a key and matches the key matching rules against the key to find a match based on the values stored in the plurality of headers.

15. A tangible non-transitory computer-readable storage medium having computer readable instructions stored therein for encoding a plurality of key matching rules grouped in a chunk, each of the key matching rules beginning with a header, which when executed by a rule encoding engine, provided with a chunk in which each key matching rule of the chunk has at least one dimension, cause the rule encoding engine to build a multi-rule corresponding to the chunk by:

storing in memory, communicatively coupled to the rule encoding engine, a multi-rule header of the multi-rule, the multi-rule header representing, collectively, a plurality of headers stored one after the other, the multi-rule header being decoded by a rule matching engine in a single decode operation to extract the plurality of headers of the key matching rules, wherein the plurality of headers include values which control the rule matching engine processing of the key matching rules, including dimensions, the rule matching engine formats the key matching rules based on a key and matches the key matching rules against the key to find a match based on the values stored in the plurality of headers.