Efficient Algorithm for Region-Disjoint Survivable Routing in Backbone Networks

Bérczi-Kovács, Erika and Gyimesi, Péter and Vass, Balázs and Tapolcai, János (2024) Efficient Algorithm for Region-Disjoint Survivable Routing in Backbone Networks. In: IEEE INFOCOM 2024 - IEEE Conference on Computer Communications.

Preview

Text Resilient_routing_INFOCOM_2024___Date_Line_Algorithm.pdf Download (264kB) | Preview

Abstract

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 find-ing a maximum number of regional-SRLG-disjoint paths between two given nodes in a planar topology, with the paths being node-disjoint. 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 NP -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.

Actions (login required)

Edit Item