Minimizing Blocking Probability for the Multicast Routing and Wavelength Assignment Problem in WDM Networks: Exact Solutions and Heuristic Algorithms

Dinh Danh Le 1 Feng Zhou 2 Miklós Molnár 1
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 LIA - Laboratoire Informatique d'Avignon
Abstract : Given a sparse splitting wavelength division multiplexing (WDM) network and a set of available wavelengths, we investigate the problem of provisioning a set of multicast requests simultaneously with the objective of minimizing the blocking probability. Two blocking models are taken into account: full blocking probability and partial blocking probability. As the problem is NP-hard, we propose an integer linear programming (ILP) formulation with two variants (each for a blocking model) to search for the optimal solution and several efficient adaptive heuristic algorithms to compute approximated solutions. In particular, instead of using light-trees, both ILP and heuristics use light-hierarchy, a recently proposed optimal route under sparse splitting configurations. Extensive simulations reveal that our adaptive algorithms are able to compute near-optimal solutions, and they outperform static approaches under both blocking probability models. The results also show that it is more advantageous to provision multiple multicast communications with light-hierarchies, since they are able to accommodate more requests and destinations compared to the light-tree solutions.
Type de document :
Article dans une revue
Journal of optical communications and networking, Piscataway, NJ ; Washington, DC : IEEE : Optical Society of America, 2015, 7 (1), pp.36-48. 〈10.1364/JOCN.7.000036〉
Liste complète des métadonnées
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01349065
Contributeur : Isabelle Gouat <>
Soumis le : mardi 26 juillet 2016 - 16:02:35
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

Collections

LIRMM | INSMI | MAORE | MIPS | UNIV-MONTPELLIER

Citation

Dinh Danh Le, Feng Zhou, Miklós Molnár. Minimizing Blocking Probability for the Multicast Routing and Wavelength Assignment Problem in WDM Networks: Exact Solutions and Heuristic Algorithms. Journal of optical communications and networking, Piscataway, NJ ; Washington, DC : IEEE : Optical Society of America, 2015, 7 (1), pp.36-48. 〈10.1364/JOCN.7.000036〉. 〈lirmm-01349065〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

165

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD