System and method for storing lookup request rules in multiple memories

Patent metadata

Field	Value
Publication number	US-10277510-B2
Application number	US-201213565271-A
Country	US
Kind code	B2
Filing date	Aug 2, 2012
Priority date	Aug 2, 2011
Publication date	Apr 30, 2019
Grant date	Apr 30, 2019

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.

First claim

What is claimed is:

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.

Assignees

• Goyal Rajan
• Bouchard Gregg A
• Cavium Llc

Inventors

• Goyal Rajan
• Bouchard Gregg A

Classifications

• G06F12/04

  Addressing variable-length words or parts of words · CPC title

• G06F12/126

  with special data handling, e.g. priority of data or instructions, handling errors or pinning · CPC title

• G06F9/46

  Multiprogramming arrangements · CPC title

• G11C7/1075

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

• H04L45/745 Primary

  Address table lookup; Address filtering · CPC title