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

• US 6,499,081 B1
• Filed: 11/12/1999
• Issued: 12/24/2002
• 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: Nataraj, Bindiganavale S., Khanna, Sandeep, Srinivasan, Varadarajan
• Primary Examiner(s): PEIKARI, BEHZAD
• Application Number:
  US09/439,834
• Time in Patent Office: 1,138 Days
• Field of Search: 711/108, 711/173, 365/49, 365/195, 365/189.07, 710/49
• US Class Current: 711/108
• CPC Class Codes: G11C 15/04 using semiconductor elements
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming

Abstract

A method and apparatus for determining a longest prefix match in a segmented content addressable memory (CAM) device. The CAM device includes multiple CAM array blocks that each may be arbitrarily loaded with CIDR addresses. For one embodiment, each 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), and prefix logic circuits for comparing the logical state of the CAM match line with the prefix mask data. The prefix logic circuits determine the longest prefix in each CAM array block from among CAM entries that match the search key. The longest prefixes from each block are provided to compare circuitry that determines which of the longest prefixes is the longest for the entire CAM device. A block select circuit selects the CAM array block that stores the longest prefix for the entire CAM device for comparison with the prefix mask data in that CAM array block. The CAM index or address of the matching location may then be output from the CAM device. By restricting the search of the device-level longest prefix to only one CAM array block, power drawn by this comparison is reduced over searching all CAM array blocks in parallel.

Claims

1. A ternary content addressable memory (CAM) device comprising:

a first ternary CAM array block having a plurality of rows of CAM cells coupled to a corresponding row of mask cells and a first plurality of signal lines to provide first mask data from one of the rows of mask cells;

a second ternary CAM array block having a plurality of rows of CAM cells coupled to a corresponding row of mask cells and a second plurality of signal lines to provide second mask data from one of the rows of mask cells;

means for determining that the first mask data indicates more unmasked bits than the second mask data; and

means for selecting the first ternary CAM array block to compare the first mask data with mask data stored in its plurality of rows of mask cells.

2. The ternary CAM device of claim 1, wherein the selecting means further comprises means for deselecting the second ternary CAM array block from comparing the second mask data with mask data stored in its plurality of rows of mask cells.

3. The ternary CAM device of claim 1, wherein the determining means determines that the first mask data indicates more contiguous unmasked bits than the second masked data.

4. The ternary CAM device of claim 1, wherein the determining means comprises compare circuitry configured to compare the first and second mask data.

5. A ternary content addressable memory (CAM) device comprising:

a plurality of ternary CAM array blocks each having a plurality of rows of ternary CAM cells coupled to a plurality of signal lines that provide mask data from one of the rows of ternary CAM cells; and

compare circuitry having inputs coupled to receive the mask data from each of the plurality of signal lines, and having outputs to provide an indication of the mask data that indicates the most unmasked bits.

6. The ternary CAM device of claim 5, further comprising a block select circuit coupled to receive the indication from the compare circuitry, the block select circuit having outputs to provide a plurality of select signals to select one of the plurality of ternary CAM array blocks.

7. The ternary CAM device of claim 6, wherein the selected CAM array block is configured to compare its mask data provided to the compare circuitry with mask data stored in its plurality of rows of ternary CAM cells.

8. The ternary CAM device of claim 6, wherein the compare circuitry provides an indication of the mask data that indicates the largest number of contiguous unmasked bits.

9. The ternary CAM device of claim 5, wherein each of the plurality of ternary CAM array blocks comprises circuitry to identify which rows of ternary CAM cells stores data matches comparand data and has the most unmasked bits.

10. A ternary content addressable memory (CAM) device comprising:

a plurality of ternary CAM array blocks each having a plurality of rows of CAM cells coupled to a corresponding row of mask cells and a plurality of signal lines that provide mask data from one of the rows of mask cells;

compare circuitry having inputs coupled to receive the mask data from each of the plurality of signal lines, and having outputs to provide composite mask data, wherein the composite mask data comprises the mask data that indicates the most unmasked bits; and

a block select circuit having inputs coupled to the compare circuitry to receive the composite mask data, the block select circuit having outputs to provide a plurality of select signals to select one of the plurality of CAM array blocks.

11. The ternary CAM device of claim 10, wherein the selected CAM array block is configured to compare its mask data provided to the compare circuitry with mask data stored in its plurality of rows of mask cells.

12. The ternary CAM device of claim 10, wherein the compare circuitry provides the mask data that indicates the largest number of contiguous unmasked bits.

13. The ternary CAM device of claim 10, wherein the compare circuitry comprises a plurality of logic gates for logically combining the mask data from each of the plurality of signal lines of the CAM array blocks to form the composite mask data.

14. The ternary CAM device of claim 10, wherein the block select circuit comprises:

a plurality of compare circuits each having first inputs to receive the composite mask data, second inputs to receive mask data from a respective one of the plurality of ternary CAM array blocks, and an output to provide a signal indicating whether the composite mask data matches the mask data received from a respective one of the plurality of ternary CAM array blocks.

