Disaster-Resilient Network Upgrade

The manifold impacts of the current pandemic have highlighted the importance of reliable communication networks and services. As more and more people and services rely on this critical infrastructure, single link failure resilience is not sufficient anymore; networks must be disaster resilient. In this paper, we analyze the effects of disasters from a connectivity perspective and focus on reducing the likelihood of network disconnection in the event of a disaster through targeted link upgrades. In particular, we formalize the generalized Minimum Cost Disaster Resilient Network Upgrade Problem (DNP) (based on the previously published eFRADIR framework). We prove that this problem is NP-hard and as hard to approximate as the Knapsack Problem (KP). We present several methods for solving the DNP, in particular an ILP and two heuristics. We evaluate their performance on real networks and earthquake data and show that the upgrade cost of our disconnection probability based heuristic is only 3.5% higher than the optimum, while its resource consumption is negligible compared to the ILP.