Reliable Adaptive Multipath Provisioning with Bandwidth and Differential Delay Constraints

Abstract

Robustness and reliability are critical issues in network management. To provide resiliency, a popular protection scheme against network failures is the simultaneous routing along multiple disjoint paths. Most previous protection and restoration schemes were designed for all-or-nothing protection and thus, an overkill for data traffic. In this work, we study the Reliable Adaptive Multipath Provisioning (RAMP) problem with reliability and differential delay constraints. We aim to route the connections in a manner such that link failure does not shut down the entire stream but allows a continuing flow for a significant portion of the traffic along multiple (not necessary disjoint) paths, allowing the whole network to carry sufficient traffic even when link/node failure occurs. The flexibility enabled by a multipath scheme has the tradeoff of differential delay among the diversely routed paths. This requires increased memory in the destination node in order to buffer the traffic until the data arrives on all the paths. Increased buffer size will raise the network element cost and could cause buffer overflow and data corruption. Therefore, differential delay between the multiple paths should be bounded by containing the delay of a path in a range. We first prove that RAMP is an NP-hard problem. Then we present a pseudo-polynomial time solution to solve a special case of RAMP, representing edge delays as integers. Next, an (1 + e)-approximation algorithm is proposed to solve the optimization version of the RAMP problem. An efficient heuristic is also provided for the RAMP problem. We also present numerical results confirming the advantage of our schemes as the first solution for the RAMP problem.