Distributed content addressable memory

• US 20030009618A1
• Filed: 06/26/2002
• Published: 01/09/2003
• Est. Priority Date: 07/06/2001
• Status: Active Grant

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Micron Technology, Inc.
• Inventors: Regev, Alon, Regev, Zvi
• Granted Patent: US 6,959,358 B2
• Time in Patent Office: Days
• US Class Current: 711/108
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories

Abstract

The present invention provides a large capacity distributed content addressable memory (CAM) made up of a plurality of smaller CAMs interconnected on a high speed data bus. Each of the smaller CAMs is located at a local node on the data bus and configured to receive commands originating from both the local node in which the CAM is located and a local node in which another CAM on the data bus is located. As the resources and the data being stored by all the CAMs are shared through the high speed data bus, the aggregate contents of all the CAMs can be viewed as being stored in a single virtual CAM.

Claims

1. A distributed content addressable memory (CAM), comprising:

a plurality of CAMs interconnected on a ring bus by a first plurality of data paths that make up the ring bus such that a command received at a first CAM on said ring bus is executable by at least one CAM on the ring bus.

2. The distributed CAM of claim 1, wherein said command received at said first CAM is executable by said first CAM and also executable by at least a second CAM on said ring bus.

3. The distributed CAM of claim 1, wherein each of said plurality of CAMs is associated with a local node of said distributed CAM.

4. The distributed CAM of claim 1, wherein each CAM further comprises:

a ring bus input for receiving first input data from said ring bus;

a CAM controller coupled to said ring bus input for controlling processing of said first input data;

a CAM array coupled to said CAM controller for comparing data stored by said CAM array with at least a portion of said first input data;

a CAM output multiplexer coupled to said CAM array for receiving a result of the comparison and for generating first output data; and

a ring bus output coupled to said CAM array for passing said first output data.

5. The distributed CAM of claim 4 further comprising:

an input controller coupled between the ring bus input and the CAM controller for controlling routing of said first input data.

6. The distributed CAM of claim 5 further comprising:

a ring first-in-first-out (FIFO) buffer coupled between said input controller and said CAM controller for temporarily storing said first input data.

7. The distributed CAM of claim 4 further comprising:

a local input for receiving second input data from a local node of said ring bus, an output of said local input being coupled to an input of said CAM controller; and

a local output for passing second output data, generated by said CAM output multiplexer, to said local node of said ring bus.

8. The distributed CAM of claim 7 further comprising

a local first-in-first-out (FIFO) buffer coupled between the local input and the CAM controller for temporarily storing said second input data;

and

a local output buffer coupled between said CAM output multiplexer and said local output for temporarily storing said second output data.

9. The distributed CAM of claim 4 further comprising:

a plurality of result registers respectively coupled between said CAM array and said CAM output multiplexer for storing the results of the comparisons between the stored data and said at least a portion of the first input data.

10. The distributed CAM of claim 5 further comprising:

a data path coupling said input controller and a local output of said CAM such that a result received by said CAM from another CAM on said ring bus is directed to said local output.

11. The distributed CAM of claim 1, wherein said plurality of CAMs are interconnected by a second ring bus.

16. The CAM of claim 15 further comprising:

an input controller for receiving said first input data from said ring bus, said input controller controlling processing of said first input data such that first input data that did not originate with said local node is processed in a first manner and first input data that did originate with said local node is processed in a second manner.

17. The CAM of claim 16 further comprising:

a CAM controller coupled to said input controller for processing said first input data in said first manner; and

a local output buffer coupled to said input controller for processing said first input data in said second manner.

18. The CAM of claim 17 further comprising:

a CAM array coupled to said CAM controller for comparing data stored by said CAM array with at least a portion of at least one of said first and second input data; and

a CAM output multiplexer coupled to said CAM array for receiving a result of the comparison and for generating at least one of said first and second output data.

19. The CAM of claim 18 further comprising:

a plurality of result registers coupled between said CAM array and said CAM output multiplexer for storing the results of the comparisons between data stored by said CAM array and said at least a portion of at least one of said first and second input data.

12. A distributed content addressable memory (CAM), comprising:

a plurality of CAMs interconnected on a ring bus by a plurality of data paths that make up the ring bus such that a command received at a first CAM on said ring bus is executable at said first CAM and also executable at every other CAM on said ring bus.

13. A distributed content addressable memory (CAM), comprising:

a first CAM having a data input and a data output; and

