Divide and conquer for fast SRLG disjoint routing

Kun Xie, Heng Tao, Xin Wang, Gaogang Xie, Jigang Wen, Jiannong Cao, Zheng Qin

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

1 Citation (Scopus)

Abstract

Ensuring transmission survivability is a crucial problem for high-speed networks. Path protection is a fast and capacity-efficient approach for increasing the availability of end to end connections. The emerging SDN infrastructure makes it feasible to provide diversity routing in a practical network. For more robust path protection, it is desirable to provide an alternative path that does not share any risk resource with the active path. We consider finding the SRLG-Disjoint paths, where a Shared Risk Link Group (SRLG) is a group of network links that share a common physical resource whose failure will cause the failure of all links of the group. Since the traffic is carried on the active path most of time, it is useful that the weight of the shorter path of the disjoint path pair is minimized, and we call it Min-Min SRLG-Disjoint routing problem. The key issue faced by SRLG-Disjoint routing is the trap problem, where the SRLG-disjoint backup path (BP) can not be found after an active path (AP) is decided. Based on the min-cut of the graph, we design an efficient algorithm that can take advantage of existing search results to quickly look for the SRLG-Disjoint path pair. Our performance studies demonstrate that our algorithm can outperform other approaches with a higher routing performance while also at a much faster speed.

Original languageEnglish
Title of host publicationProceedings - 48th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages622-633
Number of pages12
ISBN (Electronic)9781538655955
DOIs
Publication statusPublished - 19 Jul 2018
Event48th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2018 - Luxembourg City, Luxembourg
Duration: 25 Jun 201828 Jun 2018

Publication series

NameProceedings - 48th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2018

Conference

Conference48th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2018
Country/TerritoryLuxembourg
CityLuxembourg City
Period25/06/1828/06/18

Keywords

  • Max-Flow Min-Cut Theorem
  • Shared Risk Link Groups (SRLG)
  • SRLG Disjoint Routing

ASJC Scopus subject areas

  • Safety, Risk, Reliability and Quality
  • Computer Networks and Communications
  • Hardware and Architecture
  • Energy Engineering and Power Technology

Cite this