Method and apparatus for determining a longest prefix match in a segmented content addressable memory device

摘要

A method and apparatus for determining a longest prefix match in a segmented content addressable memory (CAM) device. The CAM device includes multiple CAM array blocks that each may be arbitrarily loaded with CIDR addresses. For one embodiment, each 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), and prefix logic circuits for comparing the logical state of the CAM match line with the prefix mask data. The prefix logic circuits determine the longest prefix in each CAM array block from among CAM entries that match the search key. The longest prefixes from each block are provided to compare circuitry that determines which of the longest prefixes is the longest for the entire CAM device. A block select circuit selects the CAM array block that stores the longest prefix for the entire CAM device for comparison with the prefix mask data in that CAM array block. The CAM index or address of the matching location may then be output from the CAM device. By restricting the search of the device-level longest prefix to only one CAM array block, power drawn by this comparison is reduced over searching all CAM array blocks in parallel.