Ring routing and wavelength translation

Abstract

Let G be the digraph consisting of two oppositely-directed rings on the same set of n nodes. We provide a polynomialtime algorithm which, given a list of demands---each requiring a path from a specified source node to a specified target node---routes the demands so as to minimize the largest number of paths through any of the 2n directed links of G. The algorithm makes use of a partial linear relaxation and rounding technique which together, somewhat surprisingly, produce an exact solution. The problem arises in an optical communications network with wavelength division multiplexing (WDM), configured as a ring. Such a network features a fixed number of wavelengths, each of which (at the optical level) can support a single path of high bandwidth through a given link. If there is no "wavelength translation" available, so that each demand is restricted to a single wavelength, then the combined routing and wavelength assignment problem is NPcomplete. Our results imply, however, that the p...