TY - JOUR
T1 - Multicast routing and wavelength assignment in WDM networks with limited drop-offs
AU - Hu, X. D.
AU - Shuai, T. P.
AU - Jia, Xiaohua
AU - Zhang, Mu-Hong
PY - 2004
Y1 - 2004
N2 - In WDM networks with limited drop-offs, the route of a multicast connection consists of a set of light-trees. Each of the light-tree is rooted at the source node and contains no more than a limited number, say k, destination nodes due to the power loss of dropping optical signals off at destination nodes. We call such a light-tree k-drop light-tree. In this paper we study the multicast routing problem of constructing a set of k-drop light-trees that have the minimal network cost. The network cost of a set of light-trees is defined as the summation of the link cost of all the light-trees. We first prove that this problem is polynomial-time solvable for k = 2 and NP-hard for k ≥ 3. We then propose a 4-approximation algorithm for the problem for k ≥ 3. A wavelength assignment algorithm is also proposed to assign wavelengths to the light-trees of a multicast connection. In the end we give simulation results showing that k-drop multi-tree routing can significantly save not only the network cost but also wavelengths used. Moreover, when k ≥ 5 its performance is very close to the case where k is infinite (i.e., the case of using a single tree for a multicast connection).
AB - In WDM networks with limited drop-offs, the route of a multicast connection consists of a set of light-trees. Each of the light-tree is rooted at the source node and contains no more than a limited number, say k, destination nodes due to the power loss of dropping optical signals off at destination nodes. We call such a light-tree k-drop light-tree. In this paper we study the multicast routing problem of constructing a set of k-drop light-trees that have the minimal network cost. The network cost of a set of light-trees is defined as the summation of the link cost of all the light-trees. We first prove that this problem is polynomial-time solvable for k = 2 and NP-hard for k ≥ 3. We then propose a 4-approximation algorithm for the problem for k ≥ 3. A wavelength assignment algorithm is also proposed to assign wavelengths to the light-trees of a multicast connection. In the end we give simulation results showing that k-drop multi-tree routing can significantly save not only the network cost but also wavelengths used. Moreover, when k ≥ 5 its performance is very close to the case where k is infinite (i.e., the case of using a single tree for a multicast connection).
UR - http://www.scopus.com/inward/record.url?scp=8344251724&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-8344251724&origin=recordpage
U2 - 10.1109/INFCOM.2004.1354520
DO - 10.1109/INFCOM.2004.1354520
M3 - 22_Publication in policy or professional journal
VL - 1
SP - 487
EP - 494
JO - Proceedings - IEEE INFOCOM
JF - Proceedings - IEEE INFOCOM
SN - 0743-166X
T2 - IEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies
Y2 - 7 March 2004 through 11 March 2004
ER -