Multi-overlay network planning by applying a Variable Neighborhood Search approach

This paper presents an approach for the topological design and sizing of an IP/MPLS multi-overlay network with the purpose of minimizing the economical resources involved on a major Telecommunication Enterprise 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 optimization 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 Neighborhood Search), which has shown positive qualities as simplicity, efficiency and effectiveness among others. Then, the implemented local searches and achieved results are described. The average improvement gap obtained in the test cases created is 39% in an average time of 2´50”.