On computing disjoint paths with dependent cost structure in optical networks

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.