On shortest-path all-optical networks without wavelength conversion requirements

Abstract

In all-optical networks with wavelength division multiplexing, every connection is routed along a certain path and assigned a wavelength such that no two connections use the same wavelength on the same link. For a given set $calP$ of paths (a routing), let $chi(calP)$ denote the minimum number of wavelengths in a valid wavelength assignment and let $L(P)$ denote the maximum link load. We always have $L(calP)le chi(calP)$. Motivated by practical concerns, we consider routings containing only shortest paths. We give a complete characterization of undirected networks for which any set $calP$ of shortest paths admits a wavelength assignment with $L(calP)$ wavelengths. These are exactly the networks that do not benefit from the use of (expensive) wavelength converters if shortest-path routing is used. We also give an efficient algorithm for computing a wavelength assignment with $L(calP)$ wavelengths in these networks.