Method and apparatus for determining a longest prefix match in a content addressable memory device

• US 6,892,272 B1
• Filed: 04/23/2002
• Issued: 05/10/2005
• Est. Priority Date: 02/23/1999
• Status: Expired due to Fees

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Netlogic Microsystems Incorporated (Broadcom, Inc.)
• Inventors: Madamala, Ramagopal, Srinivasan, Varadarajan
• Primary Examiner(s): BATAILLE, PIERRE MICHE
• Application Number:
  US10/131,370
• Time in Patent Office: 1,113 Days
• Field of Search: 711/108, 711/212, 711/219, 711/154, 365/49, 365/168, 365/78, 365/80, 365/189.07, 365/230.06, 379/339, 379/392, 380/50, 712/224, 712/244, 712/5, 714/3, 710/266, 710/262, 710/49, 710/48, 710/14
• US Class Current: 711/108
• CPC Class Codes: G11C 15/04 using semiconductor elements

Abstract

A method and apparatus for determining a longest prefix match in a content addressable memory (CAM) device is described. The CAM device includes a CAM array that may be arbitrarily loaded with CIDR addresses that are not prearranged prior to their entry into the CAM device. For one embodiment, the CAM array is a ternary CAM array that includes CAM cells storing CAM data, mask cells storing prefix mask data for the corresponding CAM cells, a CAM match line for indicating a match between a search key and the CAM data (as masked by the prefix mask data), prefix match lines, and prefix logic circuits for comparing the CAM match line with the prefix mask data. The prefix logic circuits determine the longest prefix among the CAM locations that match the search key, regardless of where the matching locations are logically located in the CAM array. The longest prefix is then compared against the prefix mask data stored in the mask cells to determine the location in the CAM array that stores the CIDR address corresponding to the longest prefix. The CAM index or address of the matching CIDR address may then be output from the CAM device. Additionally and/or alternatively, additional or associated data stored at the CAM index may be accessed. The additional or associated data may be, for example, routing information for the stored CIDR address.

Claims

1. A method of determining the location of an entry in one of plurality of depth cascaded content addressable memory (CAM) devices, each CAM device having a plurality of ternary CAM cells, wherein the located entry has the most unmasked bits among the CAM cells of all CAM devices, the method comprising:

determining which locations in each CAM device match comparand data;

determining the largest number of unmasked mask bits among the matching entries in each CAM device; and

comparing the largest numbers of mask bits of each of the CAM devices.

2. A method of operating a content addressable memory (CAM) device, comprising:

writing CAM data into CAM cells of a CAM array;

decoding mask data;

writing the decoded mask data into mask cells of the CAM array;

determining the logical states of a first plurality of match lines in response to comparing comparand data with the CAM data; and

logically comparing the states of the first match lines with the decoded mask data to determine the decoded mask data that has the most unmasked bits.

3. The method of claim 2, further comprising:

comparing the decoded mask data that has the most unmasked bits with the decoded mask data stored in the mask cells; and

determining the logical states of a second plurality of match lines.

4. The method of claim 3, further comprising encoding the logical the logical states of the second plurality of match lines to generate an address in the CAM array associated with the CAM data that matches the comparand data and has associated therewith the decoded mask data that has the most unmasked bits.

5. The method of claim 2, further comprising encoding the decoded mask data that has the most unmasked bits.

6. The method of claim 2, wherein the CAM data comprise Internet Protocol (IP) addresses, and the mask data comprise prefix mask data of the IP addresses.

7. A content addressable memory (CAM) device comprising:

a CAM array having a plurality of CAM cells and a plurality of mask cells, where each mask cell is coupled to a corresponding CAM cell;

cascade logic coupled to the CAM array;

a plurality of first inputs coupled to the cascade logic, the first inputs for receiving first mask input data; and

a first compare circuit coupled to the first inputs for comparing first mask input data with internal mask data.

8. The CAM device of claim 7, further comprising a cascade input coupled to the cascade logic, the cascade input for indicating when the first mask data is valid on the plurality of first inputs.

9. The CAM device of claim 7, further comprising a first plurality of mask outputs coupled to the cascade logic, the first plurality of mask outputs for providing as first mask output data either (i) internal mask data stored in the plurality of mask cells, or (ii) the first mask input data.

10. The CAM device of claim 9, further comprising a cascade output coupled to the cascade logic, the cascade output for indicating when the first mask output data is valid on the mask outputs.

11. The CAM device of claim 9, further comprising a plurality of second inputs coupled to the cascade logic, the plurality of second inputs for receiving second mask input data.

