Jeudi 7 mai 2009, à 14h30 en C048.
Olivier Hudry (TELECOM ParisTech).
Routage et affectation de longueurs d'onde dans les réseaux optiques WDM.

Résumé :

Le travail présenté ici, fruit d'une collaboration avec Lucile Belgacem et Irène Charon, concerne deux problèmes NP-difficiles relatifs au routage et à l'affectation de longueurs d'onde (problème appelé RWA dans la littérature anglo-saxonne, pour Routing and Wavelength Assignment) dans les réseaux optiques à multiplexage en longueurs d'onde (WDM dans la littérature anglo-saxonne, pour Wavelength Division Multiplexing).

Plus précisément, on dispose d'un réseau WDM, représenté par un graphe non orienté G, et on souhaite établir un certain nombre de connexions dans ce réseau. Une demande de connexion d est caractérisée par un quadruplet de la forme d = (x, y, a, b), où x et y sont des sommets de G (les sommets entre lesquels on doit établir la connexion) et où [a, b] désigne l'intervalle de temps pendant lequel la connexion doit être établie. Le routage de d = (x, y, a, b) consiste à déterminer un chemin optique, représenté par une chaîne C de G d'extrémités x et y, grâce auquel la connexion est établie pendant la fenêtre horaire [a, b]. Il faut par ailleurs attribuer une longueur d'onde à C pour satisfaire la demande d. On cherche donc à déterminer simultanément comment router les demandes dans le réseau optique et comment attribuer les longueurs d'onde.

Les contraintes techniques liées à l'utilisation d'un réseau optique sont les suivantes :

une même longueur d'onde doit être utilisée le long des arêtes constituant un chemin optique donné ;
à tout instant donné et pour toute arête e de G, une longueur d'onde ne peut être utilisée que pour satisfaire une seule demande passant par e ; autrement dit, si deux demandes ont des fenêtres horaires non disjointes, on ne peut les router à l'aide d'une même longueur d'onde que si les chemins optiques qui leur sont associés n'ont aucune arête en commun.

Le premier problème que nous considérons consiste à déterminer le nombre minimum de longueurs d'onde nécessaires pour satisfaire toutes les demandes, tout en respectant les contraintes précédentes. Dans le second problème, le nombre de longueurs d'onde est fixé et on cherche à maximiser le nombre de demandes que l'on peut satisfaire sans dépasser le nombre de longueurs d'onde disponibles tout en respectant, là encore, les contraintes précédentes.

Nous proposons une modélisation revenant à déterminer successivement des stables dans un graphe de conflit, puis une méthode de descente améliorée par une méthode de post-optimisation pour résoudre ces problèmes.