Groupage de trafic sur le chemin

Dans les réseaux SONET/WDM chaque longueur d'onde peut transporter C requêtes simultanément, C est le facteur de groupage. Étant donné un ensemble de requêtes, il faut affecter les requêtes aux longueurs d'onde de telle sorte que chaque longueur d'onde supporte au plus C requêtes. A chaque insertion ou extraction de trafic sur une longueur d'onde il faut placer dans le noeud du réseau un multiplexeur à insertion/extraction (ADM). De plus il faut un ADM pour chaque longueur d'onde utilisée dans le noeud.
Les objectifs du groupage de trafic sont d'une part le partage efficace de la bande passante et d'autre part de de réduire le coût des équipements de routage. On cherche donc à réduire le nombre total d'ADMs dans le réseau.

Le problème du groupage de trafic dans les réseaux SONET/WDM a été montré NP-complet même dans le cas où le réseau est un chemin ou un anneau.

Ce problème a été particulièrement étudié dans le cas de l'anneau unidirectionnel et principalement avec l'instance all-to-all (une requête entre chaque paire de sommets). Dans ce cas le problème se modélise par un problème de partition des arêtes du graphe des requêtes en sous-graphes Gi=(Vi,Ei), chacun ayant au plus C arêtes. L'unicité du routage force à placer les requêtes (i,j) et (j,i) sur une même longueur d'onde. Chaque longueur d'onde est alors modélisée par un graphe Gi=(Vi,Ei) tel que |Ei|<= C et l'objectif est de minimiser la somme sur i de |V_i|.

Dans le cas du chemin, Pn, les requêtes (i,j) et (j,i) sont placées sur des fibres optiques différentes. Aussi, lorsque la requête (i,j) est placée sur une longueur d'onde, elle ne consomme de la capacité qu'entre ses extrémités. De ce fait, les sous-graphes de la partition peuvent avoir jusqu'à somme pour i allant de 1 à C de N/i arêtes et les techniques utilisées pour résoudre le problème dans le cas de l'anneau unidirectionnel ne sont plus applicables.

L'objectif du stage est donc d'étudier le cas du groupage de trafic sur le chemin dans le cas de l'instance all-to-all.

INRIA - Projet MASCOTTE
2004, route des Lucioles
B.P. 93 F-06902 Sophia Antipolis  Cedex

• David Coudert
  email:David.Coudert@sophia.inria.fr
  Laboratoire : MASCOTTE