15. The ternary CAM device of claim 14, wherein the block select circuit further comprises:

an encoder having a plurality of inputs each coupled to receive one of the signals output by one of the plurality of compare circuits, and having a plurality of outputs; and

a decoder having inputs coupled to the outputs of the encoder, and outputs to provide the plurality of select signals.

16. The ternary CAM device of claim 10, wherein the block select circuit comprises:

a plurality of compare circuits each having a first input coupled to receive one bit from the composite mask data, a plurality of second inputs each coupled to receive one bit of the mask data provided by each of the plurality of signal lines from each ternary CAM array block, and an output to provide a signal indicating whether the composite mask data matches the mask data received from the plurality of ternary CAM array blocks.

17. The ternary CAM of claim 16, wherein the plurality of compare circuits comprise exclusive OR (XOR) gates.

18. The ternary CAM of claim 17, wherein the plurality of compare circuits further comprise AND gates coupled to the XOR gates.

19. The ternary CAM of claim 16, wherein the block select circuit further comprises:

an encoder having a plurality of inputs each coupled to receive one of the signals output by one of the plurality of compare circuits, and having a plurality of outputs; and

a decoder having inputs coupled to the outputs of the encoder, and outputs to provide the plurality of select signals.

20. A ternary content addressable memory (CAM) device comprising:

a first group of ternary CAM array blocks, each ternary CAM array block having a plurality of rows of CAM cells coupled to a corresponding row of mask cells and a plurality of signal lines that provide mask data from one of the rows of mask cells;

a second group of ternary CAM array blocks, each ternary CAM array block having a plurality of rows of CAM cells coupled to a corresponding row of mask cells and a plurality of signal lines that provide mask data from one of the rows of mask cells;

first compare circuitry having inputs coupled to receive mask data from each of the plurality of signal lines of the CAM array blocks in the first group, and having outputs to provide first composite mask data, wherein the first composite mask data comprises the mask data from the plurality of CAM array blocks in the first group that indicates the most unmasked bits;

second compare circuitry having inputs coupled to receive mask data from each of the plurality of signal lines of the CAM array blocks in the second group, and having outputs to provide second composite mask data, wherein the second composite mask data comprises the mask data from the plurality of CAM array blocks in the second group that indicates the most unmasked bits; and

a block select circuit having first inputs coupled to the first compare circuitry to receive the first composite mask data, second inputs coupled to the second compare circuitry to receive the second composite mask data, third inputs to receive mask data from each of the plurality of ternary CAM array blocks in each of the first and second groups, and outputs to provide a plurality of select signals to select one of the plurality of CAM array blocks.

21. The ternary CAM device of claim 20, wherein the selected CAM array block is configured to compare its mask data provided to the first or second compare circuitry with mask data stored in its plurality of rows of mask cells.

22. The ternary CAM device of claim 20, wherein the first composite mask data comprises the mask data from the plurality of CAM array blocks in the first group that indicates the largest number of contiguous unmasked bits.

23. The ternary CAM device of claim 20, wherein the second composite mask data comprises the mask data from the plurality of CAM array blocks in the second group that indicates the largest number of contiguous unmasked bits.

24. The ternary CAM device of claim 23, wherein the block select circuit comprises:

a first plurality of compare circuits each having inputs coupled to receive one bit from the first composite mask data and one bit from the mask data provided by each of the plurality of signal lines of the ternary CAM array blocks in the first group, and each further having an output to provide a signal indicating whether the first composite mask data matches the mask data received from the plurality of ternary CAM array blocks in the first group;

a second plurality of compare circuits each having inputs coupled to receive one bit from the second composite mask data and one bit from the mask data provided by each of the plurality of signal lines of the ternary CAM array blocks in the second group, and each further having an output to provide a signal indicating whether the second composite mask data matches the mask data received from the plurality of ternary CAM array blocks in the second group; and

a third plurality of compare circuits each having inputs coupled to receive one bit from the first composite mask data, one bit from the second composite mask data, and one bit from the third composite mask data, and each further having an output to provide a signal indicating whether the third composite mask data matches the first composite mask data or the second composite mask data;

a first encoder having a plurality of inputs each coupled to receive one of the signals output by one of the first plurality of compare circuits, and having a plurality of outputs;

a second encoder having a plurality of inputs each coupled to receive one of the signals output by one of the second plurality of compare circuits, and having a plurality of outputs;

select logic having inputs coupled to the outputs of the third plurality of compare circuits, and having an output to provide a multiplexer select signal;

a multiplexer having first inputs coupled to the plurality of outputs of the first encoder, second inputs coupled to the plurality of outputs of the second encoder, a select input coupled to receive the multiplexer select signal, and a plurality of outputs; and

a decoder having inputs coupled to the plurality of outputs of the multiplexer and the output of the select logic, and outputs to provide the plurality of select signals.

