Network disaster recovery and analysis tool

• US 6,496,941 B1
• Filed: 05/21/1999
• Issued: 12/17/2002
• Est. Priority Date: 12/29/1998
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Segal, Moshe, Eisenberg, Martin
• Primary Examiner(s): BADERMAN, SCOTT T
• Application Number:
  US09/316,497
• Time in Patent Office: 1,306 Days
• Field of Search: 714/4, 709/235, 709/223, 709/229, 709/102, 709/239
• US Class Current: 714/4.2
• CPC Class Codes: H04L 2012/5627 Fault tolerance and recovery
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• 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 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

An embodiment of the system and method of the present invention organizes the recovery of a communications network to minimize the interference between the recovering nodes and thus allows for a faster recovery. A metered rate is calculated at which nodes recover from a major network failure; when nodes recover at the metered rate, the network recovers quickly but without performance degrading interference. A measure of the interference between recovering nodes may be created; the interference measure may be used to partition the network, where the nodes within each partition set interfere minimally with each other during recovery and each set recovers separately. Recovering items (nodes or sets) may be sequenced so that each item recovers substantially separately in time, but where adjacent sequence items recover with some temporal overlap. Alternate embodiments may organize any system of items such as objects or devices competing for resources to minimize interference; a metered rate or measure of interference may be created, and the items may be partitioned and sequenced.

Claims

1. A method for recovering from a failure in a network, where the network comprises a set of nodes, the method comprising:

creating recovery sets of nodes by minimizing a measure of the interference among nodes within each recovery set;

assigning to each recovery set a recovery start time; and

requiring that the nodes of each recovery set start their recovery process at a time not prior to the recovery start time for their respective recovery set.

2. The method of claim 1 where the recovery sets are created by at least the substeps of:

placing each node into a set; and

combining the sets into larger sets, by performing one or more times the step of creating a set of larger sets, where the nodes in a pair of sets are placed in a larger set so that the nodes in the larger set interfere minimally with each other and so that the interference between nodes in each other larger set being created is minimized.

3. The method of claim 2 further comprising:

creating a recovery set sequence of the plurality of recovery sets such that, for the nodes of any given recovery set in the recovery set sequence, the recovery of the nodes of the subsequent recovery set in the sequence, if any, interfere minimally with the recovery of the nodes of the given recovery set.

4. The method of claim 3 further comprising:

creating, for each recovery set in the sequence, a sequence offset, each sequence offset being an estimated amount of time for the associated recovery set to perform a certain percentage of its recovery.

5. The method of claim 2 where the measure of the interference between each pair of nodes in the network is determined as a function of the number of times a first node in the pair and a second node in the pair require access to the same node during recovery.

6. The method of claim 3 where in order to recover each node must communicate with a plurality of via nodes, the method further comprising:

calculating an optimum delay period and requiring each node to recover its paths by, after recovering a first path, waiting the optimum delay period before attempting to recover a second path.

7. The method of claim 6 where each recovery set includes only nodes affected by a network failure.

8. The method of claim 6 where each node has a set of paths, each node includes at least a processor, each processor having an occupancy, and the delay period is calculated as a function of:

a measure of the average processor occupancy per node;

an average length for each path in the network; and

an average processor resource consumption per reroute attempt.

9. The method of claim 1 where in order to recover each node must communicate with a plurality of via nodes, the method further comprising:

calculating an optimum delay period and requiring each node to recover its paths by, after failing to recover a path, waiting the optimum delay period before reattempting to recover a path.

10. A network carrying traffic, comprising:

a plurality of nodes, each node owning a set of paths, each path comprising a set of via nodes; and

a plurality of recovery sets of nodes of the network, such that the nodes of each recovery set interfere minimally with the recovery of each other, where the nodes in each recovery set start their recovery operations at substantially the same time, and where the nodes in each recovery set start their recovery operations at a substantially different time from the nodes of any other recovery set.

11. The network of claim 10, further comprising:

an interference data structure containing, for each pair of nodes in the network, a measure of recovery interference between the pair of nodes.

12. The network of claim 11 further comprising:

a recovery set sequence of the plurality of recovery sets such that, for the nodes of any given recovery set in the recovery set sequence, the recovery of the nodes of the subsequent recovery set in the sequence, if any, interfere minimally with the recovery of the nodes of the given recovery set.

13. The network of claim 12 where:

each node recovers by attempting to communicate with nodes acting as via nodes; and

the measure of recovery interference for each pair of nodes is created by summing, for each via node, a measure of the interference between a first node in the pair and a second node in the pair which results from the first node and the second node competing for access to the via node.

14. A method for calculating the measure of interference between objects in each pairwise combination of objects in a set of objects, the interference being created by the objects'"'"' competing for access to resources in a set of resources, the method comprising:

for each pairwise combination from the set of objects, producing a sum, by summing, for each resource in the set of resources, a measure of the interference between a first object in the pairwise combination and a second object in the pairwise combination which results from the first object and the second object competing for access for the resource.

15. The method of claim 14 where the measure of the interference is determined from the number of times the first object and the second object require access to the resource.

16. The method of claim 15 where the measure of the interference is determined by summing the number of times the first object and the second object require access to the resource.

17. The method of claim 15 where the measure of the interference is determined by multiplying the number of times the first object and the second object require access to the resource.

18. The method of claim 16 where:

the objects are a set of nodes in a network;

the network includes paths;

the resources are a set of nodes in the network; and

the objects require access to the resources to recover paths.

19. The method of claim 17 where:

the objects are a set of nodes in a network;

the network includes paths;

the resources are a set of nodes in the network; and

the objects require access to the resources to recover paths.

20. The method of claim 15 further comprising:

partitioning the set of objects into a plurality of partition sets of objects, the objects in each partition set having a minimal measure of interference with the other objects in the partition set.

21. The method of claim 20 where the measure of the interference is determined by multiplying the number of times the first object and the second object require access to the resource, the objects are a set of nodes in a network and the resources are a set of nodes in the network, and where the objects undertake recovery processes, the method further comprising:

assigning to each partition set a recovery start time; and

requiring that the objects of each partition set start their recovery processes at a time not prior to the recovery start time for that partition set.

22. The method of claim 20 where the measure of the interference is determined by adding the number of times the first object and the second object require access to the resource, the objects are a set of nodes in a network and the resources are a set of nodes in the network, and where the objects undertake recovery processes, the method further comprising:

assigning to each partition set a recovery start time; and

requiring that the objects of each partition set start their recovery processes at a time not prior to the recovery start time for that partition set.

23. The method of claim 20 further comprising:

creating an at least one partition set sequence of the partition sets such that each partition set in the at least one partition set sequence interferes minimally with the recovery of the subsequent partition set in the at least one partition set.

24. A method for setting a timing limit on the activities of a set of objects performing activities to minimize interference among objects, the method comprising:

determining, from the characteristics of the set of objects, an optimum rate wherein the objects are nodes in a network;

creating recovery sets of nodes by minimizing a measure of the interference among nodes within each recovery set;

assigning to each recovery set a recovery start time; and

requiring that the nodes of each recovery set start their recovery process at a time not prior to the recovery start time for their respective recovery set so that each object performs its activities at the optimum rate.

25. The method of claim 24 where the characteristics include at least an average amount of time it takes for each object to perform a unit of activity.

26. The method of claim 24 where the objects are nodes in a network, the network includes a plurality of paths, and the activities are attempts to reroute paths in the network.

27. The method of claim 26 where each node includes at least a processor, each processor having an occupancy, and where the characteristics include at least:

a measure of the average processor occupancy per node;

an average length for each path in the network; and

an average processor resource consumption per reroute attempt.