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
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.