Increasing resilience of a network service

摘要

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.

主权项

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; wherein said expected resiliency is computed via E[Rm(v)]=Σfε2E P(f)N(v, f), wherein:
E represents a set of edges among the first subset of hardware nodes f;P(f) represents a probability of all edges associated with the first subset f failing together;Rm(v) represents a resiliency measure of a service deployed at a given node v; andN(v, f) represents the number of nodes that can be reached from the given node v if all edges in the first subset f fail together; and wherein said ranking comprises:identifying edge and vertex independent paths from each hardware node in the first subset to all other hardware nodes;weighting each of the edge and vertex independent paths with the estimated failure probability of the vertex and the edges in each independent path; andranking the hardware nodes in the first subset based on the weighted edge and vertex independent paths to represent expected resiliency of each hardware node by determining the number of edge and vertex independent paths derived from each hardware node and the estimated probability that each of said paths will fail.