Multiplex communications – Fault recovery – Bypass an inoperative channel
Reexamination Certificate
2003-11-21
2008-09-23
Ngo, Ricky (Department: 2616)
Multiplex communications
Fault recovery
Bypass an inoperative channel
C370S238000, C370S242000, C370S248000, C370S256000
Reexamination Certificate
active
07428213
ABSTRACT:
A method and apparatus are disclosed for performing a shortest path first network routing path determination in a data communications network based in part on information about links that are associated as shared risk link groups. Micro-loops are avoided in computing shortest path first trees by considering whether links are within shared risk link groups. In a first approach, for each link state packet in a link state database, listed adjacencies are removed if the link between the node originating the LSP and the reported adjacency belongs to a shared risk link group for which one component (local link) is known as down, and a shortest path first computation is then performed. In a second approach, during the SPT computation and after having added a first node to a path, each neighboring node is added to a tentative tree if and only if, a link between the first node and the neighboring node does not belong to a shared risk link group for which one component (local link) is known as down.
REFERENCES:
patent: 4827411 (1989-05-01), Arrowood et al.
patent: 5243592 (1993-09-01), Perlman et al.
patent: 5253248 (1993-10-01), Dravida et al.
patent: 5999286 (1999-12-01), Venkatesan
patent: 6032194 (2000-02-01), Gai et al.
patent: 6128750 (2000-10-01), Espy et al.
patent: 6256295 (2001-07-01), Callon
patent: 6278687 (2001-08-01), Hunneyball
patent: 6377542 (2002-04-01), Asprey
patent: 6535481 (2003-03-01), Andersson et al.
patent: 6578084 (2003-06-01), Moberg et al.
patent: 6578086 (2003-06-01), Regan et al.
patent: 6590868 (2003-07-01), Shen
patent: 6636498 (2003-10-01), Leung
patent: 6668282 (2003-12-01), Booth et al.
patent: 6697325 (2004-02-01), Cain
patent: 6711125 (2004-03-01), Walrand et al.
patent: 6882627 (2005-04-01), Pieda et al.
patent: 6944131 (2005-09-01), Beshai et al.
patent: 6982951 (2006-01-01), Doverspike et al.
patent: 7099286 (2006-08-01), Swallow
patent: 7113481 (2006-09-01), Elie-Dit-Cosaque et al.
patent: 2002/0012318 (2002-01-01), Moriya et al.
patent: 2002/0093954 (2002-07-01), Weil et al.
patent: 2002/0112072 (2002-08-01), Jain
patent: 2002/0116669 (2002-08-01), Jain
patent: 2003/0147352 (2003-08-01), Ishibashi et al.
patent: 2004/0085894 (2004-05-01), Wang et al.
patent: 2005/0031339 (2005-02-01), Qiao et al.
patent: 2007/0011284 (2007-01-01), Le Roux et al.
International Searching Authority, International Search Report, PCT/US04/33827, dated Mar. 28, 2005, 8 pages.
Current Claims, PCT/US04/33827, 6 pages.
Wang, Zheng et al., “Shortest Path First with Emergency Exits,” ACM 089791-405-8/90/0009/0166, 1990, pp. 166-176.
M. Watari, “Masafumi Watari's Web Site,” “Papers” page, printed May 7, 2003, http://www.sfc.wide.ad.jp/˜watari/papers.html, 1 page.
C. Perkins, “IP Mobility Support for IPv4,” Jan. 2002, IETF Network Working Group Request for Comments 3220 (RFC 322), from www.ietf.org, pp. 1-98.
S. Deering, et al., “Internet Protocol, Version 6 (IPv6), Specification,” Dec. 1998, IETF Network Working Group Request for Comments 2460, from www.ietf.org, pp. 1-39.
University of Southern California, Information Sciences Institute, “Internet Protocol, DARPA Internet Program, Protocol Specification,” Sep. 1981 (IETF RFC 791), 48 pages.
D. Johnson, et al., “Mobility Support in Ipv6, draft-ietf-mobileip-ipv6-21.txt,” Feb. 26, 2003, http://www.ietf.org/html.charters/mobileip-charter.html, pp. 1-169.
Ryuji Wakikawa, et al., “Mobility Related Research at InternetCAR Project,” http://www.connectathon.org/talks03/cthon-keio.pdf, Mar. 5, 2003, 12 pages.
William Stallings, “Mobile IP,” http://www.cisco.com/warp/public/ipi—4-2—ip.html, 11 pages.
Cisco Systems, Inc., “White Paper,Cisco Mobile IP, Executive Summary,” 2002, http://www.cisco.com/warp/public/cc/pd/10sw/prodlit/mbxul—wp.htm, 8 pages.
Cisco Systems, Inc., “Configuring Mobile IP,” http://www.cisco.com/warp/public/732/Tech/mobile/IP/techdocument, 2003, 38 pages.
Mikkel Thorup, “Fortifying OSPF/IS-IS against link-failure,” Sep. 7, 2001, pp. 1-10.
Fei Dai et al., “On Independently Finding Converging Paths in Internet,” 2001, pp. 1-13.
Paolo Narváez et al., “Local Restoration Algorithm for Link-State Routing Protocols,” 1998, 6 pages.
Jie Wu et al., “An Extended Fault-Tolerant Link-State Routing Protocol in the Internet,” 2001, 7 pages.
Paolo Narváez et al., “Fault-Tolerant Routing in the Internet without Flooding,” 1998, pp. 1-13.
Takuya Yoshihiro, “Design and Analysis of Routing Algorithms toward the Next Generation Internet,” Dec. 2002, 98 pages.
Fortz, Bernard, et al., “Optimizing OSPF/IS-IS Weights in a Changing World,” IEEE JSAC Special Issue on Advances in Fundamentals of Network Management, Spring 2002, pp. 1-31.
Thorup, Mikkel, et al., “Avoiding Ties in Shortest Path First Routing,” AT&T Labs-Research, Shannon Laboratory, Florham Park, NJ, pp. 1-13.
Thorup, Mikkel, “OSPF Areas Considered Harmful,” AT&T Labs-Research, Florham Park, NJ, Apr. 22, 2003, pp. 1-9.
M. Leelanivas, et al., “Graceful Restart Mechanism for Label Distribution Protocol,” Feb. 2003, Network Working Group, Request for Comments: 3478, http://rfc3478.x42.com, data retrieved Apr. 28, 2004, pp. 1-11.
R. Balay, et al., “IS-IS Mesh Groups,” Oct. 2000, Network Working Group, Request for Comments: 2973, pp. 1-8.
M. Shand, et al., Restart signaling for IS-IS, draft-ietf-isis-restart-05.txt, Jan. 2004, Network Working Group, Internet Draft, http://www.ietf.org/internet-drafts/draft-ietf-isis-restart-05.txt, data retrieved Apr. 28, 2004, pp. 1-20.
Amir Hermelin, et al., “Extending the Number of IS-IS LSP Fragments Beyond the 256 Limit, draft-ietf-isis-lsp-frags-02.txt,” Network Working Group, Internet Draft, http://www.ietf.org/internet-drafts/draft-ietf-isis-ext-lsp-frags-02.txt, data retrieved Apr. 28, 2004, pp. 1-12.
M. Shand, et al., “Restart signaling for IS-IS, draft-ietf-isis-restart-04.txt,” Jul. 2003, Network Working Group, Internet Draft, http://vesuvio.ipv6.tilab.com/internet-drafts/draft-ietf-isis-restart-04.txt, data retrieved Apr. 28, 2004, pp. 1-18.
U.S. Appl. No. 10/442,589, filed May 20, 2003, Stewart Frederick Bryant, et al., entitled “A Method and Apparatus for Constructing a Transition Route in a Data Communication Network,” 45 pages.
U.S. Appl. No. 10/340,371, filed Jan. 9, 2003, Kevin George Miles, et al., entitled Method and Apparatus for Constructing a Backup Route in a Data Communications Network, 33 pages.
Cisco Systems, Inc., “Tunnel ToS,” Cisco IOS Release 12.0(17)S, 12.0(17)ST, 12.2(8)T, and 12.2(14)S, Jan. 28, 2003, pp. 1-15.
Cisco Systems, Inc., “AppleTalk, IP, and Novell IPX Overview,” Sep. 9, 2002, pp. IV-1-IV-6.
Cisco Systems, Inc., “Why Are OSPF Neighbors Stuck in Exstart/Exchange State?,” 1992-2003, 8 pages.
Cisco Systems, Inc., “Trace,” Chapter 32, Sep. 13, 2002, pp. 32-1-32-12.
U.S. Appl. No. 10/323,358, filed Dec. 17, 2002, Ian Michael Charles Shand, entitled “Method and Apparatus for Advertising a Link Cost in a Data Communications Network,” 29 pages.
Office Action from China for foreign patent application 200480033399.8 dated Feb. 29, 2008 (4 pgs) with English Translation (4 pgs).
Current claims in China patent application 200480033399.8 (3 pgs) with marked up copy (4 pgs).
Filsfils Clarence
Previdi Stefano B.
Vasseur Jean Philippe
Ward David
Cisco Technology Inc.
Hickman Palermo & Truong & Becker LLP
Mui Gary
Ngo Ricky
LandOfFree
Method and apparatus for determining network routing... 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 determining network routing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for determining network routing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3986625