Wavelength routing in all-optical tree networks: A survey

We study the problem of allocating optical bandwidth to sets of communicati on requests in all-optical networks that utilize Wavelength Division Multip lexing (WDM). WDM technology establishes communication between pairs of net work nodes by establishing transmitter-receiver paths and assigning wavelen gths to each path so that no two paths going through the same fiber link us e the same wavelength. Optical bandwidth is the number of distinct waveleng ths. Since state-of-the-art, technology allows for a, limited number of wav elengths, the engineering problem to be solved is to establish communicatio n between pairs of nodes so that the total number of wavelengths used is mi nimized; this is known as the wavelength routing problem. In this paper, we survey recent advances in bandwidth allocation in tree-sh aped WDM all-optical networks: We present hardness results and lower bounds for the general problem and th e special case of symmetric communication. We give the main ideas of deterministic greedy algorithms and study their l imitations. We demonstrate how we can achieve optimal and nearly-optimal bandwidth util ization in networks with wavelength converters using simple algorithms. We also present, recent results about the use of randomization for waveleng th routing.