Le but du stage est de concevoir et d'implémenter
des algorithmes déterminants la manière de réaliser
un ensemble de requêtes dans un réseau de télécommunications
(de type atm ou optique); et ce sous diverses hypothèses.
Dans un premier temps il s'agira d'implémenter les algorithmes polynômiaux
déterministes existants qui résolvent des instances particulières du problème.
Ensuite en s'appuyant sur une recherche
bibliographique le stagiaire déterminera un algorithme général si possible performant
afin de l'implémenter.
Cette phase de développement induira certainement le choix d'heuristiques
ou la modification partielle des algorithmes proposés dans la
littérature.
Une bonne utilisation du réseau de stations de travail
impliquera une parallélisation efficace du/des algorithmes.
Dans les réseaux de télécommunication et d'interconnexion
on doit souvent définir un réseau virtuel qui repose sur une architecture
physique (réseau réel). Ce réseau abstrait reflète les besoins en communication
d'une certaine clientèle. Pratiquement on s'intéresse au
``virtual layout'' dans les réseaux atm,
au routage wdm dans certains réseaux optiques,
ou encore à l'affectation des trains aux lignes physiques dans les réseaux de transport.
Le problème consiste alors à concevoir le réseau virtuel
qui satisfasse les requêtes de trafic (par exemple une demande de bande passante)
à moindre coût. Le problème se modélise comme suit:
au réseau physique (en général irrégulier) on associe un graphe
et on cherche à tracer un certain nombre de "routes" (chemins) réalisant les requêtes
(i.e ces chemins permettent d'acheminer un trafic entre leur deux extremités).
Si dans certains cas particuliers, il existe des algorithmes efficaces,
en général le problème est difficile et sa résolution
repose souvent sur l'utilisation d'algorithmes de théorie des graphes
(multiflots, coloriage). Une importante littérature propose
aussi des algorithmes approchés ou probabilistes plus ou moins efficaces.
Dans un premier temps on peut considérer le problème statique
(les requètes sont alors déterminées à l'avance), puis le cas dynamique
(les requêtes arrivent ou disparaissent sans-cesse et on doit résoudre le problème ``en-ligne'').
Le thème de recherche abordé fait l'objet d'une collaboration avec le cnet.