Minimum cost ring survivability in WDM networks

In a recent paper [10], Modiano et. al. introduced the notion of survivable routing and established a necessary and sufficient condition for the existence survivable routes for a given logical topology in a physical topology. In two of our earlier papers we have shown that the survivability problem is NP-complete, both when the nodes of the logical topology are unlabeled [14] or labeled [15]. In those papers we have also given algorithms to test if survivable routing of a logical ring is possible in a WDM network with arbitrary physical topology. In this paper we address the following question: What is the minimum number of links that has to be added to a physical topology so that the survivable routing of a logical ring is possible? In this paper we show that not only is this problem NP-complete, an epsilon-approximation algorithm for the problem cannot be found unless P = NP We provide an ILP formulation for finding the optimal solution of the problem. In addition, we also provide an approximate solution of the problem. The approximate algorithm requires only a very small fraction of the time required by the optimal algorithm but produces results that are close to the optimal solution on two test networks ARPANET and the Italian National Network.