Network restoration

• US 6,163,525 A
• Filed: 11/20/1997
• Issued: 12/19/2000
• Est. Priority Date: 11/29/1996
• Status: Expired due to Term

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Bentall, Mark, Turton, Brian Charles Hargrave
• Primary Examiner(s): Pham, Chi H.
• Assistant Examiner(s): Pham, Brenda H.
• Application Number:
  US08/975,014
• Time in Patent Office: 1,125 Days
• Field of Search: 370/222, 370/225, 370/227, 370/228, 370/248, 370/219, 370/220, 370/221, 370/351, 340/825.01, 340/827
• US Class Current: 370/227
• CPC Class Codes: H04L 2012/5619 Network Node Interface, e.g. tandem connections, transit switching
• CPC Class Codes: H04L 2012/5627 Fault tolerance and recovery
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/247 using M:N active or standby paths
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections
• CPC Class Codes: H04Q 3/0079 involving restoration of networks, e.g. disaster recovery, self-healing networks

Abstract

For restoration of a network a plurality of possible alternative routes are determined. Messages are passed between nodes along the alternative routes to determine a spare capacity of each link in the alternative routes. An alternative route is selected from the possible alternative routes on the basis of a database of the determined link spare capacities for each of the possible alternative routes, built up at a chooser node at one side of the failed part of the network.

Claims

1. A method of determining an alternative route for a communication between nodes in a network, following failure of part of the network, the network comprising a plurality of nodes, and links between the nodes, the method comprising the steps of:

determining a plurality of possible alternative routes around the failed part and having any spare capacity;

passing messages between nodes along the possible alternative routes to gather information relating to an amount of spare capacity of each link in the possible alternative routes; and

selecting the alternative route for the communication from said possible alternative routes on the basis of at least the gathered link spare capacities.

2. The method of claim 1 further comprising the steps of:

selecting at least one of the nodes as a chooser node; and

passing information relating to the determined spare capacities to a chooser node, wherein the step of selecting the alternative route is carried out by the chooser node.

3. The method of claim 2 comprising the steps of:

using the chooser to select a further alternative route for a further communication on the basis of the link spare capacities determined at the outset, and the capacity occupied by the first alternative route.

4. The method of claim 1 further comprising the step of allocating at least a part of the spare capacity of each link used by the selected route, to the selected route.

5. The method of claim 1 further comprising the step of determining whether the alternative routes use nodes in the vicinity of the failed part, wherein the selecting step is carried out also on the basis of the determined number of nodes used in the vicinity of the failed part.

6. The method of claim 1 wherein the route comprises a virtual path.

7. The method of claim 1 further comprising the steps of:

selecting a sender node on one side of the failure, from which the messages are sent; and

selecting a chooser node on the other side of the failure to receive the messages, wherein information relating to the determined spare capacities is stored at the chooser node, and the selecting step is carried out by the chooser node.

8. The method of claim 7 wherein the chooser node is one of the nodes on an original route for the communication before the failure.

9. The method of claim 8 wherein at least one candidate chooser node is identified, further from the failed part than the chooser, on the original route, and the messages are also sent to the candidate chooser, to determine possible alternative routes not passing through the chooser.

10. The method of claim 8 wherein at least one candidate sender node is identified, further from the failed part than the sender, on an original route for the communication, and the messages are also sent from the candidate sender, to determine possible alternative routes not passing through the sender.

11. The method of claim 1 further comprising the step of changing the selected alternative route to optimise it.

12. The method of claim 11, wherein the step of optimising comprises the step of reducing the length of the selected alternative route.

13. The method of claim 11 wherein the step of optimising comprises the step of avoiding using nodes in the vicinity of the failed part.

14. The method of claim 1 for providing alternative routes for multiple concurrent communications, the method comprising the steps of:

allocating a portion of the spare capacity on one of the alternative routes to a first of the communications;

allocating remaining spare capacity, to others of the concurrent communications according to the spare capacity determined at the outset, and the amount of spare capacity already allocated.

15. The method of claim 1 further comprising the step of using the selected alternative route for the communication.

22. Software for carrying out the method of claim 1.

16. A method of providing alternative routes for multiple concurrent communications between nodes in a network, following failure of a part of the network affecting the multiple communications, the network comprising a plurality of nodes, and links between the nodes, the method comprising the steps of:

determining the route has failed;

determining alternative routes around the failed part;

selecting at least one of the nodes in the vicinity of the failed part, as a chooser node;

determining an amount of spare capacity on the alternative routes, and using the chooser node to control allocation of the determined spare capacity on the alternative routes to the multiple concurrent communications.

17. A network comprising:

a plurality of nodes and links connecting the nodes, for passing information along a route set up across the network via the nodes, the network further comprising;

means for determining a plurality of possible alternative routes having any spare capacity in the event of failure of part of the network;

means for passing messages along the possible alternative routes to determine an amount of spare capacity of each link in the alternative routes; and

means for selecting one of the possible alternative routes on the basis of the determined link spare capacities.

24. A method of using the network of claim 17 to provide a communication service by passing information.

18. A node for a network, the network comprising a plurality of such nodes, interconnected by links, for passing information along a route set up across the network, the node comprising:

means for determining a plurality of possible alternative routes having any spare capacity for use in the event of failure of part of the network and;

means for passing messages along the possible alternative routes to gather information relating to the spare capacity of each link in the possible alternative routes; and

means for receiving information relating to the spare capacity of each link in the possible alternative routes, and selecting at least one of the alternative routes on the basis of the received information.

19. Apparatus for determining an alternative route for a communication between nodes in a network, following failure of part of the network, the network comprising a plurality of nodes, and links between the nodes, the network being arranged to determine plurality of possible alternative routes having sufficient spare capacity around the failed part for the communication the apparatus comprising;

circuitry for receiving messages from nodes along the possible alternative routes, the messages comprising an indication of an amount of spare capacity of the links in the possible alternative routes; and

circuitry for selecting the alternative route for the communication from the possible alternative routes on the basis of at least the amounts of spare capacity of the links.

20. The apparatus of claim 19 further comprising circuitry for determining a remaining spare capacity for the links of the alternative route after some of the spare capacity for each of these links has been allocated to the communication.

21. The apparatus of claim 20 for determining alternative routes for at least one further communication, comprising;

circuitry for selecting an alternative route for the further communication, from the possible alternative routes on the basis of at least the remaining spare capacity.

23. Software for a node of a network, the network comprising a plurality of such nodes, interconnected by links, for passing information along a route set up across the network. The network being arranged to determine a plurality of possible alternative routes for use in the event of failure of part of the network, the software being arranged to carry out the steps of;

receiving messages from nodes along the possible alternative routes, the messages comprising an indication of an amount of spare capacity of the links in the possible alternative routes; and

selecting the alternative route for the communication, from the possible alternative routes, on the basis of at least the link spare capacities.