2nd International ICST Conference on Broadband Networks

Research Article

On computing disjoint paths with dependent cost structure in optical networks

  • @INPROCEEDINGS{10.1109/ICBN.2005.1589610,
        author={Ajay Todimala and Byrav Ramamurthy and N. V. Vinodchandran},
        title={On computing disjoint paths with dependent cost structure in optical networks},
        proceedings={2nd International ICST Conference on Broadband Networks},
        publisher={IEEE},
        proceedings_a={BROADNETS},
        year={2006},
        month={2},
        keywords={},
        doi={10.1109/ICBN.2005.1589610}
    }
    
  • Ajay Todimala
    Byrav Ramamurthy
    N. V. Vinodchandran
    Year: 2006
    On computing disjoint paths with dependent cost structure in optical networks
    BROADNETS
    IEEE
    DOI: 10.1109/ICBN.2005.1589610
Ajay Todimala1,*, Byrav Ramamurthy1,*, N. V. Vinodchandran1,*
  • 1: Department of Computer Science and Engineering, University of Nebraska-Lincoln, Lincoln NE 68588-0115 U.S.A.
*Contact email: ajayt@cse.unl.edu, byrav@cse.unl.edu, vinod@cse.unl.edu

Abstract

Providing fault tolerance against network failures in an optical WDM network is of prime importance. In this work we study the problem of computing optimal disjoint paths for providing shared protection in fully wavelength-convertible networks. We introduce and formalize the concept of dependent cost structure of a protection path on its working path and current network status. We formulate the problem of computing optimal disjoint paths for providing shared protection in fully wavelength-convertible networks as the problem of computing least-cost disjoint paths with dependent cost structure (LDP-DCS). We prove that LDP-DCS is NP-complete and is also hard to approximate. We present an iterative modified network-flow heuristic for the problem. We provide an approach to measure the optimality of the solution computed by the heuristic. Simulation results demonstrate the superior performance of our proposed heuristic in comparison to earlier heuristic approaches which did not consider the dependent cost structure.