Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
2002-06-20
2004-08-03
Moazzami, Nasser (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S108000, C711S133000
Reexamination Certificate
active
06772301
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to static information storage and retrieval systems, and more particularly hardware based database storage systems including those commonly employing associative memories, which are also referred to as content memories or tag memories.
BACKGROUND ART
Many real world applications today require searching information at high speed. In particular, as network-systems proliferate in which data packets are transferred based on the contents of address information contained there in, it is increasingly desirable to perform very high speed comparisons to deliver such data packets (“switching” and “routing” are the terms particularly used in the networking and data communication field). This has motivated the industry to turn to hardware solutions, including a class of circuits known as “content addressable memories” (CAM). The following discussion will generally use network routing as an example, although many other applications also exist where high speed searching is desirable, and where the hereby described invention may be useful.
A CAM compares an input string, bit by bit, with a plurality of data words stored in databases in the CAM. If the bits of one of the data words match those of the input data string, the CAM will provide as an output the match address of that data word. This process is typically called table lookup and the data words in the lookup table are called table entries. It should be noted in passing that there may be a number of variations in CAM and in this table lookup process. For instance, matching of a complete string can be undertaken, or only partial matching. A common example of the latter is finding a “longest prefix match.” If multiple matching data words are found, a prioritization scheme is used to output the address of just one match. Detailed coverage of these and other variations will not be provided here, but those skilled in the art will appreciate that this discussion can have wider relevance.
In a typical CAM application, such as network routing, the entries in a routing table desirably have different lifetimes. While some entries need to be “valid” all of the time, and hence remain in the lookup table permanently, other entries need to remain in the lookup table only temporarily.
Furthermore, all of the temporary entries in a lookup table do not have the same frequency of access. A temporary entry that has not been accessed for a long time should eventually be deleted and replaced by a new entry.
To achieve this, each entry is provided with a pre-determined “time to live” and a timer starts after its last access. If an entry is not accessed within its lifetime, it is regarded as invalid or expired and its address in the lookup table is made available for storing a new entry. If an entry is accessed within its lifetime, the associated timer is reset and it begins a “new life.” This aging process makes the lookup database size more manageable and keeps its content current and fresh.
In conventional practice, extra bits are tagged along with each data word when it is made a table entry. These “aging bits” are used to keep track of a respective table entry's time to live. The aging bits are first initialized to the lifetime of the corresponding table entry, and then decremented periodically by an aging clock having a period predetermined by the user of the CAM.
Updating the aging bits is preferably an atomic operation, i.e., no other operation on the bits should be allowed before completion of the update process. This is desirable because the lookup table is being constantly updated by an external host processor, and that dictates that the aging process be carried out in the shortest time possible to prevent potential interference with the external host. Prior-art implementations solve this problem by denying lookup table access to the host processor while the internal aging process is in progress. This latter case is clearly undesirable.
An aging scheme should also handle other concerns well, besides merely being fast. Recall that some entries need to remain in the lookup table permanently. An aging scheme should therefore also accommodate this need.
An aging scheme should also use the lookup table size efficiently in order to minimize circuit size, power consumption, material usage, complexity, cost, etc. The lookup table can be viewed as an array, having a width defined by the number of the data word bits and the aging bits, and a depth defined by the number of possible data words. For instance, a 128×1K CAM unit may store 1024 table entries, each consisting of a 120-bit data word and 8 aging bits. Or it might store the same number of table entries, with each entry consisting of a 125-bit data word and 3 aging bits. This is all well and good if only 3 aging bits are enough. However, if the application requires at least 80 aging increments, 3 aging bits will not be sufficient. Instead, 7 aging bits will be required and a 132×1K CAM unit may have to be used instead (2
3
=8<80; 2
7
=128>80). Therefore it would be beneficial to have an aging scheme that can provide a large number of aging increments without requiring a correspondingly large portion of the lookup table size just for that.
Accordingly, what is needed is a fast aging scheme for search engine databases. Such a scheme should preferably be atomic, use a minimal number of aging bits, and be able to well handle the three conditions wherein database entries are permanent, currently valid but not permanent, and invalid or replaceable. Furthermore the scheme should facilitate efficient database table size usage.
DISCLOSURE OF INVENTION
Accordingly, it is an object of the present invention to provide fast aging scheme for search engine databases, preferably one fast to the point of performing aging as an atomic operation.
Another object of the invention is to provide an aging scheme for search engine databases which efficiently handles permanent, valid, and invalid data entries.
And another object of the invention is to provide an aging scheme for search engine databases which efficiently uses the database table size.
Briefly, one preferred embodiment of the present invention is a system for aging data entries in a search engine database. A clock is provided for producing a clock signal. A memory is provided for containing multiple data entries to be aged, wherein each said data entry has a respective aging word. An aging address counter is provided for selecting a current data entry from among the data entries, based on the clock signal, thereby also implicitly selecting a current aging word. A linear feedback shift register (LFSR) is provided for receiving an input signal based on the current aging word and producing an output signal based on a state change responsive to that input signal. Finally, a control unit is provided for selectively updating the current aging word based on the output signal from the LFSR.
An advantage of the present invention is that it produces a flexible, atomically fast-aging scheme for search engine databases which inherently handles the three possible data entry conditions.
Another advantage of the invention is that it facilitates efficient database table size usage, in an optional yet highly user configurable manner.
Another advantage of the invention is that it is scalable to accommodate larger number of aging bits without suffering performance penalty.
Another advantage of the invention is that it works well with memory types which are used for search engine databases, including content addressable memory (CAM).
And another advantage of the invention is that it integrates well with prior art methodologies, particular working efficiently with circuitry employing the inventive fast aging scheme.
These and other objects and advantages of the present invention will become clear to those skilled in the art in view of the description of the best presently known mode of carrying out the invention and the industrial applicability of the preferred embodiment as described herein
Cheng Paul
Chow Nelson L.
Chace Christian P.
Integrated Silicon Solution Inc.
Moazzami Nasser
Raymond F. Roberts Intellectual Property Law Offices
LandOfFree
Fast aging scheme for search engine databases using a linear... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast aging scheme for search engine databases using a linear..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast aging scheme for search engine databases using a linear... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3311220