Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2004-03-25
2009-08-04
Cottingham, John R. (Department: 2167)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
07571156
ABSTRACT:
Network devices, storage mediums and methods for updating a memory structure in a data plane of the network device when route updates are received in the control plane of the network device. The methods described herein can be used to perform one of the following algorithms: a Basic Incremental Split-Merge (BISM) algorithm, a Lazy Incremental Split-Merge (LISM) algorithm, and a Down-support Split-Merge (DSM) algorithm. Each of the algorithms described herein may be used to incrementally update portions of a forwarding database stored within the memory structure, where the updated portions correspond to only those portions affected by the route updates.
REFERENCES:
patent: 5574910 (1996-11-01), Bialkowski et al.
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: 6571313 (2003-05-01), Filippi et al.
patent: 6735600 (2004-05-01), Andreev et al.
patent: 6963924 (2005-11-01), Huang et al.
patent: 7162481 (2007-01-01), Richardson 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: 7426518 (2008-09-01), Venkatachary et al.
patent: 2002/0089937 (2002-07-01), Venkatachary et al.
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.
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,” © 2002 IEEE, pp. 432-437.
Yu et al., “Forwarding Engine for Fast Routing Lookups and Updates,” 1999 Global Telecommunications Conference, pp. 1556-1564.
International Search Report, PCT/US2004/009531, mailed Sep. 2, 2004.
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-581.
Fast and Scalable Layer 4 Switching, V. Srinivasan, G Varghese, S. Suri and M. Waldvogel, Presented at ACM Sigcomm '98, 16 page slide presentation.
Forwarding Engine for Fast Routing Lookups and Updates, Yu et al., 1999 Gobal Telecommunications Conference, pp. 1556-1564.
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.
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.
Gupta Pankaj
Venkatachary Srinivasan
Cottingham John R.
Lovel Kimberly
NetLogic Microsystems, Inc.
Paradice III William L.
Shemwell Mahamedi LLP
LandOfFree
Network device, storage medium and methods for incrementally... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Network device, storage medium and methods for incrementally..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network device, storage medium and methods for incrementally... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4064609