a data input of a second CAM coupled to said data output of said first CAM via a first data path, and a data output of said second CAM coupled to said data input of said first CAM via a second data path such that a command received from a local input of said first CAM is executable at both said first and said second CAMs.

14. A packet structure for use with a distributed content addressable memory (CAM), said packet structure comprising:

a source node portion for identifying a local node on a ring bus of said distributed CAM from which said packet originated;

a request identification portion for matching a request, and a response to the request, associated with said packet;

a command portion for identifying a specific command;

a data length portion indicating a quantity of data associated with said packet; and

a data portion including said data.

15. A content addressable memory (CAM), comprising:

a first input for receiving first input data from a ring bus to which the CAM is coupled;

a first output for passing first output data to said ring bus;

a second input for receiving second input data from a local node to which said CAM belongs; and

a second output for passing second output data from said CAM to said local node.

20. A content addressable memory (CAM), comprising:

a first input for receiving first input data from a ring bus to which said CAM is coupled;

a second input for receiving second input data from a local node of said ring bus to which said CAM belongs;

a CAM controller coupled to said first and second inputs for controlling processing of said first and second input data;

a CAM array coupled to said CAM controller for storing data to be compared with at least respective portions of said first and second input data;

a plurality of result registers coupled to said CAM array for indicating a result of comparing the stored data with said respective portions of the first and second input data;

a CAM output multiplexer for receiving said results and for generating first and second output data based on said results;

a first output for passing said first output data from said CAM to said ring bus; and

a second output for passing said second output data from said CAM to said local node.

21. A semiconductor memory chip, comprising:

a distributed content addressable memory (CAM), said distributed CAM comprising;

a plurality of CAMs interconnected on a ring bus by a plurality of data paths that make up the ring bus such that a command received at a first CAM on said ring bus is executable at said first CAM and also executable at at least a second CAM of said plurality of CAMs.

22. The memory chip of claim 21, wherein each of said plurality of CAMs is associated with a local node of said distributed CAM.

23. The memory chip of claim 21, wherein each CAM further comprises:

a ring bus input for receiving first input data from said ring bus;

a CAM controller coupled to said ring bus input for controlling processing of said first input data;

a CAM array coupled to said CAM controller for comparing data stored by said CAM array with at least a portion of said first input data;

a CAM output multiplexer coupled to said CAM array for receiving a result of the comparison and for generating first output data; and

a ring bus output coupled to said CAM array for passing said first output data.

24. The memory chip of claim 23, wherein each CAM further comprises:

an input controller coupled between the ring bus input and the CAM controller for controlling routing of said first input data.

25. The memory chip of claim 24, wherein each CAM further comprises:

a ring first-in-first-out (FIFO) buffer coupled between said input controller and said CAM controller for temporarily storing said first input data.

26. The memory chip of claim 23, wherein each CAM further compries:

a local input for receiving second input data from a local node of said ring bus, an output of said local input being coupled to an input of said CAM controller; and

a local output for passing second output data, generated by said CAM output multiplexer, to said local node of said ring bus.

27. The memory chip of claim 26, wherein each CAM further comprises:

a local first-in-first-out (FIFO) buffer coupled between the local input and the CAM controller for temporarily storing said second input data; and

a local output buffer coupled between said CAM output multiplexer and said local output for temporarily storing said second output data.

28. The memory chip of claim 23, wherein each CAM further comprises:

a plurality of result registers respectively coupled between said CAM array and said CAM output multiplexer for storing the result of the comparison between the stored data and said at least a portion of the first input data.

29. The memory chip of claim 24, wherein each CAM further comprises:

a data path coupling said input controller and a local output of said CAM such that a result received by said CAM from another CAM on said ring bus is directed to said local output.

30. The memory chip of claim 21, wherein said plurality of CAMs are interconnected by a second ring bus.

31. A router, comprising:

a plurality of message receiving inputs;

a plurality of message transmitting outputs; and

a distributed content addressable memory (CAM), said distributed CAM comprising;

a plurality of CAMs interconnected on a ring bus by a plurality of data paths that make up the ring bus such that a command received at a first CAM on said ring bus is executable by at least one CAM on the ring bus.

32. The router of claim 31, wherein said command received at said first CAM is executable by said first CAM and also executable by at least a second CAM on said ring bus.

33. The router of claim 31, wherein each of said plurality of CAMs is associated with a local node of said distributed CAM.

34. The router of claim 31, wherein each CAM further comprises:

a ring bus input for receiving first input data from said ring bus;

a CAM controller coupled to said ring bus input for controlling processing of said first input data;

