Method and apparatus for verifying the integrity of a content-addressable memory result

• US 7,260,673 B1
• Filed: 07/20/2001
• Issued: 08/21/2007
• Est. Priority Date: 07/20/2001
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Ross, Mark A.
• Primary Examiner(s): Song; Jasmine
• Application Number:
  US09/910,227
• Time in Patent Office: 2,223 Days
• Field of Search: 711/108, 714/6, 365/49
• US Class Current: 711/108
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores

Abstract

Methods and apparatus are disclosed for verifying the integrity of an index or result produced by a content-addressable or associated memory or other device. A pre-computed data protection field is stored, either as part of a returned index of a content-addressable memory or in a separate storage. In one implementation, a data protection operation is performed on all or part of the returned index and a comparison is made with a pre-computed data protection field. In one implementation, a copy of the masks employed by a ternary content-addressable memory and a set of pre-computed data protection fields are stored. A particular mask and pre-computed data protection field are selected based on the generated index. The original input value is then masked by the selected mask and provided to a data protection function. The result of this function is then compared to the selected pre-computed data protection field.

Claims

1. A method comprising:

generating an index by a content-addressable memory based on an input value;

acquiring a mask value and a data protection field based on the index;

generating a comparison value based on the mask value and the input value; and

comparing the comparison value to the data protection field in order to determine the integrity of a result of the content-addressable memory associated with the index.

2. The method of claim 1, wherein the data protection field includes a pre-computed data protection result.

3. The method of claim 1, wherein the content-addressable memory includes a ternary content-addressable memory.

4. The method of claim 1, wherein said acquiring the mask value and the data protection field includes a lookup operation on a memory.

5. The method of claim 1, wherein generating the comparison value includes:

masking the input value with the mask value to generate a masked input value; and

applying a data protection function to the masked input value to generate the comparison value.

6. The method of claim 1, wherein generating the comparison value includes:

decoding the mask value to generate a decoded mask value;

masking the input value with the decoded mask value to generate a masked input value; and

applying a data protection function to the masked input value to generate the comparison value.

7. The method of claim 1, wherein generating the comparison value includes:

masking the input value with the mask value to generate a masked input value; and

applying a data protection function to the masked input value to generate the comparison value.

8. The method of claim 1, wherein the input value has a plurality of input value bits, and the content-addressable memory includes a plurality of pairs of masks and values with each mask each having a plurality of mask bits and each value having a plurality of value bits;

and

wherein said generating the index includes matching the input value with a particular one of the plurality of pairs of masks and values, wherein said matching includes comparing said input value bits whose corresponding said mask bits of the particular one of the plurality of pairs have a scalar value of one with said value bits of the particular one of the plurality of pairs whose corresponding said mask bits of the particular one of the plurality of pairs have a scalar value of one.

9. The method of claim 1, wherein the input value has a plurality of input value bits, and the content-addressable memory includes a plurality of pairs of masks and values with each mask each having a plurality of mask bits and each value having a plurality of value bits;

and

wherein said generating the index includes matching the input value with a particular one of the plurality of pairs of masks and values, wherein said matching includes comparing said input value bits whose corresponding said mask bits of the particular one of the plurality of pairs have a scalar value of zero with said value bits of the particular one of the plurality of pairs whose corresponding said mask bits of the particular one of the plurality of pairs have a scalar value of zero.

10. The method of claim 1, further comprising signaling an error condition if the comparison value is not equal to the data protection field.

11. The method of claim 1, wherein said acquiring the mask value includes:

retrieving an encoded mask value from a storage mechanism; and

decoding the encoded mask value to generate the mask value.

12. The method of claim 1, wherein the index includes an identification of a position of an entry in the content-addressable memory matching the input value.

13. A computer-readable medium containing computer-readable instructions for performing a set of steps, the set of steps comprising:

retrieving a mask value and a data protection field from a storage based on an index value generated by a content-addressable memory based on an input value;

masking the input value with the mask value to generate a masked input value;

performing a data protection function on the masked input value to generate a comparison result; and

comparing the comparison result with the data protection field in order to identify whether or not there was a data protection error.

14. The computer-readable medium of claim 13, wherein the storage includes one or more memory devices.

15. The computer-readable medium of claim 13, wherein the storage includes one or more storage devices.

16. The computer-readable medium of claim 13, wherein the content-addressable memory includes a ternary content-addressable memory.

