Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1999-12-21
2003-12-30
Ellis, Kevin L. (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S216000
Reexamination Certificate
active
06671771
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of data processing and data communication. More specifically, the present invention relates to the design of hash CAM (content addressable memory) used in data processing and data communication devices.
2. Background Information
Numerous data processing and data communication applications employ a hash CAM for data look-up. Examples of these applications include but are not limited to network routers and switches looking up forwarding instructions for received frames.
FIG. 1
illustrates a typical prior art hash CAM. Prior art hash CAM
100
is constituted with hash function
102
, pointer array
104
, memory array
106
, and comparators
108
a
-
108
b.
Hash function
102
is used to hash an m-bit input value to an n-bit index, where m and n are positive integers, with m greater than n. An example of hash function
102
is one that breaks the m-bit input into a number of vectors of size less than or equal to n and either EXCLUSIVE-OR all the vectors together, or add all the vectors together. Another example of hash function
102
is one that divides the m-bit input by an n
th
order polynomial, and uses the n-bit remainder as the index. Pointer array
104
is designed to store up to 2
n
pointers pointing to 2
n
starting memory locations of 2
n
corresponding threaded lists of entries. Each entry includes a comparand, a payload and a next entry pointer (with the “last” next entry pointer of each threaded list set to “null” indicating the end of that particular list). Some of these lists may be “empty”, in which case, the corresponding pointers in the pointer array would be “null”. Memory array
106
is designed to store the threaded lists of entries. The payload of an indexed threaded list having the associated comparand that matches the m-bit input or an indication that no match was found is returned. Accordingly, each of the associated comparands is also m-bits in size. The nature of the payloads is application dependent. In the above mentioned network router/switch example, the payloads may be e.g. destination MAC addresses (MAC=media access control) or the number of the physical port to which the intended recipient is attached. Thus, comparator
108
a
is used to determine if an m-bit comparand matches an m-bit input, while comparator
108
b
is used to determine if the next pointer is a null pointer or not. Accordingly, comparator
108
a
is also m-bit in width.
Prior art hash CAMs of the type illustrated in
FIG. 1
suffer from the disadvantage that they require large memory arrays and wide comparators for applications involving long input values, i.e. large m. For example, it is not uncommon for many networking applications where the m-bit input may be as long as 128 bits or longer. Thus, a more efficient hash CAM is desired
SUMMARY OF THE INVENTION
A hash CAM is provided with a first and a second memory array, and comparison circuitry. The first memory array is used to store an m-bit input in a partitioned manner suitable for being subsequently output in a successive manner in portions of size m/p, where m and p are positive integers, with m being greater than or equal to p. The second memory array is used to store a plurality of threaded lists of entries, with each entry having a comparand also m-bit in size and stored in the same partitioned manner suitable for being selectively output in the same successive manner in portions of size m/p. The successive output is made responsive to an n-bit index generated in accordance with the m-bit input, with n being also a positive integer, but smaller than m. The comparison circuitry, which is complementarily reduced in width, is used to successively compare corresponding portions of the m-bit input and the selectively output comparand(s) to cumulatively determine if the m-bit input relates to one of the output comparands in a pre-determined manner.
REFERENCES:
patent: 5414704 (1995-05-01), Spinney
patent: 5764895 (1998-06-01), Chung
patent: 5870324 (1999-02-01), Helwig et al.
patent: 6240000 (2001-05-01), Sywyk et al.
patent: 6418042 (2002-07-01), Srinivasan et al.
patent: 6424714 (2002-07-01), Wasilewski et al.
Blakely , Sokoloff, Taylor & Zafman LLP
Ellis Kevin L.
Inoa Midys
Intel Corporation
LandOfFree
Hash CAM having a reduced width comparison circuitry and its... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hash CAM having a reduced width comparison circuitry and its..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hash CAM having a reduced width comparison circuitry and its... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3146885