Topology-aware fast re-route algorithms for fault tolerant networking

Real-time services in communication networks require a fault tolerant data transmission to support their stringent quality of service requirements. The Internet Engineering Task Force has been working on standardizing IP Fast Re-Route (IPFRR) technologies with a full failure coverage which provide seamless forwarding of IP packets during network failures. Multi Topology Routing based IPFRR (MT-IPFRR) technologies use virtual topologies (VTs) to compute alternate routing tables to recover from failures. In this thesis, we compare the performances of the MT-IPFRR mechanisms, namely, Multiple Routing Configurations (MRC) and Maximally Redundant Trees (MRT). The results show that the alternate path lengths of the MRC are scalable with respect to the network size and density as opposed to the case for the MRT. We also provide an elaborate topological dependency analysis of the MRC. Using our automated topological analysis tool, we discover a significant correlation between the performance of the MRC and the heterogeneity level of a topology, namely, the tendency to have hub nodes, whose degree is much higher than the rest of the network. Inspired by our topological analysis results, we propose heuristic algorithms to reduce the number of VTs used by the MRC to decrease its operational complexity. Finally, we propose a new MT-IPFRR technique leading to selfrecovering Software Defined Networks.