Centralized restoration of a network using preferred routing tables to dynamically build an available preferred restoral route

• US 6,327,669 B1
• Filed: 12/31/1996
• Issued: 12/04/2001
• Est. Priority Date: 12/31/1996
• Status: Expired due to Term

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: MCI Communications Corporation (Verizon Communications Inc.)
• Inventors: Croslin, William D.
• Primary Examiner(s): Trammell, James P.
• Assistant Examiner(s): Elisca, Pierre E.
• Application Number:
  US08/775,220
• Time in Patent Office: 1,799 Days
• Field of Search: 395/182.02, 395/183.19, 395/200.59, 395/200.68, 395/200.72, 395/184.01, 370/217, 370/225, 370/16, 370/220, 370/227, 370/228, 714/4, 714/43, 714/47, 709/229, 709/238, 709/242
• US Class Current: 714/4.1
• 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/28 using route fault recovery
• CPC Class Codes: H04L 45/42 Centralised routing

Abstract

A centralized restoration system utilizes preferred routing tables to identify an optimal restoral path for restoring a network from a failure. The preferred routing tables are constructed prior to the failure of the network. This pre-construction of the preferred routing tables prior to network failure substantially diminishes the computational and temporal requirements needed to restore the network at the time of failure. The centralized restoration system is able to account for changes in network topology and configuration. The centralized restoration system builds the optimal restoral path on a link by link basis and examines the availability of links prior to adding the link to the optimal restoral path. Unavailable links are not added to the restoral path.

Claims

1. In a network having interconnected nodes and a computer system a method of constructing a segment of a preferred restoral path for restoring the network from a failure, comprising the computer-implemented steps of:

prior to the failure of the network,

providing a preferred routing table for a current node among the interconnected nodes that specifies choices for a next segment of one or more restoral paths to a target node for restoring the network from the failure;

at a time of the failure of the network,

(i) accessing the preferred routing table to examine the choices for the next segment of the preferred restoral path from the current node to the target node; and

(ii) selecting one of the choices as a next segment of the preferred restoral path to be used in restoring the network from the failure.

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

determining that the segment of a first of the choices is unavailable; and

eliminating the first of the choices as a viable choice for selection.

3. The method of claim 1 wherein the selected next segment of the preferred restoral path includes a connection between the current node and a subsequent node of the interconnected nodes, wherein a preferred routing table is provided for the subsequent node prior to the failure of the network that specifies choices for an additional segment of one or more of the restoral paths to the target node and wherein the method further comprises the steps of:

at the time of the failure of the network,

(i) accessing the preferred routing table of the subsequent node to examine the choices for the additional segment of the preferred restoral path; and

(ii) selecting one of the choices of the preferred routing table of the subsequent node as the additional segment of the preferred restoral path.

4. The method of claim 1, further comprising the step of implementing the preferred restoral path.

5. The method of claim 1, wherein the nodes are interconnected by links and wherein the step of providing the preferred routing table comprises providing a list of ports that interface with links that lead to adjacent ones of the interconnected nodes in the one or more restoral paths.

6. The method of claim 5 wherein the ports are prioritized according to cost of using the links with which the ports interface, wherein priority of each port relates inversely to the cost of the link with which the port interfaces.

7. The method of claim 6 wherein the port with the highest priority is selected.

8. The method of claim 1 wherein the network is a telecommunications network.

9. The method of claim 1 wherein the network is a telephone network.

10. In a telecommunications network having nodes, links for carrying network traffic between nodes, ports on the nodes for interfacing with the links, and a centralized restoration system for restoring the network from failures, a method of restoring the network performed by the centralized restoration system, comprising the steps of:

identifying a location of a network failure;

identifying at least one pair of end nodes that are affected by the network failure such that the failure prevents traffic from flowing between the end node pairs over given connecting paths;

providing preferred routing tables for at least each of the nodes in the identified pairs of end nodes, wherein each preferred routing table specifies a list of one or more ports that interface with links to a restoral path that leads to a target node, said list specifying priority of the one or more ports;

using the preferred routing tables to determine a preferred restoral path for at least one of the identified end node pairs on a port by port basis;

selecting one of the preferred restoral paths as a restoral path to be implemented; and

