Constructing multiple light multicast trees in WDM optical networks

Abstract

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/e|D|2/e + kn + km) time and delivers an approximation solution within 0(|D|e) 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 e is constant, 0 < ε ≤ 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|2mΔ) time and the path delay is strictly met; and another takes O(kmn/ε + |D|n2) time and the path delay is no more than (1 + ε) Δ, where ε is constant with 0 < ε ≤ 1. Show more