Etude d'un problème algorithmique intervenant dans la reconfiguration des réseaux WDM

Dans un réseau optique WDM reconfigurable, il est possible de déplacer une connexion (canal de communication optique entre 2 noeuds du réseau, généralement à plus de 2.5Gbit/s) vers une nouvelle route. L'évolution du trafic (ajout/suppression de connexions) au court du temps entraine une mauvaise utilisation des ressources du réseau. Une reconfiguration du réseau consiste alors à déplacer des connexions pour retrouver une utilisation optimale des ressources. Toutefois, le déplacement d'une connexion comporte des risques: arrêt du trafic, perte d'informations, ... Aussi il faut élaborer des algorithmes de reconfiguration minimisant par exemple le nombre de déplacements.

Lors du déploiement d'un réseau de communication de type WDM, les opérateurs dimensionnent les liens de communications (câbles de plusieurs fibres optiques) en fonction d'une connaissance du trafic à l'instant t et d'une estimation de sa croissance. L'évolution du trafic est due à 2 phénomènes, d'une part une évolution lente due à l'apparition et à la disparition de clients (réseaux d'entreprises) et, d'autre part, une évolution rapide des besoins en bande passante des clients présents. Aussi est-il intéressant pour l'opérateur de savoir modifier la configuration de son réseau selon les besoins et à moindre coût.

Dans les réseaux que nous considérons, une demande de connexion entre 2 noeuds du réseau correspond à l'affectation d'un chemin et d'une longueur d'onde, chaque connexion servant une partie des besoins en bande passante d'un client. Etant donné un réseau et un ensemble I de requêtes, le problème d'affecter un chemin optique (route + longueur d'onde) à chaque requête est NP-difficile mais des approximations performantes existent.

Dans ce contexte, une évolution du trafic correspond à l'ajout ou au retrait de connexions. Chaque requête retirée libère des ressources qui pourront être utilisées pour l'ajout de nouvelles requêtes. Lors de l'ajout de nouvelles connexions, il s'agit de trouver une route et une longueur d'onde dans le réseau sans modifier les connexions déjà établit. Dans certaines configurations, il est impossible d'établir une connexion pour une requête alors que le problème de trouver un routage optique pour l'ensemble des requêtes admet une solution.

Pour contourner cette difficulté, il faut développer des stratégies de reconfiguration du réseau (déplacement de connexions sur d'autre routes) permettant une meilleure utilisation des ressources.

Les problèmes qui devront être abordés dans ce stage sont

• De trouver un routage R(I') pour le trafic obtenu après plusieurs ajouts/suppressions de requêtes et qui soit le plus proche possible du routage original R(I). La distance entre deux routages se mesure au nombre de connexions ayant des routes différentes.
• De trouver un algorithmes fournissant une séquence minimum de déplacement permettant de passer de R(I) à R(I') et utilisant un minimum de ressources supplémentaires. Ceci permettra de déterminer quand ce processus doit être déclenché dans une séquence d'ajout/suppression de requêtes.

INRIA - Projet MASCOTTE
2004, route des Lucioles
B.P. 93 F-06902 Sophia Antipolis  Cedex

• David Coudert
  email:David.Coudert@sophia.inria.fr
  Laboratoire : MASCOTTE