MULTI-RULE APPROACH TO ENCODING A GROUP OF RULES

• US 20150189046A1
• Filed: 12/31/2013
• Published: 07/02/2015
• 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
• Granted Patent: US 9,544,402 B2
• Time in Patent Office: Days
• 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 one or more key matching rules grouped in a chunk, 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 headers of the key matching rules.

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 a rule validity value corresponding to a subject key matching rule enables matching of the subject key matching rule and storing a second value different than 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 having a third value;

and given a key matching rule that never matches, storing a rule validity having a fourth value different than 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 and storing a second value different than 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 one 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 key matching rules grouped in a chunk, 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 headers of the key matching rules.

15. A tangible non-transitory computer-readable storage medium having computer readable instructions stored therein for encoding one or more key matching rules grouped in a chunk, 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 headers of the key matching rules.