Enrutado y asignación de longitudes de onda

Abstract

El problema del enrutamiento y asignación de longitudes de onda consiste en lo siguiente: dado un grafo en el que hay un conjunto de nodos o terminales conectados por aristas, conectar un conjunto de nodos. Para conectar un par de nodos, se deben utilizar señales a través de fibra óptica, conocidas con el nombre de longitudes de onda. Así pues, el objetivo de este proyecto consiste en minimizar el número de longitudes de onda utilizadas para conectar todos los pares de nodos solicitados, por lo que se está ante un problema de minimización dentro del ámbito de la optimización. Este problema que se ha resuelto en este proyecto tiene aplicaciones en el mundo real. En concreto, tiene gran relevancia en el ámbito de las telecomunicaciones, donde hoy en día existen infinidad de aplicaciones, como por ejemplo las videoconferencias, computación distribuida, etc. en las que es necesaria la máxima velocidad de cómputo y de transporte de los datos que viajan por la red. En este proyecto se ha presentado el problema y se han aplicado un conjunto de metodologías de resolución de problemas de optimización al problema considerado. Estos métodos proporcionan soluciones en tiempos de cómputo razonables. Así, los métodos utilizados para solucionar el problema son los llamados métodos heurísticos y meta-heurísticos, que proporcionan soluciones de calidad, no necesariamente óptimas, con un coste reducido de recursos. Para solucionar el problema que se plantea, se han implementado dos algoritmos constructivos, un algoritmo perteneciente a la metaheurística GRASP, un algoritmo perteneciente a la metaheurística Tabu Search y por último, dos algoritmos que forman parte de la metaheurística Iterated Greedy. Dichos algoritmos se han realizado bajo un diseño que permite que el software implementado no sólo sea fácilmente legible, sino que también sea fácilmente modificable y extensible. Implementados los distintos algoritmos, se ha comprobado a través de la etapa de experimentación la calidad de las soluciones que proporciona cada uno de ellos, en función del tiempo de cómputo y del número de longitudes de onda empleadas en la conexión de los distintos nodos. Finalmente, se han expuesto las distintas conclusiones obtenidas a partir del trabajo realizado y de los resultados obtenidos.