Heuristic methods for shared backup path protection planning
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
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 language | English |
---|---|
Title of host publication | 2012 4th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT) |
Number of pages | 7 |
Publisher | IEEE |
Publication date | 2012 |
Pages | 712-718 |
ISBN (Print) | 978-1-4673-2016-0 |
DOIs | |
Publication status | Published - 2012 |
Event | 4th International Congress on Ultra Modern Telecommunications and Control Systems - Sankt Petersborg, Russian Federation Duration: 3 Oct 2012 → 5 Oct 2012 Conference number: 4 |
Conference
Conference | 4th International Congress on Ultra Modern Telecommunications and Control Systems |
---|---|
Nummer | 4 |
Land | Russian Federation |
By | Sankt Petersborg |
Periode | 03/10/2012 → 05/10/2012 |
- computational complexity, heuristic programming, optimisation, telecommunication cables, telecommunication network planning, telecommunication network reliability, NP-hard optimization problem, SBPP, automatic protection schemes, communication network protection, heuristic method, shared backup path protection planning, single cable failure, Benchmark testing, Cooling, Heuristic algorithms, Maintenance engineering, Planning, Simulated annealing, Temperature
Research areas
ID: 45047257