Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2005-05-10
2005-05-10
Bataille, Pierre-Michel (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C365S049130, C365S168000, C711S219000
Reexamination Certificate
active
06892272
ABSTRACT:
A method and apparatus for determining a longest prefix match in a content addressable memory (CAM) device is described. The CAM device includes a CAM array that may be arbitrarily loaded with CIDR addresses that are not prearranged prior to their entry into the CAM device. For one embodiment, the CAM array is a ternary CAM array that includes CAM cells storing CAM data, mask cells storing prefix mask data for the corresponding CAM cells, a CAM match line for indicating a match between a search key and the CAM data (as masked by the prefix mask data), prefix match lines, and prefix logic circuits for comparing the CAM match line with the prefix mask data. The prefix logic circuits determine the longest prefix among the CAM locations that match the search key, regardless of where the matching locations are logically located in the CAM array. The longest prefix is then compared against the prefix mask data stored in the mask cells to determine the location in the CAM array that stores the CIDR address corresponding to the longest prefix. The CAM index or address of the matching CIDR address may then be output from the CAM device. Additionally and/or alternatively, additional or associated data stored at the CAM index may be accessed. The additional or associated data may be, for example, routing information for the stored CIDR address.
REFERENCES:
patent: 3257646 (1966-06-01), Roth
patent: 3353159 (1967-11-01), Lee, III
patent: 3602899 (1971-08-01), Lindquist
patent: 3675211 (1972-07-01), Raviv
patent: 3685020 (1972-08-01), Meade
patent: 3868642 (1975-02-01), Sachs
patent: 4030077 (1977-06-01), Florence et al.
patent: 4112502 (1978-09-01), Scheuneman
patent: 4244033 (1981-01-01), Hattori
patent: 4464732 (1984-08-01), Clark
patent: 4472805 (1984-09-01), Wacyk
patent: 4523301 (1985-06-01), Kadota
patent: 4611280 (1986-09-01), Linderman
patent: 4646271 (1987-02-01), Uchiyama
patent: 4656626 (1987-04-01), Yudichak
patent: 4670858 (1987-06-01), Almy
patent: 4747080 (1988-05-01), Yamada
patent: 4758982 (1988-07-01), Price
patent: 4780845 (1988-10-01), Threewitt
patent: 4785398 (1988-11-01), Joyce
patent: 4791606 (1988-12-01), Threewitt
patent: 4813002 (1989-03-01), Joyce
patent: 4845668 (1989-07-01), Sano
patent: 4896261 (1990-01-01), Nolan
patent: 4903234 (1990-02-01), Sakuraba
patent: 4928260 (1990-05-01), Chuang
patent: 4958377 (1990-09-01), Takahashi
patent: 4959811 (1990-09-01), Szczepanek
patent: 4975873 (1990-12-01), Nakabayashi
patent: 4991134 (1991-02-01), Ivsin
patent: 4996666 (1991-02-01), Duluk, Jr.
patent: 5010516 (1991-04-01), Oates
patent: 5014195 (1991-05-01), Farrell
patent: 5036486 (1991-07-01), Noguchi
patent: 5051948 (1991-09-01), Watabe
patent: 5053991 (1991-10-01), Burrows
patent: 5068822 (1991-11-01), Lawrence
patent: 5072422 (1991-12-01), Rachels
patent: 5107501 (1992-04-01), Zorian
patent: 5111427 (1992-05-01), Kobayashi
patent: 5226005 (1993-07-01), Lee
patent: 5239642 (1993-08-01), Gutierrez
patent: 5247688 (1993-09-01), Ishigami
patent: 5265100 (1993-11-01), McClure
patent: 5317756 (1994-05-01), Komatsu et al.
patent: 5319590 (1994-06-01), Montoye
patent: 5319763 (1994-06-01), Ho
patent: 5339268 (1994-08-01), Machida
patent: 5383146 (1995-01-01), Threewitt
patent: 5388189 (1995-02-01), Kung
patent: 5396449 (1995-03-01), Atallah et al.
patent: 5406508 (1995-04-01), Hayashibara
patent: 5414704 (1995-05-01), Spinney
patent: 5422838 (1995-06-01), Lin
patent: 5423015 (1995-06-01), Chung
patent: 5440709 (1995-08-01), Edgar
patent: 5440715 (1995-08-01), Wyland
patent: 5446685 (1995-08-01), Holst
patent: 5454094 (1995-09-01), Montove
patent: 5455576 (1995-10-01), Clark, II
patent: 5465335 (1995-11-01), Anderson
patent: 5467319 (1995-11-01), Nusinov et al.
patent: 5469161 (1995-11-01), Bezek
patent: 5475825 (1995-12-01), Yonezawa
patent: 5485418 (1996-01-01), Hiraki
patent: 5490102 (1996-02-01), Jubran
patent: 5491703 (1996-02-01), Barnaby
patent: 5513134 (1996-04-01), Cooperman
patent: 5517441 (1996-05-01), Dietz
patent: 5592432 (1997-01-01), Vishlitzky et al.
patent: 5598115 (1997-01-01), Holst
patent: 5615135 (1997-03-01), Waclawsky et al.
patent: 5619676 (1997-04-01), Fukuda et al.
patent: 5621677 (1997-04-01), Jones
patent: 5642114 (1997-06-01), Komoto
patent: 5642322 (1997-06-01), Yoneda
patent: 5646878 (1997-07-01), Samra
patent: 5649149 (1997-07-01), Stormon
patent: 5699288 (1997-12-01), Kim et al.
patent: 5706224 (1998-01-01), Srinivasan
patent: 5740098 (1998-04-01), Adams et al.
patent: 5745488 (1998-04-01), Thompson
patent: 5752069 (1998-05-01), Roberts et al.
patent: 5818786 (1998-10-01), Yoneda
patent: 5818873 (1998-10-01), Wall
patent: 5828324 (1998-10-01), Clark, II
patent: 5841874 (1998-11-01), Kempke et al.
patent: 5860085 (1999-01-01), Stormon
patent: 5870324 (1999-02-01), Helwig
patent: 5893931 (1999-04-01), Peng
patent: 5920886 (1999-07-01), Feldmeier
patent: 5930359 (1999-07-01), Kempke
patent: 5933363 (1999-08-01), Shindo
patent: 5940852 (1999-08-01), Rangasayee
patent: 5946704 (1999-08-01), Yoneda et al.
patent: 5949696 (1999-09-01), Threewitt
patent: 5949734 (1999-09-01), Matano
patent: 5978885 (1999-11-01), Clark, II
patent: 5999435 (1999-12-01), Henderson et al.
patent: 6000008 (1999-12-01), Simcoe
patent: 6006306 (1999-12-01), Haywood
patent: 6011795 (2000-01-01), Varghese
patent: 6014732 (2000-01-01), Naffziger
patent: 6044005 (2000-03-01), Gibson
patent: 6065064 (2000-05-01), Satoh et al.
patent: 6069573 (2000-05-01), Clark, II et al.
patent: 6081440 (2000-06-01), Washburn
patent: 6108227 (2000-08-01), Voelkel
patent: 6108747 (2000-08-01), Kaganoi
patent: 6115365 (2000-09-01), Newberg et al.
patent: 6144574 (2000-11-01), Kobayashi et al.
patent: 6175514 (2001-01-01), Henderson et al.
patent: 6181698 (2001-01-01), Hariguchi
patent: 6226710 (2001-05-01), Melchior
patent: 6237061 (2001-05-01), Srinivasan
patent: 6266262 (2001-07-01), Washburn
patent: 6289414 (2001-09-01), Feldmeier et al.
patent: 6353873 (2002-03-01), Melchior
patent: 6362993 (2002-03-01), Henderson et al.
patent: 6467019 (2002-10-01), Washburn
patent: 6493791 (2002-12-01), Akkary
patent: 6499081 (2002-12-01), Nataraj et al.
patent: 6502163 (2002-12-01), Ramankutty
patent: 6539455 (2003-03-01), Khanna et al.
patent: 6567340 (2003-05-01), Nataraj et al.
patent: 6813680 (2004-11-01), Pereira
patent: 02676122 (1988-05-01), None
patent: 0381249 (1990-08-01), None
patent: 0660332 (1995-06-01), None
patent: 0872802 (1998-10-01), None
patent: 0944093 (1999-09-01), None
patent: 08167295 (1996-06-01), None
patent: WO9812651 (1998-03-01), None
patent: WO9931581 (1999-06-01), None
patent: WO0111630 (2001-02-01), None
Motorola Semiconductor Technical Data, “Advance Information 16K × 64 CA”, MCM69C432, Jan. 1996, pp. 4 pages.
GEC Plessey Semiconductors, “P2800 Multi-port Content Addressable Memory”, Functional Product Specification GPS-FPS-2800-12, Jan. 1996, pp. 1-102.
Advanced Micro Devices, “Final Am99C10A 256 × 48 Content Addressable Memory” Publication No. 08125, Rev. G, Dec. 1992, pp. 1-21.
Music Semiconductors, “MU9C2480 LANCAM Preliminary Data Sheet”, Aug. 25, 1995, pp. 1-24.
GEC Plessey Semiconductors Preliminary Information, “P2800 2K × 64 BIT Multiport Content Addressable Memory”, Feb. 1997, pp. 1-15.
Music Semiconductors, “The MU9C1480 LANCAM Handbook”, Rev. 3, Nov. 1994, pp. 1-1 through 7-12.
Music Semiconductors, “MU9C1480 LANCAM” Advance Information, Mar. 22, 1990, pp. 1-11.
KLSI, “Address Processor”, KE5B064H series-Dual Port and Fixed Table Type-, Version 1.0.1, published approximately late 1995 or early 1996, pp. 1-1 through 14-1.
KLSI, “KE5B064A1 Address Processor”, Version 2.0.2, published approximately late 1995 or early 1996, pp. 1-1 through 12-1.
Music Semiconductors, “MuAA™ CAM Family” Advance Information, Feb. 24, 1998, Rev. 0, pp. 1-16.
Soo-ik Chae et al., “Content-Addressable Memory for VLSI Pattern Inspection”, IEEE Journal of Solid State Circuits, vol. 23, No. 1, Feb. 1988, pp. 74-78.
Madamala Ramagopal
Srinivasan Varadarajan
Bataille Pierre-Michel
NetLogic Microsystems, Inc.
Shemwell Gregory & Courtney LLP
LandOfFree
Method and apparatus for determining a longest prefix match... 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 determining a longest prefix match..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for determining a longest prefix match... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3380803