Method and apparatus for determining an exact match in a ternary content addressable memory device

• US 6,539,455 B1
• Filed: 11/12/1999
• Issued: 03/25/2003
• 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/442,042
• Time in Patent Office: 1,229 Days
• Field of Search: 711/108, 365/49, 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 an exact match in a ternary CAM device. Each ternary CAM cell includes CAM cells for storing CAM data, local mask cells for storing prefix mask data for the corresponding CAM cells, and a mask override circuit. Each local mask cell includes a masking circuit that masks the prefix mask data or CAM data provided to the comparison circuit, or masks the comparison result from the match line of a CAM cell. The mask override circuit effectively overrides the prefix mask data stored in the local mask cell. The mask override circuit performs the override function by negating the operation of the mask circuit such that no masking operation occurs when an exact match compare or invalidate function is performed by the ternary CAM device. For example, during an exact match operation, the CAM cells compare comparand data with unmasked CAM data and provide the compare results to CAM match lines. The local mask cells also compare mask data with the stored prefix mask data and provide the results to mask match lines. If both compares result in a match, then an exact match entry is located in the ternary CAM device. The locations or indexes of the exact match entries may then be output from the CAM device. One or more of the exact match locations may also be invalidated or deleted.

Claims

1. A content addressable memory (CAM) cell comprising:

a first memory cell;

a first compare circuit coupled to the first memory cell;

a second memory cell for storing mask data for the first memory cell;

a second compare circuit coupled to the second memory cell;

a mask circuit coupled to the first compare circuit and the second memory cell; and

a mask override circuit coupled to the mask circuit, the mask override circuit operable to override the mask data.

2. The CAM cell of claim 1, wherein the mask circuit is coupled to a first match line.

3. The CAM cell of claim 2, wherein the second compare circuit is coupled to a second match line.

4. The CAM cell of claim 2, further comprising a logic circuit coupled to the second memory cell and the first match line.

5. The CAM cell of claim 2, wherein the mask override circuit is coupled to the first match line.

6. The CAM cell of claim 1, wherein the first compare circuit is coupled to a first match line and the second compare circuit is coupled to a second match line.

7. The CAM cell of claim 1, wherein the mask circuit is further coupled to the first memory cell.

8. The CAM cell of claim 1, wherein the first memory cell for storing an Internet Protocol (IP) address bit, and the mask data is prefix data associated with the IP address bit.

10. The CAM of claim 4, wherein the first CAM cell comprises a first memory cell coupled to a first compare circuit.

11. The CAM of claim 10, wherein the second CAM cell comprises:

a second memory cell for storing the mask data;

a second compare circuit coupled to the second memory cell and a match line; and

a masking circuit coupled to the second memory cell.

9. A content addressable memory (CAM) comprising:

a first CAM cell for storing CAM data and comparing first comparand data with the CAM data; and

a second CAM cell coupled to the first CAM cell, the second CAM cell for storing mask data for the first CAM cell; and

means for overriding the mask data.

12. The CAM of claim 9, wherein the first CAM cell is coupled to a match line.

13. The CAM of claim 12, further comprising a logic circuit coupled to the second CAM cell and the match line, the logic circuit for logically comparing the mask data with the logic state of the match line.

14. The CAM of claim 13, wherein the second CAM cell is coupled to a second match line.

15. The CAM of claim 9, wherein the CAM data comprises an Internet Protocol (IP) address bit and the mask data is prefix data associated with the IP address bit.

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

a plurality of rows of CAM cells for storing CAM data;

a plurality of rows of local mask cells each coupled to a corresponding row of CAM cells, each local mask cell for storing mask data for a corresponding CAM cell;

a plurality of first match lines;

a first plurality of signal lines;

a plurality of rows of compare circuits each coupled to a corresponding row of mask cells and a corresponding first match line, each circuit having a first input coupled to one of the first match lines, a second input coupled to receive mask data from one of the mask cells, and an output coupled to one of the first plurality of signal lines;

a second plurality of signal lines coupled to the local mask cells; and

a multiplexer circuit coupled to provide at least one of comparand data and data from the first plurality of signal lines to the second plurality of signal lines.

17. The CAM device of claim 16, further comprising a second plurality of match lines each coupled to a corresponding row of the local mask cells.

