## 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|^{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.

Original language | English |
---|---|

Pages | 482-488 |

Number of pages | 7 |

Publication status | Published - 2004 |

Event | Proceedings on the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN - Hong Kong, China Duration: 10 May 2004 → 12 May 2004 |

### Conference

Conference | Proceedings on the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN |
---|---|

Country/Territory | China |

City | Hong Kong |

Period | 10/05/04 → 12/05/04 |