Using alternate routes for fail-over in a communication network

• US 6,857,026 B1
• Filed: 12/14/1999
• Issued: 02/15/2005
• Est. Priority Date: 12/14/1999
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Cain, Bradley
• Primary Examiner(s): Dharia, Rupal
• Assistant Examiner(s): WILLETT, STEPHAN F
• Application Number:
  US09/460,566
• Time in Patent Office: 1,890 Days
• Field of Search: 709/227, 709/229, 709/237, 709/238, 709/239, 709/240, 709/242, 709/245, 714/1, 714/4, 370/389, 370/392, 370/396
• US Class Current: 709/239
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

Using alternate routes for fail-over in a communication network involves maintaining a preferred route and an alternate route in a routing table and routing protocol messages according to the alternate route when the preferred route is unavailable. A node obtains multiple routes for a destination, prioritizes the routes, and installs multiple routes in the routing table, including at least the preferred route and the alternate route. When the node receives a protocol message, the node searches the routing table for a highest priority route that is available for routing the protocol message, and routes the protocol message according to the highest priority route that is available for routing the protocol message. When a route becomes unavailable, the node updates the routing table to indicate that the route is unavailable, and may compute new routes and/or re-prioritize existing routes.

Claims

1. A method for utilizing alternate routes from a source node to a destination node for fail-over communication by the source node in a communication network, the method comprising:

maintaining a preferred route from the source node to the destination node in a routing table, the routing table accessed during operation for routing protocol messages;

maintaining, contemporaneously with the preferred route, an alternate route from the source node to the destination node in the routing table; and

selecting either the preferred route or the alternate route for routing a protocol message responsive to an availability of the referred route.

2. The method of claim 1, wherein the preferred route is a shortest-path route as determined by a predetermined shortest path computation, and wherein the alternate route is a non-shortest-path route with respect to the predetermines shortest path computation.

3. The method of claim 1, wherein at least one of the preferred routes and the alternate routes includes at least one additional node in a path from the source node to the destination node.

4. The method of claim 1, wherein the preferred route is associated with a first weight, and wherein the alternate route is associated with a second weight less than the first weight.

5. The method of claim 1, wherein the preferred route from the source node to the destination node is associated with a first interface of the source node, and wherein the alternate route is associated with a second interface of the source node different than the first interface.

6. The method of claim 1, wherein the preferred route is associated with a first next hop node, and wherein the alternate route is associated with a second next-hop node different than the fist next-hop node.

7. An apparatus for utilizing alternate routes from a source node to a destination node for fail-over communication in a network, the apparatus comprising:

a routing table accessed during operation for routing protocol messages between the source node and the destination node;

route maintenance logic operably coupled to maintain a preferred route from the source node to the destination node and to contemporaneously maintain an alternate route from the source node to the destination node in the routing table; and

routing logic operably coupled to select either the preferred route or the alternate route to route a protocol message responsive to an availability of the preferred route.

8. The apparatus of claim 7, wherein the preferred route is a shortest-path route as determined by a predetermined shortest path computation, and wherein the alternate route is a non-shortest path route with respect to the predetermines shortest path computation.

9. The apparatus of claim 7, wherein at least one of the preferred routes and the alternate routes includes at least one additional node in a path from the source node to the destination node.

10. The apparatus of claim 7, wherein the preferred route is associated with a fist weight, and wherein the alternate route is associated with a second weight less than the first weight.

11. The apparatus of claim 7, wherein the preferred route is associated with a first interface, and wherein the alternate route is associated with a second interface different than the first interface.

12. The apparatus of claim 7, wherein the preferred route is associated with a first next-hop node, and wherein the alternate route is associated with a second next-hop node different than the first next-hop node.

13. The apparatus of claim 7, wherein the route maintenance logic is operably coupled to obtain a plurality of routes from the source node to the destination node and prioritize the plurality of routes in order to determine the preferred route and the alternate route.

14. The apparatus of claim 13, wherein the route maintenance logic is operably coupled to associate each route with a weight indicating the relative priority for the route.

15. The apparatus of claim 14, wherein the route maintenance logic is operably coupled to install the preferred route and the alternate route in the routing table.

16. The apparatus of claim 15, wherein the routing logic is operably coupled to search the routing table for a highest priority route that is available for routing the protocol message.

17. The apparatus of claim 16, wherein the routing logic is operably coupled to route the protocol message according to the highest priority route that is available for routing the protocol message.

18. A program product comprising a computer readable medium having embodied therein a computer program for utilizing alternate routes from a source node to a destination node for fail-over communication by the source node in a communication network, the computer program comprising:

route maintenance logic programmed to maintain a preferred route from the source node to the destination node and to contemporaneously maintain an alternate route from the source node to the destination node in a routing table that is accessed during operation to route protocol message between the source node and destination node; and

routing logic programmed to select either the preferred route or the alternate route to route a protocol message responsive to an availability of preferred route.

19. The program product of claim 18, wherein the preferred route is a shortest-path route as determined by a predetermined shortest path computation, and wherein the alternate route is a non-shortest-path route with respect to the predetermines shortest path computation.

20. The program product of claim 18, wherein at least one of the preferred routes and the alternate routes includes at least one node in a path from the source node to the destination node.

21. The program product of claim 18, wherein the preferred route is associated with a first weight, and wherein the alternate route is associated with a second weight less than the first weight.

22. The program product of claim 18, wherein the preferred route is associated with a first interface of the nude, and wherein the alternate route is associated with a second interface of the node different than the first interface.

23. The prod product of claim 18, wherein the preferred route is associated with first next-hop node, and wherein the alternate route is associated with a second next-hop node different than the first next-hop node.

24. The program product of claim 18, wherein the route maintenance logic is programmed to obtain a plurality of mutes and prioritize the plurality of routes in order to determine the preferred route and the alternate route.

25. The program product of claim 24, wherein the route maintenance logic is programmed to associate each route with a weight indicating the relative priority for the route.

26. The program product of claim 25, wherein the route maintenance logic is programmed to install the preferred route and the alternate route in the routing table.

27. The program product of claim 26, wherein the routing logic is programmed to search the routing table for a highest priority route that is available for routing the protocol message.

28. The program product of claim 27, wherein the routing logic is programmed to route the protocol message according to the highest priority route that is available for routing the protocol message.

29. An apparatus comprising:

route determination means for determining a plurality of routes from a source node to a destination node;

route prioritization means for prioritizing said plurality of routes into at least a preferred route and an alternate route, wherein at least one of the preferred route and the alternate route include an additional node disposed between the source node and the destination node;

routing table means for contemporaneously maintaining said preferred route and said alternate route, the routing table means accessed during operation to identify a route for forwarding message between the source node and the destination node; and

routing means for selecting either the preferred route or the alternate route for routing a protocol message responsive to an availability of the preferred route.

30. A communication system comprising a plurality of interconnected nodes including at least a first node and a second node, wherein said first node is operably coupled to contemporaneously maintain at least a preferred route and an alternate route to said second node in a routing table, the routing table accessed during operation to provide ar toue and to route a protocol message to said second node using said alternate route when said preferred route is unavailable, wherein at least one of the preferred route and the alternate route include an third node disposed between the first node and the second node.