Propuesta de un algoritmo de solución directa para resolver el problema de asignación de rutas y longitudes de onda (rwa) utilizando los métodos dijkstra y first-fit.

Abstract

The objective for this degree project is solving routing and wavelength assignment problem (RWA) in a direct way in optical transport networks with ring topology interconnected nodes which dispose wavelength converters in all network elements and in all their links. The development is described in the 4 chapters described next. Chapter 1 presents routing and wavelength assignment problem and algorithms purposed to solving this optimization problem. This chapter includes the description for Dijkstra’s shortest path routing algorithm and First Fit wavelength assignment algorithm. Chapter 2 shows used methodology for purposed algorithm development. Designed program includes a module for variables, where it is defined algorithm input variables, including topology matrix defined as omega, flows matrix defined as flujos and maximum links capacity defined as capacidad. Additionally, it is developed main program and function’s module code. This chapter finishes describing optimization software code, developed on MiniZinc for finding theoretical optimum solution for each scenario. Chapter 3 describes tests scenarios defined for purposed algorithm analysis and for the comparison using optimization software MiniZinc. These results are ordered, tabulated and compared, to determine the feasibility of using purposed algorithm on real systems, to optimize an optical network. Chapter 4 shows conclusions found based on results obtained on previous chapter.