Method and apparatus encoding a rule for a lookup request in a processor

• US 9,596,222 B2
• Filed: 08/02/2012
• Issued: 03/14/2017
• Est. Priority Date: 08/02/2011
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Goyal, Rajan, Billa, Satyanarayana Lakshmipathi, Bouchard, Gregg A., Lund, Gregory E.
• Primary Examiner(s): CHIANG, JASON
• Application Number:
  US13/565,389
• Publication Number:
  US 20130036477A1
• Time in Patent Office: 1,685 Days
• Field of Search: 726/27, 726/13
• US Class Current: 1/1
• CPC Class Codes: G06F 11/203 using migration
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 12/0207 with multidimensional access, e.g. row/column, matrix
• CPC Class Codes: G06F 12/04 Addressing variable-length words or parts of words
• CPC Class Codes: G06F 12/06 Addressing a physical block of locations, e.g. base addressing, module addressing, memory dedication G06F12/08 takes precedence
• CPC Class Codes: G06F 12/0623 for memory modules
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning
• CPC Class Codes: G06F 13/16 for access to memory bus G06F13/28 takes precedence
• CPC Class Codes: G06F 13/1642 with request queuing
• CPC Class Codes: G06F 3/0629 Configuration or reconfiguration of storage systems
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: G06N 5/027 Frames
• CPC Class Codes: G11C 7/1075 for multiport memories each having random access ports and serial ports, e.g. video RAM
• CPC Class Codes: H04L 43/18 Protocol analysers
• CPC Class Codes: H04L 45/742 : Route cache; Operation thereof
• CPC Class Codes: H04L 45/745 : Address table lookup; Address filtering
• CPC Class Codes: H04L 45/7452 : Multiple parallel or consecutive lookup operations lookup operation involving Bloom filters H04L45/7459
• CPC Class Codes: H04L 47/2441 : relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/39 : Credit based
• CPC Class Codes: H04L 63/0227 : Filtering policies mail message filtering H04L51/212
• CPC Class Codes: H04L 63/0263 : Rule management
• CPC Class Codes: H04L 63/06 : for supporting key management in a packet data network cryptographic mechanisms or cryptographic arrangements for key management H04L9/08
• CPC Class Codes: H04L 63/10 : for controlling access to devices or network resources
• CPC Class Codes: H04L 67/10 : in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 69/02 : Protocol performance
• CPC Class Codes: H04L 69/22 : Parsing or analysis of headers
• CPC Class Codes: Y02B 70/30 : Systems integrating technologies related to power network operation and communication or information technologies for improving the carbon footprint of the management of residential or tertiary loads, i.e. smart grids as climate change mitigation technology in the buildings sector, including also the last stages of power distribution and the control, monitoring or operating management systems at local level
• CPC Class Codes: Y02D 10/00 : Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

In one embodiment, a method includes encoding a key matching rule having at least one dimension by storing in a memory (i) a header of the key matching rule that has at least one header field, and (ii) at least one rule value field of the key matching rule corresponding to one of the dimensions.

Claims

1. A method comprising:

encoding a key matching network security rule having at least one dimension by storing in a memory;

a length of the key matching network security rule;

a header of the key matching network security rule having at least one header field; and

at least one rule value field of the key matching network security rule, a given rule value field of the at least one rule value field corresponding to a given dimension of the at least one dimension, a given header field of the at least one header field including at least one dimension validity field storing a dimension validity value, a given dimension validity field of the at least one dimension validity field corresponding to the given dimension of the at least one dimension of the key matching network security rule, the stored length indicating an end of processing for the key matching network security rule, the dimension validity value stored in the given dimension validity field indicating whether the corresponding given dimension is stored to enable the key matching network security rule to occupy less space in the memory.

2. The method of claim 1, wherein storing the header of the key matching network security rule further includes at least one of:

storing a match type of the key matching network security rule corresponding to the given dimension;

storing the given dimension validity value with a first or second dimension validity value, enabling matching of the given dimension based on the first dimension validity value stored and disabling matching of the given dimension based on the second dimension validity value stored, wherein disabling matching of the given dimension includes masking the given dimension;

storing a rule validity value corresponding to the key matching network security rule, wherein the key matching network security rule is enabled if the rule validity value has a first rule validity value and the key matching network security rule is disabled if the rule validity value has a second rule validity value; and

storing a priority value corresponding to the key matching network security rule, wherein the priority value indicates a priority of the key matching network security rule compared to a plurality of key matching network security rules.

3. The method of claim 2, wherein disabling matching of the given dimension further includes disabling storage of the given rule value field of the key corresponding to the given dimension based on the given dimension validity value of the at least one dimension validity value of the given header field, corresponding to the given dimension, storing the second dimension validity value.

4. The method of claim 2, wherein the match type field includes an indication of at least one of a prefix match, an exact match, a mask match, and a range match, wherein the prefix match is configured to match a beginning of a field of a key to the given dimension, the exact match is configured to exactly match a field of a key to the given dimension, the mask match is configured to match bits of a field of a key corresponding to a mask to the given dimension, and the range match is configured to match a field of a key to a range of values indicated by the given dimension.

5. The method of claim 4, wherein if the match type field includes the indication of the prefix match, the match type field further includes a length to match the beginning of the field of the key.

6. The method of claim 1, further comprising aligning, by adding padding bits to the at least one header field and to the at least one rule value field in the memory, wherein the added padding bits set the at least one header fields and the at least one rule value field to be a multiple of a particular bit length.

7. The method of claim 1, further comprising:

grouping a plurality of key matching network security rules in a chunk; and

aligning the plurality of key matching network security rules within the chunk by padding each of the plurality of key matching network security rules to be a multiple of a particular bit length.

