System and method for rule matching in a processor

Patent metadata

Field	Value
Publication number	US-9344366-B2
Application number	US-201213565406-A
Country	US
Kind code	B2
Filing date	Aug 2, 2012
Priority date	Aug 2, 2011
Publication date	May 17, 2016
Grant date	May 17, 2016

Abstract

In one embodiment, a system includes a format block configured to receive a key, at least one rule, and rule formatting information. The rule can have one or more dimensions. The format block can be further configured to extract each of the dimensions from the at least one rule. The system can further include a plurality of dimension matching engines (DME). Each DME can be configured to receive the key and a corresponding formatted dimension, and process the key and the corresponding dimension for returning a match or nomatch. The system can further include a post processing block configured to analyze the matches or no matches returned from the DMEs and return a response based on the returned matches or nomatches.

First claim

What is claimed is:

1. A system comprising:
a format block configured to (a) receive a key including one or more bits from a packet, at least one rule for matching the key, and rule formatting information, the at least one rule having at least one rule dimension, the at least one rule dimension including a set of one or more bits from a corresponding rule of the at least one rule, and (b) extract each at least one rule dimension from the at least one rule;
a plurality of dimension matching engines (DMEs), each DME, of the plurality of DMEs, coupled to the format block and configured to receive the key and a corresponding formatted dimension, and process the key and the corresponding formatted dimension for returning a match or nomatch; and
a post processing block configured to analyze the matches or no matches returned from the plurality of DMEs and return a response based on the returned matches or nomatches.

2. The system of claim 1 , wherein the format block includes:
a start block configured to find rule starts, mark invalid or deactivated rules, and pre-calculate terms of the at least one rule dimension;
a middle block configured to remove marked rules, extract rule format from headers, and extract priority from headers;
a tween block configured to calculate rule header end position information and rule dimension end position information; and
a finish block configured to calculate control for the plurality of DMEs.

3. The system of claim 1 , wherein the plurality of DMEs are further configured to match the key to at least one of a range indicated by a minimum and maximum in the corresponding formatted dimension, an exact match indicated by a match value in the corresponding formatted dimension, a prefix match indicated by a prefix length and a match value in the corresponding formatted dimension, and a mask indicated by a bit mask and a match value indicated by the corresponding formatted dimension.

4. The system of claim 1 , wherein the plurality of DMEs further include at least one rule data aligner configured to align bits of a match value of the rule of the corresponding formatted dimension to a particular granularity.

5. The system of claim 1 , wherein the plurality of DMEs further include at least one key data aligner configured to align bits of the key to a particular granularity.

6. The system of claim 1 , wherein the plurality of DMEs further include a match unit to compare the key to the match value of the corresponding formatted dimension.

7. The system of claim 1 , wherein the plurality of DMEs further include a DME buffer unit configured to receive portions of a particular dimension in a buffer over a plurality of clock cycles and reassemble the portions into the particular dimension.

8. The system of claim 1 , wherein the post processing block is further configured to sort multiple responses from the plurality of DMEs for multiple rules and to return a response representing a Boolean-and of the matches or no matches returned from the plurality of DMEs.

9. The system of claim 1 , wherein the format block is further configured to receive the at least one rule by receiving at least one line of data, each line of data having a particular size and each line further storing at least one rule and/or at least one partial rule that occupy the particular size, where the at least one partial rule can continue on a subsequent line of the at least one line or be continued from a previous line of the at least one line.

10. A method comprising:
in a hardware processor:
receiving from a memory, at a format block, a key including one or more bits from a packet, at least one rule for matching the key, and rule formatting information, the at least one rule having at least one rule dimension;
extracting, at the format block, each at least one rule dimension from the at least one rule, the at least one rule dimension including a set of one or more bits from a corresponding rule of the at least one rule;
receiving, at a plurality of dimension matching engines (DMEs), each DME, of the plurality of DMEs, coupled to the format block, the key and a corresponding formatted dimension;
processing, at the plurality of DMEs, the key and the corresponding formatted dimension for returning a match or nomatch; and
analyzing, at a post processing block, the matches or no matches returned from the DMEs and return a response based on the returned matches or nomatches.

11. The method of claim 10 , further comprising:
within the format block:
finding, in a start block, rule starts;
marking, in the start block, invalid or deactivated rules;
pre-calculating, in the start block, terms of the at least one rule dimension;
removing, in a middle block, marked rules;
extracting, in the middle block, rule format from headers and priority from headers;
calculating, in a tween block, rule header end position information and rule dimension end position information; and
calculating, in a finish block, control for the plurality of DMEs.

12. The method of claim 10 , further comprising matching, at the plurality of DMEs, the key to at least one of a range indicated by a minimum and maximum in the corresponding formatted dimension, an exact match indicated by a match value in the corresponding formatted dimension, a prefix match indicated by a prefix length and a match value in the corresponding formatted dimension, and a mask indicated by a bit mask and a match value indicated by the corresponding formatted dimension.

13. The method of claim 10 , further comprising aligning, at a rule data aligner within the plurality of DMEs, bits of a match value of the rule of the corresponding formatted dimension to a particular granularity.

14. The method of claim 10 , further comprising aligning, at a key data aligner within the plurality of DMEs, bits of the key to a particular granularity.

15. The method of claim 10 , further comprising comparing, at a match unit within the plurality of DMEs, the key to the match value of the corresponding formatted dimension.

16. The method of claim 10 , further comprising:
receiving, at a DME buffer unit within the plurality of DMEs, portions of a particular dimension in a buffer over a plurality of clock cycles; and
reassembling, at the DME buffer unit, the portions into the particular dimension.

17. The method of claim 10 , further comprising:
sorting, at the post processing block multiple responses from the plurality of DMEs for multiple rules; and
returning a response representing a Boolean-and of the matches or no matches returned from the plurality of DMEs.

18. The method of claim 10 , wherein receiving the at least one rule includes receiving at least one line of data, each line of data having a particular size and each line further storing at least one rule and/or at least one partial rule that occupy the particular size, where the at least one partial rule can continue on a subsequent line of the at least one line or be continued from a previous line of the at least one line.

Assignees

• Bouchard Gregg A
• Goyal Rajan
• Lund Gregory E
• Cavium Inc

Inventors

• Bouchard Gregg A
• Goyal Rajan
• Lund Gregory E

Classifications

• H04L45/7452

  Multiple parallel or consecutive lookup operations (lookup operation involving Bloom filters H04L45/7459) · CPC title

• H04L43/18 Primary

  Protocol analysers · CPC title

• G06F12/06

  Addressing a physical block of locations, e.g. base addressing, module addressing, memory dedication (G06F12/08 takes precedence) · CPC title

• G06F13/16

  for access to memory bus (G06F13/28 takes precedence) · CPC title

• G06F9/46

  Multiprogramming arrangements · CPC title