Résolution exacte du problème de routage multicast multi-contraint de coût minimal

Session : SS1-3 / SS1 : Challenging Mixed-Integer Problems in Network Optimization
Vendredi 12 février 10:30 - 11:50 Salle : CI2-06
Walid Khallef, Sylvain Durand et Miklos Molnar

L'exigence des applications multimédia en temps réel dans les réseaux porte plusieurs défis. C'est le cas du routage des paquets d’une source vers un ensemble de destinations (routage multicast) utilisé dans les vidéoconférences, la diffusion de vidéos à la demande… Pour satisfaire les besoins des utilisateurs de ces applications, il faut s’assurer que les paquets peuvent atteindre chaque destination en respectant des contraintes de qualité de service (QoS) avec une utilisation moindre des ressources. La plupart des travaux de la littérature proposent des algorithmes de routage approchés. Ils sont efficaces dans certain cas mais se focalisent sur la recherche d’arbres pour le routage. Dans ce travail, nous proposons un programme linéaire en nombres entiers (PLNE) pour trouver une solution optimale : une route multicast qui respecte les contraintes avec un coût minimum (même si cette solution ne correspond pas un arbre). L'obtention de solutions optimales permet aussi d'analyser l'efficacité des heuristiques proposées dans la littérature.

Mots clés : optimisation, multi-contrainte, QoS, routage, multicast