18. The CAM device of claim 17, further comprising logic having first inputs coupled to the first plurality of match lines, second inputs coupled to the second plurality of match lines, and outputs coupled to a third plurality of match lines.

19. The CAM device of claim 18, wherein the logic comprises a plurality of AND gates.

20. The CAM device of claim 18, further comprising flag logic coupled to the first plurality of match lines and the third plurality of match lines, and wherein the flag logic is configured to generate a match flag signal.

21. The CAM cell of claim 18, further comprising a priority encoder coupled to the third plurality of match lines.

22. The CAM cell of claim 16, further comprising a register coupled to the first plurality of signal lines.

23. The CAM device of claim 16, wherein the comparand data comprises mask data.

24. The CAM device of claim 16, wherein the comparand data comprises decoded mask data, and wherein the CAM device further comprises decoding logic having inputs for receiving encoded mask data and outputs for providing the decoded mask data to the plurality of mask cells and to the multiplexer circuit.

25. The CAM device of claim 16, further comprising encoding logic having inputs for receiving the mask data and outputs for providing encoded mask data.

26. The CAM device of claim 16, wherein the CAM data comprises Internet Protocol (IP) addresses and the mask data comprises prefix data associated with the IP addresses.

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

a plurality of rows of CAM cells for storing CAM data;

a plurality of rows of local mask cells each coupled to a corresponding row of CAM cells, and each local mask cell for storing mask data for a corresponding CAM cell; and

means for selecting at least one of comparand data and mask data from one of the rows of local mask cells to be compared with mask data stored in each of the rows of local mask cells.

28. The CAM device of claim 27, further comprising means for overriding local mask data stored in the local mask cells.

29. The CAM device of claim 27, wherein the CAM data comprises Internet Protocol (IP) addresses and the mask data comprises prefix data associated with the IP addresses.

30. A method of operating a content addressable memory (CAM) device, the CAM device having a plurality of rows of CAM cells and corresponding local mask cells, the method comprising:

overriding local mask data stored in the local mask cells;

comparing first comparand data with data stored in the rows of CAM cells to determine logical states of a first plurality of match lines; and

comparing second comparand data with data stored in the rows of local mask cells to determine logical states of a second plurality of match lines.

31. The method of claim 30, further comprising logically combining the states of the first and second plurality of match lines.

32. The method of claim 30, further comprising determining that at least one row of CAM cells and corresponding local mask cells stores data that matches the first and second comparand data, respectively.

33. The method of claim 32, further comprising invalidating the data stored in the CAM cells of the at least one row of CAM cells that stores data that matches the first and second comparand data, respectively.

34. The method of claim 30 wherein the first comparand data is an Internet Protocol (IP) address, and the second comparand data is prefix data associated with the IP address.

35. A content address memory (CAM) device comprising:

a ternary CAM array having N rows of M ternary CAM cells, wherein each ternary CAM cell has a first and second CAM cell, and wherein N and M are integers; and

means for configuring the ternary CAM array to operate as a binary CAM array having N rows of 2M binary CAM cells.

36. A method of operating a ternary content addressable memory (CAM) array as a binary content addressable memory array, the ternary CAM array having N rows of M ternary CAM cells, wherein each ternary CAM cell has a first and second binary CAM cell, and wherein N and M are integers, the method comprising:

overriding local mask data stored in the second binary CAM cells;

comparing a first comparand word with data stored in the N rows of the first binary CAM cells to determine logical states of a first plurality of match lines;

comparing a second comparand word with data stored in the N rows of the second binary CAM cells to determine logical states of a second plurality of match lines; and

logically combining the states of the first and second plurality of match lines to determine logical states of a third plurality of match lines.

37. A content addressable memory (CAM) device, comprising:

a CAM array to store CAM data and mask data, the CAM array including a mask override circuit operable to override the mask data;

a first plurality of match lines coupled with the CAM array; and

a logic circuit coupled with the first plurality of match lines to generate a match flag indicating whether a match has occurred based on a state of the first plurality of match lines.

38. The CAM device of claim 37, further comprising a second plurality of match lines coupled with the CAM array and wherein the logic circuit is configured to generate the match flag based on a logic combination of the state of the first plurality of match lines and a state of the second plurality of match lines.