Hash Cam having a reduced size memory array and its application

Details Hash Cam having a reduced size memory array and its application Hash Cam having a reduced size memory array and its application

1999-12-21

2002-08-20

Kim, Matthew (Department: 2186)

Electrical computers and digital processing systems: memory

Address formation

Hashing

C711S108000, C711S220000

Reexamination Certificate

active

06438674

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
The novel hash CAM of the present invention comprises a hashing unit and a memory array. The hashing unit is designed to generate an n-bit index in response to an m-bit input, where n and m are positive integers, and n is smaller than m. The memory array is designed to store a number of truncated comparands of size r (in units of bits), and to output a selected one of the stored truncated comparands in accordance with the n-bit index, for comparison with a subset of r selected bits of the m-bit input, where r is also a positive integer, and m−r is less than or equal to n.


REFERENCES:
patent: 5414704 (1995-05-01), Spinney
patent: 5920886 (1999-07-01), Feldmeier
patent: 5920900 (1999-07-01), Poole et al.
patent: 6011795 (2000-01-01), Varghese et al.
patent: 6061368 (2000-05-01), Hitzelberger
patent: 6061712 (2000-05-01), Tzeng
patent: 6067574 (2000-05-01), Tzeng
patent: 6173384 (2001-01-01), Weaver
patent: 6226710 (2001-05-01), Melchior
patent: 6307855 (2001-10-01), Hariguchi
Pei et al., “VLSI Implementation of Routing Tables: Tries and Cams,” IEEE, pp. 515-524, 1999.*
Glaise et al., “A Low Cost Searching Device for an ATM Adapter,” IEEE, pp. 488-493, 1997.

Affiliated with

Also associated with

Rating

Hash Cam having a reduced size memory array and its application 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 size memory array and its application, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hash Cam having a reduced size memory array and its application will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2922972