Logical topology augmentation for guaranteed survivability under multiple failures in IP-over-WDM optical networks

The survivable logical topology mapping problem in an IP-over-WDM optical network is to map each link (u,v)(u,v) in the logical topology (at the IP layer) into a lightpath between the nodes uu and vv in the physical topology (at the optical layer) such that failure of a single physical link does not cause the logical topology to become disconnected. Kurant and Thiran (2007) [8] presented an algorithmic framework called SMART that involves successive contracting of circuits in the logical topology and mapping the logical links in the circuits into edge-disjoint lightpaths in the physical topology. In a recent work from Thulasiraman et al. (2009) [11] a dual framework involving cutsets was presented and it was shown that both these frameworks possess the same algorithmic structure. Algorithms CIRCUIT-SMART, CUTSET-SMART and INCIDENCE-SMART were also presented in [11]. All these algorithms suffer from one important shortcoming, namely, disjoint lightpaths for certain groups of logical links may not exist in the physical topology. Therefore, in such cases, we will have to augment the logical topology with new logical links to guarantee survivability. In this paper we address this augmentation problem. We first identify a logical topology that admits a survivable mapping under a physical link failure as long as the physical topology is 3-edge connected. We show how to embed this logical topology on a given logical topology so that the augmented topology admits a survivability mapping as long as the physical topology is 3-edge connected. We then generalize these results to achieve augmentation for survivability of a given logical topology under multiple physical link failures. Finally, we define the concept of survivability index of a mapping. We provide simulation results to demonstrate that even when certain requirements of the generalized augmentation procedure are relaxed, our approach will result in mappings that achieve a high survivability index.