Survivable Logical Topology Mapping under Multiple Constraints in IP-over-WDM Networks

Abstract

The survivable logical topology mapping problem in an IP-over-WDM network deals with the cascading effect of link failures from the bottom (physical) layer to the upper (logical) layer. Multiple logical links may get disconnected due to a single physical link failure, which may cause the disconnection of the logical network. Here we study survivability issues in IP-over-WDM networks with respect to various criteria.

We first give an overview of the two major lines of pioneering works for the survivable design problem. Though theoretically elegant, the first approach which uses Integer Linear Programming (ILP) formulations suffers from the drawback of scalability. The second approach, the structural approach, utilizes the concept of duality between circuits and cutsets in a graph and is based on an algorithmic framework called Survivable Mapping Algorithm by Ring Trimming (SMART). Several SMART-based algorithms have been proposed in the literature.

In order to generate the survivable routing, the SMART-based algorithms require the existence of disjoint lightpaths for certain groups of logical links in the physical topology, which might not always exist. Therefore, we propose in Chapter 4 an approach to augment the logical topology with new logical links to guarantee survivability. We first identify a logical topology that admits a survivable mapping against one physical link failure. We then generalize these results to achieve augmentation of a given logical topology to survive multiple physical link failures.

We propose in Chapter 5 a generalized version of SMART-based algorithms and introduce the concept of robustness of an algorithm which captures the ability of the algorithm to provide survivability against multiple physical link failures. We demonstrate that even when a SMART-based algorithm cannot be guaranteed to provide survivability against multiple physical link failures, its robustness could be very high.

Most previous works on the survivable logical topology design problem in IP-over-WDM networks did not consider physical capacities and logical demands. In Chapter 6, we study this problem taking into account logical link demands and physical link capacities. We define weak survivability and strong survivability in capacitated IP-over-WDM networks. Two-stage Mixed-Integer Linear Programming (MILP) formulations and heuristics to solve the survivable design problems are proposed. Based on the 2-stage MILP framework, we also propose several extensions to the weakly survivable design problem, considering several performance criteria. Noting that for some logical networks a survivable mapping may not exist, which prohibits us from applying the 2-stage MILP approach, our first extension is to augment the logical network using an MILP formulation to guarantee the existence of a survivable routing. We then propose approaches to balance the logical demands satisfying absolute or ratio-weighted fairness. Finally we show how to formulate the survivable logical topology design problem as an MILP for the multiple failure case.

We conclude with an outline of two promising new directions of research.