System and method for storing lookup request rules in multiple memories

• US 10,277,510 B2
• Filed: 08/02/2012
• Issued: 04/30/2019
• 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, Bouchard, Gregg A.
• Primary Examiner(s): Misir, Dave
• Application Number:
  US13/565,271
• Publication Number:
  US 20130036083A1
• Time in Patent Office: 2,462 Days
• Field of Search: None
• 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 data navigation unit configured to navigate through a data structure stored in a first memory to a first representation of at least one rule. The system further includes at least one rule processing unit configured to a) receive the at least one rule based on the first representation of the at least one rule from a second memory to one of the rule processing unit, and b) processing a key using the at least one rule.

Claims

1. A system for processing packets, the system comprising at least one search processor, the at least one search processor including:

a search cluster configured to receive a key from a received packet, the search cluster including an on-chip memory, a tree walk engine (TWE), a bucket walk engine (BWE) and a plurality of rule match engines (RMEs), the at least one search processor configured to use the TWE to navigate, based on the key, through a tree data structure stored in the on-chip memory to a representation of at least one rule stored on a leaf node in the on-chip memory; and

a bucket post processor (BPP), the TWE configured to determine whether the representation (i) points directly to a rule, in which case, the TWE is configured to load the rule from an external memory and provide the rule to the BPP to determine and return a match or no match result of the rule with the key or (ii) points to a bucket with entries pointing to a rule or a chunk of rules, in which case, the BWE is configured to load one or more rules, stored at locations in the on-chip memory pointed to by the bucket, and provide the rules to a given rule match engine (RME) of the plurality of RMEs, the given RME including a plurality of dimension matching engines (DMEs), the plurality of DMEs configured to match dimensions of the one or more rules with the key to enable the RME to determine and return a match or no match result of the one or more rules with the key.

2. The system of claim 1, wherein the representation of the at least one rule is a pointer to an address in the external memory.

3. The system of claim 1, wherein at least one RME of the plurality of RMEs is configured to load the at least one rule from the on-chip memory or the external memory.

4. The system of claim 1, wherein a first RME of the plurality of RMEs is configured to load the at least one rule from the on-chip memory and a second RME of the plurality of RMEs is configured to load the at least one rule from the external memory.

5. The system of claim 1, wherein the representation is a pointer to the bucket, the pointer is a first pointer, and at least one RME of the plurality of RMEs is configured to load the at least one rule from the external memory if the representation is a second pointer to the at least one rule in the external memory.

6. The system of claim 5, wherein the bucket is a first bucket and the at least one RME is further configured to load the at least one rule from the external memory if the representation is a third pointer to a second bucket in the on-chip memory that thereinafter points to the at least one rule in the external memory.

7. The system of claim 1, wherein the given RME is configured to determine and return the match or no match result of the one or more rules with the key based on match results returned from the plurality of DMEs.

8. The system of claim 1, wherein at least one RME of the plurality of RMEs is configured to receive the at least one rule by requesting the at least one rule from the external memory.

9. The system of claim 1, wherein at least one RME of the plurality of RMEs is configured to receive the at least one rule forwarded by the TWE.

10. A method for processing packets, the method comprising:

navigating, based on a key from a received packet, through a tree data structure stored in an on-chip memory to a representation of at least one rule by a tree walk engine (TWE) of a search cluster of a search processor, the representation stored on a leaf node in the on-chip memory, the search cluster including the on-chip memory, the TWE, a bucket walk engine (BWE), and a plurality of rule match engines (RMEs); and

determining, by the TWE, whether the representation (i) points directly to a rule, in which case, the method includes loading, by the TWE, the rule from an external memory and providing the rule to a bucket post processor (BPP) of the search processor to determine and return a match or no match result of the rule with the key or (ii) points to a bucket with entries pointing to a rule or a chunk of rules, in which case, the method includes loading, by the TWE, one or more rules stored at locations in the on-chip memory pointed to by the bucket, and providing the rules to a given rule match engine (RME) of the plurality of RMEs, the given RME including a plurality of dimension matching engines (DMEs), the plurality of DMEs configured to match dimensions of the one or more rules with the key to enable the RME to determine and return a match or no match result of the one or more rules with the key.

11. The method of claim 10, wherein the representation of the at least one rule is a pointer to an address in the external memory.

12. The method of claim 10, further comprising loading the at least one rule from either the on-chip memory or the external memory.

13. The method of claim 10, further comprising loading the at least one rule from the on-chip memory at a first RME of the plurality of RMEs or from the external memory at a second RME of the plurality of RMEs.

14. The method of claim 10, wherein the representation is a pointer to the bucket, the pointer is a first pointer, and the method further comprises loading the at least one rule from the external memory if the representation is a second pointer to the at least one rule in the external memory.

15. The method of claim 14, wherein the bucket is a first bucket and wherein loading the at least one rule further includes loading the at least one rule from the external memory if the representation is a third pointer to a second bucket in the on-chip memory that thereinafter points to the at least one rule in the external memory.

16. The method of claim 10, further comprising determining and returning the match or no match result of the one or more rules with the key from the given RME based on match results returned from the plurality of DMEs.

17. The method of claim 10, further comprising receiving the at least one rule by requesting the at least one rule from the external memory.

18. The method of claim 10, further comprising forwarding the at least one rule from the TWE to at least one RME of the plurality of RMEs.