System and method for providing network resiliency
First Claim
Patent Images
1. A method for providing resiliency in a network comprising:
- identifying a network topology including a plurality of nodes and links, each link connecting two nodes;
receiving criteria for preferred routes through the network between a source node and a destination node, the criteria including a number of diverse paths connecting the source node and the destination node, a path diversity criteria, and an optimization parameter for use in ranking paths;
finding paths through the network using a compass direction by;
locating a path in the network from the source node to the destination node by;
beginning at the source node, following a link most closely aligned with the selected compass direction from the source node to a next node,extending the path from the next node by following a link most closely aligned with the selected compass direction to another node, andrepeating the extending step until the path reaches the destination node;
repeating the locating step, while omitting links that are part of a previously located path, to determine additional diverse paths from the source node to the destination node;
applying the optimization parameter to rank the located paths to identify a primary path and one or more backup paths for the selected compass direction;
repeating the finding step for each compass direction;
for each compass direction that found the number of diverse paths specified by the route criteria, applying the optimization parameter to rank the primary paths to determine one or more optimal paths from the source node to the destination node; and
outputting the one or more optimal paths as the preferred route.
1 Assignment
0 Petitions
Accused Products
Abstract
The invention is directed toward an automated system and process to provide resiliency to a network infrastructure where traditional established methods tend to fail. The system analyzes the underlying physical characteristics of the network topology to identify physically diverse backup routing paths among nodes in the network. The system takes as input the number of diverse paths desired and a characteristic(s) used to choose the most desirable paths, such as delay, flow, or cost. The invention searches for multiple solutions for the selected number of diverse paths within the network.
21 Citations
18 Claims
-
1. A method for providing resiliency in a network comprising:
-
identifying a network topology including a plurality of nodes and links, each link connecting two nodes; receiving criteria for preferred routes through the network between a source node and a destination node, the criteria including a number of diverse paths connecting the source node and the destination node, a path diversity criteria, and an optimization parameter for use in ranking paths; finding paths through the network using a compass direction by; locating a path in the network from the source node to the destination node by; beginning at the source node, following a link most closely aligned with the selected compass direction from the source node to a next node, extending the path from the next node by following a link most closely aligned with the selected compass direction to another node, and repeating the extending step until the path reaches the destination node; repeating the locating step, while omitting links that are part of a previously located path, to determine additional diverse paths from the source node to the destination node; applying the optimization parameter to rank the located paths to identify a primary path and one or more backup paths for the selected compass direction; repeating the finding step for each compass direction; for each compass direction that found the number of diverse paths specified by the route criteria, applying the optimization parameter to rank the primary paths to determine one or more optimal paths from the source node to the destination node; and outputting the one or more optimal paths as the preferred route. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A method for providing resiliency in a network comprising:
-
identifying a network topology including a plurality of nodes and links, each link connecting two nodes; receiving criteria for preferred routes through the network between a source node and a destination node; finding paths in a selected compass direction by; locating a path in the network from the source node to the destination node by forcing the path in the selected compass direction, repeating the locating step as long as it is possible to determine additional diverse paths from the source node to the destination node while omitting any link that is part of a previously located path, and ranking the located paths according to the criteria to identify a primary path and one or more backup paths in the selected compass direction; repeating the finding step for each compass direction; ranking the primary path of each compass direction to determine the optimal compass direction; and selecting the paths corresponding to the optimal compass direction as the preferred routes through the network. - View Dependent Claims (7, 8, 9, 10, 11)
-
-
12. A computer system for providing resiliency in a network comprising:
-
an input device for receiving a network topology including a plurality of nodes and links, each link connecting two nodes, and for receiving criteria for finding routes through the network between a source node and a destination node; a network path processor for finding paths in a direction by; locating a path in the network from the source node to the destination node by forcing the path in the selected direction, and repeating the locating step while it is possible to determine additional diverse paths from the source node to the destination node, without using any link that is part of a previously located path; the network path processor repeating the finding step for a least one other direction; an output device for outputting the paths associated with each direction as the found routes. - View Dependent Claims (13, 14, 15, 16, 17, 18)
-
Specification