System for accessing content-addressable memory in packet processor

• US 7,554,978 B1
• Filed: 04/28/2004
• Issued: 06/30/2009
• Est. Priority Date: 03/30/2004
• Status: Active Grant

• Current Assignee: Extreme Networks, Inc.
• Original Assignee: Extreme Networks, Inc.
• Inventors: Parker, David K.
• Primary Examiner(s): Orgad, Edan
• Assistant Examiner(s): Haliyur, Venkatesh
• Application Number:
  US10/834,576
• Time in Patent Office: 1,889 Days
• Field of Search: 370389-469, 709223-249, 711108-126
• US Class Current: 370/389
• CPC Class Codes: H04L 12/56 Packet switching systems
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

Abstract

A system for accessing a content-addressable memory in a packet processing system is described. A register holds a data element having a key field. Logic derives a value of the key responsive to 1) packet processing state data relating to one or more packets undergoing processing by the packet processing system, and 2) the value of this key field. The derived value of the key is presented to the memory. In response, the memory searches for an entry associated with the presented key value. If found, the content value associated with the entry is output. If not found, a signal indicative of a miss condition is output.

Claims

1. A system for accessing a content-addressable memory in a pipelined packet processing system, the memory having a plurality of locations, each associated with a value of a key and a content value, comprising:

a register for holding a data element having a key field, the key field having a value; and

logic for deriving a value of the key responsive to

     1) packet processing state data indicating state of processing of one or more packets undergoing processing by the pipelined packet processing system, and

     2) the value of the key field of the data element held by the register, and presenting the derived value to the memory;

wherein the memory is configured to search for a location associated with the derived value of the key presented to it by the logic, and, if such a location is found, output the content value associated with the location, and, if such a location is not found, outputting a signal indicative of a miss condition;

wherein the packet processing state data comprises a sequence control table index.

2. The system of claim 1 further comprising a second memory holding a plurality of data elements, each having a key field set to a value, wherein the register may be loaded with any of the data elements, thereby varying the value of the key field presented to the memory;

wherein the register is coupled to the logic and the register is coupled to the content-addressable memory.

3. The system of claim 1 wherein the pipelined packet processing system has packet processing state data for each of one or more packets undergoing processing by the pipelined packet processing system, and the logic is configured to derive the value of the key responsive to packet processing state data relating to the packet currently undergoing processing by the pipelined packet processing system.

4. The system of claim 3 wherein the data element held in the register has a command field, the command field having a value, and the content-addressable memory is configured to perform one of several possible predetermined functions responsive to the value of the command field of the data element held in the register.

5. The system of claim 4 wherein the value of the command field of the data element specifies a search or read operation.

6. The system of claim 4 wherein the value of the command field of the data element specifies a write operation.

7. The system of claim 1 wherein the logic is configured to derive a value of the key for presenting to the content-addressable memory by selecting a subset of the packet processing state data responsive to the value of the key field.

8. The system of claim 1 wherein the packet processing state data has a size, and the logic is configured to reduce the size of at least a portion of the state data to form modified state data, and derive a value of the key for presenting to the content-addressable memory from the modified state data and the value of the key field.

9. The system of claim 8 wherein the data element held in the register has one or more reduction fields specifying a first subset of the state data, and the logic includes one or more data structures configured to map the first subset of state data into mapped state data having reduced size, and the logic is configured to select a second subset of the state data, augmented with the mapped state data of reduced size, responsive to the value of the key field.

10. A system for flexibly controlling bandwidth of a pipelined packet processing system comprising:

a content-addressable memory;

at least one packet processor configured to

     1) process in parallel a plurality of packets through at least one pipeline having a plurality of slots for placement of packet data, and

     2) perform one or more processing sets, wherein, during each of the one or more processing sets, the at least one packet processor is configured to perform a first predetermined but programmable number of processing operations (m) on each of one or more of the packets having data stored in the slots of the pipeline, each of the processing operations including at least one access to the content-addressable memory;

at least one host processor configured to direct the at least one packet processor to perform one or more host-related processing operations upon or after the completion of a second predetermined but programmable number of processing sets (r); and

at least one interface through which a user can specify the first (m) and second (r) predetermined but programmable numbers;

wherein m is the number of cycles of processing, and r is the number of processing sets;

wherein the bandwidth of the packet processing system is flexibly controlled through suitable setting of the first (m) and second (r) programmable numbers.

11. The system of claim 10, wherein the at least one host processor is configured to direct the at least one packet processor to perform a third predetermined number (p), equal to one or more, of host-related processing operations upon or after the completion of the second predetermined but programmable number of processing sets (r), and the at least one interface is configured to allow the user to specify the third predetermined but programmable number (p);

