Cost Bounds of Multicast Light-Trees in WDM Networks - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

Cost Bounds of Multicast Light-Trees in WDM Networks

Résumé

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<\frac{N}{2}$; (2) $\frac{N^2-1}{4}$ or $\frac{N^2}{4}$ respectively when $K \geq \frac{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 multicast 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-\lceil \frac{N}{K+1} \rceil$.
Fichier principal
Vignette du fichier
main.pdf (200.85 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00541058 , version 1 (29-11-2010)
hal-00541058 , version 2 (29-08-2014)

Identifiants

Citer

Fen Zhou, Miklós Molnár, Bernard Cousin, Chunming Qiao. Cost Bounds of Multicast Light-Trees in WDM Networks. The 9th International IFIP TC 6 Networking Conference (NETWORKING 2010), 2010, May 2010, Chennai, India. pp.339-350, ⟨10.1007/978-3-642-12963-6_27⟩. ⟨hal-00541058v1⟩
608 Consultations
369 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More