Increasing Resilience of a Network Service

• US 20100332991A1
• Filed: 06/29/2009
• Published: 12/30/2010
• Est. Priority Date: 06/29/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Banerjee, Dipyaman, Madduri, Venkateswara R., Srivatsa, Mudhakar
• Granted Patent: US 8,869,035 B2
• Time in Patent Office: Days
• US Class Current: 715/736
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route

Abstract

A set of data is obtained, representing a graph of a computer network having a set of hardware nodes and a set of hardware links between the hardware nodes. The hardware links are represented as edges in the graph. A first subset (for example, a vertex cut set) of the set of hardware nodes is found, such that those of the hardware nodes in the first subset are able to withstand a maximum number of failures before the graph disconnects. The failures include node failures and/or edge failures. The hardware nodes in the first subset are ranked based on expected resiliency, to obtain a ranked list. Optionally, in case of a tie between two or more of the hardware nodes in the ranked list, the tie is broken using a sum of shortest path metric.

Claims

1. A method comprising:

obtaining a set of data representing a graph of a computer network having a set of hardware nodes and a set of hardware links between the hardware nodes, the hardware links being represented as edges in the graph;

finding a first subset of the set of hardware nodes, such that those of the hardware nodes in the first subset are able to withstand a maximum number of failures before the graph disconnects, the failures comprising at least one of node failures and edge failures; and

ranking the hardware nodes in the first subset based on expected resiliency, to obtain a ranked list.

2. The method of claim 1, further comprising, in case of a tie between two or more of the hardware nodes in the ranked list, breaking the tie with a sum of shortest path metric.

3. The method of claim 2, further comprising storing the ranked list in a tangible computer-readable recordable storage medium.

4. The method of claim 2, further comprising displaying the ranked list to a human subject on a display device.

5. The method of claim 2, further comprising physically locating a network service on a preferred one of the hardware nodes from the ranked list by loading hardware processor-executable program code, embodying the network service, onto a tangible computer-readable recordable storage medium associated with the preferred hardware node.

6. The method of claim 5, wherein:

the step of finding the first subset comprises finding a vertex cut-set of the hardware nodes represented by the graph; and

the step of ranking the hardware nodes in the first subset comprises;

using Menger'"'"'s theorem to transform the graph and find edge and vertex independent paths from each hardware node in the first subset to all other hardware nodes;

estimating a failure probability of each of the edges and each of the vertices;

weighting each of the edge and vertex independent paths with the estimated failure probability of the vertex and the edges present in the particular one of the independent paths; and

employing a tournament method to rank the hardware nodes in the vertex cut set, based upon the weighting step.

7. The method of claim 5, wherein the service comprises a network-monitoring service for monitoring the network.

8. The method of claim 7, wherein the network-monitoring service functions by periodically polling all of the hardware nodes in the network, other than the preferred hardware node on which the monitoring service is located, to obtain status, and wherein the preferred hardware node is selected to maximize resiliency of the monitoring service to the node failures and the edge failures.

9. The method of claim 8, wherein the preferred hardware node is selected based upon assuming that all of the hardware nodes and all of the edges representing the hardware links are equally likely to fail.

10. The method of claim 2, wherein the ranked list is ranked based on expected resiliency to be obtained by locating a network service on each given hardware node in the ranked list.

11. The method of claim 2, further comprising providing a system, wherein the system comprises distinct software modules, each of the distinct software modules being embodied on a tangible computer-readable recordable storage medium, and wherein the distinct software modules comprise a vertex cut finder module, an edge independent path finder module, a path weighting engine module, a network fault probability estimation engine module, a tournament method based resiliency ranking engine module, and a network distance based tie breaker engine module;

wherein;

the finding of the first subset of the set of hardware nodes is carried out by the vertex cut finder module, implemented on at least one hardware processor;

the ranking of the hardware nodes in the first subset based on the expected resiliency is carried out by the edge independent path finder module, the path weighting engine module, the network fault probability estimation engine module, and the tournament method based resiliency ranking engine module, implemented on the at least one hardware processor; and

the breaking of the tie is carried out by the network distance based tie breaker engine module, implemented on the at least one hardware processor.

12. A computer program product comprising a tangible computer readable recordable storage medium including computer usable program code, the computer program product including:

computer usable program code for obtaining a set of data representing a graph of a computer network having a set of hardware nodes and a set of hardware links between the hardware nodes, the hardware links being represented as edges in the graph;

