Determining Connectivity in a Failed Network

• US 20110158083A1
• Filed: 12/24/2009
• Published: 06/30/2011
• Est. Priority Date: 12/24/2009
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Shulman, Herbert B., Bakshi, Yury, Johnson, Carolyn Roche
• Granted Patent: US 9,065,743 B2
• Time in Patent Office: Days
• US Class Current: 370/225
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/46 Cluster building

Abstract

The disclosed technology, in one embodiment, involves a method that improves the execution speed of graph algorithms that are commonly used by network service providers for network analysis and/or design. The disclosed technology can be use to provide significant efficiency improvements when applied to networks that are separated into several isolated fragments (“fragmented networks”) due to severe damage that may be caused by either natural disaster (such as hurricanes or earthquakes), or planned adversary attacks. In one embodiment of the disclosed technology, a graph algorithm, that is used to determine a characteristic of the network, is not applied directly to the whole network/graph. Instead, the graph algorithm is applied to isolated network/graph fragments that are identified, for example, by using a fragment discovery algorithm. The graph algorithm is then applied to one or more relevant fragments. The results may be combined to obtain a network wide result.

Claims

1. A method for determining a characteristic of selected network elements, the method comprising:

determining a plurality of all subnetwork fragments that include the selected network elements; and

determining the characteristic for each of the plurality of subnetwork fragments.

2. The method of claim 1 further comprising;

combining the characteristics determined for the plurality of subnetwork fragments to obtain a network result.

3. The method of claim 2 wherein the characteristic is the connectivity distance between two network nodes.

4. The method of claim 2 wherein the characteristic is the shortest path between two network nodes.

5. The method of claim 4 further comprising:

connecting two network nodes of a first fragmented network, using the determined shortest path, upon a failure of the network that results in a plurality of fragmented networks, one of which fragmented networks is the first fragmented network.

6. The method of claim 4 wherein the shortest path is determined using the Dijkstra All-Pairs Shortest Path Algorithm or the Dijkstra Single-Source Shortest Path Algorithm.

7. The method of claim 1 wherein:

the graph algorithm requires O(V²) or longer to complete, where V is the number of network nodes/graph vertices; and

the results obtained by applying the graph algorithm to each isolated network fragment separately are combined together to obtain the overall network result.

8. A computer readable storage medium encoded with computer executable instructions which, when executed by a computer, implements the operation of:

determining a plurality of all subnetwork fragments that include selected elements; and

determining a characteristic for each of the plurality of subnetwork fragments.

9. The medium of claim 8 wherein the operation further comprises;

combining the characteristics determined for the plurality of subnetwork fragments to obtain a network result.

10. The medium of claim 9 wherein the characteristic is the connectivity distance between two network nodes.

11. The medium of claim 9 wherein the characteristic is the shortest path between two network nodes.

12. The medium of claim 11 wherein the operation further comprises;

connecting two network nodes of a first fragmented network, using the determined shortest path, upon a failure of the network that results in a plurality of fragmented networks, one of which fragmented networks is the first fragmented network.

13. The medium of claim 11 wherein the shortest path is determined using the Dijkstra All-Pairs Shortest Path Algorithm or the Dijkstra Single-Source Shortest Path Algorithm.

14. The medium of claim 8 wherein:

the graph algorithm requires O(V²) or longer to complete, where V is the number of network nodes/graph vertices; and

the results obtained by applying the graph algorithm to each isolated network fragment separately are combined together to obtain the overall network result.

15. A computer readable storage medium encoded with computer executable instructions which, when executed by a computer, implements the operation of determining the connectivity-distance between a first node and a second node in a network, the instructions comprising:

determining a plurality of all subnetwork fragments that include the first and second node; and

determining the connectivity-distance between the first and second network nodes for each of the plurality of subnetwork fragments.

16. The medium of claim 15, the instructions further comprising:

combining the connectivity-distances determined for the plurality of subnetwork fragments to obtain a network result.

19. The medium of claim 18, wherein the connectivity-distances are the shortest paths between the first and second network nodes.

20. The medium of claim 19, wherein the shortest paths are determined using the Dijkstra All-Pairs Shortest Path Algorithm or the Dijkstra Single-Source Shortest Path Algorithm.