Groupe d’études et de recherche en analyse des décisions


RWA Problem with Geodesics in Realistic OTN Topologies

, , , et

This paper presents a decomposition approach for solving a variant of the Routing and Wavelength Assignment (RWA) problem, in which all connection requests are covered by geodesics, i.e., shortest paths with respect to a given cost function. In this paper we compute them with respect to the number of hops. Our decomposition approach is an extension of a recent method proposed in the literature, for the case of geodesics. We also improve this method by proposing new ways of selecting the set of promising paths in the paths selection phase. Our approach as well as an integer linear optimization formulation are tested on 29 realistic optical transport networks (OTN) ranging from 9 to 100 nodes. The results show that our approach can find the optimal number of wavelengths or an interval on this number in a short computing time. We also show that this interval can be used to accelerate the solution process of the integer linear formulation. Using these techniques, we were able to find and prove the optimal number of wavelengths for 28 of the 29 networks while providing a small interval on the optimal number of wavelengths for the remaining network. To the best of our knowledge, the RWA problem is solved with proof of optimality for the first time for such a number of realistic topologies. Furthermore, since the main assumptions made in this paper correspond to a worst-case scenario, our results can be used as an upper bound to other variants of the RWA problem.

, 20 pages