FAURE Nathalie

PhD graduated
Team : RO
Departure date : 12/08/2006
https://lip6.fr/Nathalie.Faure

Supervision : Philippe CHRÉTIENNE

Co-supervision : SOURD Francis

Contribution à la résolution de problèmes de regroupement de sessions multicasts

Dans ces travaux de thèse, nous nous sommes intéressés à la résolution de problèmes de regroupement de sessions multicasts. Les services multicasts connectent plusieurs entités qui peuvent interagir ensemble pour envoyer ou recevoir de l'information. Pour chaque session ou groupe multicast, il faut déterminer un arbre reliant l'ensemble des entités du groupe. L'émergence de ces nouveaux services implique de devoir gérer un grand nombre de sessions multicasts simultanément et donc un grand nombre d'arbres. Cependant les capacités du réseau ne permettent pas de gérer autant d'arbres en même temps. Pour remédier à ce problème, nous utilisons l'agrégation des arbres qui consiste à regrouper plusieurs sessions sur le même arbre et diminuer ainsi le nombre total d'arbres utilisés. Il en résulte que des ressources du réseau peuvent être gaspillées lorsqu'une session est envoyée vers un client ne voulant pas la recevoir. En supposant que le nombre d'arbres multicasts est limité et inférieur strictement au nombre de sessions, nous nous sommes focalisés sur le problème qui consiste à définir comment regrouper les sessions multicasts et leurs clients afin de minimiser le nombre d'informations envoyées inutilement et de satisfaire toutes les demandes. Nous avons proposé plusieurs formulations pour ce problème qui nous ont conduit à différentes résolutions. A partir d'une formulation plus compacte, nous avons implémenté une heuristique de génération de colonnes qui résout le problème rapidement. A l'aide d'une étude polyédrique, nous avons identifié de nouvelles familles d'inégalités pour renforcer la formulation. Une méthode de résolution exacte par Branch-and-Cut a pu être ainsi mise en oeuvre

Defence : 12/07/2006 - 14h - Site Jussieu - Bat 41 - Salle 203/205

Jury members :

Labbé Martine Université Libre de Bruxelles [Rapporteur]
Mahey Philippe ISIMA Université Blaise Pascal Clermont-Ferrand [Rapporteur]
Carlier Jacques Université technologique de Compiègne
Pujolle Guy Université Pierre et Marie Curie
Chrétienne Philippe, Université Pierre et Marie Curie
Gourdin Eric France Télécom DRD
Sourd Francis CNRS

2005-2007 Publications