communicating with selected ones of the nodes to implement the selected restoral path to restore the network from the network failure.

11. The method of claim 10 wherein only a single pair of end nodes is identified.

12. The method of claim 10 wherein all of the end node pairs that are affected are identified.

13. The method of claim 10 wherein each preferred restoral path has an associated cost and a lowest cost one of preferred restoral paths is selected to be implemented.

14. The method of claim 10 wherein the telecommunications network includes a trunk, wherein the failure occurs after the trunk and wherein the nodes in the end node pairs are connected by the trunk.

15. The method of claim 10 wherein the preferred routing tables are provided prior to the failure.

16. In a telecommunications network having nodes with ports that interface with links to interconnect the nodes and a computer system, a method comprising the computer-implemented steps of:

prior to a failure in the telecommunications network, providing lists of ports for connected nodes in the network wherein each list provides an indication of relative A B preference of the ports listed therein and each port interfaces with one of the links that leads to another one of the nodes that is part of a restoral path that leads to a target one of the nodes for restoring the network in response to a failure of the network; and

upon failure of the network, iteratively building a preferred restoral path on a link by link basis by using the lists of ports to identify optimal links in the preferred restoral path.

17. The method of claim 16. further comprising the step of implementing the preferred restoral path to restore the network for network traffic.

18. The method of claim 16 wherein the computer system is a tightly-coupled computer system that performs the steps of the method.

19. In a telecommunications system network having nodes that are interconnected to facilitate communications among the nodes, a centralized system for restoring the network after a failure comprising:

a static component that provides prior to failure of the network, preferred routing tables that each identify portions of at least one preferred restoral route for restoring a connection between two of the nodes; and

a dynamic component for dynamically determining a restoral route at a time of a failure in the network, said dynamic component using the preferred routing tables to determine a selected preferred restoral route based on availability of portions of the preferred restoral routes identified in the tables.

20. In a network having interconnected nodes and a computer system, a computer-readable medium holding computer-executable instructions for performing a method of constructing a segment of a preferred restoral path for restoring the network from a failure, comprising the computer-implemented steps of:

prior to the failure of the network,

providing a preferred routing table for a current node among the interconnected nodes that specifies choices for a next segment of one or more restoral paths to a target node for restoring the network from the failure;

at a time of the failure of the network,

(i) accessing the preferred routing table to examine the choices for the next segment of the preferred restoral path from the current node to the target node; and

(ii) selecting one of the choices as a next segment of the preferred restoral path to be used in restoring the network from the failure.

21. The computer-readable medium of claim 20 wherein the method further comprises the steps of:

determining that the segment of a first of the choices in unavailable; and

eliminating the first of the choices as a viable choice for selection.

22. The computer-readable medium of claim 20 wherein the selected next segment of the preferred restoral path includes a connection between the current node and a subsequent node of the interconnected nodes, wherein a preferred routing table is provided for the subsequent node prior to the failure of the network that specifies choices for an additional segment of one or more of the restoral paths to the target node and wherein the method further comprises the steps of:

at the time of the failure of the network,

(i) accessing the preferred routing table of the subsequent node to examine the choices for the additional segment of the preferred restoral path; and

(ii) selecting one of the choices of the preferred routing table of the subsequent node as the additional segment of the preferred restoral path.

23. In a telecommunications network having nodes, links for carrying network traffic between nodes, ports on the nodes for interfacing with the links, and a centralized restoration system for restoring the network from failures, a computer-readable medium holding computer-executable instructions for performing a method of restoring the network performed by the centralized restoration system, comprising the steps of:

identifying a location of a network failure;

identifying at least one pair of end nodes that are affected by the network failure such that the failure prevents traffic from flowing between the end node pairs over given connecting paths;

providing preferred routing tables for at least each of the nodes in the identified pairs of end nodes, wherein each preferred routing table specifies a list of one or more ports that interface with links to a restoral path that leads to a target node, said list specifying priority of the one or more ports;

using the preferred routing tables to determine a preferred restoral path for at least one of the identified end node pairs on a port by port basis;

selecting one of the preferred restoral paths as a restoral path to be implemented; and

communicating with selected ones of the nodes to implement the selected restoral path to restore the network from the network failure.