Approximation algorithm for minimum cost flow allocation with varied survivability

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