  We consider protection problems in multilayer networks. In single-layer
networks, a pair of disjoint paths can be used to provide protection for a
source-destination pair. However, this approach cannot be directly applied to
layered networks where disjoint paths may not always exist. In this paper, we
take a new approach which is based on finding a set of paths that may not be
disjoint but together will survive any single physical link failure. First, we
consider the problem of finding the minimum number of survivable paths. In
particular, we focus on two versions of this problem: one where the length of a
path is restricted, and the other where the number of paths sharing a fiber is
restricted. We prove that in general, finding the minimum survivable path set
is NP-hard, whereas both of the restricted versions of the problem can be
solved in polynomial time. We formulate the problem as Integer Linear Programs
(ILPs), and use these formulations to develop heuristics and approximation
algorithms. Next, we consider the problem of finding a set of survivable paths
that uses the minimum number of fibers. We show that this problem is NP-hard in
general, and develop heuristics and approximation algorithms with provable
approximation bounds. Finally, we present simulation results comparing the
different algorithms.
