Recherche locale à voisinage variable pour le routage optique dans des réseaux utilisant des routeurs latins

Cet article propose une approche basée sur la recherche locale à voisinage variable pour résoudre le problème de routage et d’affectation de longueur d’onde dans des réseaux optiques comprenant des routeurs latins. Il s’agit essentiellement de déterminer les routeurs intermédiaires constituant les chemins optiques entre chaque paire origine/destination et d’affecter des longueurs d’onde à ces chemins optiques dans de tels réseaux. Le problème sera abordé suivant deux scénarios : optimiser le nombre de connexions établies (scénario 1) ou répondre du mieux possible à une matrice précise de trafic (scénario 2). Dans les réseaux optiques classiques (sans routeurs latins), en raison de la complexité des phénomènes mis en jeu (les deux problèmes sontnp-difficiles pris séparément), l’approche généralement adoptée consiste à séparer le routage de l’affectation de longueurs d’onde. Cependant, les routeurs latins introduisent des contraintes reliant routage et affectation, ce qui nécessite un traitement simultané des deux problèmes. Une heuristique de recherche locale,vnsfor, basée sur la définition de voisinages variables est proposée dans cet article pour générer des solutions les plus proches possibles de l’optimum. Les résultats expérimentaux montrent quevnsfor génère de meilleures solutions suivant les deux scénarios, en comparaison avec l’algorithme de référencelonca.

This paper proposes an approach based on Variable Neighbourhood Search (vns) to solve the Routing and Wavelength Assignment (rwa) problem in optical networks including latin routers. It can be summed up as establishing routing (finding intermediate routers on optical paths between each origin/destination pair) and wavelength assignment of these optical paths in such networks. The problem will be tackled according to two scenarii: to optimize the number of established connections (scenario 1) or to answer as well as possible an accurate traffic array (scenario 2). In traditional optical networks (without latin routers), one often separates routing and wavelength assignment because of the general problem complexity (each of the two sub-problems isnp-hard). However, latin routers introduce constraints connecting routing and assignment, this requires a simultaneous treatment of the two problems. A local search heuristic,vnsfor, based on the definition of different neighbourhoods (with simple and double moves) is proposed in this paper to provide us with solutions close to the optimum. Experimental results show howvnsfor leads to better solutions, according to both scenarii, in comparison with the reference algorithmlonca.

Authors and Affiliations

1. Département de génie informatique, École Polytechnique de Montréal, succ. Centre-ville, CP 6079, H3C 3A7, Montréal, Québec, Canada

   Laurent Méric, Gilles Pesant & Samuel Pierre

2. Centre de Recherche sur les Transports, Université de Montréal, Succ. Centre-ville, CP 6128, H3C 3J7, Montréal, Québec, Canada

   Gilles Pesant

Reprints and permissions