Data processing: database and file management or data structures – Database and file access – Preparing data for information retrieval
Reexamination Certificate
2008-07-10
2011-12-06
Ali, Mohammad (Department: 2158)
Data processing: database and file management or data structures
Database and file access
Preparing data for information retrieval
C707S705000
Reexamination Certificate
active
08073856
ABSTRACT:
A method, apparatus, and storage medium product are provided for forming a forwarding database, and for using the formed database to more efficiently and quickly route packets of data across a computer network. The forwarding database is arranged into multiple sub-databases. Each sub-database is pointed to by a pointer within a pointer table. When performing a longest-match search of incoming addresses, a longest prefix matching algorithm can be used to find the longest match among specialized “spear prefixes” stored in the pointer table. After the longest spear prefixes are found, the pointer table will direct the next search within a sub-database pointed to by that spear prefix. Another longest-match search can be performed for database prefixes (or simply “prefixes”) within the sub-database selected by the pointer. Only the sub-database of interest will, therefore, be searched and all other sub-databases are not accessed. Using a precursor pointer and a sub-database of optimally bounded size and number ensures power consumption be confined only to the sub-database being accessed, and that higher speed lookup operations can be achieved since only the sub-database of interest is being searched.
REFERENCES:
patent: 5574910 (1996-11-01), Bialkowski et al.
patent: 5991758 (1999-11-01), Ellard
patent: 6018524 (2000-01-01), Turner et al.
patent: 6081440 (2000-06-01), Washburn et al.
patent: 6154384 (2000-11-01), Nataraj et al.
patent: 6192051 (2001-02-01), Lipman et al.
patent: 6212184 (2001-04-01), Venkatachary et al.
patent: 6215816 (2001-04-01), Gillespie et al.
patent: 6223172 (2001-04-01), Hunter et al.
patent: 6237061 (2001-05-01), Srinivasan et al.
patent: 6266262 (2001-07-01), Washburn et al.
patent: 6298340 (2001-10-01), Calvignac et al.
patent: 6307855 (2001-10-01), Hariguchi
patent: 6374326 (2002-04-01), Kansal et al.
patent: 6385649 (2002-05-01), Draves et al.
patent: 6460112 (2002-10-01), Srinivasan et al.
patent: 6499081 (2002-12-01), Nataraj et al.
patent: 6502163 (2002-12-01), Ramankutty
patent: 6505270 (2003-01-01), Voelkel et al.
patent: 6542391 (2003-04-01), Pereira et al.
patent: 6546391 (2003-04-01), Tsuruoka
patent: 6571313 (2003-05-01), Filippi et al.
patent: 6615210 (2003-09-01), Huang et al.
patent: 6662184 (2003-12-01), Friedberg
patent: 6735600 (2004-05-01), Andreev et al.
patent: 6751701 (2004-06-01), Pereira
patent: 6778984 (2004-08-01), Lu et al.
patent: 6792502 (2004-09-01), Pandya et al.
patent: 6795892 (2004-09-01), Pereira et al.
patent: 6799243 (2004-09-01), Pereira et al.
patent: 6801981 (2004-10-01), Pereira et al.
patent: 6813680 (2004-11-01), Pereira
patent: 6892272 (2005-05-01), Srinivasan et al.
patent: 6963924 (2005-11-01), Huang et al.
patent: 7050317 (2006-05-01), Lien et al.
patent: 7162481 (2007-01-01), Richardson et al.
patent: 7174441 (2007-02-01), Singh et al.
patent: 7194573 (2007-03-01), Saxtorph et al.
patent: 7246198 (2007-07-01), Nataraj et al.
patent: 7249228 (2007-07-01), Agarwal et al.
patent: 7266085 (2007-09-01), Stine
patent: 7299399 (2007-11-01), Huang
patent: 7313666 (2007-12-01), Saminda De Silva et al.
patent: 7339810 (2008-03-01), Smith
patent: 7426518 (2008-09-01), Venkatachary et al.
patent: 7461200 (2008-12-01), Birman et al.
patent: 7555593 (2009-06-01), Rosman
patent: 7571156 (2009-08-01), Gupta et al.
patent: 7624226 (2009-11-01), Venkatachary et al.
patent: 7694068 (2010-04-01), Rosman
patent: 7836246 (2010-11-01), Birman et al.
patent: 7933282 (2011-04-01), Gupta et al.
patent: 7934198 (2011-04-01), Gruner et al.
patent: 2002/0089937 (2002-07-01), Venkatachary et al.
patent: 2003/0031179 (2003-02-01), Oh
patent: 2003/0103498 (2003-06-01), Oh et al.
patent: 2004/0193619 (2004-09-01), Venkatachary et al.
patent: 2005/0122972 (2005-06-01), Gruner et al.
patent: 2008/0275872 (2008-11-01), Venkatachary et al.
patent: 4614946 (2010-10-01), None
A Fast and Scalable IP Lookup Scheme for High-Speed Networks, Chen et al., © 1999 IEEE, pp. 211-218.
Efficient hardware Architecture for Fast IP Address Lokup, Pao et al., IEEE Infocom 2002, pp. 555-561.
Fast Address lookups using controlled Prefix Expansion, Venkatachary Srinivasan et al., ACM Transactions on Computer Systems, Vol. 17., No. 1, Feb. 1999, pp. 1-40.
Fast and Scalable Layer 4 Switching, V. Srinivasan, G Varghese, S. Suri and M. Waldvogel, Presented at ACM Sigcomm '98, 18 page slide presentation.
Forwarding Engine for Fast Routing Lookups and Updates, Yu et al., 1999 Gobal Telecommunications Conference, pp. 1556-1564.
Gupta, “Algorithms for routing Lookups and packet Classification,” Dec. 2000, pp. 1-197.
International Search Report, PCT/US2004/009531, Mailed Sep. 2, 2004.
Lampson et al., “IP Lookup using Multiway and Multicolumn Search,” Aug. 1997, pp. 1-23.
Packet Classification using hierarchical Intelligent Cuttings, Pankaj Gupta and Nick McKeown, Proc. Hot Interconnects VII, Aug. 1999, Stanford University.
Packet Classification on Multiple Fields, Pankj Gupta and Nick McKeown, Proc. Sigcomm, Computer Communication Review, vol. 29, No. 4, pp. 147-160, Sep. 1999 Harvard University.
Reconfigurable memory Architecture for Scalable IP Forwarding Engines, Akhbarizadeh et al., © 2002 IEEE, pp. 432-437.
Gupta Pankaj
Venkatachary Srinivasan
Ali Mohammad
Hocker John
Mahamedi Paradice Kreisman LLP
NetLogic Microsystems, Inc.
Paradice III William L.
LandOfFree
System and method for efficiently searching a forwarding... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for efficiently searching a forwarding..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for efficiently searching a forwarding... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4311502