Multi-level content addressable memory

Abstract

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:
 an output content addressable memory coupled to receive a first search result reference from a first search type and a second search result reference from a second search type, wherein the output content addressable memory is operable to generate 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  further comprising a first content addressable memory module, wherein the first content addressable memory module comprises:
 a content addressable memory device operable to output a search result based on a search key of the first search type; and   a priority encoder coupled to receive the search result from the content addressable memory device, wherein the priority encoder encodes the search result into an address of an equivalence class memory.   
     
     
         3 . The multi-level content addressable memory of  claim 1  further comprising a first content addressable memory module, wherein the first content addressable memory module comprises:
 a content addressable memory device operable to output a search result based on a search key of the first search type;   an equivalence class memory configured to store equivalence class identifiers; and   a priority encoder coupled to receive the search result from the content addressable memory device, wherein the priority encoder 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 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 data frame and the second search type represents a search on a destination search key formed from a destination address associated with the 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:
 generating an output search result from an output content addressable memory based on a first search result reference from a first search type and a second search result reference from a second search type received by the output content addressable memory.   
     
     
         11 . The method of  claim 10  further comprising:
 outputting a search result from a content addressable memory device based on a 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  further comprising:
 outputting a search result from a content addressable memory based on a 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 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 data frame and the second search type represents a search on a destination search key formed from a destination address associated with the 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
 an output content addressable memory coupled to receive a first search result reference from a first search type and a second search result reference from a second search type, wherein the output content addressable memory is operable to generate 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 data frame and the second search type represents a search on a destination search key formed from a destination address associated with the data frame. 
     
     
         21 . A multi-level content addressable memory comprising:
 a first content addressable memory configured to output a first search result reference from a first search type;   a second content addressable memory configured to output a second search result reference from a second search type; and   means for generating an output search result based on the first search result reference and the second search result reference.   
     
     
         22 . The multi-level content addressable memory of  claim 21  further comprising:
 means for outputting a search result from the first content addressable memory device based on a search key of the first search type;   means for selecting a priority bit from the search result; and   means for encoding the priority bit into an address of an equivalence class memory as the first search result reference.   
     
     
         23 . The multi-level content addressable memory of  claim 21  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 data frame and the second search type represents a search on a destination search key formed from a destination address associated with the data frame.