ALCOMFT-TR-01-55

Ioannis Caragiannis, Christos Kaklamanis and Pino Persiano
Wavelength Routing in All-Optical Tree Networks: A Survey
Patras. Work packages 2 and 4. May 2001.

Abstract: We study the problem of allocating optical bandwidth to sets of communication requests in all-optical networks that utilize Wavelength Division Multiplexing (WDM). WDM technology establishes communication between pairs of network nodes by establishing transmitter-receiver paths and assigning wavelengths to each path so that no two paths going through the same fiber link use the same wavelength. Optical bandwidth is the number of distinct wavelengths. Since state-of-the-art technology allows for a limited number of wavelengths, the engineering problem to be solved is to establish communication between pairs of nodes so that the total number of wavelengths used is minimized; this is known as the wavelength routing problem.

In this paper we survey recent advances in bandwidth allocation in tree-shaped WDM all-optical networks. We present hardness results and lower bounds for the general problem and the special case of symmetric communication. We give the main ideas of deterministic greedy algorithms and study their limitations. We demonstrate how we can achieve optimal and nearly-optimal bandwidth utilization in networks with wavelength converters using simple algorithms. We also present recent results about the use of randomization for wavelength routing.

Postscript file: ALCOMFT-TR-01-55.ps.gz (107 kb).