DISEÑO HEURÍSTICO PARA SOLUCIONAR EL PROBLEMA DE ENRUTAMIENTO Y ASIGNACIÓN DE ESPECTRO EN REDES ÓPTICAS ELÁSTICAS ESTÁTICAS CON TOPOLOGÍA DE ANILLO

Abstract

En este trabajo de título se proponen dos métodos heurísticos para resolver el problemade enrutamiento y asignación de espectro en redes ópticas elásticas con topologíade anillo. Los modelos presentados se basan en la incidencia del ordenamiento de los usuarios en los resultados de fragmentación y costo de la red.La idea fundamental, que es compartida por los dos modelos desarrollados en estetrabajo de título, es el concepto “Spiral” que consiste en la asignación correlativa deusuarios en espiral, siguiendo la topología de anillo. Esta forma de asignación es elelemento diferenciador de las heurísticas expuestas en esta memoria.Previo a la aplicación de la asignación Spiral se clasifica a los usuarios según sus características de requerimiento de ancho de banda y largo de ruta. Esto se aplica con distintasprioridades, en el primer método se divide a los usuarios en subconjuntos segúnsu requerimiento de ancho de banda para luego ordenar cada uno de estos subconjuntosde forma decreciente de acuerdo al largo de su ruta, por el contrario, el segundo métodoforma subconjuntos según el largo de ruta para luego ordenarlos de forma decrecientesegún su requerimiento de ancho de banda. Cabe destacar que la ruta correspondientea cada usuario es calculada previamente en la etapa de enrutamiento, esta ruta es fija yestá dada por el camino más corto entre los nodos origen y destino.A modo de validar las heurísticas propuestas, estas son comparadas con los resultadosobtenidos tanto por métodos de optimización en el caso de redes pequeñas, comocon los métodos más eficientes de la literatura para redes de N nodos.

In this paper, two heuristic methods are proposed to solve the problem of routingand spectrum allocation in elastic optical networks with a ring topology. The presentedmodels based their proposals on the incidence of the users ordering in the results offragmentation and network cost.The fundamental idea, shared by the two models developed in this work, is the Spiralconcept that consists of the correlative assignment of spiral users, following the ringtopology. This assignment method is the essential element of the heuristics presentedin this report.Previous to the application of the Spiral assignment, the proposed methods classifyusers according to their characteristics of bandwidth requirements and route length. Inthe first method, the users are divided into subsets according to their bandwidth requirementand then ordering each of these subsets in a decreasing manner according to theirroute length, on the contrary, the second method creates subsets according to the routelength and then orders them according to their bandwidth requirements. Heed that theroute corresponding to each user is fixed and is the shortest path between the origin anddestination nodes.To validate the proposed heuristics, are compared with the results obtained both byoptimization in case of small networks and with the most efficient methods of the literaturefor N-node networks.