Method and apparatus for overlaying flat and tree based data sets onto content addressable memory (CAM) device
AssigneeNetLogic Microsystems, Inc.
InventorsMark Birman, Ajay Srikrishna, Srinivasan Venkatachary
Life of this patent
Estimating the term…
Abstract
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., FIB0, FIB1, ACL0) 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>).
Claims23
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.
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.
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.
Dependencies are inferred from the claim text.