Efficient routing and wavelength assignment for reconfigurable WDM ring networks with wavelength converters

We consider the problem of wavelength assignment in reconfigurable WDM networks with wavelength converters. We show that for N-node P-port bidirectional rings, a minimum number of /spl lceil/PN/4/spl rceil/ wavelengths are required to support all possible connected virtual topologies in a rearrangeably nonblocking fashion, and provide an algorithm that meets this bound using no more than /spl lceil/PN/2/spl rceil/ wavelength converters. This improves over the tight lower bound of /spl lceil/PN/3/spl rceil/ wavelengths required for such rings given in if no wavelength conversion is available. We extend this to the general P-port case where each node i may have a different number of ports P/sub i/, and show that no more than /spl lceil//spl sigma//sub i/P/sub i//4/spl rceil/+1 wavelengths are required. We then provide a second algorithm that uses more wavelengths yet requires significantly fewer converters. We also develop a method that allows the wavelength converters to be arbitrarily located at any node in the ring. This gives significant flexibility in the design of the networks. For example, all /spl lceil/PN/2/spl rceil/ converters can be collocated at a single hub node, or distributed evenly among the N nodes with min{/spl lceil/P/2/spl rceil/+1,P} converters at each node.