17. The computer-readable medium of claim 13, wherein the data protection field includes a pre-computed data protection result.

18. The computer-readable medium of claim 13, further indicating an error condition if the comparison value is not equal to the data protection field.

19. The computer-readable medium of claim 13, wherein the index value includes an identification of a position of an entry in the content-addressable memory matching the input value.

20. An apparatus comprising:

a content-addressable memory configured to receive an input word and to generate an index;

one or more storage mechanisms coupled to the content-addressable memory to receive the index and to produce a mask value and a data protection field;

a masking device coupled to said one or more storage mechanisms to generate a masked result based on the input word and the mask value;

a data protection generator coupled to the masking device to generate a comparison value based on the masked result; and

a comparison mechanism coupled to the data protection generator and said one or more storage mechanisms to compare the comparison value and the data protection field in order to identify whether or not there was a data protection error.

21. The apparatus of claim 20, wherein the masking device includes a decoder to decode the mask value.

22. The apparatus of claim 20, wherein the comparison mechanism indicates an error condition if the comparison value is not equal to the data protection field.

23. The apparatus of claim 20, wherein the data protection field includes a pre-computed data protection result.

24. The apparatus of claim 20, wherein the content-addressable memory includes a ternary content-addressable memory.

25. The apparatus of claim 20, wherein the index includes an identification of a position of an entry in the content-addressable memory matching the input value.

26. An apparatus comprising:

a content-addressable memory including a plurality of entries, each of the plurality of entries including a value and a data protection field, wherein the content-addressable memory is configured to identify one of the plurality of entries in response to a look operation on an input word;

a data protection generator, coupled to the content-addressable memory, to receive said value of said identified one of the plurality of entries and to generate a comparison value; and

a comparison mechanism, coupled to the data protection generator and the content-addressable memory, configured to compare the comparison value and said data protection field of the identified one of the plurality of entries in order to identify whether or not there was a data protection error.

27. The apparatus of claim 26, wherein the content-addressable memory includes a binary content-addressable memory.

28. The apparatus of claim 26, wherein, for each of the plurality of entries, said data protection field of a particular entry includes a pre-computed data protection result for said value of the particular entry.

29. A method comprising:

receiving a content-addressable memory index generated based on a lookup operation in a content-addressable memory on an input word, the content-addressable memory index including a value field and a data protection field;

extracting the value field and the data protection field from the content-addressable memory index;

performing a data protection function on the value field to generate a comparison result; and

comparing the comparison result with the data protection field in order to identify whether or not there was a data protection error.

30. The method of claim 29, wherein the content-addressable memory includes a binary content-addressable memory.

31. The method of claim 29, wherein the data protection field includes a pre-computed data protection result.

32. The method of claim 29, further indicating an error condition if the comparison result is not equal to the data protection field.

33. An apparatus comprising:

a content-addressable memory configured to receive an input word and to generate an index;

a memory, coupled to the content-addressable memory and a comparison mechanism, to receive at least a first portion of the index generated by the content-addressable memory and to retrieve a data protection field from a location identified based on the index;

a data protection generator, coupled to the content-addressable memory and the comparison mechanism, configured to receive at least a second portion of the index generated by the content-addressable memory and to generate a comparison value based on the index; and

the comparison mechanism configured to compare the comparison value generated by the data protection generator and the data protection field retrieved from the memory in order to identify whether or not there was a data protection error.

34. The apparatus of claim 33, wherein the content-addressable memory includes a binary content-addressable memory.

35. A method comprising:

generating an index by a content-addressable memory based on an input value, the index identifying a matching entry of the content-addressable memory;

generating a comparison value by a data protection generator based at least on a portion of the index received from the content-addressable memory;

acquiring a data protection field from a memory the data protection field being retrieved from an address based at least on a portion of the index received from the content-addressable memory; and

comparing the comparison value generated by the data protection generator to the data protection field acquired from the memory to identify whether or not an error exists.

36. The method of claim 35, wherein the data protection field includes a pre-computed data protection result.

37. The method of claim 35, wherein the content-addressable memory includes a binary content-addressable memory.

38. The method of claim 35, wherein said acquiring the data protection field includes a lookup operation on a memory.

39. The method of claim 35, wherein generating the comparison value includes applying a data protection function to the index.

40. The method of claim 35, further comprising signaling an error condition if the comparison value is not equal to the data protection field.