wherein p is the number processing operations;

wherein the bandwidth of the packet processing system is flexibly controlled through suitable setting of the first (m) and second (r) and third (p) programmable numbers.

12. A method of accessing a content-addressable memory in a pipelined packet processing system, the memory having a plurality of locations, each associated with a value of a key and a content value, comprising:

in a register, holding a data element having a field, the field having a value;

deriving a value of the key responsive to packet processing state data indicating state of processing of one or more packets undergoing processing by the pipelined packet processing system and the value of the key field of the data element held by the register, and presenting that derived value to the memory; and

in the memory, searching for a location associated with the derived value of the key presented to it, and, if such a location is found, outputting the content value associated with the location, and, if such a location is not found, outputting a signal indicative of a miss condition;

wherein the packet processing state data comprises a sequence control table index.

13. The method of claim 12 further comprising retrieving the data element from a second memory holding a plurality of data elements, each having a key field set to a value;

wherein the register is coupled to the logic and the register is coupled to the content-addressable memory.

14. The method of claim 12 wherein the pipelined packet processing system has packet processing state data for each of one or more of the packets undergoing processing by the pipelined packet processing system, and the deriving step comprises deriving the value of the key responsive to packet processing state data relating to the packet currently undergoing processing by the pipelined packet processing system.

15. The method of claim 12 wherein the deriving step comprises deriving a value of the key for presenting to the content-addressable memory by selecting a subset of the packet processing state data responsive to the value of the key field.

16. The method of claim 12 wherein the packet processing state data has a size, and the deriving step comprises reducing the size of at least a portion of the state data to form modified state data, and deriving a value of the key for presenting to the content-addressable memory from the modified state data and the value of the key field.

17. The method of claim 16 wherein the held data element has one or more reduction fields specifying a first subset of the state data, and the method further comprises mapping the first subset of state data into mapped state data having reduced size, and the deriving step comprises deriving a value of the key for presenting to the content-addressable memory by selecting a second subset of the state data responsive to the value of the key field.

18. A method of flexibly controlling bandwidth of pipelined packet processing comprising:

providing a content-addressable memory;

specifying first (m) and second (r) but programmable numbers through at least one user interface;

processing in parallel a plurality of packets through at least one pipeline having a plurality of slots for placement of packet data;

performing one or more processing sets, wherein, during each of the one or more processing sets, the first predetermined but programmable number of processing operations (m) is performed on each of one or more of the packets having data stored in the slots of the pipeline, each of the processing operations including at least one access to the content-addressable memory; and

performing one or more host-related processing operations upon or after the completion of the second predetermined but programmable number of processing sets (r);

wherein m is the number of cycles of processing, and r is the number of processing sets;

wherein the bandwidth of the packet processing system is flexibly controlled through suitable setting of the first (m) and second (r) programmable numbers.

19. The method of claim 18, wherein the specifying step further comprises specifying a third predetermined but programmable number (p) through the at least one user interface, and the last performing step comprises performing the third predetermined number (p) of host-related processing operations upon or after the completion of the second predetermined but programmable number of processing sets (r);

wherein p is the number of processing operations;

wherein the bandwidth of the Packet processing system is flexibly controlled through suitable setting of the first (m) and second (r) and third (p) programmable numbers.

20. A system for accessing content-addressable memory means in a pipelined packet processing system, the memory means having a plurality of locations, each associated with a value of a key and a content value, comprising:

holding means for holding a data element having a key field, the key field having a value; and

deriving means for deriving a value of the key responsive to

     1) packet processing state data indicating state of processing of one or more packets undergoing processing by the pipelined packet processing system, and

     2) the value of the key field of the data element held by the holding means, and presenting the derived value to the memory means;

wherein the memory means is configured to search for a location associated with the derived value of the key presented to it by the deriving means, and, if such a location is found, output the content value associated with the location, and, if such a location is not found, output a signal indicative of a miss condition;

wherein the packet processing state data comprises a sequence control table index.

21. The system of claim 20 wherein the packet processing state data has a size and the deriving means is configured to reduce the size of at least a portion of the state data to form modified state data, and derive a value of the key for presenting to the content-addressable memory from the modified state data responsive to the value of the key field.

22. The system of claim 21 wherein the data element held in the holding means has one or more reduction fields specifying a first subset of the packet processing state data, and the deriving means in configured to map the first subset of state data into mapped state data having reduced size, and derive a value of the key for presenting to the content-addressable memory by selecting a second subset of the state data, as augmented by the mapped state data of reduced size, responsive to the value of the key field.