Methods and apparatus for providing loop free routing tables

Details Methods and apparatus for providing loop free routing tables Methods and apparatus for providing loop free routing tables

2011-02-15

2011-02-15

Shah, Chirag G (Department: 2477)

Multiplex communications

Pathfinding or routing

Reexamination Certificate

active

07889712

ABSTRACT:
A router is described that includes a routing table containing route information and a module to evaluate a route and detect a loop path associated with the route using the routing table. A process is described to detect and eliminate routing loops associated with recursive routes in a routing table, so as to provide a routing table that will be loop free.

REFERENCES:
patent: 5014262 (1991-05-01), Harshavardhana
patent: 5471592 (1995-11-01), Gove et al.
patent: 5524258 (1996-06-01), Corby, Jr. et al.
patent: 5677851 (1997-10-01), Kingdon et al.
patent: 5734649 (1998-03-01), Carvey et al.
patent: 5781772 (1998-07-01), Wilkinson, III et al.
patent: 5802278 (1998-09-01), Isfeld et al.
patent: 5838894 (1998-11-01), Horst
patent: 5878415 (1999-03-01), Olds
patent: 5905725 (1999-05-01), Sindhu et al.
patent: 5909440 (1999-06-01), Ferguson et al.
patent: 5920699 (1999-07-01), Bare
patent: 5923643 (1999-07-01), Higgins et al.
patent: 5930256 (1999-07-01), Greene et al.
patent: 6011795 (2000-01-01), Varghese et al.
patent: 6018524 (2000-01-01), Turner et al.
patent: 6078963 (2000-06-01), Civaniar et al.
patent: 6091725 (2000-07-01), Cheriton et al.
patent: 6101192 (2000-08-01), Wakeland
patent: 6161139 (2000-12-01), Win et al.
patent: 6192405 (2001-02-01), Bunnell
patent: 6308219 (2001-10-01), Hughes
patent: 6430181 (2002-08-01), Tuckey
patent: 6453413 (2002-09-01), Chen et al.
patent: 6526055 (2003-02-01), Chiu et al.
patent: 6631419 (2003-10-01), Greene
patent: 6636895 (2003-10-01), Li et al.
patent: 6658002 (2003-12-01), Ross et al.
patent: 6675187 (2004-01-01), Greenberger
patent: 6687781 (2004-02-01), Wynne et al.
patent: 6697875 (2004-02-01), Wilson
patent: 6721316 (2004-04-01), Epps et al.
patent: 6731633 (2004-05-01), Sohor et al.
patent: 6732203 (2004-05-01), Kanapathippillai et al.
patent: 6751191 (2004-06-01), Davar et al.
patent: 6778490 (2004-08-01), Achilles et al.
patent: 6785728 (2004-08-01), Schneider et al.
patent: 6795886 (2004-09-01), Nguyen
patent: 6801950 (2004-10-01), O'Keeffe et al.
patent: 6804815 (2004-10-01), Kerr et al.
patent: 6879559 (2005-04-01), Blackmon et al.
patent: 6920456 (2005-07-01), Lee et al.
patent: 6922724 (2005-07-01), Freeman et al.
patent: 6941487 (2005-09-01), Balakrishnan et al.
patent: 6944183 (2005-09-01), Iyer et al.
patent: 6944860 (2005-09-01), Schmidt
patent: 6954220 (2005-10-01), Bowman-Amuah
patent: 6954436 (2005-10-01), Yip et al.
patent: 6961783 (2005-11-01), Cook et al.
patent: 6965615 (2005-11-01), Kerr et al.
patent: 6973488 (2005-12-01), Yavatkar et al.
patent: 6990527 (2006-01-01), Spicer et al.
patent: 7006431 (2006-02-01), Kanekar et al.
patent: 7020718 (2006-03-01), Brawn et al.
patent: 7024693 (2006-04-01), Byrne
patent: 7028098 (2006-04-01), Mate et al.
patent: 7043494 (2006-05-01), Joshi et al.
patent: 7051039 (2006-05-01), Murthy et al.
patent: 7051078 (2006-05-01), Cheriton
patent: 7054315 (2006-05-01), Liao
patent: 7054944 (2006-05-01), Tang et al.
patent: 7069372 (2006-06-01), Leung, Jr. et al.
patent: 7069536 (2006-06-01), Yaung
patent: 7073196 (2006-07-01), Dowd et al.
patent: 7095713 (2006-08-01), Willhite et al.
patent: 7096499 (2006-08-01), Munson
patent: 7099341 (2006-08-01), Lingafelt et al.
patent: 7103708 (2006-09-01), Eatherton et al.
patent: 7111071 (2006-09-01), Hooper
patent: 7124203 (2006-10-01), Joshi et al.
patent: 7136383 (2006-11-01), Wilson
patent: 7139238 (2006-11-01), Hwang
patent: 7150015 (2006-12-01), Pace et al.
patent: 7155518 (2006-12-01), Forslow
patent: 7159125 (2007-01-01), Beadles et al.
patent: 7167918 (2007-01-01), Byrne et al.
patent: 7185192 (2007-02-01), Kahn
patent: 7185365 (2007-02-01), Tang et al.
patent: 7200144 (2007-04-01), Terrell et al.
patent: 7200865 (2007-04-01), Roscoe et al.
patent: 7203171 (2007-04-01), Wright
patent: 7225204 (2007-05-01), Manley et al.
patent: 7225256 (2007-05-01), Villavicencio
patent: 7225263 (2007-05-01), Clymer et al.
patent: 7227842 (2007-06-01), Ji et al.
patent: 7230912 (2007-06-01), Ghosh et al.
patent: 7231661 (2007-06-01), Villavicencio et al.
patent: 7239639 (2007-07-01), Cox et al.
patent: 7249374 (2007-07-01), Lear et al.
patent: 7257815 (2007-08-01), Gbadegesin et al.
patent: 7274702 (2007-09-01), Toutant et al.
patent: 7274703 (2007-09-01), Weyman et al.
patent: 7280975 (2007-10-01), Donner
patent: 7302701 (2007-11-01), Henry
patent: 7355970 (2008-04-01), Lor
patent: 7382787 (2008-06-01), Barnes et al.
patent: 7403474 (2008-07-01), Rorie
patent: 7406038 (2008-07-01), Oelke et al.
patent: 7418536 (2008-08-01), Leung et al.
patent: 7450438 (2008-11-01), Holst et al.
patent: 7525904 (2009-04-01), Li et al.
patent: 7536476 (2009-05-01), Alleyne
patent: 7710991 (2010-05-01), Li et al.
patent: 2002/0035639 (2002-03-01), Xu
patent: 2003/0005178 (2003-01-01), Hemsath
patent: 2003/0056001 (2003-03-01), Mate et al.
patent: 2003/0056134 (2003-03-01), Kanapathippillai et al.
patent: 2003/0091043 (2003-05-01), Mehrotra et al.
patent: 2003/0108056 (2003-06-01), Sindhu et al.
patent: 2003/0163589 (2003-08-01), Bunce et al.
patent: 2003/0188192 (2003-10-01), Tang et al.
patent: 2003/0208597 (2003-11-01), Belgaied
patent: 2003/0212806 (2003-11-01), Mowers et al.
patent: 2003/0212900 (2003-11-01), Liu et al.
patent: 2004/0024888 (2004-02-01), Davis et al.
patent: 2004/0139179 (2004-07-01), Beyda
patent: 2006/0117126 (2006-06-01), Leung et al.
patent: 2009/0063702 (2009-03-01), Holst et al.
“What's Inside a Router?”, http://www-net.cs.umass.edu/kurose
etwork/inside/inside.htm, (observed Aug. 29, 2005),11 pgs.
“Xelerated Packet Devices”,MicroDesign Resources Presentation, Network Processor Forum, (Jun. 14, 2001), 11 pgs.
Belenkiy, A., “Deterministic IP Table Lookup at Wire Speed”,The Internet Global Summit(INET '99), http://www.isoc.org/inet99/proceedings/4j/4j—2.htm,(observed May 12, 2003), 18 pgs.
Cataldo, A., “Net Processor Startup Takes Pipelined Path to 40 Gbits/s”, EETimes.com, (Jul. 2, 2001),2 pgs.
Chiueh, T.-C. , et al., “High-Performance IP Routing Table Lookup Using CPU Caching”,Proceedings, Eighteenth Annual Joint Conference of the IEEE Computer and Communication Societies(INFOCOM '99), vol. 3, (1999), 1421-1428.
Degermark, M. , et al., “Small Forwarding Tables for Fast Routing Lookups”,Proceedings, ACM SIGCOMM '97, (1997), 3-14.
Gupta, P., et al., “Classifying Packets With Hierarchical Intelligent Cuttings”,IEEE Micro, 21(1), (Jan./Feb. 2000), 34-41.
Gupta, P., et al., “Packet Classification on Multiple Fields”,Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication(ACM SIGCOMM '99), (1999),147-160.
Gupta, P., et al., “Routing Lookups in Hardware at Memory Access Speeds”,Proceedings, Seventeen Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM '98), vol. 3, (1998), 1240-1247.
Kung, H. T., et al., “Algorithms for VLSI Processor Arrays”, In:Introduction to VLSI Systems, Mead, C., et al., Editors, Addison-Wesley, Reading, MA,(1980), 271-292.
Lakshman, T. V., et al., “High-Speed Policy-Based Packet Forwarding Using Efficient Multi-Dimensional Range Matching”,Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications(ACM SIGCOMM '98), (1998), 203-214.
Lampson, B., et al., “IP Lookups Using Multiway and Multicolumn Search”,IEEE/ACM Transactions on Networking, 7(3), (Jun. 1999), 324-334.
Lindberg, K., “Multi-Gigabit Routers”,Proceedings, HUT Internetworking Seminar, http://www.tml.hut.fi/Opinnot/Tik-110.551/1998/papers/02/MultiGigabitRouter/paper.html,(observed May 12, 1998), 14 pgs.
McAuley, A. J., et al., “Fast Routing Table Lookup Using CAMs”,Proceedings, Twelfth Annual Joint Conference of the IEEE Computer and Communications Societies, Networking: Foundation for the Future(INFOCOM '93), vol. 3, (1993), 1382-1391.
Partridge, C., et al., “A 50-Gb/s IP Router”,IEEE/ACM Transactions on

Affiliated with

Also associated with

Rating

Methods and apparatus for providing loop free routing tables does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Methods and apparatus for providing loop free routing tables, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for providing loop free routing tables will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2639199