Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1999-10-25
2002-04-16
Gossage, Glenn (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S005000, C711S168000, C365S049130, C365S230030, C370S392000
Reexamination Certificate
active
06374326
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally concerns memory devices, in particular content addressable memories (CAMs).
2. Description of the Related Art
Content-addressable memories (CAMs) allow a simultaneous search of all entries by performing a bit-wise comparison of an input value (the key or compared) against every entry at the same time. If a match is found between the key and an entry, the CAM returns the address of the matching entry. This address may be used directly by the function requesting the comparison. More commonly, it may be used as a pointer or an index to a conventional memory array (such as a static random access memory or SRAM) to return another value. In one typical use of CAMs, a router lookup or access control application, the conventional memory contains the action to be taken for a packet whose flow label matches the corresponding CAM entry, such as “forward out port 5, ” “permit,” or “deny.”
Common applications of CAMs in router and communications switching often require a large number of CAM entries. Thus, CAMs rapidly grow to unmanageable depths (i.e., size in terms of number of entries). The power consumed by such CAMs and their cost rapidly become excessive.
Furthermore, the CAM size problem is only exacerbated by the expected shift to Internet Protocol version 6 (IPv6), which uses 128 bit addresses instead of the current 32 bit addresses used by IPv4. This shift requires wider CAMs. For a given size CAM, as the width increases, the depth must correspondingly decrease.
To address these CAM size limitations, current applications use depth-cascaded CAMs, which are sets of CAM devices (i.e., physical parts or components) connected together externally so as to increase the depth (number) of entries to be checked in response to a lookup instruction. Such a configuration increases the CAM space in the depth dimension, but does not address the problem of limited CAM width, i.e., the width or address dimension. These schemes perform lookups in each CAM device in parallel, but the lookup is of the same key in all CAM devices and only a single value is returned for each lookup. In other words, only a single lookup function is performed even though multiple CAMs are employed.
Today's rapidly evolving routing and switching systems, among other applications of CAM technology, need ever faster and more cost-efficient lookup systems. In particular, it is desirous to perform two or more parallel lookup functions (i.e., lookups of different keys or parts of keys) at the same time. Furthermore, it is desirous to do so without expanding the CAM space in either the width or depth dimension or using additional CAM devices.
What is needed is a method of using a CAM or a set of CAMs to perform multiple lookup functions simultaneously from the same key or different keys, thus saving both the costs of CAM devices and lookup time.
SUMMARY
The present invention is a CAM architecture and method of use thereof that enables multiple simultaneous lookup functions within a grouping of content addressable memory arrays, each returning a different result.
The architecture consists of a new arrangement of a well-known CAM array or set of arrays into multiple banks (not necessarily the same size), an expanded size select logic, and a new operating instruction set that allows the parallel use of multiple lookup key strings in multiple banks. For a given input key of n bits, simultaneous parallel lookups in a plurality of CAM banks are performed, each using a bank key consisting of a subset of the bits of the input key, with potentially as many different bank keys as there are banks. Expresses mathematically, each bank key consists of w bits, where w≦n.
In operation, a single lookup key and a “lookup” command are passed to the multiple bank CAM by the usual means well-known in the art. The key consists of many bits. In the present invention, however, the multiple bank CAM is configured to extract one or more distinct subsets of the bits in the input key for use as bank lookup keys. Each bank key comprises some or all of the bits in the input key, e.g., each bank key may be a copy of the input key. There may be any number of bank keys; in one embodiment of the present invention there are two bank keys.
Each bank key is passed to the appropriate bank according to the configuration of the multiple bank CAM. Multiple bank depths as well as widths, depending on the key width and overall size of the CAM array, are possible. All banks perform their respective CAM lookups by means well-known in the art at the same time. Each bank produces one or more output results for each lookup, again by the usual method employed in a CAM. This set of outputs, one or more per bank, is then returned to the host or controlling entity that initially commanded the lookup function.
The architecture of the present invention and its various embodiments thus provide a fast, efficient, cost-saving lookup system readily adaptable for a wide variety of data processing applications, especially including but not limited to communications routing and switching.
REFERENCES:
patent: 3648254 (1972-03-01), Beausoleil
patent: 4996666 (1991-02-01), Duluk, Jr.
patent: 5956336 (1999-09-01), Loschke et al.
patent: 5978885 (1999-11-01), Clark, II
patent: 6041389 (2000-03-01), Rao
patent: 6069573 (2000-05-01), Clark, II et al.
patent: 6081440 (2000-06-01), Washburn et al.
Kansal Arvind K.
Ross Mark A.
Sambandan Sachidanandan
Cisco Technology Inc.
Gossage Glenn
LandOfFree
Multiple bank CAM architecture and method for performing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiple bank CAM architecture and method for performing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple bank CAM architecture and method for performing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2886510