Progressive Network Recovery

• US 20130227334A1
• Filed: 02/23/2012
• Published: 08/29/2013
• Est. Priority Date: 02/23/2012
• Status: Active Grant

• Current Assignee: City University of Hong Kong
• Original Assignee: City University of Hong Kong
• Inventors: WANG, Jianping
• Granted Patent: US 8,935,561 B2
• Time in Patent Office: Days
• US Class Current: 714/3
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• CPC Class Codes: H04L 41/0654 using network fault recovery ring fault isolation or reconfiguration in loop networks without recovery actions by a network management system H04L12/437
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network

Abstract

Technologies are generally described for systems and methods effective to schedule repair (e.g., allocate repair resources, determine a repair sequence, etc.) of a system effected by a large-scale failure caused by a natural disaster, malicious attack, faulty components, or the like. In an example, the system can generate a schedule that indicates amounts of repair resources allocated for repair of specific components of a disrupted system as well as a time or sequence in which the components are to be repaired. The schedule, in some instance, can operate to maximize an amount of restoration, at each stage of a recovery process, relative to the characteristic of the disrupted system. For example, with a communications network as the disrupted system, the schedule can maximize the amount of total traffic flow capacity recovered after respective steps of the recovery process.

Claims

1. A method, comprising:

identifying a subset of network links, of a set of network links of a communications network, having reduced capacity due to impairment;

determining a set of resources available, for allocation at a given time, for repair of the subset of network links; and

scheduling the set of resources for the repair of the subset of network links in an order based on a characteristic of the communications network and a recovery condition as a function of the characteristic.

2. The method of claim 1, wherein the scheduling further comprises generating a schedule for allocating resources, from the set of resources, to facilitate repair of network links, from the subset of network links, to recuperate a predetermined capacity of the communications network within a predetermined time period.

3. The method of claim 1, wherein the scheduling further comprises determining a schedule for allocating resources, from the set of resources, to facilitate repair of network links, from the subset of network links to recover a maximal or substantially maximal amount of capacity of the communications network within a predetermined time period.

4. The method of claim 1, wherein the scheduling further comprises:

determining, for a network link of the subset of network links, a repair cost that represents an amount of resources from the set of resources to recuperate a predetermined capacity of the network link;

determining, based on the predetermined capacity of the network link, an amount of total capacity of the communications network regained by recuperating the predetermined capacity of the network link; and

determining, based on the repair cost and the amount of the total capacity regained, a utility gain of the network link representing an amount of capacity recovered per unit of resource.

5. The method of claim 4, wherein the scheduling further comprises assigning higher priority to network links from the subset of network links having a higher utility gain.

6. A system, comprising:

a fault detection module configured to identify a disruption of a computing network, wherein the disruption results in reduced traffic flow capacity for a set of network nodes and a set of network links of the computing network; and

a recovery module configured to generate a repair schedule that specifies an order of allocation of a set of repair resources among the set of network nodes and the set of network links to facilitate progressive recovery of the computing network from the disruption based on a condition relative to a characteristic of the computing network.

7. The system of claim 6, wherein the set of repair resources comprise at least one of manpower, equipment, or parts available at a particular time.

8. The system of claim 6, wherein the condition relative to the characteristic of the computing network specifies a predetermined amount of traffic flow capacity to be recovered within a predetermined time period.

9. The system of claim 6, wherein the condition relative to the characteristic of the computing network specifies a predetermined time period within which a maximum or substantially maximum amount of traffic flow capacity is to be recovered.

10. The system of claim 6, wherein the recovery module is further configured to segment network recovery, as specified in the repair schedule, into a plurality of stages, wherein the repair schedule indicates, for a respective stage, which nodes from the set of network nodes and which links from the set of network links are respectively scheduled for repair, and an amount of resources from the set of repair resources respectively allocated to the nodes and the links scheduled for the repair.

11. The system of claim 10, wherein the recovery module is further configured to select the nodes and the links for the repair during the respective stage and the amount of resources allocated to the nodes and the links in accordance with an optimization condition.

12. The system of claim 11, wherein the optimization condition specifies a maximization of a total traffic flow capacity of the computing network.

13. The system of claim 6, wherein the repair schedule represents an optimum allocation to achieve the condition relative to the characteristic of the communication network.

14. A computer-readable storage medium having stored thereon computer-executable instructions that, in response to execution, cause a computing device to perform operations, comprising:

segmenting a network recovery process for a network into a plurality of stages respectively associated with a respective set of repair resources available for allocation during respective stages of the plurality of stages; and

