Determination of the Minimum Cost Pair of D-Geodiverse Paths

Conference: DRCN 2017 – Design of Reliable Communication Networks - 13th International Conference
03/08/2017 - 03/10/2017 at München, Deutschland

Proceedings: 13th International Conference DRCN 2017

Pages: 8Language: englishTyp: PDF

Personal VDE Members are entitled to a 10% discount on this title

Sousa, Amaro de; Monteiro, Paulo (Instituto de Telecomunicações, Universidade de Aveiro, Aveiro, Portugal)
Santos, Dorabella (Instituto de Telecomunicações, Aveiro, Portugal)

Consider a geographical network with associated link costs and a distance parameter D. The minimum cost pair of D-geodiverse paths (MCPD-GP) is the minimum cost pair of paths, from a given source node to a given destination node, such that the geographical distance between any intermediate element (node or link) of one path and any element of the other path is at least D. Such a solution has the property that any disaster based failure with a coverage diameter below D affecting one or more intermediate elements of one path cannot affect any element of the other path, enhancing in this way the network robustness to disaster based failures. A related problem is to compute, for a given network and a given source-destination node pair, the maximum distance D such that a pair of D-geodiverse paths exists. In this paper, we show how both problems can be modelled and efficiently solved through integer linear programming. We also extend the MCPD-GP problem to consider the existence of vulnerability regions, where the geographical distance D is only imposed between network elements belonging to the same region.