Cost Bounds and Approximation Ratios of Multicast Light-Trees in WDM Networks

Fen Zhou 1, 2, * Miklós Molnár 3 Bernard Cousin 1 Chunming Qiao 4
* Auteur correspondant
1 ATNET - Advanced Technolgy in Networking
IRISA-D2 - RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES
3 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The construction of light-trees is one of the principal subproblems for all-optical multicast routing in sparse splitting wavelength division multiplexing (WDM) networks. Due to the light splitting constraint and the absence of wavelength converters, several light-trees may be required to establish a multicast session. However, the computation of the cost-optimal multicast light-trees is NP-hard. In this paper, first we study the cost bounds of the light-trees built for a multicast session in unweighted WDM networks. Then, partially based on this result, the approximation ratios of some classical multicast light-tree computation algorithms, i.e., the reroute-to-source (R2S) and member-only (MO) algorithms, are derived in both unweighted and non-equally-weighted WDM networks. Moreover, integer linear programming formulations are introduced and carried out to search the optimal light-trees for multicast routing. The cost bounds and approximation ratios of the R2S and MO algorithms in some candidate WDM backbone networks are examined through simulations.
Type de document :
Article dans une revue
Journal of optical communications and networking, Piscataway, NJ ; Washington, DC : IEEE : Optical Society of America, 2011, 3 (4), pp.323-334. 〈10.1364/JOCN.3.000323〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00738071
Contributeur : <>
Soumis le : mercredi 3 octobre 2012 - 12:43:13
Dernière modification le : mardi 16 janvier 2018 - 15:54:19

Identifiants

Citation

Fen Zhou, Miklós Molnár, Bernard Cousin, Chunming Qiao. Cost Bounds and Approximation Ratios of Multicast Light-Trees in WDM Networks. Journal of optical communications and networking, Piscataway, NJ ; Washington, DC : IEEE : Optical Society of America, 2011, 3 (4), pp.323-334. 〈10.1364/JOCN.3.000323〉. 〈lirmm-00738071〉

Partager

Métriques

Consultations de la notice

255