Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2003-03-28
2008-09-16
Wu, Yicun (Department: 2165)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
07426518
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: 6018524 (2000-01-01), Turner et al.
patent: 6154384 (2000-11-01), Nataraj et al.
patent: 6192051 (2001-02-01), Lipman et al.
patent: 6215816 (2001-04-01), Gillespie et al.
patent: 6223172 (2001-04-01), Hunter 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: 6546391 (2003-04-01), Tsuruoka
patent: 6963924 (2005-11-01), Huang 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: 2002/0089937 (2002-07-01), Venkatachary et al.
Venkatachary Srinivasan et al Fast Address lookups using Controlled Prefix Expansion, vol. 17, No. 1 Feb. 1999, pp. 1-40.
Chen et al., “A Fast and Scalable IP Lookup Scheme for High-Speed Networks,” © 1999 IEEE, pp. 211-218.
Pao et al., “Efficient Hardware Architecture for Fast IP Address Lookup,” IEEE INFOCOM 2002, pp. 555-561.
Akhbarizadeh et al., “Reconfigurable Memory Architecture for Scalable IP Forwarding Engines,” © IEEE, pp. 432-437.
Yu et al., “Forwarding Engine for Fast Routing Lookups and Updates,”0 1999 Global Telecommunications Conference, pp. 1556-1564.
International Search Report, PCT/US2004/009531, mailed Sep. 2, 2004.
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.
Lampson et al., “IP Lookup using Multiway and Mulcicolumn Search,” Aug. 1997, pp. 1-23.
Gupta, “Algorithms for Routing Lookups and Packet Classification,” Dec. 2000, pp. 1-197.
Gupta Pankaj
Venkatachary Srinivasan
NetLogic Microsystems, Inc.
Shemwell Mahamedi LLP
Wu Yicun
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-3986435