Facility restoration for telecommunications networks

Claim 2

For use with a telecommunications network having nodes interconnected by edges, a method for restoring telecommunications traffic in the network following a disruption of traffic due to a circuit outage affecting traffic between nodes, comprising the steps of: (a) determining where within the network the outage occurred; (b) retrieving prestored circuit routing data from a central data base; (c) characterizing the telecommunications traffic disrupted by the outage as commodities for restoral; (d) developing a multicommodity model of the network based on the information obtained from steps (a) and (b); (e) establishing decision variables for determining actions potentially to be taken within the nodes; (f) applying a multicommodity algorithm to the model and to the decision variables to determine (i) reroutes available via spare and impacted edges and (ii) actions to be taken within the nodes for achieving said reroutes; (g) transmitting instructions for implementing the determined actions to all nodes affected by performance of step (f).

Claim 3

The method of claim 1 wherein (i) a restoral priority is established for each commodity to be restored; (ii) an edge capacity available for restoral is determined; and (iii) steps (d), (e), and (f) are repeatedly applied to the commodities in order of priority until all commodities are restored or the capacity available for restoral is exhausted.

Claim 4

The method of claim 2 wherein the multicommodity model is based on a measure of the commodities to be restored between nodes and the capacity available for restoral.

Claim 5

The method of claim 3 wherein the prestored circuit routing data includes information on spare edges and wherein the capacity available for restoral is determined from the capacity remaining available in impacted edges and from spare edge groups, said spare edge groups being formed from spare edges between nodes which have preselected attributes in common.

Claim 6

The method of claim 4 wherein the decision variables are established for a node by grouping all incident edges into groups such that the incident edges of a group all meet a common preselected criterion, and further including the steps of: creating a pair of dummy nodes having a first and a second dummy node for each incident edge group; redirecting all edges of each incident edge group to the first dummy node of the pair with which that group is associated; redirecting duplicate edges of each incident edge group from the second dummy node of the pair with which that group is associated; and creating a potential action edge between each first dummy node and each second dummy node from which the actions to be taken within a node may be selected.

Claim 7

The method of claim 5 including the further step of establishing a cost factor for each impacted edge having capacity remaining for restoral, for each spare edge, and for each potential action edge, and wherein such cost factors are used in step (f) so that the reroutes and actions are determined to be at the lowest cost.

Claim 8

The method of claim 6 wherein in step (a) the location of the outage is determined via control circuits providing outage alarms and in step (g) the instructions for implementing the actions to be taken in said nodes are transmitted via said control circuits.

Claim 9

The method of claim 5 wherein prior to step (g) the reroutes and actions determined in step (f) are provided for review and approval by operating personnel.

Claim 10

For a communications network having nodes and routes providing circuits interconnecting the nodes, each circuit having some capacity for carrying communications traffic as a commodity, a method for restoring commodities between nodes following a disruption of traffic due to a circuit outage, comprising the steps of: (a) determining where within the network the outage occurred; (b) retrieving prestored circuit routing data from a central data base; (c) developing a multicommodity model of the network based on the information obtained from steps (a) and (b) by (i) determining a measure of the commodities desired to be restored between nodes; (ii) determining capacity available for restoral by (ii') determining capacity in each remaining circuit which was carrying traffic affected by the outage; (ii") grouping spare circuits between adjacent nodes into spare circuit groups wherein the spare circuits of a group have certain attributes in common; (ii'") determining capacity in each spare circuit group; (d) establishing decision variables to determine actions to be taken within a node by (i) grouping all circuits incident upon the node into incident circuit groups wherein the incident circuits of a group meet a common preselected criteria; (ii) creating a pair of dummy nodes for each incident circuit group, each pair having a first and a second dummy node; (iii) redirecting all circuits of each incident circuit group to the first dummy node of the dummy node pair with which that group is associated; (iv) redirecting duplicate circuits of each incident circuit groups from the second dummy node of the dummy node pair with which that group is associated; (v) creating a potential action connection between each first dummy node and each second dummy node; (e) establishing a restoral priority for each commodity to be restored; (f) applying a multicommodity algorithm to the model and to the decision variables to determine a reroute and actions to be taken within a node for the commodity having the highest priority; (g) repeating steps (c), (d), and (f) in order of priority for each remaining commodity to be restored until either reroutes are determined for all remaining commodities to be restored or the capacity for restoral is exhausted, taking into account in each repetition, any changes in capacity resulting from prior higher priority determinations; and (h) transmitting instructions for implementing the determined actions to all nodes affected by performance of step (g).

Claim 11

For a communications network having nodes and routes providing circuits interconnecting the nodes, each circuit having some capacity for carrying communications traffic as a commodity, a method for restoring commodities between nodes following a disruption of traffic due to a circuit outage, comprising the steps of: (a) determining where within the network the outage occurred; (b) retrieving prestored circuit routing data from a central data base; (c) developing a multicommodity model of the network based on the information obtained from steps (a) and (b) by (i) determining a measure of the commodities desired to be restored between nodes; (ii) determining capacity available for restoral by (ii') determining capacity in each remaining circuit which was carrying traffic affected by the outage; (ii") grouping spare circuits between adjacent nodes into spare circuit groups wherein the spare circuits of a group have certain attributes in common; (ii'") determining capacity in each spare circuit group; (d) establishing decision variables to determine actions to be taken within a node by (i) grouping all circuits incident upon the node into incident circuit groups wherein the incident circuits of a group meet a common preselected criteria; (ii) creating a pair of dummy nodes for each incident circuit group, each pair having a first and a second dummy node; (iii) redirecting all circuits of each incident circuit group to the first dummy node of the dummy node pair with which that group is associated; (iv) redirecting duplicate circuits of each incident circuit groups from the second dummy node of the dummy node pair with which that group is associated; (v) creating a potential action connection between each first dummy node and each second dummy node; (e) establishing a restoral priority for each commodity to be restored; (f) applying a multicommodity algorithm to the model and to the decision variables to determine a reroute and actions to be taken within a node for the commodity having the highest priority; (g) repeating steps (c), (d), and (f) in order of priority for each remaining commodity to be restored until either reroutes are determined for all remaining commodities to be restored or the capacity for restoral is exhausted, taking into account in each repetition, any changes in capacity resulting from prior higher priority determinations; and (h) transmitting instructions for implementing the determined actions to all nodes affected by performance of step (g).