Circuits/Cutsets Duality and a Unified Algorithmic Framework for Survivable Logical Topology Design in IP-over-WDM Optical Networks

Given a logical topology G_L and a physical topology G, the survivable logical topology design problem in an IP-over- WDM optical network is to map the logical links into lightpaths in G such that G_L remains connected after the failure of any edge in G. In view of its fundamental nature and its practical importance, this problem has received considerable attention in the literature. The SMART algorithmic framework based on the circuits in G_L is a novel and very significant contribution to this problem. Taking advantage of the dual relationship between circuits and cutsets in a graph, we first present in this paper the primal algorithm CIRCUIT-SMART (similar to SMART) and algorithm CUTSET-SMART that is dual of CIRCUIT-SMART and proofs of correctness of these algorithms. To guarantee survivability we add additional logical links called protection edges, if necessary. This investigation has provided much insight into the structural properties of solutions to this problem and the structure of survivable logical graphs. Specifically, we present a highly simplified version of CUTSET-SMART that always provides a survivable mapping as long as G is 3-edge connected, and a survivable logical topology structure. We also present algorithm INCIDENCE-SMART that uses incidence sets that are special cases of a cut. Two efficient heuristics, one based on maximum matching theory and the other based on both the primal and dual algorithms are also presented. Simulation results comparing the different algorithms in terms of computational time, protection capacity and survivability success rate are also presented.