System and Method for Providing Network Resiliency

• US 20110228702A1
• Filed: 05/26/2011
• Published: 09/22/2011
• Est. Priority Date: 08/26/2009
• Status: Active Grant

• Current Assignee: Noblis, Inc.
• Original Assignee: Noblis, Inc.
• Inventors: Knepley, Joseph E. JR., Garbin, David Anthony
• Granted Patent: US 8,472,347 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 45/126 minimising geographical or physical path length

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.

Claims

1-18. -18. (canceled)

19. 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.

20. The method of claim 19, wherein the path diversity criteria is link diversity, such that each located path cannot share any links.

21. The method of claim 19, wherein the path diversity criteria is link-and-node diversity, such that each located path cannot share any node or link, and, wherein nodes that are part of a previously located path are further omitted when the locating step is repeated.

22. The method of claim 19, wherein the optimization criteria is at least one of distance, cost, availability, bandwidth, throughput, capacity, delay, and speed.

23. The method of claim 19, wherein the compass directions are north, south, east, and west.

24. 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.

25. The method of claim 24, wherein the criteria includes at least one of availability, cost, distance, speed, throughput, bandwidth, capacity, and delay.

26. The method of claim 24, wherein the criteria includes a number of diverse paths connecting the source node and the destination node.

27. The method of claim 24, wherein the criteria includes a path diversity criteria.

28. The method of claim 27, wherein the path diversity criteria is link diversity, such that each determined path cannot share any links.

29. The method of claim 27, wherein the path diversity criteria is link-and-node diversity, such that each determined path cannot share any node or link, and, wherein nodes that are part of a previously located path are further omitted when the locating step is repeated.

30. 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.

31. The system of claim 30, wherein the route criteria includes at least one of availability, cost, distance, speed, throughput, bandwidth, capacity, and delay.

32. The system of claim 30, wherein the network path processor further applies the route criteria to rank the paths associated with each direction.

33. The system of claim 30, wherein the route criteria includes a number of diverse paths connecting the source node and the destination node.

34. The system of claim 30, wherein the finding further comprises:

ranking the located paths using the route criteria to identify a primary path and one or more backup paths for the selected direction.

35. The system of claim 30, wherein the route criteria specifies link diversity, such that each determined path cannot share any links.

36. The system of claim 30, wherein the route criteria specifies link-and-node diversity, such that each determined path cannot share a node or link, and wherein nodes that are part of a previously located path are further omitted when locating is repeated.