Circuits/cutsets duality and a unified algorithmic framework for survivable logical topology design in IP-over-WDM optical networks

Krishnaiyan Thulasiraman, Muhammad S. Javed, Guoliang Xue

Research output: Chapter in Book/Report/Conference proceedingConference contribution

43 Scopus citations


Given a logical topology GL and a physical topology G, the survivable logical topology design problem in an IP-over-WDM optical network is to map the logical links into lightpaths in G such that GL remains connected after the failure of any edge in G. In view of its fundamental nature and its practical importance, this problem has received considerable attention in the literature. The SMART algorithmic framework based on the circuits in GL is a novel and very significant contribution to this problem. Taking advatange of the dual relationship between circuits and cutsets in a graph, we first present in this paper the primal algorithm CIRCUIT-SMART (similar to SMART) and algorithm CUTSET-SMART that is dual of CIRCUIT-SMART and proofs of correctness of these algorithms. To guarantee survivability we add additional logical links called protection edges, if necessary. This investigation has provided much insight into the structural properties of solutions to this problem and the structure of survivable logical graphs. Specifically, we present a highly simplified version of CUTSET-SMART that always provides a survivable mapping as long as GL is 3-edge connected, and a survivable logicl topology structure. We also present algorithm INCIDENCE-SMART that uses incidence sets that are special cases of a cut. Two efficient heuristics, one based on maximum matching theory and the other based on both the primal and dual algorithms are also presented. Simulation results comparing the different algorithms in terms of computational time, protection capacity and survivability success rate are also presented.

Original languageEnglish (US)
Title of host publicationIEEE INFOCOM 2009 - The 28th Conference on Computer Communications
Number of pages9
StatePublished - 2009
Event28th Conference on Computer Communications, IEEE INFOCOM 2009 - Rio de Janeiro, Brazil
Duration: Apr 19 2009Apr 25 2009

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


Other28th Conference on Computer Communications, IEEE INFOCOM 2009
CityRio de Janeiro


  • Circuits
  • Cutsets and duality
  • Disjoint paths
  • IP-over-WDM
  • Lightpath routing
  • Survivable networks

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'Circuits/cutsets duality and a unified algorithmic framework for survivable logical topology design in IP-over-WDM optical networks'. Together they form a unique fingerprint.

Cite this