Travail en commun avec
J. Mouliérac (IRISA-Rennes).
La technique classique pour gérer les communications multipoints (c'est-à-dire
des communications entre les membres d'un groupe partageant une application
comme par exemple une visioconférence)
consiste à allouer au groupe ``une bonne structure'' dans le réseau
sous-jacent, toutes les communications du groupe passant par cette structure.
Classiquement, la structure choisie est un arbre couvrant les membres du
groupe. Le choix de cette topologie est lié à la nécessité de simplicité dans
la gestion du groupe et en particulier pour l'algorithme de
routage utilisé entre les membres du groupe.
Pour des contraintes de qualités de service (temps réel notamment) et de coût
(le groupe utilise des ressources du réseau), il est nécessaire d'optimiser
certains paramètres dans la construction de l'arbre.
Par exemple le problème de construire un arbre ayant un minimum de liens a été
très étudié. Ce problème appelé ``problème de l'arbre de Steiner'' est
NP-complet et on connait des algorithmes approchés pour le résoudre.
Nous étudions une variante du problème précédent : les communications entre un
émetteur et les membres du groupes doivent passer par un ou plusieurs noeuds
capable de rendre un service, dans la suite nous appelerons ces noeuds des
traducteurs. Le problème se décompose donc en deux phases l'émission d'un
message de l'émetteur vers l'ensemble (ou un sous-ensemble) des traducteurs,
puis d'un message des traducteurs vers les membres du groupe.