|
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 presence of even a single wavelength translator (at any node) guarantees both full capacity and polynomial-time optimizability. Single-translator sufficiency in the ring is a special case of a simple criterion which, given a set of nodes in an arbitrary WDM network, determines whether wavelength translators on those nodes allow the network to run at maximum capacity. Although the problem of minimizing the cardinality of this set is NP-complete (even in the planar case), the high cost of wavelength translators can be expected to make the criterion a useful tool., |
