Abordagem matemática e algorítmica do problema de roteamento e agregação de tráfego em redes ópticas

Abstract

The necessity to transmit large amounts of data in networks, with low delay, boosted research in the telecommunications area. Optical networks have provided an infrastructure for high-performance switching and data transmission, providing high transmission rates having a short delays in data delivery. The wavelength, as transport unit in the network, has a high potential for data transmission. However, when a set of requests is routed without concern for the best usage of network resources, various quality of service criteria can be affected. Therefore, techniques for traffic grooming, that enables various demands to be transmitted in the same wavelength, fail-safe protection and load balancing may become necessary for the optical fiber to be used optimally, ensuring reliability and scalability. This paper presents mathematical models and heuristics for the routing and wavelength assignment problem, traffic grooming and fail-safe protection in optical networks. Various criteria are analyzed such as minimizing the number of hops and the number of allocated wavelengths, maximizing the network load balancing and the number of requests served. They are analized in single domain and multi-domain scenarios, the latter considering integrated and hierarchical approaches. Since the problem is of high complexity, and its exact solution is impractical for large instances, polynomial algorithms have been proposed, one being based on GRASP and another based on an evolutionary algorithm. They are tested with several instances of the literature and the results are compared to the optimal solution obtained with the mathematical model resolution. The latter is solved in a commercial package called CPLEX. The algorithms have shown good results for the criteria, achieving objective function values very close to those obtained by the commercial package CPLEX. What leads to the conclusion that these algorithms can be used in more realistic scenarios.