A GRASP algorithm for designing a Wide Area Network backbone

Abstract

The greedy randomized adaptive search procedure (GRASP) is a well-known metaheuristic for combinatorial optimization. In this work, we introduce a GRASP for designing a survivable Wide Area Network backbone. The algorithm builds topologies which comply with heterogeneous node-connectivity requirements. This work is motivated by the need of designing a low-cost backbone network which can survive to failures in switch sites as well as in the connection lines. The method is applied to a set of problem instances with different connectivity requirements, obtaining results which appear promising.