A GRASP algorithm with tree based local search for designing a survivable wide area network backbone

Abstract

System survivability is the ability to give service in spite of failures of some of the components. To assure survivability is an important goal when designing a communications network backbone, to ensure that it can resist to failures in the switch sites as well as in the connection lines. Previous work has employed a Greedy Randomized Adaptive Search Procedure (GRASP), based on path algorithms, to build low cost network topologies which comply with heterogeneous node-connectivity requirements, which can model the survivability goals. In this work, we present another variant of the GRASP procedure, based on a tree search, which obtains good results in topologies with a large number of switch nodes.