Two-stage cut saturation algorithm for designing all-optical networks

Gaoxi Xiao*, Yiu Wing LEUNG, Kwok Wah Hung

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

20 Citations (Scopus)


In this paper, 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 it has 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.

Original languageEnglish
Pages (from-to)1102-1115
Number of pages14
JournalIEEE Transactions on Communications
Issue number6
Publication statusPublished - Jun 2001

Scopus Subject Areas

  • Electrical and Electronic Engineering

User-Defined Keywords

  • All-optical networks
  • Cut saturation method
  • Network design
  • Routing and wavelength assignment
  • Wavelength-division multiplexing


Dive into the research topics of 'Two-stage cut saturation algorithm for designing all-optical networks'. Together they form a unique fingerprint.

Cite this