A Novel Graph Model for Maximum Survivability in Mesh Networks under Multiple Generic Risks

This paper investigates the path protection problem in mesh networks under multiple generic risks. Disjoint logical links may fail simultaneously if they share the same components in the physical layer. Each component is associated with one or more risks, and each risk may involve more than one logical link. This property introduces failure dependence for different logical links in layered networks. In this paper, the network failure scenario is under multiple risks. Each risk is a generic failure event, which may result in single-link failure, multiple-link failure, or all-link failure associated with a node (node failure). The objective aims at minimizing the end-to-end failure probability, or equivalently, maximizing the survivability by using two disjoint paths under multiple generic risks. The problem is shown to be NP-complete, and a novel graph model and corresponding heuristic algorithm are proposed. The time efficiency of the algorithms is analyzed, and the simulation results show that, compared to some existing diverse routing algorithms, the proposed heuristic algorithm can significantly improve the survivability at the cost of higher hop distance.