TY - GEN
T1 - Cost bounds of multicast light-trees in WDM networks
AU - Zhou, Fen
AU - Molnár, Miklós
AU - Cousin, Bernard
AU - Qiao, Chunming
PY - 2010
Y1 - 2010
N2 - 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) N2-1/4 or N2/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 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 - ⌈N/K+1⌉.
AB - 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) N2-1/4 or N2/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 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 - ⌈N/K+1⌉.
KW - All-Optical Multicast Routing (AOMR)
KW - Cost bounds
KW - Light-trees
KW - Sparse splitting
KW - WDM networks
UR - https://www.scopus.com/pages/publications/77953273332
U2 - 10.1007/978-3-642-12963-6_27
DO - 10.1007/978-3-642-12963-6_27
M3 - Conference contribution
AN - SCOPUS:77953273332
SN - 3642129625
SN - 9783642129629
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 339
EP - 350
BT - NETWORKING 2010 - 9th International IFIP TC 6 Networking Conference, Proceedings
T2 - 9th International IFIP-TC6 Networking Conference, NETWORKING 2010
Y2 - 11 May 2010 through 15 May 2010
ER -