Robustness of logical topology mapping algorithms for survivability against multiple failures in an IP-over-WDM optical network

The survivable logical topology mapping (SLTM) problem in an IP-over-WDM optical network is to map each link (u, v) in the logical topology G_L (at the IP layer) into a lightpath between the nodes u and v in the physical topology G_P (at the optical layer) such that failure of a physical link does not cause the logical topology to become disconnected. It is assumed that both the physical and logical topologies are 2-edge connected. There are two lines of approach for the study of the SLTM problem. One approach uses Integer Linear Programming formulations. The main drawback with this approach is the use of exponential number of constraints, one for each cutset in G_L. Moreover, it does not provide insight into the solution when survivability against multiple physical failures is required. The other approach, called the structural approach, uses graph theory and was pioneered by Kurant and Thiran and further generalized by us. In this paper we first present a generalized algorithmic framework for the SLTM problem. This framework includes several other frameworks considered in earlier works as special cases. We then define the concept of robustness of a mapping algorithm which captures the ability of the algorithm to provide survivability against multiple physical failures. This is similar to the concept of fault coverage used in hardware/software testing. We analyse the different frameworks for their robustness property. Using simulations, we demonstrate that even when an algorithm cannot be guaranteed to provide survivability against multiple failures, its robustness could be very high. The work also provides a basis for the design of survivability mapping algorithms when special classes of failures such as SRLG failures are to be protected against.