Wavelength allocation on trees of rings

We consider a problem that arises from communication in all-optical network s. Data are transmitted from source nodes to destination nodes via fixed ro utes. The high bandwidth of the optic fiber allows for wavelength-division multiplexing so that a single physical optical link can carry several logic al signals of different wavelengths. The problem is to carry out a set of r equests using a limited number of wavelengths so that different routes usin g the same wavelength never use the same physical link. We focus on trees o f rings which are constructed as follows: Start from a tree and replace eac h node of the tree by a cycle. Each edge in the tree corresponds to the cor responding cycles sharing a common node. We design an approximation algorit hm that routes any set of requests on the tree of rings using no more than 2.5w(opt) wavelengths, where w(opt) is the minimum possible number of wavel engths for that set of requests. This improves a 3-approximation solution o f Raghavan and Upfal. (C) 2000 John Wiley & Sons, Inc.