Program > By author > Perrot Nancy

Nous nous intéressons dans ce papier au problème de dimensionnement d'un réseau optique multicouche, utilisant la technologie OFDM (Orthogonal Frequency Division Multiplexing) Multi-Bandes. Etant donnée une couche physique de réseau composée d'un ensemble de noeuds de transmission, liés par des fibres optiques, et des demandes définies par une origine, une destination et une quantité de trafic. On dispose d'un ensemble de capacités modulaires, appelées sous-bandes OFDM, à installer entre les nœuds de transmission, de sorte que la circulation du trafic soit possible. Chaque sous-bande possède une capacité et induit un coût d'installation, qui est celui des équipements optiques qui génèrent la sous-bande. Si une ou plusieurs sous-bandes sont installées entre deux noeuds de transmission, on dit qu'il existe un lien virtuel entre ces noeuds. L'ensemble des liens virtuels ainsi que les noeuds extrémités définissent la couche virtuelle du réseau optique. Le problème que nous étudions peut alors être défini comme suit. Nous souhaitons déterminer le nombre de sous-bandes OFDM à installer sur les liens du réseau, de sorte que toute les demandes soient routées, que chaque sous-bande utilisée soit associée à un chemin utilisant des fibres optiques, et que le coût total soit minimum. Nous appellerons ce problème Conception de Réseau Optique Multi-Bandes (Optical Multi-Band Network Design (OMBND) problem).

Nous proposons ici une approche de modélisation basée sur des coupes, et donnons une formulation en programme linéaire en nombres entiers ayant un nombre exponentiel de contraintes. Nous examinons d'abord le polyèdre associé à la formulation en coupes ainsi que la structure faciale des contraintes de base. Nous dérivons ensuite d'autres familles d'inégalités valides, et décrivons les conditions nécessaires aussi bien que les conditions suffisantes pour qu'elles définissent des facettes non triviales du polyèdre. Par ailleurs, nous proposons une étude expérimentale afin d'avoir un aperçu sur l'efficacité, en pratique, des contraintes valides introduites. Nous décrivons d'abord les procédures de séparation que nous proposons afin de générer chaque famille d'inégalités valides. Nous donnons ensuite les détails de la mise en œuvre et présentons les instances de réseaux considérées dans notre étude expérimentale. Enfin, des résultats numériques sont donnés pour des instances réalistes issues de la librairie SNDlib, ainsi que pour des instances réelles fournies par Orange Labs. Nos résultats montrent le gain apporté par les inégalités valides proposées comparé à la formulation de base. En particulier, les inégalités de type Min Set I, Capacitated Cutset inequalities et Flow-Cutset inequalities ont permis de réduire sensiblement le saut d'intégrité, et ainsi d'améliorer la qualité de la relaxation linéaire de la formulation en coupes.