12. The CAM device of claim 11, further comprising a second plurality of mask outputs coupled to the cascade logic, the second plurality of mask outputs for providing as second mask output data either (i) the internal mask data, or (ii) the second mask input data.

13. The CAM device of claim 7, further comprising encoding logic having inputs coupled to receive mask data from the mask cells of the CAM array, and further having outputs coupled to the cascade logic.

14. The CAM device of claim 13, further comprising a register coupled between the CAM array and the encoding logic.

15. The CAM device of claim 7, wherein the cascade logic includes a compare circuit.

16. The CAM device of claim 7, wherein the cascade logic comprises:

a first signal generator for generating a first cascade output signal in response to a first cascade input signal.

17. The CAM device of claim 16, wherein the cascade logic further comprises:

a second signal generator for generating a second cascade output signal in response to a second cascade input signal; and

a second compare circuit for comparing second mask input data with the internal mask data.

18. The CAM device of claim 7, wherein the plurality of first inputs are mask inputs.

19. A system comprising:

a first content addressable memory (CAM) device having;

a first plurality of mask inputs; and

a first plurality of mask outputs; and

a second CAM device comprising;

a first plurality of mask inputs coupled to the first plurality of mask outputs of the first CAM device; and

a first plurality of mask outputs coupled to the first plurality of mask inputs of the first CAM device.

20. The system of claim 19, wherein the first CAM device further includes a second plurality of mask inputs.

21. The system of claim 19, wherein the second CAM device further comprises a second plurality of mask outputs.

22. The system of claim 19, wherein:

the first CAM device further includes;

a first cascade input; and

a first cascade output; and

wherein the second CAM device further comprises a first cascade input coupled to the first cascade output of the first CAM device.

23. The system of claim 22, wherein:

the first CAM device further includes a second cascade input; and

the second CAM device further includes a cascade output coupled to the second cascade input of the first CAM device.

24. The system of claim 19, further comprising:

an instruction bus coupled to the first and second CAM devices;

a comparand bus coupled to the first and second CAM devices; and

a data output bus coupled to the first and second CAM devices.

25. The system of claim 19, wherein the first CAM device comprises:

a CAM array having a plurality of CAM cells and a plurality of mask cells for storing mask data for a corresponding CAM cell; and

cascade logic coupled to the ternary CAM array and the mask inputs and outputs.

26. The system of claim 25, wherein the CAM array further comprises:

a match line;

a plurality of signal lines; and

a plurality of circuits each having a first input coupled to the match line, a second input coupled to receive the mask data, and an output coupled to one of the plurality of signal lines.

27. A content addressable memory (CAM) device comprising:

a ternary CAM array for storing mask data; and

encoding logic for receiving and encoding the mask data, wherein the ternary CAM array is configured to store CAM data and wherein the CAM device further comprises;

a first plurality of inputs for receiving comparand data to be compared with the CAM data; and

a second independent plurality of inputs for receiving mask data to be stored in the ternary CAM array.

28. The CAM device of claim 27, further comprising a plurality of outputs for outputting longest mask data.

29. A content addressable memory (CAM) device comprising:

a ternary CAM array for storing mask data; and

encoding logic for receiving and encoding the mask data wherein the ternary CAM array comprises;

a first plurality of memory cells for storing first data;

a first plurality of compare circuits for comparing the first data with search data to generate first comparison results;

a second plurality of memory cells for storing the mask data corresponding to the first data;

a second plurality of compare circuits for comparing a longest mask data with the mask data to generate second comparison results;

a plurality of first match lines coupled to the first compare circuits to receive the first comparison results;

a plurality of masking circuits coupled to the first compare circuits and the second memory cells;

a plurality of prefix signal lines; and

a plurality of prefix logic circuits each having a first input coupled to one of the first match lines, a second input coupled to receive the mask data from one of the second memory cells, and an output coupled to one of the plurality of prefix signal lines.

30. The CAM device of claim 29, further comprising decoding logic coupled to the ternary CAM array to receive and decode encoded input mask data for storage in the ternary CAM array.

31. The CAM device of claim 29, further comprising a second plurality of match lines each coupled to a row of the second memory cells to receive the second comparison results.

32. The CAM device of claim 31, further comprising a priority encoder coupled to the second plurality of match lines.

33. The CAM device of claim 32, further comprising an address decoder coupled to the priority encoder and the ternary CAM array.

34. The CAM array of claim 31, further comprising a plurality of logic gates each coupled to one of the first match lines and one of the second match lines.

35. The CAM array of claim 34, wherein the logic gates comprise AND gates.

36. The CAM device of claim 29, wherein the mask data comprises prefix mask data for Internet Protocol addresses.