Routing Algorithms In Survivable Telecommunication Networks

The aim of the dissertation is to present effective routing algorithms in survivable mesh communication networks that meet several Quality-of-Service requirements. The thesis first investigates shared path protection (SPP) in mesh telecommunication networks. Two novel heuristic algorithms are proposed for SPP based on problem decomposition and linear algebra. Shared Segment Protection (SSP) is the second topic investigated. SSP is formulated as an integer linear program, which can be used to derive the optimal solution for small problem instances. Finally, the thesis presents possible shared protection implementations for networks with distributed control planes. A new algebraic approach is proposed to measure the performance of different distributed architectures. All the algorithms and solutions are designed for the switches of the future survivable mesh telecommunication networks considering QoS requirements. Most of the simulation tools and heuristic algorithms used in the dissertation are part of the lemon- routing package and available on-line. The obtained results are supported by 8 journal papers and 18 conference presentations.