MASCOTTE no longer exists => visit the new project-team
Internship MASCOTTEReconfiguration de routage dans les réseaux tout optique
by Ronan Soares
| | | | Advisor | David Coudert (CR INRIA) et Nicolas Nisse (post-doc INRIA) | | School | Universidade Federal do Ceará | | Degree | Master | | Period | 15/02/09-15/05/09 |
Dans les réseaux de communications orientés connexions tels que les réseaux de coeurs et certains
réseaux d’accès, le problème de la reconfiguration d’un routage est un problème central. On le re-
trouve lors du rétablissement du trafic interrompu par une panne, ou encore lorsque les ressources
du réseau sont mals utilisées, par exemple suite à des variations de trafic (ajout ou suppression
de connections). Reconfigurer un réseau consiste à basculer un ensemble de connexions d’un
routage R1 vers un routage R2 . Plusieurs stratégies sont possibles selon le type de réseau et les
contraintes de QoS. Lorsque les contraintes de QoS sont fortes (par exemple pas d’interruption
de service), on cherche à déplacer les connexions une par une. Il s’agit alors de déterminer l’ordre
de déplacement des connexions. Toutefois, l’existence de cycles de dépendances peut imposer
l’utilisation de ressources temporaires qu’il faut alors minimiser. Lorsque l’utilisation de res-
sources temporaires est impossible, des connexions devront être temporairement interrompu. Il
faut alors d’une part minimiser le nombre de connexions simultanément interrompues et d’autre
part minimiser la durée d’interruption de chaque connexion. Une modélisation de ce problème de
reconfiguration comme un problème de poursuite dans un graphe orienté a été proposée dans [2].
Ce problème est en général NP-difficile et difficile à approximer, mais peut-être résolu en temps
polynomial pour certaines classes de graphes. De plus, des algorithmes heuristiques donnant de
bons résultats ont été poposés [1].
Les objectifs de ce stage sont de :
– Caractériser de nouvelles classes de graphes pour lesquelles le problème se résoud en temps
polynomial ;
– Concevoir un algorithme exact permettant de résoudre le problème de reconfiguration sur des
petites instances (quelques centaines de connexions).
Références
[1] D. Coudert, F. Huc, D. Mazauric, N. Nisse, and J-S. Sereni. Routing Reconfiguration/Process
Number : Coping with Two Classes of Services. In 13th Conference on Optical Network
Design and Modeling (ONDM), Braunschweig, Germany, February 2009. IEEE.
http://hal.inria.fr/inria-00331807
[2] D. Coudert and J-S. Sereni. Characterization of graphs and digraphs with small process
number. Research Report 6285, INRIA, September 2007.
http://hal.inria.fr/inria-00171083/
List of interships | 
