Enhancement of multiple routing configurations based on graph augmentation approach and its performance analysis

The seamless transmission of real-time traffic flows in IP networks in case of network failures is of great importance to meet the stringent timing requirements. Multiple Routing Configurations (MRC) is a mechanism which efficiently provides alternative routes against link/node failures in a network. This mechanism creates virtual topologies (VT) which have the same graph as the physical topology, whose link weights are intelligently selected and which provide protection for different failure scenarios, and then computes a separate routing table for each VT. When a failure is detected, the affected traffic flows is started to be transmitted using the routing table that provides protection against the failure. The selection of a large quantity by the network operator as the number of VTs to be generated by MRC increases the probability of a successful termination of the algorithm, while negatively affecting the computational complexity and the amount of network resources to be consumed. Thus, ensuring the success of MRC even if the number of VTs to be generated is selected to be a small quantity is crucial. In this thesis, a graph augmentation approach enhancing the graph connectivity by intelligently adding new links to the physical topology graph, and hence significantly improving the performance of MRC is presented. The performance analysis realized by using synthetic and real network topologies shows that the proposed approach significantly enhances the performance of MRC.