Diseño de redes de comunicación

Abstract

El objetivo principal de este trabajo es el estudio y modelación matemática de diversos problemas de diseño óptimo de redes. Primero se introducirá un tipo de problema de optimización diferente como son los problemas de flujo en redes, que nos servirán de gran ayuda para los problemas de diseño de redes que estudiaremos posteriormente. Se tratará la evolución histórico científica de las distintas topologías de redes, que se han ido adaptando a las diversas necesidades operativas y tecnológicas de cada momento. Partiremos de un problema central, el Problema Conector o también llamado Problema del Mínimo Árbol Expandido (Minimal Spanning Tree, MST), que se trata de conectar mediante enlaces los distintos puntos de una red (de ordenadores, telefónica, etc.) de manera óptima. A continuación, mostraremos distintas extensiones y especificaciones más restrictivas de este problema: el MST con restricciones de capacidades (CMST) o restricciones de salto (HMST). Estos problemas se presentarán como problemas teóricos de optimización de redes, en los que se mostrarán algoritmos y formulaciones matemáticas basados en programación lineal y entera, que nos permitirán modelar matemáticamente y estudiar cada problema. El trabajo finalizará con un capítulo dedicado a la implementación práctica de las distintas formulaciones y algoritmos, en las que sacaremos algunas observaciones y conclusiones.

The main objective of this thesis is the study and mathematical modeling of va- rious optimal network design problems. We will begin with a historical and scientific overview of the different network topo- logies, which have evolved over time to meet changing operational and technological needs. The work will be centered around a core problem, the Connector Problem, also known as the Minimal Spanning Tree Problem (MST), which consists of optimally connecting the nodes of a network (such as computer or telephone networks) through links. We will then present several extensions and more restrictive variants of this problem, such as the Capacitated Minimal Spanning Tree (CMST) and the Hop-Constrained Minimal Spanning Tree (HMST). These problems will be approached as theoretical network optimization problems, and we will introduce algorithms and mathematical formulations based on linear and integer programming that allow us to model and analyze each case. The thesis concludes with a chapter dedicated to the practical implementation of the different formulations and algorithms, from which several observations and conclusions will be drawn.