Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1999-02-02
2002-03-05
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C365S049130
Reexamination Certificate
active
06353873
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention is generally directed to the storage, manipulation and retrieval of information from a memory. More particularly, the present invention is directed to a method and apparatus for locating the longest prefix match in a content addressable memory.
Content addressable memory (CAM) is a known type of associative memory which provides for retrieval of information based on partial knowledge of that information. An exemplary CAM controller is disclosed in pending U.S. application Ser. No. 08/970,718 filed Nov. 14, 1997, now U.S. Pat. No. 6,226,710 B1, entitled “Content Addressable Memory (CAM) Engine,” referred to herein as the CAM-Engine, which is herein incorporated by reference in its entirety. In routing processors on networks, an important task is to determine a next destination address for a particular message. This task may be performed by using look up tables to match addresses to locations. If a match is found, the associated data is returned to the processor. Such lookup tables can be fairly large and thus a search using normal methods of storing data in a random access memory are time consuming. Usual methods are inefficient and unresponsive when managing large look up tables. Thus, there is a need in the art for improved methods for accessing information in content addressable memory.
SUMMARY OF THE INVENTION
An exemplary embodiment of the invention is a method and apparatus for determining the longest prefix match in a content addressable memory. A content addressable memory device comprises an application specific integrated circuit which interfaces between a general microprocessor and a random access memory so as to create an associative memory structure which includes transition nodes, significant nodes and arcs. A table including multiple data structures is created in the random access memory by the device for storing prefixes and associated data in a predetermined manner. The table is manipulated by the device in response to commands such as add data, delete data, and search for data by the microprocessor.
The above-discussed and other features and advantages of the present invention will be appreciated and understood by those skilled in the art from the following detailed description and drawings.
REFERENCES:
patent: 4602368 (1986-07-01), Circello et al.
patent: 4758982 (1988-07-01), Price
patent: 4758983 (1988-07-01), Berndt
patent: 5053951 (1991-10-01), Nusinov et al.
patent: 5383146 (1995-01-01), Threewitt
patent: 5423015 (1995-06-01), Chung
patent: 5530958 (1996-06-01), Agarwal et al.
patent: 5568415 (1996-10-01), McLellan et al.
patent: 5602764 (1997-02-01), Eskandari-Gharnin et al.
patent: 5615309 (1997-03-01), Bezek et al.
patent: 5615360 (1997-03-01), Bezek et al.
patent: 5619446 (1997-04-01), Yoneda et al.
patent: 5640534 (1997-06-01), Liu et al.
patent: 5706224 (1998-01-01), Srinivasan et al.
patent: 5752260 (1998-05-01), Liu
patent: 5761714 (1998-06-01), Liu et al.
patent: 5787458 (1998-07-01), Miwa
patent: 5796974 (1998-08-01), Goddard et al.
patent: 5806083 (1998-09-01), Edgar
Aeroflex UTMC Microelectronic Systems Inc.
Kim Matthew
Morgan & Finnegan , LLP
Tran Denise
LandOfFree
Apparatus and method to determine a longest prefix match in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method to determine a longest prefix match in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method to determine a longest prefix match in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2845039