Content addressable memory (CAM) with accesses to multiple CAM arrays used to generate result for various matching sizes

• US 6,526,474 B1
• Filed: 11/09/1999
• Issued: 02/25/2003
• Est. Priority Date: 10/25/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Ross, Mark A.
• Primary Examiner(s): BRAGDON, REGINALD GLENWOOD
• Application Number:
  US09/437,012
• Time in Patent Office: 1,204 Days
• Field of Search: 711/108, 711/212, 711/158, 365/49
• US Class Current: 711/108
• CPC Class Codes: G11C 15/04 using semiconductor elements

Abstract

The invention provides a method and system for operating a CAM with a variable size input tag. The improved CAM has multiple access sizes and is divided into multiple stored match sections. Each of the multiple stored match sections can be independently matched against a portion of the input tag, responsive to a type field for each entry. A size selection circuit accumulates the independent match results; a priority encoder coupled thereto collects the accumulated matches and presents a match as an output from the CAM. Each CAM entry can be selected from a set of preselected sizes, each corresponding to a contemplated input tag size, such as 72 bits, 144 bits, or 288 bits.

Claims

1. A method comprising:

receiving an input tag;

identifying one or more input tag widths;

performing a first lookup in a first content-addressable memory (CAM) array to generate a first CAM result indication of which of a plurality of first CAM entries within the first CAM array produced a hit based on the input tag;

performing a second lookup in a second CAM array to generate a second CAM result indication of which of a plurality of second CAM entries within the second CAM array produced a hit based on the input tag; and

generating one or more size selection CAM result indications based on the first and second CAM result indications and said one or more input tag widths;

wherein each of the plurality of first and second CAM entries include a plurality of value bits.

2. The method of claim 1, wherein when said one or more input tag widths include a first width, said one or more size selection CAM result indications indicate which corresponding locations within both the first and second CAM arrays produced a hit based on the input tag.

3. The method of claim 2, further comprising generating a single priority result value based on said one or more size selection CAM result indications.

4. The method of claim 2, wherein when said one or more input tag widths include a second width, said one or more size selection CAM result indications indicate which corresponding locations within one of the first and second CAM arrays produced a hit based on the input tag.

5. The method of claim 4, wherein said generating one or more size selection CAM result indications includes generating a first set of match bits corresponding to said first width and a second set of match bits corresponding to said second width.

6. The method of claim 5, further comprising generating a first priority result value based on the first set of match bits and a second priority result value based on the second set of match bits.

7. The method of claim 6, further comprising reading from, writing to, or reading from and writing to the first CAM array, the second CAM array, or the first and second CAM arrays based on the first priority result value, the second priority result value, or the first and second priority result values.

8. The method of claim 1, wherein when said one or more input tag widths include a second width, said one or more size selection CAM result indications indicate which corresponding locations within one of the first and second CAM arrays produced a hit based on the input tag.

9. The method of claim 8, further comprising generating a single priority result value based on said one or more size selection CAM result indications.

10. The method of claim 1, wherein each of the plurality of first and second CAM entries further includes a plurality of mask bits.

11. The method of claim 1, wherein said performing the first lookup and said performing the second lookup are performed simultaneously.

12. An apparatus comprising:

means for receiving an input tag;

means for identifying one or more input tag widths;

means for performing a first lookup in a first content-addressable memory (CAM) array to generate a first CAM result indication of which of a plurality of first CAM entries within the first CAM array produced a hit based on the input tag;

means for performing a second lookup in a second CAM array to generate a second CAM result indication of which of a plurality of second CAM entries within the second CAM array produced a hit based on the input tag; and

means for generating one or more size selection CAM result indications based on the first and second CAM result indications and said one or more input tag widths;

wherein each of the plurality of first and second CAM entries include a plurality of value bits.

13. The apparatus of claim 12, wherein when said one or more input tag widths include a first width, said one or more size selection CAM result indications indicate which corresponding locations within both the first and second CAM arrays produced a hit based on the input tag.

14. The apparatus of claim 13, further comprising means for generating a single priority result value based on said one or more size selection CAM result indications.

15. The apparatus of claim 13, wherein when said one or more input tag widths include a second width, said one or more size selection CAM result indications indicate which corresponding locations within one of the first and second CAM arrays produced a hit based on the input tag.

16. The apparatus of claim 15, wherein said means for generating one or more size selection CAM result indications includes means for generating a first set of match bits corresponding to said first width and a second set of match bits corresponding to said second width.

17. The apparatus of claim 16, further comprising means for generating a first priority result value based on the first set of match bits and a second priority result value based on the second set of match bits.

