Efficient Algorithm for Region-Disjoint Survivable Routing in Backbone Networks

摘要

Survivable routing is crucial in backbone networks to ensure connectivity, even during failures. At network design, groups of network elements prone to potential failure events are identified. These groups are referred to as Shared Risk Link Groups (SRLGs), and if they are a set of links intersected by a connected region of the plane, we call them regional-SRLGs. A recent study has presented a polynomial-time algorithm for finding a maximum number of regional-SRLG-disjoint paths between two given nodes in a planar topology, with the paths being nodedisjoint. However, existing algorithms for this problem are not practical due to their runtime and implementation complexities.This paper investigates a more general model, the maximum number of non-crossing, regional-SRLG-disjoint paths problem. It introduces an efficient and easily implementable algorithmic framework, leveraging an arbitrarily chosen shortest path finding subroutine for graphs with possibly negative weights. Depending on the subroutine chosen, the framework improves the previous worst-case runtime complexity, or can solve the problem w.h.p. in near-linear expected time. The proposed framework enables the first additive approximation for a more general ${\mathcal{N}}{\mathcal{P}}$ -hard version of the problem, where the objective is to find the maximum number of regional-SRLG-disjoint paths. We validate our findings through extensive simulations.