Le problème de la reconfiguration dans les réseaux optiques multifibres
Institution:
NiceDisciplines:
Directors:
Abstract EN:
Un réseau de télécommunication optique est configuré de manière à répondre à une demande donnée, avec un certain objectif. Avec le temps, la demande d’exploitation du réseau change. C’est dans ce contexte que se pose le problème de la reconfiguration : être capable de changer la configuration du réseau de manière à l’adapter à des nouvelles demandes. Pour reconfigurer un réseau, il faut généralement interrompre totalement ou partiellement le trafic. Etant donné les quantités de données y circulant, il n’est guère envisageable d’arrêter le réseau. De nombreux paramètres sont à prendre en compte afin de déterminer ce qui sera une bonne solution. Nous proposons un modèle mathématique permettant de représenter le problème. Cependant, le résoudre exactement peut être très coûteux en temps de calcul. Nous proposons également une heuristique gloutonne et une heuristique basée sur le recuit simulé. Les solutions obtenues présentent différentes caractéristiques selon la métrique optimisée. L’algorithme glouton est rapide et trouve des solutions qui sont comparables aux solutions optimales. Dans une seconde partie, nous nous intéressons à l’aspect multi objectif du problème. Il consiste à considérer simultanément les différentes métriques et rechercher un ensemble de solutions représentant différents compromis intéressants. Puis nous proposons un algorithme basé sur notre modélisation mathématique. Nous adaptons également un algorithme évolutif. Donner une certaine flexibilité par rapport à une métrique permet généralement d’améliorer de manière significative les solutions obtenues par rapport aux autres métriques.
Abstract FR:
An optical telecommunication network is configured to transmit a given traffic, to meet a given objective. However, the demand changes with the time and the development of infrastructures. The reconfiguration problem lies in this context : being able to change the configuration of the network to adjust it to the new demands. In general, to reconfigure a network, it is required to interrupt totally or partially the network traffic. Considering the amount to data flowing on it, it may not be possible to regularly stop the network, even if it is only for a few minutes. Many parameters have to be taken into account to find out what will be a good solution. We propose a mathematical model allowing to represent the reconfiguration problem. However, solve the proposed model exactly may require a high computation time. Then, we also propose a greedy and a simulated annealing heuristics. Depending on the metric optimized, the solutions have different characteristics. The greedy algorithm provides solutions competing with the optimal ones. In a second part, we focus on the multiobjective aspect of the reconfiguration problem. It considers at the same time the different metrics and searches for a seat of solutions representing different interesting trade-offs instead of a unique solution. We proposed an algorithm based on our mathematical formulation. We also adapt an evolutionary algorithm. The proposed methods succeed in finding different interesting trade-offs. Giving a little flexibility with respect to a metric generally allows to significantly improve the solutions with respect to the other metrics.