Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2011-03-01
2011-03-01
Yao, Kwang B (Department: 2473)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S392000, C370S400000, C370S351000
Reexamination Certificate
active
07899067
ABSTRACT:
Methods and apparatus are disclosed for generating and using an enhanced tree bitmap data structure in determining a longest prefix match, such as in a router, packet switching system. One implementation organizes the tree bitmap to minimize the number of internal nodes that must be accessed during a lookup operation. A pointer is included in each of the trie or search nodes to the best match so far entry in the leaf or results array which allows direct access to this result without having to parse a corresponding internal node. Moreover, one implementation stores the internal node for a particular level as a first element in its child array. Additionally, one implementation uses a general purpose lookup engine that can traverse multiple tree bitmaps or other data structures simultaneously, and perform complete searches, partial searches, and resume partial searches such as after receiving additional data on which to search.
REFERENCES:
patent: 5528701 (1996-06-01), Aref
patent: 5651099 (1997-07-01), Konsella
patent: 5721899 (1998-02-01), Namba
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), Tikkanen
patent: 5884297 (1999-03-01), Noven
patent: 6018524 (2000-01-01), Turner et al.
patent: 6067574 (2000-05-01), Tzeng
patent: 6115716 (2000-09-01), Tikkanen et al.
patent: 6188694 (2001-02-01), Fine et al.
patent: 6298339 (2001-10-01), Bjornson
patent: 6560610 (2003-05-01), Eatherton et al.
patent: 6697363 (2004-02-01), Carr
patent: 6724734 (2004-04-01), Shabtay et al.
patent: 6728732 (2004-04-01), Eatherton et al.
patent: 6876655 (2005-04-01), Afek et al.
patent: 6891834 (2005-05-01), Dalley et al.
patent: 6915291 (2005-07-01), Carlson et al.
patent: 6917954 (2005-07-01), Ahmad et al.
patent: 7054315 (2006-05-01), Liao
patent: 7106732 (2006-09-01), Brown
patent: 2002/0039350 (2002-04-01), Wang et al.
patent: 2003/0108043 (2003-06-01), Liao
patent: 2003/0174717 (2003-09-01), Zabarski et al.
patent: 2004/0236720 (2004-11-01), Basso et al.
patent: 2005/0026603 (2005-02-01), Rajaram
patent: 2005/0157712 (2005-07-01), Rangarajan et al.
patent: 2005/0171959 (2005-08-01), Deforche et al.
patent: 2007/0038626 (2007-02-01), Waters et al.
patent: 1168723 (2002-01-01), None
patent: 1168723 (2002-10-01), None
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 pp.
V. Srinivasan and George Varghese, “Faster IP Lookups using Controlled Prefix Expansion,” ACM Sigmetrics Performance 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.
William N. Eatherton, Hardware-Based Internet Protocol Prefix Lookups, Master's thesis, Sever Institute, Washington University, St. Louis, MO, May 1999, 109 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.
Panicaj Gupta and Nick Mckeown, “Algorithms for Packet Classification,” IEEE Network Special Issue, Mar./Apr. 2001, vol. 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).
Waldvogel et al., “Scalable High Speed IP Routing Lookups,” Computer Communications Review, ACM, Sep. 14, 1997, pp. 25-36.
Eatherton William N.
Rangarajan Vijay
Sagi Dalit
Cisco Technology Inc.
Ngo Nguyen
The Law Office of Kirt D. Williams
Yao Kwang B
LandOfFree
Method and apparatus for generating and using enhanced tree... 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 generating and using enhanced tree..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating and using enhanced tree... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2714119