Evaluating the network survivability issue of k-best paths through graph theoretic techniques

Abstract

In this thesis graph theoretic techniques are adopted for addressing the network survivability issue of disjoint paths selection. The evaluation was conducted after the implementation of a solver that produces a solution of the problem after successive application of two algorithms on any given topology, the algorithm of Louca et al [19] and Castanon’s [8]. The first algorithm transforms any networks into a trellis graph and the second exploits the special structure of the trellis graph and solves for the k-best paths using the minimum cost network flow (MCNF) algorithm. The transformation and evaluation of the K-best paths solution is illustrated for a number of topologies through the graphical user interface adapted from [37]. It is also contrasted with the k-successive approximation methods, which cannot guarantee the selection of the K-best paths, due to the successive removal of shortest paths at each iteration. Furthermore, the performance of the algorithm and its time complexity are investigated and also compared with Surballe’s Disjoint Pair Algorithm [31]. Even though the trellis transformations algorithm can find all possible disjoint paths in the vast majority of cases, pathological situations where the algorithm may fail is also identified in the thesis, analysed, and a solution is provided and evaluated.