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

Patent metadata

Field	Value
Publication number	US-9596222-B2
Application number	US-201213565389-A
Country	US
Kind code	B2
Filing date	Aug 2, 2012
Priority date	Aug 2, 2011
Publication date	Mar 14, 2017
Grant date	Mar 14, 2017

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.

First claim

What is claimed is:

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 fu

Assignees

• Goyal Rajan
• Billa Satyanarayana Lakshmipathi
• Bouchard Gregg A
• Lund Gregory E
• Cavium Inc

Inventors

• Goyal Rajan
• Billa Satyanarayana Lakshmipathi
• Bouchard Gregg A
• Lund Gregory E

Classifications

• H04L69/02

  Protocol performance · CPC title

• H04L63/06 Primary

  for supporting key management in a packet data network (cryptographic mechanisms or cryptographic arrangements for key management H04L9/08) · CPC title

• Y02B60/142

  Cross-Sectional Technologies · mapped topic

• H04L69/22

  Parsing or analysis of headers · CPC title

• G11C7/1075

  for multiport memories each having random access ports and serial ports, e.g. video RAM · CPC title