A method and apparatus for determining a longest prefix match in a content addressable
memory (CAM) device is described. The CAM device includes a CAM array that may
be arbitrarily loaded with CIDR addresses that are not prearranged prior to their
entry into the CAM device. For one embodiment, the CAM array is a ternary CAM array
that includes CAM cells storing CAM data, mask cells storing prefix mask data for
the corresponding CAM cells, a CAM match line for indicating a match between a
search key and the CAM data (as masked by the prefix mask data), prefix match lines,
and prefix logic circuits for comparing the CAM match line with the prefix mask
data. The prefix logic circuits determine the longest prefix among the CAM locations
that match the search key, regardless of where the matching locations are logically
located in the CAM array. The longest prefix is then compared against the prefix
mask data stored in the mask cells to determine the location in the CAM array that
stores the CIDR address corresponding to the longest prefix. The CAM index or address
of the matching CIDR address may then be output from the CAM device. Additionally
and/or alternatively, additional or associated data stored at the CAM index may
be accessed. The additional or associated data may be, for example, routing information
for the stored CIDR address.
