DEA Concernés : DEA RSD, DEA INFO

Encadrement : J-C. Bermond et S. Perennes

Courrier électronique  {bermond, speren}@sophia.inria.fr

Téléphone : 0492387679 ou 0492387191

Adresse : SLOOP, projet commun CNRS/INRIA/UNSA, INRIA,2004 route des Lucioles BP 93, 06902 Sophia-Antipolis

Laboratoire d'accueil : Projet SLOOP, projet commun CNRS/INRIA/UNSA

Connaissances pré-requises   

Goût pour l'algorithmique et les Mathématiques Discrètes. Des connaissances en théorie des graphes, en programmation en nombre entiers ,en particulier sur les problèmes de flots et multi-flots, en algorithmique d'approximation de problèmes d'optimisation combinatoire seront un plus.

Objectifs :  

L'objectif est de dimensionner des réseaux haut débit qui peuvent être, soit des réseaux atm soit des réseaux utilisant les standards de la sdh (Synchronous Digital Hierarchy) définis pour permettre d'atteindre des hauts débits sur les liaisons téléphoniques et l' interopérabilité directe entre les différents systèmes de multiplexage.

Description du sujet :  

Dans tous les cas on cherche à satisfaire un ensemble de requêtes ou demandes exprimées par exemple sous forme d'une matrice de trafic (indiquant le trafic que l'on doit écouler d'un noeud à un autre). Dans le cas des réseaux atm un problème consiste à déterminer un graphe virtuel dont les arcs représentent des chemins virtuels. Le routage dans le réseau est effectué en utilisant ces chemins virtuels. La somme des largeurs de bande des chemins virtuels empruntant un arc du graphe physique est la charge du lien. Le nombre de chemins virtuels utilisés afin d'établir une connexion est appelé le nombre de sauts. En général, on cherche à déterminer un graphe virtuel admissible (i.e. où la charge d'un lien ne dépasse pas sa capacité), minimisant une fonction de la charge et du nombre maximum de sauts d` une connexion (soit approximativement le diamètre du graphe virtuel).

Pour la sdh un objectif est de minimiser la charge des liens de la boucle sdh par un choix pertinent des routes (dans le sens des aiguilles d' une montre ou dans le sens inverse). On s'intéresse aussi à optimiser les propositions tarifaires que peut proposer l'opérateur à ses clients.

Des problèmes connexes peuvent être étudiés. Par exemple il peut s'agir d'optimiser une architecture utilisant le multiplexage en longueurs d'onde (minimisation du nombre de longueurs d'onde utilisées, maximisation du nombre de requêtes satisfaites ou encore minimisation du nombre de brasseurs optiques nécessaires).

Ces recherches seront menées en collaboration avec France Télécom dans le cadre d'une cti cnet; par ailleurs certaines d'entre elles font l'objet de collaboration avec Alcatel (Marcoussis) et France Télécom (dans le cadre du programme rnrt)