Computing Safest $st$-Paths in Backbone Networks: Efficiently Solvable Cases and Fast Heuristics
Balázs Vass, Péter Revisnyei, Alija Pašíć · 2024
For proper evaluation and optimization of the expected availability of a backbone network service, two related very fundamental modeling and algorithmic questions are the following. 1) Realistically estimate the availability of a given$st$-path for some source and target pair of communicating nodes$s$and$t$, and 2) Find a safest$st$-path. For these, traditional approaches suppose network element failures are independent. In this paper, we show that, by not considering joint failure probabilities, the traditional approaches may misguess the$st$-path availabilities and, consequently, the total connection availability, which can lead to more frequent Service Level Agreement (SLA) violations and a financial burden on the Communication Service Provider (CSP). Due to the inconsistent estimations, the supposedly safest paths yielded by these approaches may turn out to be suboptimal. On the positive side, we propose a fast algorithmic approach, that, under some assumptions, returns with a (truly) safest$st$-path accompanied by its exact expected availability. When the aforementioned assumptions do not hold, in our simulations, the proposed algorithmic scheme proved to be a good heuristic, performing at least as well as the traditional method.