Abstract

Survivable network design has become increasingly important due to the need for reliable communication service. One of its important components is the spare capacity design. Its main purpose is to provide cost-efficient spare capacity reservation at certain survivability level in case of predicted failures. In this thesis, we study various kinds of network survivability techniques and the corresponding algorithms. Subsequently; we introduce our two pre-planned path restoration algorithms for spare capacity design in mesh-like networks. They can get higher utilization of spare capacity and reasonable reaction time. First one is a spanning tree based algorithm with backup parents, which needs much less spare capacity than the well known hierarchical tree algorithm while the restorability is slightly higher or lower. The second algorithm is a cycle tree based algorithm with backup parents and some extra cycle edges. Simulation results show that this algorithm works much better on restorability than the other two algorithms. The time complexities of the two new algorithms are: O ( n 4 ), where n is the total number of nodes in the network. The space complexities are the same too: O ( n 3 )