![[Autres stages]](/mascotte/accueil/images/prev2.gif){kind=small}
| Retour à la page des stages effectués dans le projet MASCOTTE |
Le stage s'effectuera en collaboration avec ALCATEL SPACE INDUSTRIES (Toulouse) qui a posé le problème suivant. Dans les satellites de télécommunication, des signaux audio ou vidéo sont routés à travers un réseau de commutateurs vers des amplificateurs de relais. Le coût d'une maintenance orbitale étant prohibitif, on choisit de multiplier les composants susceptibles de tomber en panne : il s'agit des amplificateurs ou des commutateurs eux-mêmes. Le problème est de construire un réseau dit valide qui doit permettre de router p signaux d'entrée pris parmi n vers p amplificateurs (sorties) choisis arbitrairement parmi p+k, tolérant ainsi k pannes d'amplificateurs. Les commutateurs ont 4 liens et les routes empruntées par les signaux doivent être disjointes. Pour des raisons de coût, l'objectif est de construire des réseaux valides ayant le minimum de commutateurs.
Le problème ci dessus a été quasiment résolu dans le cas où le nombre p de signaux d'entrée est égal au nombre n de ports, en le ramenant à un problème de flots sur un graphe auxiliaire. Le but du stage est de regarder si dans le cas général, p<=n, les idées developpées précédemment peuvent s'appliquer. On pourra aussi regarder le cas où certains signaux sont prioritaires et doivent atteindre un ensemble de sorties variant dans le temps. On pourra aussi regarder s'il est plus intéressant de considérer des commutateurs ayant 6 liens. Suivant les goûts du stagiaire on pourra considérer soit des aspects théoriques (détermination de l'optimum ou de bornes, constructions etc ...) ou des aspects plus appliqués comme l'implémentation d'algorithmes.
INRIA - Projet MASCOTTE 2004, route des Lucioles B.P. 93 F-06902 Sophia Antipolis Cedex
|
| Retour à la page des stages effectués dans le projet MASCOTTE |