Routing to reduce the cost of wavelength conversion |
| |
Authors: | Thomas Erlebach Stamatis Stefanakos |
| |
Institution: | a Department of Computer Science, University of Leicester, Leicester LE1 7RH, United Kingdom b Computer Engineering and Networks Laboratory, ETH Zürich, CH-8092 Zürich, Switzerland |
| |
Abstract: | We consider all-optical networks that use wavelength-division multiplexing and employ wavelength conversion at specific nodes in order to maximize their capacity usage. We investigate the effect of allowing reroutings on the number of necessary wavelength converters. We disprove a claim of Wilfong and Winkler G. Wilfong, P. Winkler, Ring routing and wavelength translation, in: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’98, 1998, pp. 333-341] according to which reroutings do not have any effect on the number of necessary wavelength converters on bidirected networks. We show that there exist (bidirected) networks on n nodes that require Θ(n) converters without reroutings, but only O(1) converters if reroutings are allowed. We also address the cases of undirected networks and networks with shortest-path routings. In each case, we resolve the complexity of computing optimal placements of converters. |
| |
Keywords: | Graph algorithms Path coloring Sufficient set Optical networks Wavelength assignment |
本文献已被 ScienceDirect 等数据库收录! |
|