"Cross-Layer Survivability in a Layered Network"by Prof. KT

An IP-over-WDM optical network is an example of a layered network. In this network, the grapah representing the optical network is called the physical topology G_P and the graph representing the IP layer is called the logical topology G_L.  Without loss of generality, we assume that  G_L has the same set of nodes as G_P . Each logical link (i,j) is associated with a path incurrent  connecting the nodes i and j. Such a path is called a lightpath.  The survivable logical topology mapping problem in a layered network is to map each link (u, v) in the logical topology into a lightpath between the nodes u and v in the physical topology 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. This mapping problem also arises in other areas of applications such as the problem of mapping a parallel program onto a multiprocess system, though the constraints there are of a different type.

For the survivable logical mapping problem, two lines of investigations have been pursued in the literature: mathematical programming based approach  pioneered by Modiano et al., and the structural approach pioneered by Kurant and Thiran.  Kurant and Thiran presented an algorithmic framework called SMART that involves successively contracting 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, we presented a dual framework involving cutsets and showed that both these frameworks possess the same algorithmic structure. In a series of papers, we have developed several versions of this framework with varying degrees of robustness in providing survivability against multiple failures. We have also  investigated several issues related to the sturctural survivability of logical topology, as well as augmenting a logical topology with additional links that guarantees the existence of a survivable mapping. In this lecture we will present  a review of these results and some of our research directions in this area.