Availability-Aware Routing in Presence of Geographically Correlated Failures

Abstract

Survivable routing is crucial in backbone networks to ensure connectivity, even during failures, including natural and man-made disasters. Service-level agreements (SLAs) often define availability targets in terms of "number of nines" (e.g., 99.99%, 99.999%), and network operators aim to meet or exceed these targets by provisioning redundant paths between source-destination pairs. Nevertheless, ensuring extremely high availabilities comes with extra cost in terms of total network bandwidth usage. This study formalizes the problem of availability-aware routing based on risk zone failure probabilities. On the downside, we find the problem is $\mathcal{N}\mathcal{P}$-hard, with minimizing unavailabilities being even inapproximable in polynomial time (supposing $\mathcal{P} \ne \mathcal{N}\mathcal{P}$). Motivated by the hardness results, we initiate the study of heuristics providing availability-aware routing considering regional failures. Our methods are suitable for providing a range of routing plans, navigating the trade-off between availability and bandwidth usage. At the core of the heuristics, we rely on an efficiently solvable problem variant, where failure probabilities of risk zones are changed to capacities. We validate our findings through extensive simulations based on real-world input data. With reasonably low bandwidth usage, our heuristic is close to a lower bound on unavailability, the median and average gap being 1.23% and 2.21%, respectively.