Top NSA Banner

Aliases:

None

Technical Challenge:

To disclose a computationally efficient method of finding links and, possibly, nodes, that cost the least to eliminate in order to isolate two user-selected nodes from each other.

Description:

A set of links or nodes to be removed from a graph to isolate one node from another node is often referred to as a cutset. This method identifies in a computationally efficient manner, all minimum-cost cutset in a network to isolate one node in the network from another node. The network is any suitable network such as a computer network, a telephone network, an infrastructure network, an integrated-circuit interconnection network, and so on.

This method employs a cost-saving process to isolate two user nodes from each other in a given network, consisting of nodes and links. It replaces bi-direction links with parallel uni-direction links that have been assigned cost. The cost assigned to each node or link is the cost of eliminating, or cutting, that node or link from the network. Network Analyzer is an automated information systems capability of identifying all choke points in an arbitrary network topology. Applications of this technology include communications network reliability, power grid vulnerabilities, information operations and event-based risk analysis modeling. Network Analyzer provides a high-level real-time automated analysis capability for network topologies containing thousands of nodes and links, problem sizes that were previously deemed prohibitive to solve with current technology.

Demonstration Capability:

There is no way of demonstrating capability.

Potential Commercial Application(s):

Any application there use a network infrastructure.

Patent Status:

A Patent Application is on file at the United States Patent and Trademark Office.

Reference Number: 1139

If you are interested in exploring this technology further, please call 443-445-7159 or express your interest in writing to the:

National Security Agency
NSA Technology Transfer Program
9800 Savage Road, Suite 6541
Fort George G. Meade, Maryland 20755-6541