Ring-mesh topology design in a SONET-WDM network

Youngjin Kim, Youngho Lee, Junghee Han

    Research output: Contribution to journalArticlepeer-review

    Abstract

    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
    Volume20
    Issue number1
    DOIs
    Publication statusPublished - 2010 Aug

    Keywords

    • 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

    Fingerprint

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

    Cite this