Method and apparatus for overlaying flat and tree based data sets onto content addressable memory (CAM) device
View Patent ↗A content addressable memory device ( 100 ) and method can have CAM blocks ( 102 - 0 to 102 - 29 ) organized in block sections ( 104 - 0 to 104 - 6 ). In an overlay mode of operation, an overlay engine ( 106 ) can access an algorithmic search (SPEAR) CAM ( 102 - 28 and 102 - 29 ) to generate overlay data set search keys (keyFIB< 0 > and < 1 >). Multiple data sets (e.g., FIB 0 , FIB 1 , ACL 0 ) can be accommodated on the same CAM device by search key multiplexers ( 108 - 0 to 108 - 6 ) that selectively apply any of a number of data set search keys (keyACL< 0 >, keyFIB< 0 > and keyFIB< 1 >).
1. A content addressable memory (CAM) device, comprising:
a plurality of regular CAM blocks each having a plurality of CAM entries for comparing stored data values with corresponding internal search key values;
at least one algorithmic search CAM block for storing data set values that generate match results corresponding at least a first search data set in response to at least a portion of an external search key data value; and
an overlay engine that, in an overlay mode, generates an overlay search key in response to a match result from the at least one algorithmic search CAM block, and applies the overlay search key to at least one regular CAM block, and in a non-overlay mode, generates at least one non-overlay search key from an external search key data value without accessing the algorithmic search CAM block, and applies the non-overlay search key to at least one regular CAM block storing data set values of a second data set.
2. The CAM device of claim 1 , wherein:
the at least one regular CAM block stores at least a portion of a forwarding information base (FIB).
3. The CAM device of claim 1 , wherein:
in the non-overlay mode, the overlay generates at least one non-overlay search key from an external search key data value without accessing the algorithmic search CAM block, and applies the non-overlay search key to the algorithmic search CAM block.
4. The CAM device of claim 1 , wherein:
the second data set comprises at least one access control list (ACL).
5. The CAM device of claim 1 , wherein:
the CAM device comprises an array of N×M block areas, where N and M are integers greater than one, at least one algorithmic search CAM block occupying at least one circuit block area, a majority of the remaining circuit block areas containing one of the regular CAM blocks.
6. The CAM device of claim 5 , wherein:
the overlay engine occupies at least one of the circuit block areas.
7. The CAM device of claim 6 , wherein:
the at least one circuit block area containing the at least one algorithmic search CAM block is adjacent to the at least one circuit block area containing the overlay engine.
8. The CAM device of claim 1 , wherein:
the CAM device comprises an array of N×M block areas, where N and M are integers greater than one; and
the overlay engine occupies a space outside of the N×M block areas.
9. The CAM device of claim 1 , wherein:
the overlay engine further comprises an algorithmic search random access memory for receiving index values from the algorithmic search CAM block and generating overlay search keys therefrom.
10. The CAM device of claim 1 , wherein:
the overlay engine further includes a decoder for decoding a portion of an external search key value to establish the overlay mode.
11. A content addressable memory (CAM) device, comprising:
a plurality of regular CAM blocks each having a plurality of CAM entries for comparing stored data values with corresponding internal search key values;
at least one algorithmic search CAM block for storing data set values that generate match results corresponding to at least a first search data set in response to at least a portion of an external search key data value;
an overlay engine that, in an overlay mode; generates an overlay search key in response to a match result from the at least one algorithmic search CAM block, and applies the overlay search key to at least one regular CAM block, and in a predetermined mode, generates at least one non-overlay search key from an external search key data value without accessing the algorithmic search CAM block, and applies the non-overlay search key to at least one regular CAM block storing data set values of a second data set different from the first data set;
the CAM blocks are organized into block sections to which data set search key values are commonly applied;
a mode selector that determines which regular CAM block receives which search key according to configuration selection bits; and
a selector multiplexer (MUX) corresponding to each block section, each selector MUX having at least one input for
receiving an overlay search key and at least one input for receiving a non-overlay search key, and a MUX output coupled to the corresponding block section.
12. The CAM device of claim 11 , wherein:
the overlay search key and non-overlay search key are provided to the block sections by search key wiring; and
each selector MUX is formed below the search key wiring.
13. The CAM device of claim 11 , further including:
a configuration store having a plurality of configuration storage locations, each configuration storage location storing a set of configuration bits for defining search characteristics for the block sections, each configuration storage location being selectable by at least a portion of the external search key data.
14. The CAM device of claim 13 , wherein:
the search characteristics defined by each set of configuration bits are selected from the group consisting of: how portions of the external search key are applied to the block section, which data sets are searched in the block section, and which data sets can be searched simultaneously in the block section.
15. The CAM device of claim 11 , wherein:
each block section provides compare results to one of a plurality of compare result buses.
16. A method for performing multiple data sets search types on the same content addressable memory (CAM) device, comprising the steps of:
providing a plurality CAM entries arranged into entry groups for selectively storing data values for one of a plurality of data sets;
in an overlay mode, searching an overlay mode portion of the CAM entries according to at least a portion of an external search key value to generate an overlay data set search key, and searching selected non-overlay mode portions of the CAM entries with the overlay data set search key;
in a non-overlay mode, generating non-overlay data set search keys from the external search key value without accessing the overlay mode portion of the CAM entries, and searching selected non-overlay mode portions of the CAM entries with the non-overlay data set search key; and
the non-overlay mode portion of the CAM entries are arranged into a plurality of CAM blocks, each comprising a plurality of CAM entries, the CAM blocks being organized into block sections, the CAM blocks of each block section commonly receiving the overlay data set search key in the overlay mode and the non-overlay data set search key in the non-overlay mode.
17. The method of claim 16 , wherein:
the overlay data set search key comprises at least a portion of the external search key value.
18. The method of claim 16 , wherein:
the overlay mode also includes, according to predetermined external search key data,
generating non-overlay data set search keys from the external search key value without accessing the overlay mode portion of the CAM entries, and
searching at least a first set of the CAM entries with the overlay data set search key and searching at least a second set of the CAM entries with the non-overlay data set search key, essentially simultaneously.
19. The method of claim 16 , wherein:
the plurality of data sets comprises at least one forwarding information base and at least one access control list.
20. The method of claim 16 , wherein:
the overlay mode includes multiplexing one of a plurality of data set search keys to a corresponding entry group, the data set search keys including overlay data set search key for application to a corresponding entry group.
21. The method of claim 16 , wherein:
the non-overlay mode portion of the CAM entries are arranged into block sections, and
the method further includes a write operation, comprising
receiving a data set value, and
writing the data set value to block section if configuration bits for the entry group correspond to the block section.
22. The method of claim 16 , wherein:
the block sections have a priority with respect to one another,
the data set values include at least a first data set and a second data set, the first data set value having a higher priority than the second data set value, and
writing the data set values includes
writing data set values of the first data set to block sections of higher priority than block sections containing data values of the second data set.
23. The method of claim 16 , wherein:
the CAM blocks include a plurality of regular CAM blocks and at least one redundant CAM block for replacing a defective regular CAM block, and if a redundant CAM block is available, assigning such a redundant CAM block as at least a portion of the overlay mode portion of the CAM entries.