Multi-Overlay network planning by applying a variable neighbourhood search approach.

Abstract

This thesis presents an approach for the topological design and sizing of an IP/MPLSmultioverlay network with the purpose of minimising the economical resources involved on ANTEL (Administración Nacional de Telecomunicaciones) infrastructure. The overlay network is an MPLS Data Network, which physically exchange traffic over an existent Transport infrastructure. The solution to find must be of optimal cost, robust to simple failures in the Transport Network, and deal with differential traffic. The mathematical model for this kind of problems is obtained by using weighted graphs which leads to a combinatorial optimisation formulation. As the problem undertaken is NP-Hard concerning computational complexity, a metaheuristic methodology is employed, which reaches approximate though often optimal solutions in a reasonable time. The metaheuristic selected is VNS (Variable Neihbourhood Search), which has shown positive qualities as simplicity, efficiency and effectiveness among others. Then, the implemented local searches and achieved results are described.