Multi-Commodity Network Flows Over Multipaths With Bounded Buffers

In this paper, the authors address the issue of designing multipath routing algorithms. Multi-path routing has the potential of improving the throughput but requires buffers at the destination. Their model assumes a network with capacitated edges and a delay function associated with the network links (edges). They consider the problem of establishing a specified throughput from multiple sources to destination pairs in the network, given bounds on the buffer sizes available at the network intermediate nodes and a bound on the maximum delay that the paths are allowed to have. They formulate the problem using a linear programming model.