Ring-mesh topology design in a SONET-WDM network

Youngjin Kim, Youngho Lee, Junghee Han

Research output: Contribution to journalArticlepeer-review


This article deals with a ring-mesh network design problem arising from the deployment of an optical transport network. The problem seeks to partition the set of demand pairs to a number of rings and a mesh cluster, and to determine the location of the optical cross-connect system (OXC), while minimizing the total cost of optical add-drop multiplexers (OADMs), OXCs, and fiber links. We formulate this problem as a zero-one integer programming problem. In strengthening the formulation, we develop some valid inequalities for the zero-one quadratic (knapsack) polytope and a column generation formulation that eliminates the symmetry of ring configurations. Also, we prescribe an effective tabu search procedure for finding a good quality feasible solution, which is also used as a starting column for the column generation procedure. Computational results show that the proposed solution procedure provides tight lower and upper bounds within a reasonable time bound.

Original languageEnglish
Pages (from-to)43-53
Number of pages11
JournalPhotonic Network Communications
Issue number1
Publication statusPublished - 2010 Aug


  • Column generation
  • Integer programming
  • Optical transport network
  • Ring-mesh topology
  • Tabu search
  • Valid inequality

ASJC Scopus subject areas

  • Software
  • Atomic and Molecular Physics, and Optics
  • Hardware and Architecture
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Ring-mesh topology design in a SONET-WDM network'. Together they form a unique fingerprint.

Cite this