Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2003-11-07
2008-08-19
Wong, Don (Department: 2163)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
07415463
ABSTRACT:
Inter alia, methods, apparatus, data structures, computer-readable medium, mechanisms, and means for programming routes and access control lists in comparison tree data structures and their use such as in performing lookup operations for use in routers, packet switching systems, and other devices. One implementation identifies a parent node, the parent node including a first node value for indicating a path through a subtree from a root node to the parent node, and the parent node including a first base pointer. A child node of the parent node is added at a memory location based on the base pointer and a next stride value, the child node including a second node value including the first node value and the next stride value.
REFERENCES:
patent: 5088032 (1992-02-01), Bosack
patent: 5528701 (1996-06-01), Aref
patent: 5574910 (1996-11-01), Bialkowski et al.
patent: 5627748 (1997-05-01), Baker et al.
patent: 5651099 (1997-07-01), Konsella
patent: 5721899 (1998-02-01), Namba
patent: 5740171 (1998-04-01), Mazzola et al.
patent: 5781431 (1998-07-01), Duret et al.
patent: 5781772 (1998-07-01), Wilkinson, III et al.
patent: 5787430 (1998-07-01), Doeringer et al.
patent: 5809501 (1998-09-01), Noven
patent: 5829004 (1998-10-01), Au
patent: 5848416 (1998-12-01), Tikkanan
patent: 5857196 (1999-01-01), Angle et al.
patent: 5884297 (1999-03-01), Noven
patent: 5920857 (1999-07-01), Rishe et al.
patent: 5920886 (1999-07-01), Feldmeier
patent: 5995971 (1999-11-01), Douceur et al.
patent: 6014659 (2000-01-01), Wilkinson, III et al.
patent: 6018524 (2000-01-01), Turner et al.
patent: 6041053 (2000-03-01), Douceur et al.
patent: 6067574 (2000-05-01), Tzeng
patent: 6115716 (2000-09-01), Tikkanan et al.
patent: 6141738 (2000-10-01), Munter et al.
patent: 6185559 (2001-02-01), Brin et al.
patent: 6236658 (2001-05-01), Essbaum et al.
patent: 6237061 (2001-05-01), Srinivasan et al.
patent: 6243667 (2001-06-01), Kerr et al.
patent: 6289414 (2001-09-01), Feldmeier et al.
patent: 6295576 (2001-09-01), Ogura et al.
patent: 6298339 (2001-10-01), Bjornson
patent: 6334153 (2001-12-01), Boucher et al.
patent: 6341346 (2002-01-01), Benyaoun et al.
patent: 6356902 (2002-03-01), Tan et al.
patent: 6356951 (2002-03-01), Gentry, Jr.
patent: 6560610 (2003-05-01), Eatherton et al.
patent: 6564211 (2003-05-01), Andreev et al.
patent: 6725326 (2004-04-01), Patra et al.
patent: 6728732 (2004-04-01), Eatherton et al.
patent: 6741985 (2004-05-01), Green
patent: 7002917 (2006-02-01), Saleh
patent: 7158975 (2007-01-01), Mazzagatti
patent: WO 2004/102856 (2004-11-01), None
U.S. Appl. No. 10/833,532, filed Apr. 26, 2004, Eatherton et al.
U.S. Appl. No. 10/356,262, filed Jan. 31, 2003, Rangarajan et al.
U.S. Appl. No. 10/278,623, filed Oct. 23, 2002, Eatherton et al.
U.S. Appl. No. 10/161,504, filed May 31, 2002, Rangarajan et al.
William N. Eatherton, Hardware-Based Internet Protocol Prefix Lookups, Master's thesis, Sever Institute, Washington University, St. Louis, MO, May 1999, 109 pages.
Donald R. Morrison, “PATRICIA—Practical Algorithm to Retrieve Information Coded in Alphanumeric,” Journal of the ACM, vol. 15, No. 4, Oct. 1968, pp. 514-534.
Waldvogel et al., “Scalable High Speed IP Routing Lookups,” Proc. Sigcomm '97, ACM, 1997, pp. 25-36.
Lampson et al., “IP Lookups Using Multiway and Multicolumn Search,” Proc. Infocom 98, Mar. 1998, 24 pages.
V. Srinivasan and George Varghese, “Faster IP Lookups using Controlled Prefix Expansion,” ACM Sigmetrics Peformance Evaluation Review, vol. 26 No. 1, Jun. 1998, p. 1-10.
Stefan Nilsson and Gunnar Karlsson, “Fast Address Look-up for Internet Routers,” Proceedings of IEEE Broadband Communications, Apr. 1998, 12 pages.
Lampson et al., “IP Lookups Using Multiway and Multicolumn Search,” IEEE Transactions on Networking, vol. 7, No. 3, Jun. 1999, pp. 324-334.
Lockwood et al., “Field Programmable Port Extender (FPX) for Distributed Routing and Queuing, ”Proceedings of the ACM/SIGDA international symposium on Field programmable gate arrays, Feb. 2000, pp. 137-144.
Ruiz-Sanchez et al., “Survey and Taxonomy of IP Address Lookup Algorithms,” IEEE Network Magazine, vol. 15, No. 2, Mar./Apr. 2001, pp. 8-23.
Pankaj Gupta and Nick McKewon, “Algorithms for Packet Classification,” IEEE Network Magazine, vol. 15, No. 2, Mar./Apr. 2001, pp. 24-32.
Iyer et al., “ClassiPI: An Architecture for Fast and Flexible Packet Classification,” IEEE Network Magazine, vol. 15, No. 2, Mar./Apr. 2001, pp. 33-41.
Waldvogel et al., “Scalable High Speed Prefix Matching,” ACM Transactions on Computer Systems, vol. 19, No. 4, Nov. 2001, pp. 440-482.
Devavrat Shah and Pankaj Gupta, “Fast Incremental Updates on Ternary-CAMs for Routing Lookups and Packet Classification,” Proc. Hot Interconnects VIII, Aug. 2000, Stanford. IEEE Micro, vol. 21, No. 1, Jan./Feb. 2001, 9 pages.
Waldvogel et al., “Scalable Best Matching Prefix Lookups,” PODC 98, ACM 1998.
Radia Perlman, Interconnections: Bridges, Routers, Switches, and Internetworking Protocols, Second Edition, Addison-Wesley, 2000, pp. 347-365.
Pankaj Gupta and Nick McKeown, “Algorithms for Packet Classification,” IEEE Network Special Issue, Mar./Apr. 2001, vol. 15, No. 15, No. 2, pp. 24-32 (reprint 29 pages).
Srinivasan et al., “Packet Classification Using Tuple Space Search,” ACM Computer Communication Review, 1999. ACM Sigcomm'99, Sep. 1999 (12 pages).
Srinivasan et al., “Fast and Scalable Layer Four Switching,” ACM Computer Communication Review, 28(4):191-202, 1998. ACM Sigcomm'98, Sep. 1998 (12 pages).
Stefan Nilsson and Gunnar Karlsson, “IP-Address Lookup Using LC-Tries,” IEEE Journal on Selected Areas in Communications, Jun. 1999 (12 pages).
Cisco Technology Inc.
Filipczyk Marc R
The Law Office of Kirk D. Williams
Wong Don
LandOfFree
Programming tree data structures and handling collisions... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Programming tree data structures and handling collisions..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Programming tree data structures and handling collisions... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4002810