Wavelength allocation on trees of rings

Abstract

We consider a problem that arises from communication in all-optical networks. Data are transmitted from source nodes to destination nodes via fixed routes. The high bandwidth of the optic fiber allows for wavelength-division multiplexing so that a single physical optical link can carry several logical signals of different wavelengths. The problem is to carry out a set of requests using a limited number of wavelengths so that different routes using the same wavelength never use the same physical link. We focus on trees of rings which are constructed as follows: Start from a tree and replace each node of the tree by a cycle. Each edge in the tree corresponds to the corresponding cycles sharing a common node. We design an approximation algorithm that routes any set of requests on the tree of rings using no more than 2.5wopt wavelengths, where wopt is the minimum possible number of wavelengths for that set of requests. This improves a 3-approximation solution of Raghavan and Upfal. © 2000 John Wiley & Sons, Inc.