recursively selecting, for the respective stages, respective network paths from a set of disrupted network paths for repair until the respective set of repair resources available for allocation is exhausted, wherein the recursively selecting the respective network paths comprises identifying the respective network paths from the set of disrupted network paths which, in response to repair of the respective network paths, increase a total weighted traffic flow capacity of the network after respective conclusions of the respective stages.

15. The computer-readable storage medium of claim 14, the operations further comprising:

identifying the set of disrupted network paths based upon a set of designed capacities respectively corresponding to the set of disrupted network paths and a set of measured capacities respectively corresponding to the set of disrupted network paths.

16. The computer-readable storage medium of claim 14, the operations further comprising:

determining the total weighted traffic flow capacity as a function of,

a set of weights assigned to respective network paths of the set of disrupted network paths, wherein respective weights of the set of weights correspond to the respective stages, and

a set of traffic flow capacities assigned to respective network paths, wherein respective traffic flow capacities of the set of traffic flow capacities correspond to the respective stages.

17. The computer-readable storage medium of claim 14, the recursively selecting further comprising:

selecting the respective network paths starting from a first stage, in time, of the plurality of stages and ending with a last stage, in time, of the plurality of stages.

18. The computer-readable storage medium of claim 14, the recursively selecting further comprising:

selecting the respective network paths starting from a last stage, in time, of the plurality of stages and ending with a first stage, in time, of the plurality of stages.

19. The computer-readable storage medium of claim 14, the recursively selecting further comprising:

selecting the respective network paths starting from an intermediate stage, in time, of the plurality of stages to a first stage, in time, of the plurality of stages and from the intermediate stage, in time, of the plurality of stages to a last stage, in time, of the plurality of stages.

20. The computer-readable storage medium of claim 14, wherein the identifying the respective network paths includes identifying the respective network paths that maximally increases the total weighted traffic flow capacity of the network after the respective conclusions of the respective stages.

21. A system, comprising:

means for detecting a set of network paths, of a communications network, suffering reduced traffic flow capacity due to a disruption;

means for determining, for a network path of the set of network paths, an amount of overall traffic flow capacity of the communications network recoverable through repair of the network path and an amount of repair resources implicated by the repair the network path; and

means for identifying a subset of network paths, from the set of network paths, for repair based upon the amount of overall traffic flow capacity recoverable, the amount of repair resources implicated, and an overall amount of repair resources available for allocation including means for increasing a total traffic flow capacity of the communications network in response to the repair of the subset of network paths.

22. The system of claim 21, further comprising means for recursively selecting subsets of network paths, from the set of network paths, over a plurality of stages until a recovery condition is satisfied.

23. A method, comprising:

employing at least one component of at least one computing device to perform operations comprising;

segmenting a network recovery process for a network into a plurality of stages respectively associated with a respective set of repair resources available for allocation during respective stages of the plurality of stages; and

recursively selecting, for the respective stages, respective network paths from a set of disrupted network paths for repair until the respective set of repair resources available for allocation is exhausted, wherein the recursively selecting the respective network paths comprises identifying the respective network paths from the set of disrupted network paths and, in response to the repair of the respective network paths, increasing a total weighted traffic flow capacity of the network after respective conclusions of the respective stages.

24. The method of claim 23, the operations further comprising determining the set of disrupted network paths based on a set of predicted capacities respectively corresponding to the respective network paths of the set of disrupted network paths and a set of actual capacities respectively corresponding to the respective network paths of the set of disrupted network paths.

25. The method of claim 23, further comprising:

receiving a set of weights associated with respective network paths of the set of disrupted network paths, wherein respective weights of the set of weights correspond to the respective stages of the plurality of stages, and

determining a set of traffic flow capacities associated with the respective network paths, wherein respective traffic flow capacities of the set of traffic flow capacities correspond to the respective stages of the plurality of stages.

26. The method of claim 25, further comprising determining the total weighted traffic flow capacity of the network as a function of the set of weights associated with the respective network paths and the set of traffic flow capacities associated with the respective network paths.

27. The method of claim 23, further comprising determining a predetermined number of stages, wherein the recursively selecting of the network paths further comprises identifying the respective network paths from the set of disrupted network paths for repair over the predetermined number of stages and maximizing the total weighted traffic flow capacity of the network.

28. The method of claim 23, further comprising determining a predetermined overall traffic flow capacity, wherein the recursively selecting further comprises identifying the respective network paths from the set of disrupted network paths for repair over a minimized number of stages to reach the predetermined overall traffic flow capacity.