Cost Bounds of Multicast Light-trees in WDM Networks

Abstract : The construction of light-trees is one principal subproblem for 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 optimal multicast light-trees is NP-hard. In this paper, we study the wavelength channel cost (i.e., total cost) of the light-trees built for a multicast session. An equal cost of 1 unit hop-count cost is assumed over all the fiber links in the network. We prove that the total cost of a multicast session is tightly lower limited to K and upper bounded to (1) K(N −K) when K < N/2 ; (2) (N^2 −1)/4 or (N^2)/4 respectively when K ≥ N/2 and N is odd or even, where K is the number of destinations in the multicast session and N is the number of nodes in the network. Classical sparse splitting multi- cast routing algorithms such as Reroute-to-Source and Member-Only [3] also follow these bounds. And particularly in WDM rings, the optimal multicast light-tree has a cost inferior to N − ⌈ N/( K+1) ⌉.
Type de document :
Communication dans un congrès
Mark Crovella; Laura Marie Feeney; Dan Rubenstein; S. V. Raghavan. IFIP Networking conference, May 2010, Chennai, India. Springer, Lecture Notes in Computer Science, 6091, pp.339-350, 2010, Lecture Notes in Computer Science, proceedings of IFIP Networking conference. 〈10.1007/978-3-642-12963-6_27〉
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00541058
Contributeur : Hal Ifip <>
Soumis le : vendredi 29 août 2014 - 13:22:26
Dernière modification le : jeudi 5 avril 2018 - 12:30:14
Document(s) archivé(s) le : dimanche 30 novembre 2014 - 10:39:03

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Fen Zhou, Miklos Molnar, Bernard Cousin, Chunming Qiao. Cost Bounds of Multicast Light-trees in WDM Networks. Mark Crovella; Laura Marie Feeney; Dan Rubenstein; S. V. Raghavan. IFIP Networking conference, May 2010, Chennai, India. Springer, Lecture Notes in Computer Science, 6091, pp.339-350, 2010, Lecture Notes in Computer Science, proceedings of IFIP Networking conference. 〈10.1007/978-3-642-12963-6_27〉. 〈hal-00541058v2〉

Partager

Métriques

Consultations de la notice

696

Téléchargements de fichiers

145