Efficient routing in optical networks

Reviewer: Valerie King

The authors clearly describe models of optical networks and prove several upper and lower bounds, using a broad range of techniques. They also pose some good open problems. An optical network consists of wavelength routers and endnodes, pairwise connected by links. Each link can support several signals, provided that each signal has a distinct wavelength. Each endnode can transmit any available wavelength. Routers transmit signals on the same wavelength on which they are received. A nonreconfigurable network contains routers that, for each input port and each wavelength, transmit onto a fixed set of output ports. Reconfigurable networks may also contain routers whose input/ output pattern can be dynamically reconfigured. This paper considers networks in which the routers' pattern can depend on wavelength, and ones in which they cannot. Reconfigurable routers are of bounded degree, while nonreconfigurable routers may not be. A routing scheme is oblivious if it always uses the same wavelength to satisfy a given connection request; it is partially oblivious if the wavelength must be chosen from a subset of available wavelengths. This paper proves bounds on the number of wavelengths needed for oblivious, nonoblivious, and partially oblivious wide-sense nonblocking permutation routing for nonreconfigurable networks. For reconfigurable networks, bounds are given on the number of routers needed, with the number of wavelengths as a parameter. Finally, the paper considers the problem of determining the number of wavelengths needed to implement any routing scheme for any network, as a function of the congestion and dilation of that network.