Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2005-03-22
2005-03-22
Sparks, Donald (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S220000, C711S217000, C365S049130
Reexamination Certificate
active
06871262
ABSTRACT:
Methods and apparatus are disclosed for matching a string with multiple lookups using a single associative memory, such as, but not limited to binary and ternary content-addressable memories (CAMs). In one implementation, an information string is partitioned into multiple segments. A first lookup operation is performed on the associative memory using the first segment to produce a first associative memory result, which is used as input to a memory lookup operation to produce a first result. The first result can be programmed to have any desired value or length. This first result along with a second segment of the information string is then used as input to the same associative memory to produce a second associative memory result, which is typically used as input to a memory lookup operation to produce a second result. This process can be repeated for an arbitrary or predetermined number of times.
REFERENCES:
patent: 3648254 (1972-03-01), Beausoleil
patent: 4296475 (1981-10-01), Nederlof et al.
patent: 4791606 (1988-12-01), Threewitt et al.
patent: 4996666 (1991-02-01), Duluk, Jr.
patent: 5088032 (1992-02-01), Bosack
patent: 5319763 (1994-06-01), Ho et al.
patent: 5383146 (1995-01-01), Threewitt
patent: 5440715 (1995-08-01), Wyland
patent: 5450351 (1995-09-01), Heddes
patent: 5481540 (1996-01-01), Huang
patent: 5515370 (1996-05-01), Rau
patent: 5740171 (1998-04-01), Mazzola et al.
patent: 5841874 (1998-11-01), Kempke et al.
patent: 5842040 (1998-11-01), Hughes et al.
patent: 5898689 (1999-04-01), Kumar et al.
patent: 5920886 (1999-07-01), Feldmeier
patent: 5930359 (1999-07-01), Kempke et al.
patent: 5956336 (1999-09-01), Loschke et al.
patent: 5978885 (1999-11-01), Clark, II
patent: 6000008 (1999-12-01), Simcoe
patent: 6041389 (2000-03-01), Rao
patent: 6047369 (2000-04-01), Colwell et al.
patent: 6061368 (2000-05-01), Hitzelberger
patent: 6069573 (2000-05-01), Clark, II et al.
patent: 6081440 (2000-06-01), Washburn et al.
patent: 6091725 (2000-07-01), Cheriton et al.
patent: 6097724 (2000-08-01), Kartalopoulos
patent: 6134135 (2000-10-01), Andersson
patent: 6137707 (2000-10-01), Srinivasan et al
patent: 6141738 (2000-10-01), Munter et al.
patent: 6148364 (2000-11-01), Srinivasan et al.
patent: 6154384 (2000-11-01), Nataraj et al.
patent: 6175513 (2001-01-01), Khanna
patent: 6181698 (2001-01-01), Hariguchi
patent: 6199140 (2001-03-01), Srinivasan et al.
patent: 6236658 (2001-05-01), Essbaum et al.
patent: 6237061 (2001-05-01), Srinivasan et al.
patent: 6240003 (2001-05-01), McElroy
patent: 6243667 (2001-06-01), Kerr et al.
patent: 6246601 (2001-06-01), Pereira
patent: 6295576 (2001-09-01), Ogura et al.
patent: 6307855 (2001-10-01), Hariguchi
patent: 6389506 (2002-05-01), Ross et al.
patent: 6526474 (2003-02-01), Ross
patent: 6651096 (2003-11-01), Gai et al.
patent: 6658002 (2003-12-01), Ross et al.
patent: 6658458 (2003-12-01), Gai et al.
patent: 6687144 (2004-02-01), Batson et al.
patent: 6715029 (2004-03-01), Trainin et al.
patent: 6738862 (2004-05-01), Ross et al.
Liu, “Partial Address Directory for Cache Access”, © IEEE 1994, p. 226-240.*
Donald R. Morrison, “Patricia—Practical Algorithm to Retrieve Information Coded in Alphanumeric,” Journal of the ACM, Oct. 1968, pp. 514-534, vol. 15, No. 4.
Waldvogel et al., “Scalable High Speed IP Routing Lookups,” Proc. SIGCOMM '97, pp. 25-36, 1997, ACM.
Jon P. Wade and Charles G. Sodini, “A Ternary Content Addressable Search Engine,” IEEE Journal of Solid-State Circuits, vol. 24, No. 4, Aug. 1989, pp. 1003-1013.
Teuvo Kohonen, Content-Addressable Memories, 1987, pp. 128-129 and 142-144, Springer-Verlang, New York.
Brian Dipert, ed., “Special-purpose SRAMs Smooth the Ride,” EDN, Jun. 24, 1999, pp. 93-104.
“Extending the LANCAM Comparand,” Application Brief AB-N3, Rev. 1.0a Draft, Music Semiconductors, Milpitas, CA, Sep. 30, 1998, 4 pages.
“Advantages of CAM in ASIC-Based Network Address Processing,” Application Brief AB-N11, Rev. 1.2a Draft, Music Semiconductors, Milpitas, CA, Sep. 30, 1998, 4 pages.
“Virtual Memory Applications of the MU9C1480A LANCAM,” Application Note AN-N3, Rev. 1a, Music Semiconductors, Milpitas, CA, Sep. 30, 1998, 12 pages.
“Using the MU9C1965A LANCAM MP for Data Wider than 128 Bits,” Application Note AN-N19, Rev. 1a, Music Semiconductors, Milpitas, CA, Sep. 30, 1998, 16 pages.
“Fast IPv4 and IPv4 CIDR Address Translation and Filtering Using the MUAC Routing CoProcessor (RCP),” Application Note AN-N25, Rev. 0a, Music Semiconductors, Milpitas, CA, Oct. 1, 1998, 16 pages.
“Using MUSIC Devices and RCPs for IP Flow Recognition,” Application Note AN-N27, Rev. 0, Music Semiconductors, Milpitas, CA, Oct. 21, 1998, 20 pages.
“Wide Ternary Searches Using Music CAMs and RCPs,” Application Note AN-N31, Rev. 0, Music Semiconductors, Milpitas, CA, Apr. 13, 1999, 8 pages.
US Patent Appl. No. 09/854,013, Varagur V. Chandrasekaran, filed May, 10, 2001.
Belz David E.
Oren Eyal
Cisco Technology Inc.
Peugh Brian R.
Sparks Donald
The Law Office of Kirk D. Williams
LandOfFree
Method and apparatus for matching a string with multiple... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for matching a string with multiple..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for matching a string with multiple... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3419720