Multi-level content addressable memory
View Patent ↗A multi-level content addressable memory (CAM) architecture compresses out much of the redundancy encountered in the search space of a single CAM, particularly for flow-based lookups in a network. Destination and source address may be associated with internal equivalence classes independently in one level of the multi-level CAM architecture, while flow-specific properties linking arbitrary classes of the destination and source addresses may be applied in a later level of the multi-level CAM.
1. A multi-level content addressable memory comprising:
a first content addressable memory module that receives a search key of a first search type and outputs a first search result reference;
a second content addressable memory module that receives a search key of a second search type and outputs a second search result reference; and
an output content addressable memory coupled to receive the first search result reference from the first content addressable memory module and the second search result reference from the second content addressable memory module, wherein the output content addressable memory outputs an output search result based on the first search result reference and the second search result reference.
2. The multi-level content addressable memory of claim 1 wherein the first content addressable memory module comprises:
a content addressable memory device that receives the search key of the first search type and outputs a search result based on the search key of the first search type; and
a priority encoder that receives the search result from the content addressable memory device and encodes the search result into an address of an equivalence class memory.
3. The multi-level content addressable memory of claim 1 wherein the first content addressable memory module comprises:
a content addressable memory device that receives the search key of the first search type and outputs a search result based on the search key of the first search type;
an equivalence class memory storing equivalence class identifiers; and
a priority encoder that receives the search result from the content addressable memory device and encodes the search result into an address to an equivalence class identifier stored in the equivalence class memory, wherein the equivalence class identifier represents the first search result reference.
4. The multi-level content addressable memory of claim 1 wherein the first search result reference identifies an equivalence class.
5. The multi-level content addressable memory of claim 1 wherein the output content addressable memory module comprises a RAM-based binary search tree.
6. The multi-level content addressable memory of claim 1 wherein the multi-level content addressable memory implements a forwarding database in a network communications device, and further the first search type represents a search on a source search key formed from a source address associated with a received data frame and the second search type represents a search on a destination search key formed from a destination address associated with the received data frame.
7. The multi-level content addressable memory of claim 1 wherein the output search result of the output content addressable memory represents a port number of a network communications device.
8. The multi-level content addressable memory of claim 1 wherein the output search result of the output content addressable memory represents a virtual input queue reference of a network communications device.
9. The multi-level content addressable memory of claim 1 wherein the output search result of the output content addressable memory represents a virtual output queue reference of a network communications device.
10. A method for processing data using a multi-level content addressable memory comprising:
receiving a search key of a first search type in a first content addressable memory module;
outputting a first search result reference from the first content addressable memory module, based on the search key of the first search type;
receiving a search key of a second search type in a second content addressable memory module;
outputting a second search result-reference from the second content addressable memory module, based on the search key of the second search type;
outputting an output search result from output content addressable memory based on the first search result reference and the second search result reference, wherein the output content addressable memory is coupled to receive the first search result reference from the first content addressable memory module and the second search result reference from the second content addressable memory module.
11. The method of claim 10 wherein the operation of receiving a search key of a first search type in a first content addressable memory module comprises:
receiving the search key into a content addressable memory device;
outputting a search result from the content addressable memory device based on the search key of the first search type;
selecting a priority bit from the search result; and
encoding the priority bit into an address of an equivalence class memory as the first search result reference.
12. The method of claim 10 wherein the operation of receiving a search key of a first search type in a first content addressable memory module comprises:
receiving the search key of the first search type into a content addressable memory device;
outputting a search result from the content addressable memory based on the search key of the first search type;
selecting a priority bit from the search result;
encoding the priority bit into an address of an equivalence class memory; and
outputting an equivalence class identifier from the equivalence class memory as the first search result reference.
13. The method of claim 10 wherein the first search result reference identifies an equivalence class.
14. The method of claim 10 wherein the output content addressable memory module comprises a RAM-based binary search tree.
15. The method of claim 10 wherein the multi-level content addressable memory implements a forwarding database in a network communications device, and further the first search type represents a search on a source search key formed from a source address associated with a received data frame and the second search type represents a search on a destination search key formed from a destination address associated with the received data frame.
16. The method of claim 10 wherein the output search result of the output content addressable memory represents a port number of a network communications device.
17. The method of claim 10 wherein the output search result of the output content addressable memory represents a virtual input queue reference of a network communications device.
18. The method of claim 10 wherein the output search result of the output content addressable memory represents a virtual output queue reference of a network communications device.
19. A network communications device comprising:
a multi-level content addressable memory including
a first content addressable memory module that receives a search key of a first search type and outputs a first search result reference;
a second content addressable memory module that receives a search key of a second search type and outputs a second search result reference; and
an output content addressable memory coupled to receive the first search result reference from the first content addressable memory module and the second search result reference from the second content addressable memory module, wherein the output content addressable memory outputs an output search result based on the first search result reference and the second search result reference.
20. The network communications device of claim 19 wherein the multi-level content addressable memory implements a forwarding database in the network communications device, and further the first search type represents a search on a source search key formed from a source address associated with a received data frame and the second search type represents a search on a destination search key formed from a destination address associated with the received data frame.