loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2004 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'04)
Constructing Multiple Light Multicast Trees in WDM Optical Networks
Hong Kong, SAR, China
May 10-May 12
ISBN: 0-7695-2135-5
Weifa Liang, Australian National University
Multicast routing is a fundamental problem in any telecommunication network. We address the multicast issue in a WDM optical network without wavelength conversion capability. To realize a multicast request in such network, it is required to establish multiple light multicast trees (MLMT) sometimes due to the fact that the requested network resources are being occupied by other routing traffic and therefore it is impossible to establish a single light multicast tree for the request. In this paper we first propose a multiple light multicast tree model. We then show the MLMT is NP-hard, and devise an approximation algorithm for it which takes O((kn){1/∊}|D|{2/∊} + kn + km) time and delivers an approximation solution within O(|D|{∊}) times of the optimal, where n, m, and k are the numbers of nodes, links, and wavelengths in the network, D is the set of destination nodes and ∊ is constant, O < ∊ ≤ 1. We finally extend the problem further with the end-to-end path delay is bounded by an integer Δ, and we call this latter problem as the multiple delay-constrained light multicast tree problem (MDCLMT), for which we propose two approximation algorithms with the performance ratios of |D|. One of the proposed algorithms takes O(km|D|Δ + |D|{2}mΔ) time and the path delay is strictly met; and another takes O(kmn/∊ + |D|n{2}) time and the path delay is no more than (1 + ∊)Δ, where ∊ is constant with 0 < ∊ ≤ 1.
Citation:
Weifa Liang, "Constructing Multiple Light Multicast Trees in WDM Optical Networks," ispan, pp.482, 2004 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.