Multicast and broadcast routing in WDM optical networks.

摘要

Wavelength Division Multiplexed (WDM) optical networks are believed to be the future wide-area backbone networks. This thesis studies multicast and broadcast routing in WDM optical networks, with the goals of minimizing the transmission delay and minimizing the use of network resources.; A broadcast connection is supported by a spanning light-tree with possibly wavelength conversions performed at some nodes. We study the problem of finding a minimum set of network nodes such that with wavelength converters placed at these nodes, any broadcast connection can be supported. We show that the problem is NP-hard and derive both a lower bound and an upper bound of its approximation ratio. An approximation algorithm is proposed to solve the problem. Experimental results show that this algorithm achieves average performance ratio 1.169.; In a network with wavelength conversion capability at every node, we investigate the routing and wavelength assignment problem for a given broadcast connection such that a minimum number of wavelength conversions are needed. We prove that this problem is NP-hard and present a greedy approximation algorithm that achieves almost the best possible performance ratio. Experiments on randomly generated network configurations show that the algorithm produces optimal solutions in 81% of the time.; Given a multicast connection request, an important problem is to construct a routing tree such that the number of wavelengths used in the tree is minimized. We prove this problem to be NP-hard and propose an approximation algorithm that produces a routing tree with not only a small number of wavelengths but also short delay from the source to all destinations.; There are three important problems for constructing routing trees in a WDM network with dynamic connection requests: the multicast routing problem, the wavelength assignment problem (WAP) and the load balancing problem (LBP). We consider simultaneously these three problems on tree of rings networks. We prove, under the context of generalized competitiveness, that Shortest Path Tree and Minimum Spanning Tree algorithms not only can produce routing trees with low network costs and short transmission delays, but also have small competitive ratios for WAP and LBP at the same time.