Content addressable memory with hashing function

Details Content addressable memory with hashing function Content addressable memory with hashing function

2005-08-23

2005-08-23

Verbrugge, Kevin (Department: 2188)

Electrical computers and digital processing systems: memory

Storage accessing and control

Specific memory composition

C365S049130

Reexamination Certificate

active

06934796

ABSTRACT:
A content addressable memory (CAM) device having a memory, a hash index generator to associate a search value with a unique location within a memory, and a compare circuit. The index generator generates an index based on the search value. The memory receives the index from the index generator and outputs a stored data value from a location indicated by the index. A compare circuit receives the data value from the memory and compares the data value and the search value to generate a match signal indicative of whether the data value and search value match. The match signal and index are output from the CAM device.

REFERENCES:
patent: 4152762 (1979-05-01), Bird et al.
patent: 4813002 (1989-03-01), Joyce et al.
patent: 4958377 (1990-09-01), Takahashi
patent: 5129074 (1992-07-01), Kikuchi et al.
patent: 5359720 (1994-10-01), Tamura et al.
patent: 5386413 (1995-01-01), McAuley et al.
patent: 5414704 (1995-05-01), Spinney
patent: 5440715 (1995-08-01), Wyland
patent: 5485418 (1996-01-01), Hiraki et al.
patent: 5515370 (1996-05-01), Rau
patent: 5526504 (1996-06-01), Hsu et al.
patent: 5530958 (1996-06-01), Agarwal et al.
patent: 5574871 (1996-11-01), Hoyt et al.
patent: 5642322 (1997-06-01), Yoneda
patent: 5706492 (1998-01-01), Hoyt et al.
patent: 5724538 (1998-03-01), Morris et al.
patent: 5818786 (1998-10-01), Yoneda
patent: 5870324 (1999-02-01), Helwig et al.
patent: 5903751 (1999-05-01), Hoyt et al.
patent: 5920886 (1999-07-01), Feldmeier
patent: 5944817 (1999-08-01), Hoyt et al.
patent: 5999435 (1999-12-01), Henderson et al.
patent: 6006306 (1999-12-01), Haywood et al.
patent: 6011795 (2000-01-01), Varghese et al.
patent: 6098147 (2000-08-01), Mizuhara
patent: 6161144 (2000-12-01), Michels et al.
patent: 6199140 (2001-03-01), Srinivasan et al.
patent: 6226710 (2001-05-01), Melchior
patent: 6289414 (2001-09-01), Feldmeier et al.
patent: 6362992 (2002-03-01), Cheng
patent: 6370613 (2002-04-01), Diede et al.
patent: 6374349 (2002-04-01), McFarling
patent: 6389506 (2002-05-01), Ross et al.
patent: 6393544 (2002-05-01), Bryg et al.
patent: 6499081 (2002-12-01), Nataraj et al.
patent: 6735670 (2004-05-01), Bronstein et al.
patent: 2003/0093616 (2003-05-01), Slavin
J. Da Silva and I. Watson, “Pseudo-Associative Store with Hardware Hashing,” IEE Proceedings, Computers and Digital Techniques, vol. 130, Pt. E, No. 1, Jan. 1, 1983, pp. 19-24.
D. Knuth, “The Art of Computer Programming, vol. 3, Sorting and Searching, Second Edition,” Addison Wesley Longman, 1998, pp. 541-545.
V. Srinivasan, S. Suri and G. Varghese, “Packet Classification using Tuple Space Search,” Proceedings of SIGCOMM, 1999, pp. 135-146.
Z. Cao, Z. Wang and E. Zegura, “Performance of Hashing-Based Schemes for Internet Load Balancing,” Proc. IEEE INFOCOM 2000, Conf. on Computer Comm., vol. 1, 19th Annual Joint Conf. of the IEEE Computer and Comm. Soc., Tel Aviv, Israel, Mar. 26-30, 2000, pp. 1-10.
A. Broder and M. Mitzenmacher, “Using Multiple Hash Functions to Improve IP Lookups,” Proceedings of IEEE INFOCOM, 2001, pp. 1454-1463.
Motomura, M., et al., “A 1.2 Million Transistor, 33 MHz, 20-b Dictionary Search Processor (DISP) ULSI with a 160-kb CAM,” IEEE Journal of Solid-State Circuits, vol. 25, No. 5, Oct. 1990, pp. 1158-1165.
Robinson, I., “Patern-Addressable Memory,” IEEE Micro, vol. 12, No. 3, Jun. 1992, pp. 20-30.
Shah, D. and Gupta, P., “Fast Incremental Updates on Ternary-CAMs for Routing Lookups and Packet Classification,” IEEE Micro, 21(1), Jan. 2001, pp. 1-9.
Waldvogel et al., “Scalable High-Speed Prefix Matching,” ACM Transactions on Computer Systems, vol. 19, No. 4 Nov. 2001, pp. 440-482.
Kobayashi, M. and Murase, T., “A Processor Based High-Speed Longest Prefix Match Search Engine,” IEEE 2001, pp. 233-239.
Huang et al., “A Fast IP Routing Lookup Scheme for Gigabit Switching Routers,” IEEE 1999, pp. 1429-1436.
Huang, Nen-Fu and Zhao, Shi-Ming, “A Novel IP-Routing Lookup Scheme and Hardware Architecture for Multigigabit Switching Routers,” IEEE Journal on Selected Areas in Communications, vol. 17, No. 6, Jun. 1999, pp. 1093-1104.
V. Srinivasan and G. Varghese, “Fast Address Lookups Using Controlled Prefix Expansion,” ACM Transactions on Computer systems, vol. 17, No. 1, Feb. 1999, pp. 1-40.
Gupta et al., “Routing Lookups in Hardware at Memory Access Speeds,” Proc. Infocom, San Francisco, CA, Apr. 1998, pp. 1-8.
Waldvogel et al., “Scalable High Speed IP Routing Lookups,” SIGCOMM, Cannes, France, 1997, pp. 25-35.

Affiliated with

Also associated with

Rating

Content addressable memory with hashing function does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Content addressable memory with hashing function, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Content addressable memory with hashing function will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3466180