| Large bandwidth offered by a single fiber link in optical networks greatly reduces communication costs and makes many traffic intensive applications possible. However, fiber cuts disrupt such applications with disastrous consequences. For this reason, survivability of networks has become a major concern for network service providers. Significant research efforts, both in industry and in academia, are currently underway to address this issue. This research is focused on survivability problems in communication networks.; A new pre-configured protection scheme (p-walk) for heterogeneous networks is proposed. This scheme extends the widely known cycle-based pre-configured protection scheme (e.g., pre-configured cycle or p-cycle) to a heterogeneous network environment. An optimal p-walk can be obtained by computing the metric Hamiltonian path between two specified endpoints. Four polynomial-time approximation algorithms for computing an optimal p-walk with performance bounds of 32 , 75 , and 1511 are presented. These bounds are valid when the weight of each link lies in the interval [c, 2c] for some positive number c.; The survivable routing problem is the problem of mapping a logical network into a physical network such that the failure of any one physical link does not disconnect the logical network. This research investigates two different versions of the problem, one with the knowledge of the structure and the topology of a logical network and one without it. Furthermore, results related to minimum cost augmentation of the physical network to make the logical network survivable are presented. The problem of finding a set of k disjoint paths between a source-destination node pair such that the longest path in the set is shortest among all such sets of paths is known as the shortest-longest disjoint k-path problem. Algorithms and complexity results for the shortest-longest disjoint k-path problem are also presented in this dissertation. |
