Novel survivable logical topology routing by logical protecting spanning trees in IP-over-WDM networks

Zhili Zhou, Tachun Lin, Krishnaiyan Thulasiraman, Guoliang Xue

Research output: Contribution to journalArticlepeer-review

18 Scopus citations


The survivable logical topology mapping (routing) problem in IP-over-wavelength-division multiplexing networks is to map each link in the logical topology (IP layer) onto a lightpath in the physical topology (optical layer), such that failure of a physical link does not cause the logical topology to become disconnected. In this paper, we propose a novel approach based on the concept of protecting spanning tree set of the logical topology. We present necessary and sufficient conditions based on this concept and study three optimization problems with varying degrees of difficulty. We study a generalized logical routing problem with the objective to protect the logical topology against maximal number of physical link failures. The new problem aims to find a survivable routing if one exists, or achieve maximal protection of physical link failures otherwise. We also show that the problem is equivalent to the minimum dominating set problem in bipartite graphs. We discuss how one can use the column generation technique to speed up the execution of this formulation, which obviates the need to find all spanning trees at the beginning of the execution of this formulation. In addition, we also present which has several nice features a heuristic approach, which incorporates a method to augment the logical topology with additional links to guarantee a survivable routing, which only requires a shortest path algorithm and an algorithm to generate an appropriate spanning tree. We provide the results of extensive simulations conducted to evaluate our formulations and demonstrate the effectiveness of our new approach.

Original languageEnglish (US)
Article number7831473
Pages (from-to)1673-1685
Number of pages13
JournalIEEE/ACM Transactions on Networking
Issue number3
StatePublished - Jun 2017


  • Column generation technique
  • Cross-layer survivability
  • IP-over-WDM optical networks
  • Protecting spanning tree set
  • Survivable logical topology routing

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Novel survivable logical topology routing by logical protecting spanning trees in IP-over-WDM networks'. Together they form a unique fingerprint.

Cite this