18. The apparatus of claim 17, further comprising means for reading from, writing to, or reading from and writing to the first CAM array, the second CAM array, or the first and second CAM arrays based on the first priority result value, the second priority result value, or the first and second priority result values.

19. The apparatus of claim 12, wherein when said one or more input tag widths include a second width, said one or more size selection CAM result indications indicate which corresponding locations within one of the first and second CAM arrays produced a hit based on the input tag.

20. The apparatus of claim 19, further comprising means for generating a single priority result value based on said one or more size selection CAM result indications.

21. The apparatus of claim 12, wherein each of the plurality of first and second CAM entries further includes a plurality of mask bits.

22. An apparatus comprising:

a first content-addressable memory (CAM) array including a plurality of first CAM entries, the first CAM array configured to generate a first CAM result indication of which of the plurality of first CAM entries produce a hit based on an input tag;

a second CAM array including a plurality of second CAM entries, each of the plurality of first and second CAM entries including a plurality of value bits, the second CAM array configured to generate a second CAM result indication of which of the plurality of second CAM entries produce a hit based on the input tag; and

a size selection mechanism coupled to the first and second CAM arrays, the size selection mechanism configured to generate one or more size selection CAM result indications based on the first and second CAM result indications and one or more input tag widths.

23. The apparatus of claim 22, further comprising an input request register coupled to the first and second CAM arrays, the input request register configured to store the input tag.

24. The apparatus of claim 22, wherein when said one or more input tag widths include a first width, said one or more size selection CAM result indications indicate which corresponding locations within both the first and second CAM arrays produced a hit based on the input tag.

25. The apparatus of claim 24, further comprising a priority encoder coupled to the size selection mechanism, the priority encoder configured to generate a single priority result value based on said one or more size selection CAM result indications.

26. The apparatus of claim 24, wherein when said one or more input tag widths include a second width, said one or more size selection CAM result indications indicate which corresponding locations within one of the first and second CAM arrays produced a hit based on the input tag.

27. The apparatus of claim 26, wherein said one or more size selection CAM result indications include a first set of match bits corresponding to said first width and a second set of match bits corresponding to said second width.

28. The apparatus of claim 27, further comprising a priority encoder coupled to the size selection mechanism, the priority encoder configured to generate a first priority result value based on the first set of match bits and a second priority result value based on the second set of match bits.

29. The apparatus of claim 22, wherein when said one or more input tag widths include a second width, said one or more size selection CAM result indications indicate which corresponding locations within one of the first and second CAM arrays produced a hit based on the input tag.

30. The apparatus of claim 29, further comprising a priority encoder coupled to the size selection mechanism, the priority encoder configured to generate a single priority result value based on said one or more size selection CAM result indications.

31. The apparatus of claim 22, wherein each of the plurality of first and second CAM entries further includes a plurality of mask bits.

32. A method comprising:

receiving an input tag;

identifying a selected input tag width, the selected input tag width being one of a plurality of possible input tag widths;

performing a first lookup in a first content-addressable memory (CAM) array to generate a first CAM result indication of which of a plurality of first CAM entries within the first CAM array produced a hit based on the input tag;

performing a second lookup in a second CAM array to generate a second CAM result indication of which of a plurality of second CAM entries within the second CAM array produced a hit based on the input tag; and

generating one or more size selection CAM result indications based on the first and second CAM result indications and the selected input tag width;

wherein each of the plurality of first and second CAM entries include a plurality of value bits.

33. The method of claim 32, wherein when the selected input tag width corresponds to a first width, said one or more size selection CAM result indications indicate which corresponding locations within both the first and second CAM arrays produced a hit based on the input tag.

34. The method of claim 33, further comprising generating a single priority result value based on said one or more size selection CAM result indications.

35. The method of claim 33, wherein when the selected input tag width corresponds to a second width, said one or more size selection CAM result indications indicate which locations within the first and second CAM arrays produced a hit based on the input tag.

36. The method of claim 35, wherein said generating one or more size selection CAM result indications includes generating a first set of match bits corresponding to said first width and a second set of match bits corresponding to said second width.

37. The method of claim 36, further comprising generating a first priority result value based on the first set of match bits and a second priority result value based on the second set of match bits.

38. The method of claim 37, further comprising reading from, writing to, or reading from and writing to the first CAM array, the second CAM array, or the first and second CAM arrays based on the first priority result value, the second priority result value, or the first and second priority result values.

39. The method of claim 32, wherein when the selected input tag width corresponds to a second width, said one or more size selection CAM result indications indicate which locations within the first and second CAM arrays produced a hit based on the input tag.