8. The method of claim 7, wherein aligning the plurality of key matching network security rules within the chunk aligns any particular key matching network security rule to be less than the particular bit length after a successive particular bit length.

9. The method of claim 7, wherein each of the key matching network security rules includes a corresponding priority, the method further comprising:

ordering the each of the plurality of key matching network security rules in the chunk according to the corresponding priority.

10. The method of claim 1, wherein the given header field is a first header field, the given rule value field is a first rule value field, the given dimension is a first dimension, and a second header field of the at least one header field corresponds with a second dimension of the at least one dimension, and the second rule value field, according to the second header field, is configured to be compared against a key or a field of the key.

11. The method of claim 10, wherein (i) if the second header field indicates a prefix match, the second rule value field includes a rule value and a bit length, and the rule value is compared against the bit length of the key or the field of the key, (ii) if the second header field indicates a mask match, the rule value field includes the rule value and a bit mask, and the rule value is compared against the particular bits of the key or the field of the key indicated by the bit mask, (iii) if the second header field indicates a range match, the rule value field includes a minimum and a maximum, and the key or the field of the key is determined to be within or out of a range indicated by the minimum and the maximum, and (iv) if the second header field indicates an exact match, the rule value field includes the rule value, and the key or the field of the key is compared against the rule value.

12. The method of claim 1, wherein storing the header of the key matching network security rule further includes:

storing the given dimension validity value with a first or second dimension validity value, enabling matching of the given dimension based on the first dimension validity value stored and disabling matching of the given dimension based on the second dimension validity value stored, wherein disabling matching of the given dimension includes masking the given dimension.

13. An apparatus comprising:

a memory;

a processor configured to encode a key matching network security rule having at least one dimension by storing in the memory;

a length of the key matching network security rule;

a header of the key matching network security rule having at least one header field; and

at least one rule value field of the key matching network security rule, a given rule value field of the at least one rule value field corresponding to a given dimension of the at least one dimension, a given header field of the at least one header field including at least one dimension validity field storing a dimension validity value, a given dimension validity field of the at least one dimension validity field corresponding to the given dimension of the at least one dimension of the key matching network security rule, the stored length indicating an end of processing for the key matching network security rule, the dimension validity value stored in the given dimension validity field indicating whether the corresponding given dimension is stored to enable the key matching network security rule to occupy less space in the memory.

14. The apparatus of claim 13, wherein the processor is further configured to encode the key matching network security rule by storing the header of the key network security matching rule by at least one of:

storing a match type of the key matching network security rule corresponding to the given dimension;

storing the given dimension validity value with a first or second dimension validity value, enabling matching of the given dimension based on the first dimension validity value stored and disabling matching of the given dimension based on the second dimension validity value stored, wherein disabling matching of the given dimension includes masking the given dimension;

storing a rule validity value corresponding to the key matching network security rule, wherein the key matching network security rule is enabled if the rule validity value has a first rule validity value and the key matching network security rule is disabled if the rule validity value has a second rule validity value; and

storing a priority value corresponding to the key matching network security rule, wherein the priority value indicates a priority of the key matching network security rule compared to a plurality of key matching network security rules.

15. The apparatus of claim 14, wherein the processor is further configured to disable storing of the given rule value field of the key corresponding to the given dimension, if the given dimension validity value corresponding to the given dimension is storing the second dimension validity value.

16. The apparatus of claim 14, wherein the match type field includes an indication of at least one of a prefix match, an exact match, a mask match, and a range match, wherein the prefix match is configured to match a beginning of a field of a key to the given dimension, the exact match is configured to exactly match a field of a key to the given dimension, the mask match is configured to match bits of a field of a key corresponding to a mask to the given dimension, and the range match is configured to match a field of a key to a range of values indicated by the given dimension.

17. The apparatus of claim 16, wherein if the match type field includes the indication of the prefix match, the match type field further includes a length to match the beginning of the field of the key.

18. The apparatus of claim 13, wherein the processor is further configured to align, by adding padding bits to the at least one header field and to the at least one rule value field in the memory, wherein the added padding bits set the at least one header fields and the at least one rule value field to be a multiple of a particular bit length.

19. The apparatus of claim 13, wherein the processor is further configured to (a) group a plurality of key matching network security rules in a chunk, and (b) align the plurality of key matching network security rules within the chunk by padding each of the plurality of key matching network security rules to be a multiple of a particular bit length.

20. The apparatus of claim 19, wherein the processor is further configured to align any particular key network security matching rule to be less than the particular bit length after a successive particular bit length.

21. The apparatus of claim 19, wherein each of the key matching network security rules includes a corresponding priority, the processor further configured to order the each of the plurality of key matching network security rules in the chunk according to the corresponding priority.

22. The apparatus of claim 13, wherein the given header field is a first header field, the given rule value field is a first rule value field, the given dimension is a first dimension, and a second header field of the at least one header field corresponds with a second dimension of the at least one dimension, and the second rule value field, according to the second header field, is configured to be compared against a key or a field of the key.

23. The apparatus of claim 22, wherein (i) if the second header field indicates a prefix match, the second rule value field includes a rule value and a bit length, and the rule value is compared against the bit length of the key or the field of the key, (ii) if the second header field indicates a mask match, the rule value field includes the rule value and a bit mask, and the rule value is compared against the particular bits of the key or the field of the key indicated by the bit mask, (iii) if the second header field indicates a range match, the rule value field includes a minimum and a maximum, and the key or the field of the key is determined to be within or out of a range indicated by the minimum and the maximum, and (iv) if the second header field indicates an exact match, the rule value field includes the rule value, and the key or the field of the key is compared against the rule value.

24. The apparatus of claim 13, wherein the processor is a compiler and the processor is further configured to compile the key matching network security rules in a textual format to a binary format.