Fecha: Lunes 5 de mayo de 2014
Hora: 15:00
Lugar: Sala de Posgrados, Instituto de Computación, Facultad de Ingeniería
Título de la tesis: "Using GRASP and GA to design resilient and cost-effective IP/MPLS networks"
Director Académico: Dr. Franco Robledo
Directores de Tesis: Dr. Franco Robledo y Dr. Gerardo Rubino
Tribunal:
- Dr. Mauricio Resende (AT&T Labs Research, USA) -Revisor-
- Dr. Martín Varela (Investigador Senior, VTT Technical Research Centre of Finland) -Revisor-
- Dr. Francisco Barahona (IBM Watson Research, USA)
- Dr. Antonio Mauttone (Instituto de Computación, Facultad de Ingeniería, UdelaR / PEDECIBA Informática)
- Dr. Eduardo Canale (Instituto de Matemática, Facultad de Ingeniería, UdelaR / PEDECIBA Informática)
- Dr. Gregory Randall (Instituto de Ingeniería Eléctrica, Facultad de Ingeniería, UdelaR)
Resumen
The main objective of this thesis is to find good quality solutions for representative 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 particular requirements of our counterparts. We highlight among these requirements, the need of getting solutions transparently implementable over a heterogeneous network 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 metaheuristics 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 uncertainty. Therefore, we have worked closely with our counterparts to reduce the fuzzinessupon data to a set of representative cases. They were combined with different strategies of design to get to scenarios, which were translated into representativeinstances of these problems.
Finally, the algorithms were fed with this information, and from their outcome we derived our results and conclusions.
Keywords: Multilayer networks, design of resilient networks, combinatorial optimization, metaheuristics, graph theory, optical transport networks, IP/MPLS