Samer Lahoud, Géraldine Texier, and Laurent Toutain (2006)
Approximation algorithm for minimum cost flow allocation with varied survivability
In: 2nd Conference on Next Generation Internet Design and Engineering, NGI '06, Valencia, Spain, pages 8 pp. -299.
In this work, we study the minimum cost flow allocation
problem with varied survivability. Given a set of demands
and a capacitated network, the problem consists of
allocating each demand to a set of primary paths that carry
the flows realizing the demand volume in the normal
operation mode. To ensure survivability, bandwidth is
allocated over a disjoint set of backup links protecting
the primary path. With the varied survivability concept,
only a varied portion of the primary flow is guaranteed to
be recovered in failure situations. The recovery ratio is
predefined for a given demand and denotes the guaranteed
quality of protection. We associate a unitary cost for
using the installed bandwidth in core links. Thus, the
problem provides a minimum cost solution for allocating the
demands and ensuring their survivability. The main
contribution of this paper is a new approximation algorithm
using a primal-dual approach. This approximation algorithm
computes a solution that is within a guaranteed factor of
the optimal one and runs in time polynomial in the problem
size