Determining connectivity in a failed network

• US 9,065,743 B2
• Filed: 12/24/2009
• Issued: 06/23/2015
• Est. Priority Date: 12/24/2009
• Status: Expired due to Fees

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Bakshi, Yury, Johnson, Carolyn Roche, Shulman, Herbert B.
• Primary Examiner(s): Thier, Michael
• Assistant Examiner(s): MYERS, ERIC A
• Application Number:
  US12/647,026
• Publication Number:
  US 20110158083A1
• Time in Patent Office: 2,007 Days
• Field of Search: 370/225, 370/229, 370/252, 370/254, 370/230, 370/235, 370/237, 370/238, 370/256, 370/257, 370/379, 370/382, 370/389, 370/437, 370/462, 709/217, 709/223, 709/224, 709/238, 709/241
• US Class Current: 1/1
• 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 used 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, comprising:

executing, by a processor, an algorithm that discovers failed network fragments in a network, each one of the failed network fragments having no connectivity path to any other failed network fragment;

determining, by the processor, a shortest path between nodes in the network;

assigning, by the processor, an infinite length between two nodes in different ones of the failed network fragments;

applying, by the processor, a graphing algorithm, after discovery, to each one of the failed network fragments discovered by the algorithm;

generating, by the processor, a result of the graphing algorithm for each one of the failed network fragments;

combining, by the processor, results of the graphing algorithm for all the failed network fragments; and

assigning, by the processor, a combined result to the network.

2. The method of claim 1, further comprising determining a connectivity distance between two network nodes in the network.

3. A non-transitory computer readable storage medium encoded with computer executable instructions which, when executed by a computer, implement the operations of:

executing an algorithm that discovers failed network fragments in a network, each one of the failed network fragments having no connectivity path to any other failed network fragment;

determining a shortest path between nodes in the network;

assigning an infinite length between two nodes in different ones of the failed network fragments;

applying a graphing algorithm, after discovery, to each one of the failed network fragments discovered by the algorithm;

generating a result of the graphing algorithm for each one of the failed network fragments;

combining results of the graphing algorithm for all the failed network fragments; and

assigning a combined result to the network.

4. A system, comprising:

a processor; and

a memory storing code that when executed causes the processor to perform operations, the operations comprising;

executing an algorithm that discovers failed network fragments in a network, each one of the failed network fragments having no connectivity path to any other failed network fragment;

identifying a pair of nodes in different ones of the failed network fragments;

determining a shortest path between two nodes in the network;

assigning an infinite length to the shortest path in response to the two nodes located in different ones of the failed network fragments;

applying a graphing algorithm to each one of the failed network fragments discovered by the algorithm;

generating a result of the graphing algorithm for each one of the failed network fragments;

combining results of the graphing algorithm for all the failed network fragments; and

assigning a combined result to the network.