With the frequent occurrences of natural disasters and the rising risk of malicious attacks, improving network survivability and guaranteeing connectivity in the presence of large-scale failures have emerged as a critical research challenge. Traditional studies on improving edge/node connectivity assume that failures occur at random and fail to capture the locality of large-scale failures. Although studies on region-based connectivity can address this limitation, they fail to consider how local failures affect the communication between certain key source-destination (SD) pairs. In this paper, we first extend the definition of region-based connectivity to include SD pairs. Given ℓ failure regions andkSD pairs, we study the problem of shielding edges with minimum cost to improve region-based connectivity between thekSD pairs. Second, we systematically analyze the computational complexity of the problem under different settings of ℓ,kand topologies of failure regions. Third, we design an ILP-based formulation to solve the general problem and propose two polynomial-time algorithms for two special cases based on the matroid technique and the biconnected component decomposition, respectively. Experimental results show that our algorithms are much faster than previously known algorithms.

Network protection has drawn a certain interest in network optimization. One of the most effective and widely used methods to protect networks from failures is to establish backup paths for working paths. For example, we find${k}$node-disjoint paths between a source and a sink with one working path and${k}\,\,-$1 backup paths. However, the demand for full protection of a network is somewhat too restrictive and there may not exist${k}$node-disjoint paths in the network due to the limitation of geographical environments. On the other hand, the occurrence probability of node failures is usually much less than that of link failures in real-world models. To save network resources, we turn to establish link-disjoint paths allowing a few shared nodes. We study the problem of finding${k}$link-disjoint paths between a source and a sink under the constraint that the number of nodes shared by at least${r}$paths is at most$\delta $, minimizing the total link weight. First, we systematically study the computational complexity of the problem with respect to three parameters${k}$,${r}$, and$\delta $. Then, we build an integer linear programming for the general model and design a polynomial-time algorithm for the case that${k}\,\,=\,\,{r}$by using the techniques of augmenting paths and splitting nodes. Finally, we carry out experimentations on synthetic and real networks that show the effectiveness of our algorithms in practice.

As networks and their inter-connectivity grow and become complex, failures in the networks impact society and industries more than ever. In these networks the notion of connectedness is the key to understanding and reasoning about these failures. Traditional studies in improving edge/node connectivity assume that failures occur at random. However, in many scenarios (such as earthquakes, hurricanes, and human-designed attacks on networks) failures are not random, and most traditional methods do not always work. To address this limitation, we consider region-based connectivity to capture the local nature of failures under the geographical failure model, where failures may happen only on edges in a sub-network (region) and we want to shield some edges in regions to protect the connectivity. There may be several regions and in different regions the failures occur independently. Firstly, we establish the NP-hardness of the problem for regions, answering a question proposed in previous papers. Secondly, we propose a polynomial-time algorithm for the special case of two regions based on the matroid techniques. Furthermore, we design an ILP-based algorithm to solve the problem for regions. Experimental results on random and real networks show that our algorithms are much faster than previously known algorithms.

Network survivability has drawn certain interest in network optimization. However, the demand for full protection of a network is usually too restrictive. To overcome the limitation of geographical environments and to save network resources, we turn to establish backup networks allowing a few common nodes. It comes out the problem of finding k link-disjoint paths between a given pair of source and sink in a network such that the number of common nodes shared by at least two paths is bounded by a constant and the total link weight of all paths is minimized under the above constraints. For the case k = 2, where we have only one backup path, several fast algorithms have been developed in the literature. For the case k > 2, little results are known. In this paper, we first establish the NP-hardness of the problem with general k. Motivated by the situation that each node in a network may have a capability of multicasting, we also study a restricted version with one more requirement that each node can be shared by at most two paths. For the restricted version, we build an ILP model and design a fast algorithm by using the techniques of augmenting paths and splitting nodes. Furthermore, experimental results on synthetic and real networks show that our algorithm is effective in practice.