Content addressable memory device

Details Content addressable memory device Content addressable memory device

2002-02-01

2004-02-24

Dinh, Son T. (Department: 2824)

Static information storage and retrieval

Associative memories

Ferroelectric cell

C365S189070, C711S108000

Reexamination Certificate

active

06697276

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to information retrieval systems and more particularly to content addressable memory devices.
BACKGROUND
Content addressable memory (CAM) devices are often used to support packet forwarding and classification operations in network switches and routers. A CAM device can be instructed to compare a search value, typically formed from one or more fields within the header of an incoming packet, with entries within an associative storage array of the CAM device. If the search value matches an entry, the CAM device generates an index that corresponds to the location of the matching entry within the storage array, and asserts a match flag to signal the match. The index may then be used to address another storage array, either within or separate from the CAM device, to retrieve routing or classification information for the packet.
FIG. 1
illustrates a prior art CAM device
100
that includes a CAM array
101
coupled to match logic
103
via a plurality of match lines
105
(ML). During a search operation, a search key is compared with the contents of each row of CAM cells
107
within the CAM array
101
to generate a corresponding row match signal. Each row match signal is either asserted or deasserted to indicate a match or mismatch condition, and is output to the match logic
103
via a respective one of the match lines
105
. The match logic
103
responds to an asserted match signal by generating a match address
114
(MA) that corresponds to the row of CAM cells
107
that signaled the match, and by asserting a match flag
116
(MF) to indicate the match detection.
Referring to
FIG. 2
, each CAM cell
107
within the CAM array of
FIG. 1
includes both a storage element
123
and a compare circuit
125
. During a search operation, a data bit within the storage element is compared to a corresponding bit (B
SK
) of the search key. If the bits do not match, compare circuit
125
pulls match line
105
low to indicate the mismatch. By integrating a storage element and compare circuit within each CAM cell
107
of the CAM array in this manner, a search key may be simultaneously compared with the contents of each row of CAM cells, thereby providing a massively parallel, and therefore extremely rapid search.
Although the integration of compare and storage circuits within each CAM cell
107
enables simultaneous, multi-row searching within the CAM array, the additional transistors required to implement the compare circuit significantly increases the size of the cell
107
, reducing the memory density that can be achieved within the CAM device. Also, because each compare circuit in each row of CAM cells is simultaneously activated during a search operation, a relatively large amount of power is required to perform a search. This power consumption results in heat generation that further limits the storage density that can be achieved within the CAM device (i.e., due to thermal constraints).


REFERENCES:
patent: 4897720 (1990-01-01), Wu et al.
patent: 5319589 (1994-06-01), Yamagata et al.
patent: 5544357 (1996-08-01), Huei
patent: 5920900 (1999-07-01), Poole et al.
patent: 6226710 (2001-05-01), Melchior
J. Da Silva and I. Watson, “Pseudo-Associative Store with Hardware Hashing,” IEE Proceedings, Computers and Digital Techniques, vol. 130, Pt. E, No. 1, Jan. 1983, pp. 19-24.
D. Knuth, “The Art of Computer Programming, vol. 3, Sorting and Searching, Second Edition,” Addison Wesley Longman, 1998, pp. 541-545.
V. Srinivasan, S. Suri and G. Varghese, “Packet Classification using Tuple Space Search,” Proceedings of SIGCOMM, 1999, pp. 135-146.
Z. Cao, Z. Wang and E. Zegura, “Perfromance of Hashing-Based Schemes for Internet Load Balancing,” Proc. IEEE INFOCOM 2000, Conf. on Computer Comm., vol. 1, 19th Annual Joint Conf. of the IEEE Computer and Comm. Soc., Tel Aviv, Israel, Mar. 26-30, 2000, pp. 1-10.
A. Broder and M. Mitzenmacher, “Using Multiple Hash Functions to Improve IP Lookups,” Proceedings of IEEE INFOCOM, 2001, pp. 1454-1463.

Affiliated with

Also associated with

Rating

Content addressable memory device does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Content addressable memory device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Content addressable memory device will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3322719