Votre courriel/e-mail of the sender : bermond@sophia.inria.fr

Nom du projet/Research team name : Mascotte

Unité de recherche/Research Unit : Sophia-Antipolis

Thème INRIA/Research theme : Com 

Nom et prénom du chef de projet/Research team leader name : Jean-Claude Bermond

Encadrant du stage/Intern tutor : Jean-Claude Bermond

Titre du sujet du stage/Internship title :

Combinatoire des réseaux optiques tolérant aux pannes / Fault tolerant optical networks

Type de stage/Intern level : diplôme d'ingénieur-Engineering school / Mastère-Master's thesis / Doctorat-Ph'D.

Durée minimum du stage (en mois)/Internship duration (months) : indifférente / no matter

Ce stage pourrait-il déboucher sur une thèse ou un post-doc ?/Eventual follow-up : oui-yes

Description du sujet du stage/Internship description (une dizaine de lignes/about ten lines) :

Acheminer une requête (x,y) dans un réseau optique revient à associer un chemin dans le réseau de x à y et une longueur d'onde (couleur).On cherche à acheminer un ensemble de requêtes dans un réseau en respectant des contraintes de capacité (ou débit) sur chaque arête de sorte que deux chemins ayant une arête en commun n'utilisent pas la même longueur d'onde. L'objectif est alors de minimiser le nombre de longueur d'ondes utilisées.  Nous proposons dans le stage de rajouter de la tolérance aux pannes (protection) en associant à chaque arête non pas un chemin, mais k chemins 2 à 2 arc-disjoints dans le réseau (de manière à tolérer k-1 pannes d'arêtes).  Traiter ce problème se ramène à la construction d'objets généralisant les carrés latins idempotents et nécessitant l'utilisation de nouveaux outils en combinatoire et théorie des groupes. The aim of the internship is to study the problem of designing fault tolerant routings in optical networks. Routing a request (x,y) in an optical network consists in assigning a directed path from x to y and a wavelength (color). One wants to route a family of requests in the networks under some capacity constraints with the property that two paths of the routing using the same arc have different wavelengths. One of the objective is to minimize the number of wavelengths.  In this internship we add another property of fault tolerance. We want that the requests are still routed if at most f edges (or vertices) fail. To do that we now associate to each request a set of (f+1)- arc (vertex) disjoint paths from x to y. We still want to respect the constraint capacity or to minimize the number of wavelengths used. The solution of these problems need to use tools of design theory like idempotent latin squares and new algorithmic ideas.

Préciser les pré-requis nécessaires pour ce stage/Pre-requisit :

Optimisation combinatoire, théorie des graphes / Combinatorial optimisation, graph theory