Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2001-09-28
2004-02-03
Moazzami, Nasser (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S206000, C365S049130
Reexamination Certificate
active
06687786
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the field of data memories, and more particularly relates to storage of information using content-addressable Memory.
2. Description of the Related Art
A Content Addressable Memory (CAM) is a specialized memory device that is used for fast searches of data stored in the CAM. In some networking systems, CAMs are used to store packet pointers. When packets arrive at such a system, the system assigns a specific identification tag (ID) to each packet and places the ID and the packet pointer into a CAM. The packets are later retrieved by searching for a given ID. Generally, a CAM's architecture includes a table of memory cells to store data and control logic to search and compare the data in the table. To search for a data, a system provides the data to be searched and the control logic of the CAM performs the search and provides search results to the system. Two types of CAMs are binary CAMs and Ternary CAMs (TCAMs). A binary CAM searches for and recognizes data that is comprised of bits that can have two states, 0 and 1. A TCAM searches for and recognizes three states: 0, 1, and X (“don't care”).
When a data is to be written into a CAM, the system must usually find an empty location (free entry) in the CAM. Generally, the process of data search in a given CAM table takes one clock cycle. Multiple clock cycles may be required to write data to an entry in the CAM.
One method to find empty locations in a CAM is to maintain a list of locations that are empty. This method requires a large memory structure to maintain such list. Another method of finding empty locations in the CAM is to designate one bit of each location in the CAM to represent whether the location is empty or occupied. Every time data is to be written into the CAM, the system looks up an empty location by searching for the designated bit. The problem with this method is that there is latency associated with the search. Once a lookup instruction is posted to the CAM, the system waits until an empty location address is returned. The lookup process can take a significant amount of time. In addition, a lookup must follow every write to the CAM. In some cases, the lookup process uses up to 20 percent of the CAM bandwidth.
SUMMARY
The present invention describes a method for managing free entries in a content-addressable memory. The method includes assigning memory locations in the content-addressable memory to multiple virtual pages, pre-fetching an address of at least one free memory location from at least one of the virtual pages, and storing the address in a free entry list. The method further includes retrieving the address from the free entry list and storing data in the content-addressable memory using the address. The assigning of the virtual pages is independent of a physical address of the memory locations. In one embodiment of the present invention, the storing of the address in the free entry list is done on a round-robin basis for each one of the virtual pages. In another embodiment of the present invention, each writing of data is done in a different virtual page than a previous writing of data, and the pre-fetching the address of free memory location in one of the virtual pages is done while data is being written in a different virtual page.
The method further includes receiving a first data to write in the content-addressable memory, searching for a first address of first memory location in the free entry list, and if the first address of the first memory location is not found, generating an error message. The method further includes if the first address of the first memory location is found in the free entry list, writing the first data in the first memory location, setting a valid bit of the first memory location to indicate ‘not free’, removing the first address of the first memory location from the free entry list, pre-fetching a second address of a second free memory location in the content-addressable memory and storing the second address of the second free memory location in the free entry list. In one embodiment of the present invention, the pre-fetching of the second address of the second free memory location is done from one of the virtual pages assigned to the first memory location.
In one embodiment of the present invention, the method further includes receiving a request to retrieve a second data from the content-addressable memory. During retrieval, the method further includes searching for the second data in the content-addressable memory and if the second data is not found in the content-addressable memory, responding with an error. If the second data is found in the content-addressable memory, retrieving the second data from a third memory location, setting the valid bit of the third memory location to indicate ‘free’ and assigning one of the virtual pages to the third memory location. In one embodiment of the present invention, the third memory location is assigned a different virtual page than the third memory location had before the retrieval of the second data
The foregoing is a summary and thus contains, by necessity, simplifications, generalizations and omissions of detail; consequently, those skilled in the art will appreciate that the summary is illustrative only and is not intended to be in any way limiting. Other aspects, inventive features, and advantages of the present invention, as defined solely by the claims, will become apparent in the non-limiting detailed description set forth below.
REFERENCES:
patent: 5392415 (1995-02-01), Badovinatz et al.
patent: 5600820 (1997-02-01), Johnson
patent: 6026467 (2000-02-01), Petty
patent: 6366996 (2002-04-01), Hobson et al.
patent: 6425048 (2002-07-01), Kaganoi
patent: 6446188 (2002-09-01), Henderson et al.
patent: 6477634 (2002-11-01), Comment
patent: 6490671 (2002-12-01), Frank et al.
patent: 6516383 (2003-02-01), Patra et al.
Hoffman Robert L.
Parlan Jonathan M.
Wong Calvin C.
Campbell Stephenson Ascolese LLP
Cisco Technology Inc.
Moazzami Nasser
LandOfFree
Automated free entry management for content-addressable... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Automated free entry management for content-addressable..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automated free entry management for content-addressable... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3335622