a CAM array coupled to said CAM controller for comparing data stored by said CAM array with at least a portion of said first input data;

a CAM output multiplexer coupled to said CAM array for receiving a result of the comparison and for generating first output data; and

a ring bus output coupled to said CAM array for passing said first output data.

35. The router of claim 31 further comprising a semiconductor chip containing said distributed CAM.

36. The router of claim 34, wherein each CAM further comprises:

an input controller coupled between the ring bus input and the CAM controller for controlling routing of said first input data.

37. The router of claim 36, wherein each CAM further comprises:

a ring first-in-first-out (FIFO) buffer coupled between said input controller and said CAM controller for temporarily storing said first input data.

38. The router claim 34, wherein each CAM further comprises:

a local input for receiving second input data from a local node of said ring bus, an output of said local input being coupled to an input of said CAM controller; and

a local output for passing second output data, generated by said CAM output multiplexer, to said local node of said ring bus.

39. The router of claim 38, wherein each CAM further comprises:

a local first-in-first-out (FIFO) buffer coupled between the local input and the CAM controller for temporarily storing said second input data; and

a local output buffer coupled between said CAM output multiplexer and said local output for temporarily storing said second output data.

40. The router of claim 34, wherein each CAM further comprises:

a plurality of result registers respectively coupled between said CAM array and said CAM output multiplexer for storing the results of the comparisons between the stored data and said at least a portion of the first input data.

41. The router of claim 36, wherein each CAM further comprises:

a data path coupling said input controller and a local output of said CAM such that a result received by said CAM from another CAM on said ring bus is directed to said local output.

42. The router of claim 31, wherein said plurality of CAMs are interconnected by a second ring bus.

43. A method for operating a distributed content addressable memory (CAM), the method comprising:

receiving a command at a first CAM of a plurality of CAMs interconnected on a ring bus; and

executing said command at said first CAM.

44. The method of claim 43 further comprising:

executing said command at at least a second CAM of said plurality of CAMs.

46. The method of claim 45 further comprising:

receiving said result at a ring bus input of said first CAM;

passing said result to a local output buffer of said first CAM; and

receiving said result at a local node coupled to said local output buffer.

47. The method of claim 45, wherein said act of receiving comprises:

receiving said command at a local input of said first CAM.

48. The method of claim 45, wherein said act of executing comprises:

passing said command from said first CAM to said ring bus via a ring bus output of said first CAM;

receiving said command at a ring bus input of said second CAM; and

executing said command at said second CAM.

49. The method of claim 45, wherein said act of passing comprises:

passing said result of said executing operation to a ring bus output of said second CAM and to said ring bus; and

receiving said result at a ring bus input of said first CAM.

50. The method of claim 47, wherein said act of receiving comprises:

receiving said command at a CAM controller of said first CAM;

unsuccessfully attempting to execute said command at a CAM array of said first CAM; and

generating a first data output to be sent to said second CAM in an attempt to execute said command in said second CAM.

51. The method of claim 48, wherein said act of receiving comprises:

receiving said command at a CAM controller of said second CAM;

executing said command at a CAM array of said second CAM; and

generating a data output to be sent from said second CAM to said first CAM notifying said first CAM that said command has been executed.

45. A method for operating a distributed content addressable memory (CAM), the method comprising:

receiving a command at a first CAM of a plurality of CAMs interconnected on a ring bus;

executing said command at a second CAM on said ring bus; and

passing a result of said executing operation to said first CAM via said ring bus.

52. A method of operating a distributed content addressable memory (CAM), the method comprising:

receiving a packet at a ring bus input of a first CAM of a plurality of CAMs interconnected on a ring bus;

determining that said packet originated at said first CAM; and

copying said packet to a local output of said first CAM.

53. A method of operating a distributed content addressable memory (CAM), the method comprising:

receiving a packet at a ring bus input of a first CAM of a plurality of CAMs interconnected on a ring bus;

determining that said packet did not originate at said first CAM; and

executing a command associated with said packet at said first CAM.

54. A method of operating a distributed content addressable memory (CAM), the method comprising:

receiving a learn command at a first CAM of a plurality of CAMs interconnected on a ring bus; and

storing data associated with said learn command only in said first CAM.

55. The method of claim 54 further comprising:

copying said data associated with said learn command to each of said plurality of CAMs.

56. The method of claim 55 further comprising:

subsequently conducting an unsuccessful search for said data in a second CAM; and

copying said data to said second CAM such that any additional searches for said data in said second CAM will be successful.