System and method for rule matching in a processor

• US 9,344,366 B2
• Filed: 08/02/2012
• Issued: 05/17/2016
• 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: Bouchard, Gregg A., Goyal, Rajan, Lund, Gregory E.
• Primary Examiner(s): Le, David
• Application Number:
  US13/565,406
• Publication Number:
  US 20130036471A1
• Time in Patent Office: 1,384 Days
• Field of Search: None
• 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 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.

Claims

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.