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(HO(1)m 1O(1)) where H is the number of edges on any allowed flow-path. No prior results exist for our model. Our algorithm is a reasonable alternative to existing polynomial sequential approximation algorithms, such as Garg-Könemann (Proceedings of the 39th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, USA, pp. 300-309, 1998). 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. © 2008 Springer-Verlag.