25. The ternary CAM device of claim 24, wherein the block select circuit comprises:

a first encoder having a plurality of inputs each coupled to receive one of the signals output by one of the first plurality of compare circuits, and having a plurality of outputs;

a second encoder having a plurality of inputs each coupled to receive one of the signals output by one of the second plurality of compare circuits, and having a plurality of outputs;

select logic having inputs coupled to the outputs of the third plurality of compare circuits, and having an output to provide a multiplexer select signal;

a multiplexer having first inputs coupled to the plurality of outputs of the first encoder, second inputs coupled to the plurality of outputs of the second encoder, a select input coupled to receive the multiplexer select signal, and a plurality of outputs; and

a decoder having inputs coupled to the plurality of outputs of the multiplexer and the output of the select logic, and outputs to provide the plurality of select signals.

26. The ternary CAM device of claim 20, wherein the first compare circuitry comprises a first plurality of logic gates for logically combining the mask data from each of the plurality of signal lines of the CAM array blocks in the first group to form the first composite mask data, and wherein the second compare circuitry comprises a second plurality of logic gates for logically combining the mask data from each of the plurality of signal lines of the CAM array blocks in the second group to form the second composite mask data.

27. The ternary CAM device of claim 20, wherein the block select circuit comprises:

a first plurality of compare circuits each having inputs coupled to receive one bit from the first composite mask data and one bit from the mask data provided by each of the plurality of signal lines of the ternary CAM array blocks in the first group, and each further having an output to provide a signal indicating whether the first composite mask data matches the mask data received from the plurality of ternary CAM array blocks in the first group;

a second plurality of compare circuits each having inputs coupled to receive one bit from the second composite mask data and one bit from the mask data provided by each of the plurality of signal lines of the ternary CAM array blocks in the second group, and each further having an output to provide a signal indicating whether the second composite mask data matches the mask data received from the plurality of ternary CAM array blocks in the second group;

an encoder having a first plurality of inputs each coupled to receive one of the signals output by one of the first plurality of compare circuits, a second plurality of inputs each coupled to receive one of the signals output by one of the second plurality of compare circuits, and having a plurality of outputs; and

a decoder having inputs coupled to the outputs of the encoder, and outputs to provide the plurality of select signals.

28. The ternary CAM device of claim 20, further comprising third compare circuitry having first inputs coupled to receive the first composite mask data, second inputs coupled to receive the second composite mask data, and outputs to provide third composite mask data to the block select circuit, wherein the third composite mask data comprises the mask data from the first and second composite mask data that indicates which ternary CAM array block in the first or second group has mask data with the most unmasked bits.

29. A method of operating a ternary content addressable memory (CAM) device having first and second ternary CAM array blocks, comprising:

determining first mask data for a row of CAM cells in the first ternary CAM array block that stores data matching comparand data;

determining second mask data for a row of CAM cells in the second ternary CAM array block that stores data matching the comparand data;

determining that the first mask data indicates more unmasked bits than the second mask data; and

determining a location of the first mask data in the first ternary CAM array block.

30. The method of claim 29, wherein determining the location of the first mask data in the first ternary CAM array block comprises:

selecting the first ternary CAM array block; and

comparing the first mask data with mask data stored in rows of mask cells, each row of mask cells coupled to a corresponding row of CAM cells in the first ternary CAM array block.

31. The method of claim 30, further comprising deselecting the second ternary CAM array block.

32. The method of claim 30, further comprising determining logical states of a plurality of match lines in response to the comparing of the first mask data with data stored in the rows of mask cells.

33. The method of claim 29, wherein the rows of CAM cells in the first and second ternary CAM arrays store Internet Protocol (IP) addresses.

34. The method of claim 33, wherein the first and second mask data comprise prefix mask data for the IP addresses.

35. The method of claim 29, wherein determining that the first mask data indicates more unmasked bits comprises logically combining the first and second mask data.

36. The method of claim 29, wherein determining that the first mask data indicates more unmasked bits comprises logically combining the first and second mask data to form composite mask data, and wherein determining a location of the first mask data in the first ternary CAM array block comprises:

determining that the composite mask data is the first mask data from the first ternary CAM array block;

selecting the first ternary CAM array block; and

comparing the first mask data with mask data stored in rows of mask cells, each row of mask cells coupled to a corresponding row of CAM cells in the first ternary CAM array block.

37. A method of determining the location of an entry in one of plurality of ternary content addressable memory CAM array blocks, each CAM array block having a plurality of ternary CAM cells, wherein the located entry has the most unmasked bits among the CAM cells of all CAM array blocks, the method comprising:

determining which locations in each CAM array block match comparand data;

determining the largest number of unmasked bits among the matching entries in each ternary CAM array block;

comparing the largest numbers of unmasked bits from each of the ternary CAM array blocks to select one of the largest numbers of unmasked bits; and

comparing the selected largest number of unmasked bits with mask data stored in the ternary CAM array block associated with the selected largest number of unmasked bits.