Minimizing the network availability upgrade cost with geodiversity guarantees

Abstract

As telecommunication networks are a critical infrastructure of our society, they must evolve to provide high end-to-end availability and high resilience to large-scale disasters. Path protection mechanisms can improve end-to-end availability but, in general, might not be enough to reach the availability required by critical services. Moreover, adding geodiversity to the routing paths (i.e., selecting path pairs with higher geographical distance between them) enhances the network disaster resilience but also makes it more challenging to reach a high end-to-end availability as the resulting paths tend to be longer. So, for a network where each link is characterized by its current availability and by the cost of upgrading its availability to a new value, this paper proposes some strategies aiming to determine a set of links to be upgraded at a minimum cost ensuring a desired level of availability and geodiversity. The problem is defined as an integer non-linear programming model, a solving algorithm based on different greedy strategies is proposed and the relative performance of the different strategies is evaluated on a set of problem instances.