Heuristic methods for shared backup path protection planning

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

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-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. The SBPP problem 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 more than half of the benchmark instances (and a gap of less than 12% for the remaining instances.)
    Original languageEnglish
    Title of host publicationProceedings of RNDM 2012 - 4th International Workshop on Reliable Networks Design and Modeling, co-located with ICUMT 2012 Conference
    PublisherIEEE
    Publication date2012
    Pages712-718
    ISBN (Print)978-1-4673-2016-0, 978-1-4673-2017-7
    DOIs
    Publication statusPublished - 2012
    Event4th International Congress on Ultra Modern Telecommunications and Control Systems (ICUMT 2012) - St. Petersburg, Russian Federation
    Duration: 3 Oct 20125 Oct 2012
    http://icumt.org/2012/

    Conference

    Conference4th International Congress on Ultra Modern Telecommunications and Control Systems (ICUMT 2012)
    CountryRussian Federation
    CitySt. Petersburg
    Period03/10/201205/10/2012
    Internet address

    Bibliographical note

    This peer-reviewed full text paper was presented at RNDM 2012 - 4th International Workshop on Reliable Networks Design and Modeling, co-located with ICUMT 2012 Conference

    Keywords

    • Benchmark testing
    • Cooling
    • Heuristic algorithms
    • Maintenance engineering
    • Planning
    • Simulated annealing
    • Temperature

    Fingerprint Dive into the research topics of 'Heuristic methods for shared backup path protection planning'. Together they form a unique fingerprint.

    Cite this