Electrical computers and digital processing systems: memory – Address formation – Hashing
Reexamination Certificate
2011-03-22
2011-03-22
Gu, Shawn X (Department: 2189)
Electrical computers and digital processing systems: memory
Address formation
Hashing
C711S206000, C711S221000, C711SE12014, C711SE12060, C370S395320, C370S395310
Reexamination Certificate
active
07913060
ABSTRACT:
A lookup unit matrix combines a plurality of lookup units to provide a longest prefix match for a search key longer than the lookup unit's mapper key. A portion of the search key is provided to each of the plurality of lookup units in a single search request issued to the lookup unit matrix. Each lookup unit in the lookup unit matrix performs a multi-level search for the result value based on the portion of the search key forwarded as the mapper key and the result of a multilevel search in the previous lookup unit. The search results in a value corresponding to the search key stored in a single location in one of the lookup units.
REFERENCES:
patent: 3716840 (1973-02-01), Masten
patent: 4450525 (1984-05-01), Demuth et al.
patent: 4661658 (1987-04-01), Matyas
patent: 5202986 (1993-04-01), Nickel
patent: 5329618 (1994-07-01), Moati et al.
patent: 5359724 (1994-10-01), Earle
patent: 5384568 (1995-01-01), Grinberg et al.
patent: 5386413 (1995-01-01), McAuley et al.
patent: 5438535 (1995-08-01), Lattibeaudiere
patent: 5459717 (1995-10-01), Mullan et al.
patent: 5479401 (1995-12-01), Bitz et al.
patent: 5561786 (1996-10-01), Morse
patent: 5680161 (1997-10-01), Lehman et al.
patent: 5727051 (1998-03-01), Holender
patent: 5787151 (1998-07-01), Nakatsu et al.
patent: 5857196 (1999-01-01), Angle et al.
patent: 5930805 (1999-07-01), Marquis
patent: 5946679 (1999-08-01), Ahuja
patent: 6011795 (2000-01-01), Varghese
patent: 6014659 (2000-01-01), Wilkinson
patent: 6034958 (2000-03-01), Wicklund
patent: 6067574 (2000-05-01), Tzeng
patent: 6085188 (2000-07-01), Bachmann et al.
patent: 6141655 (2000-10-01), Johnson et al.
patent: 6161144 (2000-12-01), Michels
patent: 6189143 (2001-02-01), Simonyi
patent: 6192051 (2001-02-01), Lipman
patent: 6199100 (2001-03-01), Filepp
patent: 6223172 (2001-04-01), Hunter
patent: 6226710 (2001-05-01), Melchior
patent: 6247014 (2001-06-01), Ladwig et al.
patent: 6266706 (2001-07-01), Brodnik
patent: 6285994 (2001-09-01), Bui
patent: 6338079 (2002-01-01), Kanamori et al.
patent: 6385649 (2002-05-01), Draves et al.
patent: 6430527 (2002-08-01), Waters
patent: 6434144 (2002-08-01), Romanov
patent: 6452908 (2002-09-01), Yamada et al.
patent: 6460112 (2002-10-01), Srinivasan
patent: 6490592 (2002-12-01), St. Denis et al.
patent: 6512766 (2003-01-01), Wilford
patent: 6513028 (2003-01-01), Lee
patent: 6522632 (2003-02-01), Waters
patent: 6526055 (2003-02-01), Perlman et al.
patent: 6539369 (2003-03-01), Brown
patent: 6539455 (2003-03-01), Khanna
patent: 6553002 (2003-04-01), Bremer
patent: 6563823 (2003-05-01), Przygienda et al.
patent: 6570866 (2003-05-01), Murase et al.
patent: 6571313 (2003-05-01), Filippi
patent: 6658482 (2003-12-01), Chen et al.
patent: 6675163 (2004-01-01), Bass
patent: 6687247 (2004-02-01), Wilford et al.
patent: 6691218 (2004-02-01), Brown
patent: 6711153 (2004-03-01), Hebb et al.
patent: 6744775 (2004-06-01), Beshai et al.
patent: 6754799 (2004-06-01), Frank
patent: 6778530 (2004-08-01), Greene
patent: 6782282 (2004-08-01), Bielefeldt et al.
patent: 6782382 (2004-08-01), Lunteren
patent: 6826561 (2004-11-01), Cao
patent: 6836771 (2004-12-01), Brown
patent: 6839825 (2005-01-01), Brown
patent: 6873982 (2005-03-01), Bates
patent: 6877005 (2005-04-01), Hunter
patent: 6880064 (2005-04-01), Brown
patent: 6917954 (2005-07-01), Ahmad et al.
patent: 6956858 (2005-10-01), Hariguchi et al.
patent: 7023807 (2006-04-01), Michels
patent: 7106732 (2006-09-01), Brown
patent: 7423981 (2008-09-01), Brown
patent: 7715385 (2010-05-01), Brown
patent: 2001/0042130 (2001-11-01), Brown
patent: 2001/0056417 (2001-12-01), Cao et al.
patent: 2002/0059197 (2002-05-01), Hunter et al.
patent: 2002/0080798 (2002-06-01), Hariguchi et al.
patent: 2005/0175005 (2005-08-01), Brown
patent: 0453707 (1991-10-01), None
patent: 10-257066 (1998-09-01), None
patent: 11-191781 (1999-07-01), None
patent: 2000-151691 (2000-05-01), None
patent: 2001-517024 (2001-10-01), None
patent: 2005-022297 (2005-01-01), None
patent: WO 99/13619 (1999-03-01), None
patent: WO 99/14606 (1999-03-01), None
patent: WO 99/14906 (1999-03-01), None
patent: WO 01/10097 (2001-02-01), None
Degermark Mikael et al., “Small Forwarding Tables for Fast Routing Lookups”, Department of Computer Science and Electrical Engineering, Luleå University of Technology, Sweden,SigComm '97 Cannes, Francepp. 3-14 (1997).
Ruiz-Sanchez, M.A., et al., “XP002901792 Survey and Taxonomy of IP Address Lookup Algorithms,”IEEE Network, (Mar./Apr. 2001), 16 pages.
Hariguchi, Network Routing Table, Jun. 30, 2000, U.S. Appl. No. 60/215,653, pp. 1-52, Figs. 1-23 and Appendixes 1-2, 93 pages.
Office Action in JP Patent Application 2001-542955, mailed May 11, 2010, 5 pages.
Response to May 11, 2010 Office Action in JP Patent Application 2001-542955, dated Aug. 22, 2010, 10 pages.
International Search Report for PCT/CA2000/01442 mailed Jul. 12, 2001, 5 pages.
Written Opinion for PCT/CA2000/01442 mailed Jan. 21, 2002, 2 pages.
Reply to Written Opinion for PCT/CA2000/01442; dated Mar. 14, 2002, 12 pages.
International Preliminary Examination Report for PCT/CA2000/01442 mailed Apr. 16, 2002, 6 pages.
Notice of Allowance for U.S. Appl. No. 09/733,627 mailed Sep. 26, 2003, 6 pages.
Office Action in U.S. Appl. No. 09/886,659 mailed Nov. 23, 2004, 10 pages.
Response to Nov. 23, 2004 Office Action in U.S. Appl. No. 09/886,659, dated Apr. 25, 2005, 14 pages.
Final Rejection in U.S. Appl. No. 09/886,659 mailed Jul. 13, 2005, 7 pages.
Response to Jul. 13, 2005 Final Rejection in U.S. Appl. No. 09/886,659, dated Nov. 14, 2005, 8 pages.
Advisory Action for U.S. Appl. No. 09/886,659 mailed Dec. 8, 2005, 3 pages.
Notice of Appeal filed for U.S. Appl. No. 09/886,659, dated Dec. 13, 2005, 3 pages.
Request for Continued Examination filed for U.S. Appl. No. 09/886,659, dated Apr. 13, 2006, 5 pages.
Office Action in U.S. Appl. No. 09/886,659 mailed Aug. 14, 2006, 10 pages.
Response to Aug. 14, 2006 Office Action in U.S. Appl. No. 09/886,659, dated Dec. 14, 2006, 11 pages.
Examiner Interview Summary Record, U.S. Appl. No. 09/886,659, mailed Dec. 28, 2006, 4 pages.
Final Rejection in U.S. Appl. No. 09/886,659, mailed Jul. 16, 2008, 8 pages.
Request for Continued Examination filed for U.S. Appl. No. 09/886,659, dated Oct. 16, 2008, 14 pages.
Office Action in U.S. Appl. No. 09/886,659 mailed Jan. 6, 2009, 9 pages.
Response to Jan. 6, 2009 Office Action in U.S. Appl. No. 09/886,659, dated Jun. 6, 2009, 10 pages.
Final Rejection in U.S. Appl. No. 09/886,659 mailed Oct. 2, 2009, 10 pages.
Response to Oct. 2, 2009 Final Rejection in U.S. Appl. No. 09/886,659, dated Dec. 2, 2009, 11 pages.
Notice of Allowance for U.S. Appl. No. 09/886,659 mailed Mar. 8, 2010, 8 pages.
Request for Continued Examination filed for U.S. Appl. No. 09/886,659, dated Jun. 7, 2010, 2 pages.
Office Action in U.S. Appl. No. 09/886,659 mailed Jun. 22, 2010, 7 pages.
Notice of Allowance for U.S. Appl. No. 09/886,650 mailed Dec. 3, 2004, 6 pages.
U.S. Appl. No. 09/886,648 filed Jun. 21, 2001.
U.S. Appl. No. 09/886,659 filed Jun. 21, 2001.
U.S. Appl. No. 09/733,628 filed Dec. 8, 2000.
International Search Report for PCT/CA2000/01441 mailed Jul. 12, 2001, 5 pages.
Written Opinion for PCT/CA2000/01441, mailed Jan. 21, 2002, 2 pages.
Reply to Written Opinion for PCT/CA2000/01441; dated Mar. 14, 2002, 13 pages.
International Preliminary Examination Report for PCT/CA2000/01441 mailed Apr. 15, 2002, 7 pages.
International Search Report for PCT/CA2000/01444 mailed Jul. 13, 2001, 4 pages.
Written Opinion for PCT/CA2000/01444 mailed Jan. 21, 2002, 2 pages.
Reply to Written Opinion for PCT/CA2000/01444; dated Mar. 21, 2002, 10 pages.
International Preliminary Examination Report for PCT/CA2000/01444 mailed Apr. 23, 2002, 6 pages.
International Search Report for PCT/CA2000/01443 mailed Jul. 12, 2001, 4 pages.
International Preliminary Examination Report for PCT/CA2000/01443 mailed Jan. 21, 2002, 3 pages.
International Search Report for PCT/CA2002/00786 mailed Mar. 13, 2003, 5 pages.
Written Opinion for PCT/CA2002/00786 mailed Oct. 20, 2003, 3 pages.
International Preliminary Examin
Gu Shawn X
SAtech Group A.B. Limited Liability Company
LandOfFree
Method and apparatus for physical width expansion of a... 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 physical width expansion of a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for physical width expansion of a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2758221