Determining connectivity in a failed network

Patent metadata

Field	Value
Publication number	US-9065743-B2
Application number	US-64702609-A
Country	US
Kind code	B2
Filing date	Dec 24, 2009
Priority date	Dec 24, 2009
Publication date	Jun 23, 2015
Grant date	Jun 23, 2015

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.

First claim

The invention claimed is:

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.

Assignees

• Bakshi Yury
• Johnson Carolyn Roche
• Shulman Herbert B
• At & T Ip I Lp

Inventors

• Bakshi Yury
• Johnson Carolyn Roche
• Shulman Herbert B

Classifications

• H04L45/03

  by updating link state protocols · CPC title

• H04L45/04 Primary

  Interdomain routing, e.g. hierarchical routing · CPC title

• H04L45/02

  Topology update or discovery · CPC title

• H04L45/46

  Cluster building · CPC title

• H04L41/12 Primary

  Discovery or management of network topologies · CPC title