A Survivable & Reliable Network Topological Design Model

Abstract

This paper is focused on the resolution of a mixed model for the design of large size networks which will be topologically robust regarding its connectivity and reliability. More precisely, we combined the Network Survivability & Network Reliability approaches. The problem of the topological design has been modeled based on the Generalized Steiner Problem with Node-Connectivity Constraints (GSP-NC), which is NP-Hard. Our aim is to heuristically solve the GSP-NC model by designing low cost highly connected topologies and to measure the reliability of such solutions with respect to a certain prefixed lower threshold. We introduce a Greedy Randomized algorithm for the construction of feasible solutions for the GSP-NC and a local search algorithm based on the Variable Neighbourhood Search (VNS) method customized for the GSP-NC. To compute the built networks reliabilities we adapted the Recursive Variance Reduction (RVR) technic as simulation method since the exact evaluation of this measurement is also NP-Hard. The experimental tests were performed over a wide set of testing cases which contained heterogeneous topologies, including instances of more than 200 nodes. The computational results showed highly competitive execution times, achieving minimal local optimal solutions of good quality fulfilling the imposed survivability and reliability conditions.