Premium
Wavelength allocation on trees of rings
Author(s) -
Deng Xiaotie,
Li Guojun,
Zang Wenan
Publication year - 2000
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/1097-0037(200007)35:4<248::aid-net2>3.0.co;2-9
Subject(s) - wavelength division multiplexing , tree (set theory) , wavelength , computer science , node (physics) , bandwidth (computing) , set (abstract data type) , mathematics , algorithm , computer network , combinatorics , optics , physics , programming language , quantum mechanics
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.5 w opt wavelengths, where w opt 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.