Samer Lahoud, Géraldine Texier, and Laurent Toutain (2006)
Flow Allocation with Path Protection in Next Generation Internet Networks
In: IEEE International Conference on Communications, ICC '06, Istanbul, Turkey, pages 860 -865.
In this work, we study the flow allocation problem in Next
Generation Internet (NGI) networks. Given a capacitated
network, flow allocation consists of a simultaneous routing
and bandwidth allocation problem for flows realizing a set
of source-destination demands. We consider the case where
demands are elastic and the flow realizing one demand can
be arbitrary split over multiple paths. Moreover, we ensure
that the allocated flows are survivable to network failures
using path protection. We investigate the possibility of
sharing backup capacity, thus enabling more efficient
resource consumption. Depending on the optimization
objective, we provide two different approaches to the
problem. The first approach maximizes the total allocated
volume and the second one maximizes the minimum allocated
volume. We build mathematical formulations based on
generalizations of the maximum multicommodity flow and the
maximum concurrent flow problems. Moreover, we provide new
approximation algorithms based on a primal-dual approach.
These algorithms compute a solution that is within a
guaranteed factor of the optimal. Numerical results enable
to get deeper insights on the quality and compared
performance of the different approaches.