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 utilise un ADM (Add/Drop Multiplexer) par noeud et par
longueur d'onde concernée. 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.
Objectifs :
L'objectif du stage sera d'une part de raffiner les bornes
inférieures et supérieures du nombre total d'ADMs dans le cas de
l'instance all-to-all sur l'anneau unidirectionnel et d'autre part de
trouver de bons algorithmes d'approximations.
![[Autres stages]](/mascotte/accueil/im
ages/prev2.gif){kind=small}