formation par la recherche / formation doctorale / enseignement, stages / sujets de thèses

Allocation optimale des VP dans les réseaux

Localisation :Irisa, Rennes

Equipe ARMOR

Responsable : Raymond MARIE (tél. direct : 02 99 84 72 95, email : marie@irisa.fr)
Miklós MOLNAR (tél. direct : 02 99 84 74 42, email : molnar@irisa.fr)

Mot-clés : Réseaux, qualité de services, routage de VP, optimisation multicritère et combinatoire

Sujet :

Un élément efficace du contrôle de trafic et de gestion des ressources dans les réseaux à haut débit orientés connexion (ou dans tous ceux qui définissent une garantie de qualité) consiste à préconfigurer des chemins virtuels (VP). Pour une topologie donnée, l'application d'un système de VP diminue les coûts, protège la qualité et influence beaucoup la gestion du réseau (l'admission des appels individuels, le taux d'utilisation des dispositifs physiques, ...). Les réseaux d'aujourd'hui doivent satisfaire des classes de trafic très différentes. Les normes ATM prévoient plusieurs classes de services avec des exigences différentes et la technologie DiffServ nécessite également l'allocation préalable de certaines ressources du réseau Internet. Les critères de qualité sont négociés et fixés dans un contrat caractérisé par la qualité de services (QoS). Le gestionnaire du réseau doit respecter ces contrats, en utilisant - entre autres - des VP garantis.

L'optimisation d'un système de VP correspond à un cas particulier de l'optimisation des multiflots dans un graphe. Même si l'on suppose des demandes homogènes, reposant sur un seul critère, le problème est NP-difficile. Plusieurs algorithmes heuristiques nécessitant un temps de calcul polynomial sont connus pour approcher ce problème. Dans le cadre de cette thèse, nous proposons d'examiner la possibilité d'une optimisation efficace, complexe et réalisable des VP. L'optimisation doit tenir compte des importants critères de qualité du trafic futur : les coûts, les capacités nécessaires ainsi que des contraintes sur le délai et/ou sur la variation du délai. Le projet nécessite l'analyse de la gestion de trafic et vise la recherche d'algorithmes d'optimisation combinatoire efficaces et implémentables.