Method and apparatus for dynamically generating lookup words for content-addressable memories

• US 7,065,083 B1
• Filed: 10/04/2001
• Issued: 06/20/2006
• Est. Priority Date: 10/04/2001
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Oren, Eyal, Belz, David E.
• Primary Examiner(s): Ho, Duc
• Assistant Examiner(s): Nguyen, Phuongchau Ba
• Application Number:
  US09/974,296
• Time in Patent Office: 1,720 Days
• Field of Search: None
• US Class Current: 370/392
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 45/7453 using hashing

Abstract

Methods and apparatus are disclosed for using a programmable lookup word generator to produce a lookup word for use by a content-addressable memory. The programmable lookup word generator includes a profile memory which contains instructions on how to build a particular lookup word. The programmable lookup word generator receives a set of information and possibly other operands typically including a profile selection. Based on the profile selection, a set of instructions is retrieved from the profile memory. Control logic uses this set of instructions to build the lookup word by extracting portions of the received information and other operands and ordering these extracted portions possibly with additional information to build the lookup word. The lookup word is then used by a CAM, typically to classify the received set of information and other operands. In one context, the CAM produces a packet classification indication in a communication or computer system.

Claims

1. A system comprising:

a programmable lookup word generator to receive a set of information and to produce a lookup word, the programmable lookup word generator including;

a profile memory configured to store a set of instructions for generating the lookup word; and

a selection mechanism for selecting portions of the set of information in response to the set of instructions retrieved from the profile memory, the selection mechanism including a matrix of storage elements and shift logic for use in generating the lookup word; and

a content-addressable memory, coupled to the programmable lookup word generator, configured to receive said generated lookup word and to perform a lookup operation based on said generated lookup word in order to generate one or more lookup result indications.

2. The system of claim 1, further comprising a queue coupled to the matrix of storage elements and the content-addressable memory.

3. The system of claim 1, wherein the profile memory is responsive to a profile selection in retrieving the set of instructions used by the selection mechanism;

and wherein the received set of information includes the profile selection.

4. The system of claim 3, wherein the programmable lookup word generator includes a shift logic control unit responsive to the set of instruction for controlling said shift logic.

5. The system of claim 1, wherein the programmable lookup word generator includes a shift logic control unit responsive to the set of instruction for controlling said shift logic.

6. The system of claim 1, wherein the set of information includes information contained in a packet.

7. The system of claim 1, wherein the set of information includes one or more fields from a header of the packet.

8. The system of claim 1, wherein the set of information includes an indication of other information not contained in the packet.

9. The system of claim 1, wherein the content-addressable memory is a binary content-addressable memory.

10. The system of claim 1, wherein the content-addressable memory is a ternary content-addressable memory.

11. A packet switching system including the system of claim 1.

12. A computer system including the system of claim 1.

13. A communications system including the system of claim 1.

14. A router including the system of claim 1.

15. A method for generating a lookup word, the method comprising:

receiving a set of information including a profile identification;

retrieving a set of instructions from a profile memory based on the profile identification;

manipulating the set of information in response to the set of instructions to generate the lookup word, said manipulation including controlling a selection mechanism, the selection mechanism including a matrix of storage elements and shift logic for use in generating the lookup word; and

exporting the lookup word to a content-addressable memory for use by said content-addressable memory in performing a lookup operation to identify one or more content-addressable memory lookup results.

16. The method of claim 15, further comprising programming the profile memory with the set of instructions.

17. The method of claim 15, wherein the set of information includes information related to a packet, and said one or more content-addressable memory results include a packet classification.

18. The system of claim 15, wherein the content-addressable memory is a binary content-addressable memory.

19. The system of claim 15, wherein the content-addressable memory is a ternary content-addressable memory.

20. A system for generating a lookup word, the system comprising:

means for receiving a set of information including a profile identification;

means for retrieving a set of instructions from a profile memory based on the profile identification;

means for manipulating the set of information in response to the set of instructions to generate the lookup word, said means for manipulating the set of information includes a matrix of storage elements and shift logic for use in generating the lookup word; and

means for exporting the generated lookup word to a content-addressable memory for use by said content-addressable memory in performing a lookup operation to identify one or more content-addressable memory lookup results.

21. The system of claim 20, wherein said means for manipulating the set of information includes means for controlling shift logic.

22. The system of claim 20, wherein the set of information includes information related to a packet.

23. The system of claim 20, wherein the content-addressable memory is a binary content-addressable memory.

24. The system of claim 20, wherein the content-addressable memory is a ternary content-addressable memory.