DocumentCode :
1504937
Title :
Two-stage cut saturation algorithm for designing all-optical networks
Author :
Xiao, Gaoxi ; Leung, Yiu-Wing ; Hung, Kwok-Wah
Author_Institution :
Center for Adv. Telecommun. Syst. & Services., Texas Univ., Richardson, TX, USA
Volume :
49
Issue :
6
fYear :
2001
fDate :
6/1/2001 12:00:00 AM
Firstpage :
1102
Lastpage :
1115
Abstract :
We design and optimize the physical topology of all-optical networks. This problem is more challenging than the traditional one for electronic communication networks, because of the wavelength-continuous constraint and it involves routing and wavelength assignment. In this problem, we are given the number of lightpaths required by every node pair and a cost specification, and our objective is to determine a physical topology of minimal cost. We formulate the problem, prove that it is NP-hard, and design an efficient algorithm called two-stage cut saturation algorithm for it. In the first stage, we relax the wavelength-continuous constraint and apply the main idea of the cut saturation method to determine a good initial network. In the second stage, we impose the wavelength-continuous constraint and perform routing and wavelength assignment to establish the specified lightpaths on the initial network. When some lightpaths cannot be established, we apply the main idea of the cut saturation method to optimize the insertion of additional links into the network. Simulation results show the following: (1) the proposed algorithm can efficiently design networks with low costs and high utilization and (2) if wavelength converters are available to support full wavelength conversion, the total cost of the links can be significantly reduced
Keywords :
network topology; optical fibre networks; optical wavelength conversion; optimisation; telecommunication network routing; wavelength division multiplexing; NP-hard problem; WDM networks; all-optical network design; cost specification; efficient algorithm; lightpaths; link cost reduction; network node; physical topology design; physical topology optimisation; routing; simulation results; two-stage cut saturation algorithm; wavelength assignment; wavelength conversion; wavelength converters; wavelength-continuous constraint; Algorithm design and analysis; All-optical networks; Circuit topology; Communication networks; Costs; Design optimization; Network topology; Optimization methods; Wavelength assignment; Wavelength routing;
fLanguage :
English
Journal_Title :
Communications, IEEE Transactions on
Publisher :
ieee
ISSN :
0090-6778
Type :
jour
DOI :
10.1109/26.930640
Filename :
930640
Link To Document :
بازگشت