Routing and wavelength assignment in WDM optical networks : exact resolution vs. random search based heuristics
Résumé
Le probleme de routage et d’affectation de longueurs d’onde (RWA) dans les r ` eseaux optiques ´ a multiplexage en longueurs `
d’onde (reseaux WDM) a ´ et´ e abondamment ´ etudi ´ e depuis deux d ´ ecennies. La plupart des ´ etudes consid ´ erent un trafic incr ` emental ´
et traitent les demandes sequentiellement selon leur ordre d’arriv ´ ee. L’ordre selon lequel les demandes sont trait ´ ees a un impact ´
considerable sur la qualit ´ e de la solution obtenue par l’algorithme. ´
Dans une prec´ edente ´ etude, les auteurs de ce rapport ont propos ´ e un algorithme de routage et d’affectation de longueurs d’onde ´
sequentiel am ´ elior ´ e dans le cas o ´ u l’on consid ` ere une matrice de demandes. Cet algorithme a pour but de trouver rapidement un `
ordre de traitement des demandes plus favorable que l’ordre initial des demandes. Le present rapport a pour objet d’ ´ evaluer les ´
performances de cet algorithme en proposant une comparaison systematique des solutions obtenues avec l’algorithme s ´ equentiel ´
amelior ´ e aux solutions optimales obtenues par un mod ´ ele de programmation lin ` eaire. On constate que les solutions obtenues ´
par l’algorithme sequentiel am ´ elior ´ e sont, pour les situations ´ etudi ´ ees, tr ´ es proches des solutions optimales. L’efficacit ` e et les ´
performances de l’algorithme sequentiel am ´ elior ´ e justifient donc son utilisation.