Institute of Information Science, Academia Sinica



Press Ctrl+P to print from browser


Cross-Layer Survivability in a Layered Network

  • LecturerProf. Krishnaiyan Thulasiraman (School of Computer Science University of Oklahoma)
    Host: Dr. Wen-Lian Hsu
  • Time2011-07-13 (Wed.) 10:30 – 12:00
  • LocationAuditorium 101 at new IIS Building

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 GP and the graph representing the IP layer is called the logical topology GL.  Without loss of generality, we assume that  GL  has the same set of nodes as GP . Each logical link (i,j) is associated with a path in GP 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: one pioneered by Modiano etal., and the other pioneered by Kurant and Thiran.  Since then there has been a great deal of research on this problem. 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. Algorithms CIRCUIT-SMART, CUTSET-SMART, CUTSET-SMART-SIMPLIFIED and INCIDENCE-SMART were also presented in our work.  Effectiveness of both these frameworks as well as their robustness in providing survivability against multiple failures depends on the lengths of the cutset cover and circuit cover sequences on which they are based. In subsequent works we 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 of the logical topology as long as the physical topology is 3-edge connected. In this lecturewe will preent these results and recent advances in this area.