SOFSEM 2001 28th Annual Conference on Current Trends in Theory and Practice of Informatics November 24 - December 1, 2001 Piestany, Slovak Republic, Europe

Wavelength Routing in All-Optical Tree Networks

by Christos Kaklamanis

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 talk 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.