| Abstract | We describe the optimization problem associ-ated with the concurrent routing of demands with guar-
anteed shared recovery in case of network failures. This
problem arises in routing with protection in meshes and is
known to be hard. We describe the problem in the context
of the efficient design of restorable MP S tunnels in optical
networks. The underlying design gives rise to a stochastic
optimization problem that is equivalent to a (very) large-
scale linear programming (LP) problem that explicitly in-
corporates the network failure scenarios. The feasible re-
gion for this LP is given by combined packing and cover-
ing constraints for concurrent and optimal multicommodity
flows. We develop a novel -approximation procedure for
this problem and demonstrate its performance for a variety
of real network sizes. An attraction of our approach is that
its main computation consists of routing flow along a pair
of short paths and these paths are easily found. Commer-
cial general-purpose LP solvers are typically unable to solve
these problems once they become large enough, while our
approach scales for large networks. We conclude that the
proposed scheme provides guaranteed approximation to the
design of restorable MP S tunnels with shared protection
within realistic network settings.
|
