Multicasting in All-Optical WDM Networks

Abstract

n this dissertation, we study the problem of (i) routing and wavelength assignment, and (ii) traffic grooming for multicast traffic in Wavelength Division Multiplexing (WDM) based all-optical networks.

We focus on the 'static' case where the set of multicast traffic requests is assumed to be known in advance. For the routing and wavelength assignment problem, we study the objective of minimizing the number of wavelengths required; and for the traffic grooming problem, we study the objectives of minimizing (i) the number of wavelengths required, and (ii) the number of electronic components required.

Both the problems are known to be hard for general fiber network topologies. Hence, it makes sense to study the problems under some restrictions on the network topology. We study the routing and wavelength assignment problem for bidirected trees, and the traffic grooming problem for unidirectional rings. The selected topologies are simple in the sense that the routing for any multicast traffic request is trivially determined, yet complex in the sense that the overall problems still remain hard. A motivation for selecting these topologies is that they are of practical interest since most of the deployed optical networks can be decomposed into these elemental topologies.

In the first part of the thesis, we study the the problem of multicast routing and wavelength assignment in all-optical bidirected trees with the objective of minimizing the number of wavelengths required in the network. We give a 5/2-approximation algorithm for the case when the degree of the bidirected tree is at most 3. We give another algorithm with approximation ratio 10/3, 3 and 2 for the case when the degree of the bidirected tree is equal to 4, 3 and 2, respectively. The time complexity analysis for both these algorithms is also presented. Next we prove that the problem is hard even for the two restricted cases when the bidirected tree has (i) depth 2, and (ii) degree 2. Finally, we present another hardness result for a related problem of finding the clique number for a class for intersection graphs.

In the second part of the thesis, we study the problem of multicast traffic grooming in all-optical unidirectional rings. For the case when the objective is to minimize the number of wavelengths required in the network, given an 'a'-approximation algorithm for the circular arc coloring problem, we give an algorithm having asymptotic approximation ratio 'a' for the multicast traffic grooming problem. We develop an easy to calculate lower bound on the minimum number of electronic components required to support a given set of multicast traffic requests on a given unidirectional ring network. We use this lower bound to analyze the worst case performance of a pair of simple grooming schemes. We also study the case when no grooming is carried out in order to get an estimate on the maximum number of electronic components that can be saved by applying intelligent grooming. Finally, we present a new grooming scheme and compare its average performance against other grooming schemes via simulations. The time complexity analysis for all the grooming schemes is also presented.