A Distributed Method for Optimal Capacity Reservation

Journal of Optimization Theory and Applications, 182(3): 1130–49, 2019.

• Manuscript

• Code

We consider the problem of reserving link capacity in a network in such a way that any of a given set of flow scenarios can be supported. In the optimal capacity reservation problem, we choose the reserved link capacities to minimize the reservation cost. This problem reduces to a large linear program, with the number of variables and constraints on the order of the number of links times the number of scenarios. We develop a scalable, distributed algorithm for the problem that alternates between solving (in parallel) one flow problem per scenario, and coordination steps, which connect the individual flows and the reservation capacities.