Optimisation du groupage dans les réseaux de télécommunication
Description du sujet :
Les réseaux de télécommunication se présentent souvent sous la forme
de couches qui correspondent à des technologies ou des protocoles de
transports différents. Ces couches sont organisées de manière
hiérarchique et utilisent intensivement différentes formes de
multiplexage. On peut citer WDM pour la couche optique ou SONET/SDH.
Le principe du groupage est d'agréger des flux ou conduits de faibles
débits d'une couche du réseau dans des conduits de plus gros débits de
la couche inférieure. Par exemple on cherchera à grouper des OC-3 (155
Mb/s) en OC-48 (2,5 Gb/s) qui seront transportés par une seule longueur
d'onde.
Au plus on groupe de conduits, au mieux on exploite la bande passante
disponible. Cependant le groupage induit un coût en équipement en
chaque noeud du réseau qui doit insérer ou extraire l'un des flux
groupés. On est donc face à un problème d'optimisation qui consiste à
trouver le meilleur compromis entre maximiser le groupage des flux et
minimiser le nombre de fois où les flux doivent être séparés pour
atteindre leurs destinations. Même dans des cas très simples où le
réseau est un anneau unidirectionnel et où les communications sont
connues à l'avance (All-To-All) ce problème est prouvé NP-complet. De
plus l'optimisation dépend aussi du routage choisi (chemins dans le
réseau) pour acheminer les flux de bout en bout.
Objectifs :
L'objectif du stage sera dans un premier temps de trouver une bonne
modélisation générale de ce problème étudié au cas par cas dans la
littérature, et de spécifier les cas importants pour la
pratique. Ensuite on proposera des solutions pour ces cas particuliers,
soit en utilisant des techniques classiques d'optimisation
combinatoire, soit en essayant de trouver des algorithmes polynomiaux
approchés performants. Jusqu'à maintenant toutes les recherches ont porté
sur un groupage entre deux niveaux ; il sera intéressant de généraliser
ces études pour un nombre quelconque de niveaux.
![[Autres stages]](/mascotte/accueil/images/prev2.gif){kind=small}