Heuristic methods for single link shared backup path protection

Jørgen Thorlund Haahr, Thomas Riis Stidsen, Martin Zachariasen

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    Protecting communication networks against failures is becoming increasingly important as they have become an integrated part of our society. Cable failures are fairly common, but it is unacceptable for a single cable failure to disconnect communication for more than a few seconds—hence protection schemes are employed. In contrast to manual intervention, automatic protection schemes such as shared backup path protection (SBPP) can recover from failure quickly and efficiently. SBPP is a simple but efficient protection scheme that can be implemented in backbone networks with technology available today. In SBPP backup paths are planned in advance for every failure scenario in order to recover from failures quickly and efficiently. Planning SBPP is an NP-hard optimization problem, and previous work confirms that it is time-consuming to solve the problem in practice using exact methods.We present heuristic algorithms and lower bound methods for the SBPP planning problem. Experimental results show that the heuristic algorithms are able to find good quality solutions in minutes. A solution gap of less than 3.5 % was achieved for 5 of 7 benchmark instances (and a gap of less than 11 % for the remaining instances.)
    Original languageEnglish
    JournalJournal of Heuristics
    Volume20
    Issue number5
    Pages (from-to)539-560
    ISSN1381-1231
    DOIs
    Publication statusPublished - 2014

    Keywords

    • Network survivability
    • Shared backup path protection
    • Heuristics algorithms
    • Upper and lower bounds methods
    • Protection capacity minimization

    Cite this