Strictly nonblocking WDM cross-connects

Using wavelength division multiplexing (WDM) technology, an optical network can route multiple signals simultaneously along a single optical fiber by encoding each signal on its own wavelength. If the network contains places where multiple fibers connect together and signals are allowed to be moved from any of the incoming fibers to any of the outgoing fibers, then the network is said to contain cross-connects. More precisely, a k(1) x k(2) WDM cross-connect has k(1) input fibers and k(2) output fibers. Each of the k(1) input fibers supports the same n(1) input wavelengths and each of the k(2) output fibers supports the same n(2) output wavelengths. Since a signal on input wavelength. can be routed from its input fiber to an output fiber such that it arrives on the output fiber using wavelength gamma, where lambda not equal gamma, the cross- connect must be capable of performing wavelength conversion. Along any fiber in the cross- connect a device called a wavelength interchanger can be inserted to perform wavelength conversion. In other words if the path of a signal from an input fiber to an output fiber passes through a wavelength interchanger, then the wavelength of the signal can be changed to any wavelength that is not already in use along the fiber leaving the wavelength interchanger. Given the high cost of wavelength interchangers, the overall cost of a k(1) x k(2) WDM cross- connect is minimized by reducing the number of wavelength interchangers in the cross- connect. However, a desirable property for a cross- connect C is for C to always be able to provide a route ( and wavelength conversion) for any valid demand from any pair of input and output fibers regardless of the routes of other demands currently routed in C. If C has this capability then it is said to be strictly nonblocking. For most of this paper we consider a demand to be a request for a connection from an input fiber to an output fiber such that the connection starts on a specified input wavelength and leaves the cross- connect on a second specified wavelength. Using this demand model, we consider cross- connects for which k1 is not necessarily equal to k2 and the number n1 of supported input wavelengths can differ from the number n2 of supported output wavelengths. Without loss of generality we assume that k(1)