40. The method of claim 39, further comprising generating a single priority result value based on said one or more size selection CAM result indications.

41. The method of claim 32, wherein each of the plurality of first and second CAM entries includes a plurality of mask bits.

42. The method of claim 32, wherein said performing the first lookup and said performing the second lookup are performed simultaneously.

43. An apparatus comprising:

means for receiving an input tag;

means for identifying a selected input tag width, the selected input tag width being one of a plurality of possible input tag widths;

means for performing a first lookup in a first content-addressable memory (CAM) array to generate a first CAM result indication of which of a plurality of first CAM entries within the first CAM array produced a hit based on the input tag;

means for performing a second lookup in a second CAM array to generate a second CAM result indication of which of a plurality of second CAM entries within the second CAM array produced a hit based on the input tag; and

means for generating one or more size selection CAM result indications based on the first and second CAM result indications and the selected input tag width;

wherein each of the plurality of first and second CAM entries include a plurality of value bits.

44. The apparatus of claim 43, wherein when the selected input tag width corresponds to a first width, said one or more size selection CAM result indications indicate which corresponding locations within both the first and second CAM arrays produced a hit based on the input tag.

45. The apparatus of claim 44, further comprising means for generating a single priority result value based on said one or more size selection CAM result indications.

46. The apparatus of claim 44, wherein when the selected input tag width corresponds to a second width, said one or more size selection CAM result indications indicate which locations within the first and second CAM arrays produced a hit based on the input tag.

47. The apparatus of claim 46, wherein said means for generating one or more size selection CAM result indications includes means for generating a first set of match bits corresponding to said first width and a second set of match bits corresponding to said second width.

48. The apparatus of claim 47, further comprising means for generating a first priority result value based on the first set of match bits and a second priority result value based on the second set of match bits.

49. The apparatus of claim 48, further comprising means for reading from, writing to, or reading from and writing to the first CAM array, the second CAM array, or the first and second CAM arrays based on the first priority result value, the second priority result value, or the first and second priority result values.

50. The apparatus of claim 43, wherein when the selected input tag width corresponds to a second width, said one or more size selection CAM result indications indicate which locations within the first and second CAM arrays produced a hit based on the input tag.

51. The apparatus of claim 50, further comprising means for generating a single priority result value based on said one or more size selection CAM result indications.

52. The apparatus of claim 43, wherein each of the plurality of first and second CAM entries includes a plurality of mask bits.

53. An apparatus comprising:

a first content-addressable memory (CAM) array including a plurality of first CAM entries, the first CAM array configured to generate a first CAM result indication of which of the plurality of first CAM entries produce a hit based on an input tag;

a second CAM array including a plurality of second CAM entries, each of the plurality of first and second CAM entries including a plurality of value bits, the second CAM array configured to generate a second CAM result indication of which of the plurality of second CAM entries produce a hit based on the input tag; and

a size selection mechanism coupled to the first and second CAM arrays, the size selection mechanism configured to generate one or more size selection CAM result indications based on the first and second CAM result indications and a selected input tag width, the selected input tag width being one of a plurality of possible input tag widths.

54. The apparatus of claim 53, further comprising an input request register coupled to the first and second CAM arrays, the input request register configured to store the input tag.

55. The apparatus of claim 53, wherein when the selected tag width corresponds to a first width, said one or more size selection CAM result indications indicate which corresponding locations within both the first and second CAM arrays produced a hit based on the input tag.

56. The apparatus of claim 55, further comprising a priority encoder coupled to the size selection mechanism, the priority encoder configured to generate a single priority result value based on said one or more size selection CAM result indications.

57. The apparatus of claim 55, wherein when the selected tag width corresponds to a second width, said one or more size selection CAM result indications indicate which corresponding locations within one of the first and second CAM arrays produced a hit based on the input tag.

58. The apparatus of claim 57, wherein said one or more size selection CAM result indications include a first set of match bits corresponding to said first width and a second set of match bits corresponding to said second width.

59. The apparatus of claim 58, further comprising a priority encoder coupled to the size selection mechanism, the priority encoder configured to generate a first priority result value based on the first set of match bits and a second priority result value based on the second set of match bits.

60. The apparatus of claim 53, wherein when the selected tag width corresponds to a second width, said one or more size selection CAM result indications indicate which corresponding locations within one of the first and second CAM arrays produced a hit based on the input tag.

61. The apparatus of claim 60, further comprising a priority encoder coupled to the size selection mechanism, the priority encoder configured to generate a single priority result value based on said one or more size selection CAM result indications.

62. The apparatus of claim 53, wherein each of the plurality of first and second CAM entries further includes a plurality of mask bits.