Greedy distributed optimization of multi-commodity flows

Abstract

The multi-commodity flow problem is a classical combinatorial optimization problem that addresses a number of practically important issues of congestion and bandwidth management in connection-oriented network architectures. We consider solutions for distributed multi-commodity flow problems, which are solved by multiple agents operating in a cooperative but uncoordinated manner. We provide the first stateless greedy distributed algorithm for the concurrent multi-commodity flow problem with poly-logarithmic convergence. More precisely, our algorithm achieves 1+ε approximation, with running time O(log P·logO(1) m·(1/ε)O(1)) where P is the number of flow-paths in the network. No prior results exist for our model. Our algorithm is a reasonable alternative to existing polynomial sequential approximation algorithms, such as Garg-Konemann [17]. The algorithm is simple and can be easily implemented or taught in a classroom. Remarkably, our algorithm requires that the increase in the flow rate on a link is more aggressive than the decrease in the rate. Essentially all of the existing flow-control heuristics are variations of TCP, which uses a conservative cap on the increase (e.g., additive), and a rather liberal cap on the decrease (e.g., multiplicative). In contrast, our algorithm requires the increase to be multiplicative, and that this increase is dramatically more aggressive than the decrease. Copyright © 2007 ACM.