Direction de recherche : Philippe CHRÉTIENNE

Co-encadrement : 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

Publications 2005-2007

• 2007
  • N. Faure, Ph. Chrétienne, E. GOURDIN, F. Sourd : “Biclique completion problems for multicast network design”, Discrete Optimization, vol. 4 (3-4), pp. 360-377, (Elsevier) (2007)
• 2006
  • N. Faure : “Contribution à la résolution de problèmes de regroupement de sessions multicasts”, soutenance de thèse, soutenance 07/12/2006, direction de recherche Chrétienne, Philippe, co-encadrement : Sourd, Francis (2006)
  • P. Fouilhoux, N. Faure, E. GOURDIN : “Le problème d’agrégation de sessions multicast”, Journées Polyèdres et Optimisation Combinatoire, Avignon, France, pp. 29-31 (2006)
• 2005
  • Ph. Chrétienne, N. Faure, E. GOURDIN, F. Sourd : “Multicast sessions partitioning problem”, 5^th ALIO/EURO conference on combinatorial optimization, Paris, France, pp. 47-47 (2005)
  • N. Faure, Ph. Chrétienne, E. GOURDIN, F. Sourd : “Arbres multicast optimaux dans les réseaux de télécommunication”, 6^e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2005), Tours, France, pp. 313-325, (Presses Universitaires François Rabelais) (2005)