Fault-tolerant non-flooding routing

• US 6,721,899 B1
• Filed: 01/12/2000
• Issued: 04/13/2004
• Est. Priority Date: 01/12/2000
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Tzeng, Hong-Yi, Siu, Kai-Yeung, Narvaez-Guarnieri, Paolo
• Primary Examiner(s): Iqbal, Nadeem
• Application Number:
  US09/481,100
• Time in Patent Office: 1,553 Days
• Field of Search: 714/4, 714/3, 714/7, 714/13, 714/18, 714/25, 714/39, 714/43, 714/56, 370/218, 370/217, 370/220, 370/227, 370/234, 709/104, 709/105, 709/220, 709/221, 709/239
• US Class Current: 714/4.3
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

This invention is an algorithm that restores routing in a link-state network after a link failure without flooding the entire routing area with new routing information. The algorithm operates only in the local neighborhood of the failed link and informs the minimum number of routers about the failure.

Claims

1. A non-flooding routing restoration method for use in a network with link-state routing protocol and shortest path routing, said network comprising a plurality of nodes and a plurality of links between the nodes, each said link being associated with a metric, said plurality of nodes including a plurality of routers, said plurality of routers comprising a first router and a second router, said plurality of links comprising a first link between said first router and said second router, said method comprising the steps of:

determining all nodes of a set of nodes D₀, said set D₀ including all descendants of said first link in any current shortest path tree rooted at said first router;

modifying a link-state database of said first router to include a change in a metric of said first link;

selecting a restoration path for sending packets from said first router to said second router, said restoration path being loop-free and not traversing said first link, said restoration path including n restoration path routers in a sequence, n being one or more, the sequence determined by the order in which a packet traveling from said first router to said second router along said restoration path would encounter said restoration path routers, a first restoration path router being one hop away from said first router, said second router being one hop away from a last restoration path router;

setting, in said first router, next hops for all nodes of said set D₀ to said first restoration path router;

notifying each restoration path router of said change in said metric of said first link;

identifying all nodes of a set of nodes associated with said each restoration path router, said set of nodes associated with said each restoration path router including all descendants of said first link in any current shortest path tree rooted at said each restoration path router;

assigning, in each restoration path router except said last restoration path router, next hops for all nodes of the set of nodes associated with said each restoration path router to an immediately following restoration path router in the sequence;

designating, in said last restoration path router, next hops for all nodes of the set of nodes associated with said last restoration path router to said second router.

2. A method according to claim 1, further comprising the step of incorporating said change in said metric of said first link in link-sate databases of said restoration path routers.

3. A method according to claim 2, wherein said step of incorporating includes the step of reconstructing, in said each restoration path router, a routing table based on a shortest path tree computation corresponding to said each restoration path router, said computation carried out on topological data that include said change in said metric of said first link.

4. A method according to claim 1 wherein said step of selecting includes the step of determining a shortest restoration path from said first router to said second router.

5. A method according to claim 1 wherein said step of selecting includes the step of determining a minimal restoration path from said first router to said second router.

6. A method according to claim 1 wherein said network'"'"'s routing protocol is OSPF.

7. A method according to claim 1 wherein said network'"'"'s routing protocol is IS—

IS.

8. Apparatus for updating routing in a network with link-state routing protocol and shortest path routing, said network comprising a plurality of nodes and a plurality of links between the nodes, each said link being associated with a metric, said plurality of nodes including a plurality of routers, said plurality of routers comprising a first router and a second router, said plurality of links comprising a first link between said first router and said second router, the apparatus comprising:

means for modifying a link-state database of said first router to include a change in a metric of said first link;

means for selecting a restoration path for sending packets from said first router to said second router, said restoration path including n restoration path routers in a sequence, n being one or more, the sequence determined by the order in which a packet traveling from said first router to said second router along said restoration path would encounter said restoration path routers, a first restoration path router being one hop away from said first router, said second router being one hop away from a last restoration path router;

means for setting, in said first router, next hops for all nodes that are descendants of said first link in any current shortest path tree rooted at said first router to said first restoration path router;

means for notifying each restoration path router of said change in said metric of said first link;

means for identifying all nodes of a set of nodes associated with said each restoration path router, said set of nodes associated with said each restoration path router including all descendants of said first link in any current shortest path tree rooted at said each restoration path router;

means for assigning, in each restoration path router except said last restoration path router, next hops for all nodes belonging to the set of nodes associated with said each restoration path router to an immediately following restoration path router in the sequence;

designating, in said last restoration path router, next hops for all nodes belonging to the set of nodes associated with said last restoration path router to said second router.

9. Apparatus according to claim 8, wherein said means for selecting a restoration path selects a shortest restoration path and, said means for selecting a restoration path further includes short path first engines in said restoration path.

10. Apparatus according to claim 8, wherein said means for selecting a restoration path selects a minimal restoration path.