ACCESS CONTROL LIST PROCESSOR

• US 20060294297A1
• Filed: 06/22/2006
• Published: 12/28/2006
• Est. Priority Date: 06/22/2005
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Netlogic Microsystems Incorporated (Broadcom, Inc.)
• Inventors: Gupta, Pankaj
• Granted Patent: US 7,389,377 B2
• Time in Patent Office: Days
• US Class Current: 711/108
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores

Abstract

An integrated circuit device for processing an access control list. The integrated circuit device includes a first content addressable memory (CAM) including a plurality of CAM blocks to generate respective match indices, each match index indicating a storage location within the corresponding CAM block of an entry that matches a search key. The integrated circuit device further includes a plurality of memory arrays to receive the match indices from the CAM blocks and to output respective lookup values from storage locations indicated by the match indices, each lookup value including information that indicates an action to be taken with respect to a packet used to obtain the search key and information that indicates a priority of the action relative to actions indicated by information in others of the lookup values.

Claims

1. An integrated circuit device comprising:

a first content addressable memory (CAM) including a plurality of CAM blocks to generate respective match indices, each match index indicating a storage location within the corresponding CAM block of an entry that matches a search key; and

a plurality of memory arrays to receive the match indices from the plurality of CAM blocks and to output respective lookup values from storage locations indicated by the match indices, each lookup value including information that indicates an action to be taken with respect to a packet used to obtain the search key and information that indicates a merging operation for merging the action with one or more actions indicated by information in others of the lookup values.

2. The integrated circuit device of claim 1 further comprising a first logic circuit to merge the information included within at least a portion of the lookup values.

3. The integrated circuit device of claim 2 wherein each lookup value includes information that indicates a priority of the action to be taken with respect to the packet relative to actions indicated by information in others of the lookup values.

4. The integrated circuit device of claim 3 wherein the first logic circuit includes circuitry to compare the information that indicates the priority of an action indicated by a first one of the lookup values with information that indicates the priority of an action indicated by a second one of the lookup values and to output either the first one of the lookup values or the second one of the lookup values as a selected lookup value based on whether the priority of the action indicated by the first one of the lookup values exceeds the priority of the second one of the lookup values.

5. The integrated circuit device of claim 2 wherein each of the lookup values additionally includes an identifier value that corresponds to an operation to be conditionally performed with respect to the packet, and wherein the first logic circuit comprises comparison circuitry to compare the identifier value within each of the lookup values with an identifier-selection value to determine the portion of the lookup values.

6. The integrated circuit device of claim 1 further comprising a plurality of logic circuits each to merge the information included within a respective subset of the lookup values.

7. The integrated circuit device of claim 6 wherein the plurality of logic circuits output a plurality of merged values that are fewer in number than the plurality of lookup values.

8. The integrated circuit device of claim 6 wherein the plurality of logic circuits output a plurality of merged values and wherein the integrated circuit device further comprises a second CAM to receive a second search key formed, at least in part, from contents within the plurality of merged values, and to output a index value that indicates a manner of merging at least two of the merged values.

9. The integrated circuit device of claim 1 further comprising a lookup circuit to look up a rule for merging the action with the one or more actions indicated by information in others of the lookup values.

10. The integrated circuit device of claim 9 wherein the lookup circuit comprises circuitry to receive a lookup index that includes at least a portion of the action and at lest a portion of the one or more actions indicated by information in others of the lookup values.

11. The integrated circuit device of claim 9 wherein the lookup circuit comprises a second CAM.

12. The integrated circuit device of claim 11 wherein the lookup circuit further comprises a lookup memory that is indexed based on a match address generated by the second CAM, the lookup memory to store information that indicates a merged action value to be output from the integrated circuit device.

13. A method of operation within an integrated circuit device, the method comprising:

comparing a search key with contents of a plurality of content addressable memory (CAM) blocks in concurrent search operations to generate a plurality of match indices; and

concurrently addressing a plurality of lookup memories using the plurality of match indices to retrieve respective lookup values, each lookup value indicating an action be taken with respect to a packet used to obtain the search key and a merging operation for merging the action with one or more actions indicated by others of the lookup values.

14. The method of claim 13 wherein comparing a search key with contents of a plurality of CAM blocks in concurrent search operations comprises comparing a search key constructed based, at least in part, on one or more header fields within the packet with respective access control lists stored within the plurality of CAM blocks.

15. The method of claim 13 wherein each lookup value further indicates a packet processing feature associated with the action indicated by the lookup value, and wherein the method further comprises merging at least two of the actions associated with matching packet processing features.

16. The method of claim 15 wherein merging at least two of the actions associated with matching packet processing features comprises consolidating the at least two of the actions into a single action based, at least in part, on prioritizing information associated with each of the two actions.

17. The method of claim 13 further comprising:

generating a search key based on selected fields within the lookup values; and

comparing the search key with a plurality of rules for merging the actions indicated by the lookup values.

18. The method of claim 17 further comprising:

identifying a first rule that matches the search key within the plurality of rules for merging the actions;

generating an index that corresponds to the first rule; and

retrieving a merged action value from a location with another lookup memory based on the index that corresponds to the first rule.

19. The method of claim 18 further comprising outputting at least a portion of the merged action value from the integrated circuit device.

20. An integrated circuit device comprising:

a plurality of content addressable memory (CAM) blocks;

a plurality of lookup memories;

means for comparing a search key with contents of the plurality of CAM blocks in concurrent search operations to generate a plurality of match indices; and

means for concurrently addressing a plurality of lookup memories using the plurality of match indices to retrieve respective lookup values, each lookup value indicating an action be taken with respect to a packet used to obtain the search key and a merging operation for merging the action with one or more actions indicated by others of the lookup values.

21. Computer-readable media having information embodied therein that includes a description of an integrated circuit device, the information including descriptions of:

a first content addressable memory (CAM) including a plurality of CAM blocks to generate respective match indices, each match index indicating a storage location within the corresponding CAM block of an entry that matches a search key; and

a plurality of memory arrays to receive the match indices from the plurality of CAM blocks and to output respective lookup values from storage locations indicated by the match indices, each lookup value including information that indicates an action to be taken with respect to a packet used to obtain the search key and information that indicates a merging operation for merging the action with one or more actions indicated by information in others of the lookup values.