41. An apparatus comprising:

means for generating an index by a content-addressable memory based on an input value;

means for acquiring a mask value and a data protection field based on the index;

means for generating a comparison value based on the mask value and the input value; and

means for comparing the comparison value to the data protection field in order to identify whether or not an error exists.

42. The apparatus of claim 41, wherein the data protection field includes a pre-computed data protection result.

43. The apparatus of claim 41, wherein the content-addressable memory includes a ternary content-addressable memory.

44. The apparatus of claim 41, wherein said means for acquiring the mask value and the data protection field includes means for performing a lookup operation on a memory.

45. The apparatus of claim 41, wherein said means for generating the comparison value includes:

means for masking the input value with the mask value to generate a masked input value; and

means for applying a data protection function to the masked input value to generate the comparison value.

46. The apparatus of claim 44, wherein said means for comparing includes means for indicating an error condition if the comparison value is not equal to the data protection field.

47. The apparatus of claim 44, wherein the data protection field includes a pre-computed data protection result.

48. An apparatus comprising:

means for receiving an input word and for generating an index;

means for receiving the index and for producing a mask value and a data protection field;

means for generating a masked result based on the input word and the mask value;

means for generating a comparison value based on the masked result; and

means for comparing the comparison value and the data protection field in order to identify whether or not an error exists.

49. The apparatus of claim 48, wherein said means for generating a masked result includes means for decoding the mask value.

50. The apparatus of claim 48, wherein said means for comparing includes means for indicating an error condition if the comparison value is not equal to the data protection field.

51. The apparatus of claim 48, wherein the data protection field includes a pre-computed data protection result.

52. The apparatus of claim 48, wherein said means for receiving the input word and for generating the index includes a content-addressable memory.

53. The apparatus of claim 48, wherein said means for receiving the input word and for generating the index includes a ternary content-addressable memory.

54. An apparatus comprising:

means for receiving an index and for producing a value and a data protection field based on the index;

means for generating a comparison value based on the value; and

means for comparing the comparison value to the data protection field in order to identify whether or not an error exists.

55. The apparatus of claim 54, wherein said means for receiving the index and for producing the value and the data protection field includes a binary content-addressable memory.

56. The apparatus of claim 55, wherein the data protection field includes a pre-computed data protection result for the value.

57. An apparatus comprising:

means for generating an index based on an input value to a content-addressable memory identifying a matching entry of the content-addressable memory;

means for generating a comparison value based on the index received from the content-addressable memory;

means for acquiring a data protection field from a memory based on the index received from the content-addressable memory; and

means for comparing the comparison value generated by said means for generating the comparison value to the data protection field acquired by said means for acquiring the data protection field in order to identify whether or not an error exists.

58. The apparatus of claim 57, wherein said means for generating the index based on the input value includes a binary content-addressable memory.

59. The apparatus of claim 57, wherein said means for acquiring the data protection field includes means for performing lookup operation on a memory.

60. The apparatus of claim 57, further comprising means for signaling an error condition if the comparison value is not equal to the data protection field.

61. A computer-readable medium containing computer-executable instructions for performing operations, said operations comprising:

receiving a content-addressable memory index;

extracting a value field and a data protection field from the content-addressable memory index;

performing a data protection function on the value to generate a comparison result; and

comparing the comparison result with the data protection field in order to identify whether or not an error exists.

62. The computer-readable medium of claim 61, wherein the content-addressable memory includes a binary content-addressable memory.

63. The computer-readable medium of claim 61, wherein the data protection field includes a pre-computed data protection result.

64. The computer-readable medium of claim 61, further indicating an error condition if the comparison result is not equal to the data protection field.

65. An apparatus comprising:

a content-addressable memory configured to receive an input word and to perform a content-addressable memory lookup operation in order to generate a data result for the input word, the data result including a value and a data protection field of an entry in the content-addressable memory matching the input value;

a data protection generator, coupled to the content-addressable memory, configured to generate a comparison data protection value based on the value; and

a comparison mechanism, coupled to both of the data protection generator and the content-addressable memory, configured to compare the comparison data protection value and the data protection field in order to identify whether or not there was a data protection error for said content-addressable memory lookup operation.

66. The apparatus of claim 65, wherein the comparison mechanism indicates an error condition if the comparison data protection value is not equal to the data protection field.