computer usable program code for finding a first subset of the set of hardware nodes, such that those of the hardware nodes in the first subset are able to withstand a maximum number of failures before the graph disconnects, the failures comprising at least one of node failures and edge failures; and

computer usable program code for ranking the hardware nodes in the first subset based on expected resiliency, to obtain a ranked list.

13. The computer program product of claim 12, further comprising computer usable program code for, in case of a tie between two or more of the hardware nodes in the ranked list, breaking the tie with a sum of shortest path metric.

14. The computer program product of claim 13, wherein:

the computer usable program code for finding the first subset comprises computer usable program code for finding a vertex cut-set of the hardware nodes represented by the graph; and

the computer usable program code for ranking the hardware nodes in the first subset comprises;

computer usable program code for using Menger'"'"'s theorem to transform the graph and find edge and vertex independent paths from each hardware node in the first subset to all other hardware nodes;

computer usable program code for estimating a failure probability of each of the edges and each of the vertices;

computer usable program code for weighting each of the edge and vertex independent paths with the estimated failure probability of the vertex and the edges present in the particular one of the independent paths; and

computer usable program code for employing a tournament method to rank the hardware nodes in the vertex cut set, based upon the weighting step.

15. The computer program product of claim 13, further comprising distinct software modules, each of the distinct software modules being embodied on the tangible computer-readable recordable storage medium, the distinct software modules comprising a vertex cut finder module, an edge independent path finder module, a path weighting engine module, a network fault probability estimation engine module, a tournament method based resiliency ranking engine module, and a network distance based tie breaker engine module;

wherein;

the vertex cut finder module comprises the computer usable program code for finding of the first subset of the set of hardware;

the edge independent path finder module, the path weighting engine module, the network fault probability estimation engine module, and the tournament method based resiliency ranking engine module comprise the computer usable program code for the ranking of the hardware nodes in the first subset based on the expected resiliency; and

the network distance based tie breaker engine module comprises the computer usable program code for the breaking of the tie.

16. An apparatus comprising:

a memory; and

at least one processor, coupled to the memory, and operative to;

obtain a set of data representing a graph of a computer network having a set of hardware nodes and a set of hardware links between the hardware nodes, the hardware links being represented as edges in the graph;

find a first subset of the set of hardware nodes, such that those of the hardware nodes in the first subset are able to withstand a maximum number of failures before the graph disconnects, the failures comprising at least one of node failures and edge failures; and

rank the hardware nodes in the first subset based on expected resiliency, to obtain a ranked list.

17. The apparatus of claim 16, wherein the at least one processor is further operative, in case of a tie between two or more of the hardware nodes in the ranked list, to break the tie with a sum of shortest path metric.

18. The apparatus of claim 17, wherein the at least one processor is operative to:

find the first subset by finding a vertex cut-set of the hardware nodes represented by the graph; and

rank the hardware nodes in the first subset by;

using Menger'"'"'s theorem to transform the graph and find edge and vertex independent paths from each hardware node in the first subset to all other hardware nodes;

estimating a failure probability of each of the edges and each of the vertices;

weighting each of the edge and vertex independent paths with the estimated failure probability of the vertex and the edges present in the particular one of the independent paths; and

employing a tournament method to rank the hardware nodes in the vertex cut set, based upon the weighting step.

19. The apparatus of claim 17, further comprising a tangible computer-readable recordable storage medium having distinct software modules embodied thereon, wherein the distinct software modules comprise a vertex cut finder module, an edge independent path finder module, a path weighting engine module, a network fault probability estimation engine module, a tournament method based resiliency ranking engine module, and a network distance based tie breaker engine module;

wherein;

the finding of the first subset of the set of hardware nodes is carried out by the vertex cut finder module, implemented on the at least one processor;

the ranking of the hardware nodes in the first subset based on the expected resiliency is carried out by the edge independent path finder module, the path weighting engine module, the network fault probability estimation engine module, and the tournament method based resiliency ranking engine module, implemented on the at least one processor; and

the breaking of the tie is carried out by the network distance based tie breaker engine module, implemented on the at least one processor.

20. An apparatus comprising:

means for obtaining a set of data representing a graph of a computer network having a set of hardware nodes and a set of hardware links between the hardware nodes, the hardware links being represented as edges in the graph;

means for finding a first subset of the set of hardware nodes, such that those of the hardware nodes in the first subset are able to withstand a maximum number of failures before the graph disconnects, the failures comprising at least one of node failures and edge failures; and

means for ranking the hardware nodes in the first subset based on expected resiliency, to obtain a ranked list.