Heuristic Methods for the Shared Backup Path Protection Problem – Københavns Universitet

Heuristic Methods for the Shared Backup Path Protection Problem

Master thesis defence by Jørgen Thorlund Haahr

Abstract:

Protecting communication networks against failures is becoming increasingly important as they become a more and more integrated part of our society. Cable failures are common on a communication network even though a lot of eff ort is put into physical protection. Such failures can usually be repaired within several hours and manual rerouting of disconnected communications can be done in less time.

Network services can recover from failures if it is restored within a few seconds but the outage has societal impacts if it lasts longer than a couple of minutes.

It is argued in this thesis that Shared Backup Path Protection (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 in order to recover from failures quickly and efficiently. It is proved in this thesis that the SBPP problem is NP-Hard and heuristic algorithms are developed to solve the SBPP problem. Some considerations and consequences of greedy approaches are described. Benchmark results show that the developed heuristic algorithms are able to find good quality solutions within few minutes. A solution gap of less than 4% was achieved in 4 of 7 cases and less than 19% for the other cases. This is very satisfying considering that the lower bounds are relaxed and found heuristically.

Good results are also obtained when considering a more realistic non-linear cost function.

Examiner:

Martin Zachariasen, DIKU

Censor:

Jesper Larsen, DTU Management