Using GRASP and GA to design resilient and cost-effective IP/MPLS networks

The main objective of this thesis is to find good quality solutions for rep- resentative instances of the problem of designing a resilient and low cost IP/MPLS network, to be deployed over an existing optical transport network. This research is motivated by two complementary real-world application cases, which comprise the most important commercial and academic networks of Uruguay. To achieve this goal, we performed an exhaustive analysis of existing models and technologies. From all of them we took elements that were contrasted with the par- ticular requirements of our counterparts. We highlight among these requirements, the need of getting solutions transparently implementable over a heterogeneous net- work environment, which limit us to use widely standardized features of related technologies. We decided to create new models more suitable to fit these needs. These models are intrinsically hard to solve (NP-Hard). Thus we developed meta- heuristics to find solutions to these real-world instances. Evolutionary Algorithms and Greedy Randomized Adaptive Search Procedures obtained the best results. As it usually happens, prospective real-world problems are surrounded by uncer- tainty. Therefore, we have worked closely with our counterparts to reduce the fuzzi- ness upon data to a set of representative cases. They were combined with different strategies of design to get to scenarios, which were translated into representative instances of these problems. Finally, the algorithms were fed with this information, and from their outcome we derived our results and conclusions.